algorithm - 逆时针排列凹多边形顶点

Question

我有一组位于凹多边形边界上的点。我想找到一个以这些点为顶点的非交叉多边形。换句话说，我想以 ccw(或 cw)方式对凹多边形的顶点进行排序。

我查看了评估多边形是按 ccw 还是 cw 方式排序的方法(计算和求和叉积)。这不完全是我的问题:我有随机顺序的顶点，我想对它们进行排序，以便它们在多边形的地壳上顺时针或逆时针。

我想到了采用初始顶点序列，并依次识别交叉点。如果初始点序列是 [x1,y1 ; x2, y2 ; x3, y3 ; ...] 并且第 2 点和第 3 点相交，我们继续序列 [x1,y1 ; x2, y3 ; x3, y2 ; ...]

你能想到什么算法？背后的概念是什么？您有一些引用资料的提示吗？

注册

Answer 1

如果我对问题的理解正确，您想要对输入的点集进行排序，以便它们按顺时针顺序出现在某个可能的凹多边形中。这可以通过以下方式解决。

设 p1 和 p2 为最左边和最右边的点。找到点的下凸包 S。 S 包含 p1、p2 和线 p1p2 下方的所有凸包点。现在按 x 坐标对剩余的点(不在 S 中的点)进行排序。此排序顺序与 S 的顺序(由下凸包算法生成)将为您提供所有顶点的所需顺时针顺序。