确定顶点的排序以形成四边形

Question

假设我在二维空间中有4个顶点。 有没有一种有效的算法可以给我一个顶点的排序，该排序对应于简单四边形？也就是说，它将标记顶点1、2、3、4，以便如果我遵循1-2、2-3、3-4，我将跟踪一个简单（即非交叉）四边形。只需提供我可以Google的标准算法的名称即可。

- Il-Bhima

---

三维空间中四个点位于一般位置（即不共面），将永远不会定义相交的边。在平面上，您可以按照重心的旋转顺序进行排列。 - Kerrek SB

那其实是个打字错误！感谢你发现了它。我想表达的是2D。 - Il-Bhima

可能是按顺时针排序四个点的重复问题。 - Colonel Panic

Answer 1

如果你的形状是凸的，你可以按照绕过你的点的重心（即重心或“平均值”）的曲线顺序进行操作：

B = (X_1 + X_2 + X_3 + X_4) / 4

每个顶点的两个坐标要么在重心对应坐标的上方，要么在下方：

 (-,+)                   (+,+)
   X                       X

              B
      X
    (-,-)               X
                      (+,-)

因此，从任何一个点开始，只需移动到一个点，其中仅更改两个符号中的一个，而不是两个都更改。

如果您的形状不是凸形的，则可以首先通过内部边缘对其进行三角剖分，为每个三角形应用具有一致方向的顶点排序，然后通过取消成对相反内部来合并边缘。

请注意，对于非凸点集（即包含在该点集的凸包开放内部中的一个点），可能会有多个四边形具有这些点作为顶点（考虑连接内部顶点到两个外部顶点的所有方式）。

- Kerrek SB

---

这是一条曲线吗？这条曲线有反函数吗？如果我按照这个顺序对所有点进行排序，会发生什么？ - Micromega

Answer 2

您可能会对凸包计算方法感兴趣，例如Graham扫描算法。

- eugene_che

Answer 3

您可以在Google上搜索顺时针排序点，例如：

按顺时针顺序排序四个点
如何按顺时针顺序排序点？

- Tomas

Answer 4

有一个解决方案，不需要计算"中心"，只涉及少量乘法和加法，并且能优雅地处理退化案例（例如所有点共线）。

考虑一个四边形，其角落为ABCD（即有线段AB、BC、CD和DA）。

考虑四个三角形ABC、ABD、ACD、BCD。

如果顶点是（Ax，Ay）、（Bx，By）、（Cx，Cy），则计算每个三角形的面积有一个简单的公式，请查看https://www.cs.princeton.edu/courses/archive/fall07/cos226/lectures/16Geometric.pdf第9页。

面积=（Bx-Ax）（Cy-Ay）-（By-Ay）（Cx-Ax）

如果面积为正，则表示点是逆时针的；如果面积为负，则表示点是顺时针的；如果面积为零，则表示点共线。

非相交四边形可能具有三个共线点。因此，ABC、ABD、ACD、BCD中的其中一个三角形的面积可能为零。但是如果其中两个面积为零，则意味着ABCD必须共线，因此所有四个三角形的面积都为零。在这种情况下，无法进行非相交排列。

因此，计算对应于ABC、ABD和ACD的面积（只需要考虑三角形）。

如果其中两个面积为零，则所有三个面积都将为零，四个点ABCD共线。

如果其中一个面积为零，则选择另外两个面积。

如果它们都不为零，则只需选择其中任意两个面积。

如果四边形没有相交，则这两个三角形必须沿着同一方向旋转，即都是顺时针或逆时针。这意味着两个面积的乘积必须是正数（正数乘以正数或负数乘以负数）。因此，只需形成这两个面积的乘积，两者都不为零，以获得非零结果。如果面积的乘积大于零，则四边形不自相交；如果小于零，则自相交。

- Peter Webb

Answer 5

一个莫顿曲线或者Z曲线可以实现这个功能。但是我建议使用希尔伯特曲线或者摩尔曲线，因为它们具有更好的空间填充属性。

- Micromega