将4个坐标连接成一个四边形的算法，以确保始终得到一个四边形。

Question

我们在二维平面上给出了4个点的坐标。如何找到一种连接它们形成四边形的顺序（如果可能的话）？

- Neel

---

如果这些点共线怎么办？ - Paul Hankin

需要在那种情况下画一条直线。 - Neel

只有三种可能性：ABCD，ABDC，ACBD。都试一遍吗？ - Paul Hankin

Answer 1

考虑通过绘制由前三个点定义的三条线获得平面的分区。它定义了7个区域。您可以通过三个符号面积测试（ABD，BCD，CAD三角形的代数面积）轻松找到第四个点属于哪个区域。

在每种情况下绘制四边形很简单（每种情况可能有一、两或三个解决方案）。

在下面的示例中，如果D位于区域- ++中，则ADBC将是一个解决方案。

实际上，只需要进行两次面积评估：如果第一个测试返回-（区域-+-，-++或-- +），则ADBC是一个解决方案，否则如果第二个测试返回-（区域+-+或+--），则ABDC是一个解决方案，否则（区域++ - 或+++）ABCD是一个解决方案。

- user1196549

---

你是如何通过类似于“-++”这样的三个术语推导出有符号面积测试的？这里的-++代表什么意思？请解释一下。 - Am_I_Helpful

@shekharsuman：三角形ABD，BCD，CAD的代数面积。http://en.wikipedia.org/wiki/Triangle#Using_coordinates - user1196549

@shekharsuman：我不感谢你的投反对票。这是一种最优解，非常简单易实现。两个区域评估和两次测试！ - user1196549

@shekharsuman：你错过了整个事情。共线性测试与有向面积是相同的表达式。这也是计算几何中的标准。你需要执行它四次而不是两次，并且丢失了重要信息，即符号。这迫使你进行后处理并排序（你没有清楚地详细说明）。 - user1196549

Answer 2

为了更加清晰，我将一个点 p_n 视为具有坐标 (x_n, y_n) 的点。

要连接4个点，您可以按照以下步骤进行：

1. 获取具有最小 x 值的点 p_1。
2. 计算从 p_1 到其余每个点的3条线的 斜率。
3. 将 p_1 与具有最大斜率的点 p_2 连接。
4. 将 p_1 与具有最小斜率的点 p_3 连接。
5. 将剩余的点 p_4 与 p_2 和 p_3 连接。

如果有不清楚的地方，请告诉我。

- Gentian Kasa

Answer 3

考虑仿射变换。

Px = Ax + u (Bx - Ax) + v (Cx - Ax)
Py = Ay + u (By - Ay) + v (Cy - Ay)

它将(0, 0)映射为A，将(1, 0)映射为B，将(0, 1)映射为C。（这将三角形ABC放置在规范位置。）

解2x2线性系统。

Dx = Ax + u (Bx - Ax) + v (Cx - Ax)
Dy = Ay + u (By - Ay) + v (Cy - Ay)

这将为您提供与 D 相应的 (u, v) 值。

然后，

if u < 0 => ABCD
else if v < 0 => BCAD
else => CABD

得到的四边形方向与三角形 ABC 相同。

- user1196549

---

这是一份更好、更智能的工作。+1. :) 请不要抱怨我赞了你的回答。:P - Am_I_Helpful

这是我之前的回答的精确复制品，使用了规范坐标重新表述。计算过程完全相同（使用Cramer时的2x2行列式仍然是带符号面积），讨论涉及相同的2个比较/3个结果。它确实更易读。 - user1196549

但是，最终它更易读。无论如何，我也将从另一个答案中移除我的负投票，因为我意识到了相同的问题。 - Am_I_Helpful

@shekharsuman：谢谢。考虑所有这些区域的“深层”原因是为了分析解空间的几何形状。你会学到两件事情：1）区域的边界是直线，因此共线性（或面积）测试就足够了；2）有7个不同的区域，所以只需要3个测试就可以将它们分开。（结果证明只需要两个测试就足够了。） - user1196549

Answer 4

编辑：正如评论中指出的那样，它只适用于特定情况，因此是一个糟糕的答案。

四边形可以通过找到4个点中距离最远的一对点来绘制。一旦找到这对点，就可以通过将剩余的两个点与每个点连接来绘制四边形。

- HairyBlob

---

输入的数据 (0,0), (2,1), (3,1), (10,0) 与此算法相矛盾。 - shapiro yaacov

@shekharsuman：Shapiro是对的。该算法连接(1,0)，(1,3)，(2,0)和(2,3)，但(2,0)横跨了(1,3)。 - user1196549

Answer 5

编辑：这个回答已经被证明是错误的。

1. 计算四个点的中心。
2. 按逆时针（或顺时针）方向枚举点。
3. 将它们连接在一起。

- solalito

---

第二步需要角度计算，这似乎并不必要。 - CiaPan

如果四边形不是凸的，这种方法并不总是有效。例如，在等边三角形的角落上放置三个点，并将第四个点放在中间。 - Paul Hankin

@PaulHankin 是的，你说得对... 让我再想一想！ - solalito

Answer 6

您可以使用任何凸包的著名算法的简化版本。Jarvis算法是比较容易实现的。如果凸包是一个三角形，那么四边形就是凸的。只需在边缘列表中的任意位置插入缺失的点即可。如果凸包是一条线（2个端点），只需按x或y坐标对所有点进行排序，以获得退化的四边形。（如果更接近水平（abs delta x > abs delta y），则使用x进行排序，否则使用y。）

- Gene

Answer 7

我认为，你只需要每次连接两个点，我们就能得到一条线段，并检查剩下的另外两个点是否在该线段的同侧，如果不是，则这不是所需的四边形的线段，如果是，则使用不同的点集继续进行（即一个点可以是该线段的一个坐标，另一个点将来自剩下的两个点），并重复相同的步骤，直到得到4条线段。

- ratnesh

Answer 8

寻找凸包算法。其中之一由两个步骤组成：在给定的顶点集上构建普通多边形（可能是凹的），然后删除“凹顶点”，使剩余的多边形变为凸多边形。

第一步是解决您问题的方案。

当然，这有点过度了。对于4个顶点，只需将它们按顺序设置（任意顺序），然后验证连接点1-2和3-4的线段是否相交；如果是，则交换点2和3；或者可能边缘2-3和1-4相交-然后交换点3和4。完成。

要验证线段AB和CD是否相交，请测试点A和B是否在线CD的两侧，以及点C和D是否在线AB的两侧。

要确定点K所在的线PQ的哪一侧，请计算PQ×PK向量积的Z部分：(xq-xp)(yk-yp)-(yq-yp)(xk-xp)。该表达式在线的一侧为正，在另一侧为负（在线上为零）。

- CiaPan

Answer 9

这里有一种简单的、非数学的方法来解决问题。我已经在几个例子上尝试过了，没有发现错误。如果您知道如何改进它，请告诉我：

1. 选择其他点右侧的两个点，比如点1和点2。
2. 将点1-2和点3-4连接起来。
3. 每个点只能与另外两个点相连，所以只有两种可能：连接点1-3和点2-4，或连接点1-4和点2-3。
4. 检查每条线是否与另一条线相交。

就是这样。

注意：在选择前两个点时，有一些特殊情况：

1. 点1在所有其他点的右侧，但点2和点3在同一x坐标上。选择距离点1最近的点。
2. 如果三个点1、2和3具有相同的x坐标，则连接彼此最接近的两个点。如果这些点等距分布，则选择其中一个可能性。

- solalito

Answer 10

通过使用一个函数来判断两条线段是否相交，可以很容易地解决这个问题。

给定点A、B、C、D，只有三种不同的连接顶点的顺序：ABCD、ABDC和ACBD（顶点A要么连接到顶点B，要么不连接。如果连接，则有两种方式来排序C和D。如果不连接，则A连接到C和D中的每一个，而且这些点都必须连接到B）。

如果四个点的排序产生了一个四边形，并且除了在角落处之外，没有任何边相交，那么就可以得到一个有效的排序过程：

If AB intersects with CD then return ACBD.
If AD intersects with BC then return ABDC.
Otherwise return ABCD.

这个方法的证明很简单：

1. ABCD和ABDC都包括边缘AB和CD，因此如果这对边相交，则正确的顺序必须是ACBD。
2. ABCD和ACBD都包括边缘AD和BC，因此如果这对边相交，则正确的顺序必须是ABDC。
3. 如果AB/CD和AD/BC都不相交，则顺序ABCD产生一个四边形。

如果您无法自行解决问题，则可以在网上找到确定两条线段是否相交的代码。

- Paul Hankin