algorithm - 找出构成四边形的点的顺序

Question

同时给予an answer至 "Given four coordinates check whether it forms a square" ，我遇到了this answer ，先检查平行四边形，然后检查直角。这有效，但前提是进入的点按一定顺序排列。即，P1 和 P3 必须彼此“相对”，而不是相邻。

所以，问题。如果进入的四个点可以按任何顺序排列，您如何对它们进行排序以使它们处于“正确”的顺序以形成四边形？

我能想到的最简单的事情是这样的:

for each valid permutation of points[]{ // see below for "valid"
    generate line segment for:
        points[0] -> points[1]
        points[1] -> points[2]
        points[2] -> points[3]
        points[3] -> points[0]
    if any line segment crosses another // use cross product
        continue
    return permutation
}

我知道大多数排列都是简单的旋转(0123 == 1230)，所以我可以保持第一点“固定”。另外，我想我可以通过只考虑每个排列点的 0 和 2 中的点来减少它，因为其他两个的顺序无关紧要.例如，如果 0123 是多边形，0321 也是，因为它生成相同的线段。

这让我只剩下三个基本排列要检查:

• [0,1,2,3]
• [0,1,3,2]
• [0,2,1,3]

每个排列都有 6 次段到段检查，因此总共有 18 次比较。

我想不出任何其他方法来做到这一点，但似乎我遗漏了什么。有一个更好的方法吗？平方问题的答案很好，但如果我必须进行额外的(最多)18 次检查以验证点的顺序是否正确，那么只使用角间距离会更快。

Answer 1

Each permutation has six segment-to-segment checks, so that's a total of 18 comparisons.

您不需要检查所有段:检查段 [0-2] 和 [1-3] 就足够了(即两个对角线)相交。您需要检查线段是否相交，而不是线段所属的线，即线段外的交点不算数。

一旦确定了起点“A”，您就会得到六种可能的排列:

其中两个(A-B-D-C 和 A-C-D-B)是好的；剩下的四个都不好。您只需进行两项检查就可以得到一个好的结果:

• 检查初始排列；好就留着；否则
• 交换点 1 和 2，并检查排列；好就留着；否则
• 恢复原来的排列，交换点 2 和 3，并保持那个排列；它一定是“好”的。