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

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
                      (+,-)

因此，从任何一点开始，只需移动到一个点，其中两个符号中只有一个发生变化，但不会同时发生变化。

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

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