algorithm - 确定顶点的顺序以形成四边形

Question

假设我在 2D 空间中有 4 个顶点。有什么人知道一种有效的算法可以给我一个对应于简单四边形的顶点的排序吗？也就是说，它将标记顶点 1, 2, 3, 4 这样如果我遵循 1-2, 2-3, 3-4 我将追踪到一个简单的(即不相交的)四边形。

只要提供我可以用谷歌搜索的标准算法的名称就可以了。

Answer 1

如果你的形状是凸的，你可以绕着你的点的质心(即重心，或“平均”)按顺序排列:

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

每个顶点的两个坐标都将高于或低于相应的重心坐标:

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

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

所以从任何一点开始，只要移动到两个符号中只有一个改变的点，而不是两个都改变的点。

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

请注意，对于一组非凸点(即一个点包含在该组凸包的开放内部的一组)，可能有多个四边形以这些点为顶点(想想连接内部顶点和两个外部顶点的所有方式)。