algorithm - 给定三角网格顺时针排序点

Question

给定一个三角形网格(没有自相交，没有孔，可能是凹面)表示为三角形的无序列表(3 个顶点的列表)或矩形(4 个顶点的列表)，即

[
    [[x1, y1], [x2, y2], [x3, y3]],
    [[x4, y4], [x5, y5], [x6, y6], [x7, y7],
    ....
]

如何按顺时针顺序对顶点进行排序？

Answer 1

您可以 sort by angle .

有不同的实现方式，例如您可以在 C++ 中使用 atan2() 来计算每个顶点的角度并将它们排序。

如果它们具有相同的角度，您可以按到原点的距离对它们进行排序以打破平局。