找出点的顺序以形成四边形

Question

在回答“给定四个坐标，检查它们是否构成正方形”时，我遇到了这个答案，它先检查平行四边形，然后检查直角。这个方法可以工作，但仅当输入的点按特定顺序排列时才有效。即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]

每个排列都有六个线段对线段的检查，总共需要18次比较。

我想不出其他方法，但似乎我漏掉了什么。有更好的方法吗？对于正方形问题给出的答案很好，但如果我必须进行额外（最多）18次检查来验证点的正确顺序，那么使用角间距离会更快。

- Geobits

---

这个问题是否专门涉及正方形问题的四边形，您是想要所有四边形的通用解决方案还是都可以呢？ - Bernhard Barker

最好使用通用解决方案。这个问题最初是“如何确定如何将它们排序以供给平方问题”，但我猜它可能有其他有用的应用。 - Geobits

我有一个愚蠢的问题：我们是在谈论二维点，对吗？ - beaker

@beaker 是的，仅限于此问题的目的，只涉及2D。 - Geobits

Answer 1

每个排列都有六个段对段的检查，这总共需要18次比较。

你不需要检查所有的段：只需检查段[0-2]和[1-3]（即两条对角线）是否相交。需要检查的是段之间的交点，而不是段所属的线，即段之外的交点不算。

一旦你确定了起点"A"，你就会得到六种可能的排列： 其中两个(A-B-D-C和A-C-D-B)是好的，其余四个是坏的。你只需要进行两次检查就可以得到一个好的排列:

1. 检查初始排列，如果它是好的，就保留它；否则 2. 交换点1和点2，检查排列，如果它是好的，就保留它；否则 3. 回到原始排列，交换点2和点3，并保留该排列；它一定是“好”的。

- Sergey Kalinichenko

---

这很有道理。两个排列检查，每个交叉检查一次。我认为它不可能比这更简单了。 - Geobits

请注意，ABDC = ACDB，ABCD = ADCB，ACBD = ADBC。添加第四行（第四个和第一个点之间的线）即可看到它。 - Bernhard Barker

@Dukeling 对的，我故意跳过了方向对称性（顺时针 vs. 逆时针），以使自己相信该图表涵盖了所有六种可能性。 - Sergey Kalinichenko

Answer 2

你不能只是检查所有下面的内容，直到找到一个正确的吗？（也就是说，检查P1相对的每个点）

P3 = P1 + (P2-P1) + (P4-P1)
P2 = P1 + (P3-P1) + (P4-P1)
P4 = P1 + (P2-P1) + (P3-P1)

对于正方形变体，如果它们恰好是轴对齐的，则可以执行以下操作：（也就是说，相反的点是那个没有共同坐标的点）

if (P1.x != P3.x && P1.y != P3.y)
  check P3 = P1 + (P2-P1) + (P4-P1)

if (P1.x != P2.x && P1.y != P2.y)
  check P2 = P1 + (P3-P1) + (P4-P1)

if (P1.x != P4.x && P1.y != P4.y)
  check P4 = P1 + (P2-P1) + (P3-P1)

otherwise return false

- Bernhard Barker

---

你的第一个观点现在在我想来最有意义。然而第二个却否定了旋转的正方形。 - Geobits

轴对齐法是我首先想到的方法，但它真的限制了其实用性。尽管如此，还是要点个赞。不确定我的大脑怎么会忽略我可以运行公式三次这一事实。当然，这只适用于正方形/平行四边形问题，而不是四边形总体。 - Geobits

Answer 3

实现一个名为isParallelAndEqual(p0,p1,q0,q1)的方法。它检查线段p0-p1和q0-q1是否平行且长度相等。

给定点a，b，c和d，最终结果如下：

ifParallelAndEqual(a,b,c,d)||ifParallelAndEqual(a,c,b,d)

- ElKamina

---

我更喜欢一个四边形的通用解决方案，不一定是平行四边形。虽然同意它对于平行四边形很有用。 - Geobits

在一般的四边形中，答案可能是不确定的。考虑这样一种情况：你有任意三个点，第四个点在由前三个点构成的三角形内。在这种情况下，就没有确切的答案（或者说所有答案组合都是有效的）。 - ElKamina

是的，我想我只是指凸性。很好的观点，这是我没有考虑过的。 - Geobits

Answer 4

这样做不是更简单吗：

1. 检查点0, 1和2是否构成三角形（如果它们共线，四边形也是退化的）
2. 检查以下线段是否相交：

[0, 3] and [1, 2]
[1, 3] and [0, 2]
[2, 3] and [0, 1]

如果它们都不相交，那么这个四边形就是非凸的。

否则，你应该只有一个相交的情况。在那里你找到了对面的顶点。

- Vincent van der Weele

---

如果3,0,1是共线的（按照这个顺序），那么它不会看到[1,3]与[0,2]相交吗？这是我在纸上想出的第一个反例，但我担心可能还有其他情况。我想我可以检查所有点的组合是否共线，但是... - Geobits

@Geobits 我觉得这取决于相交检查。如果使用叉积，找到边界案例不容易吗？（在[0,1]中表示相交，所以恰好为0或1表示边界案例？） - Vincent van der Weele

确实这取决于情况。使用叉积时，如果您使用浮点数运算，就必须非常小心。有效/退化四边形之间的差异可能非常小，而“完全为零”并不太可行。 - Geobits