algorithm - 求四点是否构成四边形

有人可以告诉我一个算法来编写一个函数，如果 4 个点形成一个四边形，则返回 true，否则返回 false？积分没有任何顺序。

我试图检查 4 个点的所有排列，看看是否有 3 个点形成一条直线。如果有 3 个点形成一条直线，则它不是四边形。但后来我意识到没有办法告诉订单。然后我挣扎了几个小时的思考和谷歌搜索没有结果:(

我已经阅读了这些问题:

find if 4 points on a plane form a rectangle?

Determining ordering of vertices to form a quadrilateral

但是还是没有找到解决办法。在1的情况下，它无法检测到另一种四边形，而在2的情况下，它假设这些点已经是四边形的。有没有其他方法可以找出 4 个点是否形成四边形？

之前谢谢。

编辑澄清:

我把四边形定义为简单的四边形，基本上就是这张图所示的所有形状:

除了带有“四边形”和“复杂”标题的形状。

至于“检查共线三元组”方法的问题，我试着用这样的东西检查垂直、水平和对角线:

def is_linear_line(pt1, pt2, pt3):
    return (pt1[x] == pt2[x] == pt3[x] ||
            pt1[y] == pt2[y] == pt3[y] ||
            slope(pt1, pt2) == slope(pt2, pt3))

并意识到矩形和正方形将算作直线，因为点的斜率都是相同的。希望这能解决问题。

最佳答案

这是为了检查四边形是否是凸的。如果它是简单的四边形，则不会。

我在objective-c https://github.com/hfossli/AGGeometryKit/ 中确实喜欢这个

extern BOOL AGQuadIsConvex(AGQuad q)
{
    BOOL isConvex = AGLineIntersection(AGLineMake(q.bl, q.tr), AGLineMake(q.br, q.tl), NULL);
    return isConvex;
}

BOOL AGLineIntersection(AGLine l1, AGLine l2, AGPoint *out_pointOfIntersection)
{
    // http://stackoverflow.com/a/565282/202451

    AGPoint p = l1.start;
    AGPoint q = l2.start;
    AGPoint r = AGPointSubtract(l1.end, l1.start);
    AGPoint s = AGPointSubtract(l2.end, l2.start);

    double s_r_crossProduct = AGPointCrossProduct(r, s);
    double t = AGPointCrossProduct(AGPointSubtract(q, p), s) / s_r_crossProduct;
    double u = AGPointCrossProduct(AGPointSubtract(q, p), r) / s_r_crossProduct;

    if(t < 0 || t > 1.0 || u < 0 || u > 1.0)
    {
        if(out_pointOfIntersection != NULL)
        {
            *out_pointOfIntersection = AGPointZero;
        }
        return NO;
    }
    else
    {
        if(out_pointOfIntersection != NULL)
        {
            AGPoint i = AGPointAdd(p, AGPointMultiply(r, t));
            *out_pointOfIntersection = i;
        }
        return YES;
    }
}

关于algorithm - 求四点是否构成四边形，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/9513107/