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

假设我在 2D 空间中有 4 个顶点。有谁知道一种有效的算法可以给我对应于简单四边形的顶点排序？也就是说，它将标记顶点1, 2, 3, 4这样如果我跟随1-2, 2-3, 3-4我将绘制一个简单的（即不相交的）四边形。

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

如果你的形状是凸的，你可以绕着你的点的重心（即重心，或“平均”）缠绕：

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

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

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

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

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

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

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