我有一组位于凹多边形边界上的点。我想找到一个以这些点为顶点的非交叉多边形。换句话说，我想以 ccw（或 cw）方式排列凹多边形的顶点。
我查看了评估多边形是否以 ccw 或 cw 方式排序的方法（计算和求和叉积）。这不完全是我的问题：我有随机序列的顶点，我想对它们进行排序，以便让它们在多边形的外壳上顺时针或逆时针。
我想取顶点的初始序列，并依次识别交叉点。如果初始点序列是 [x1,y1 ; x2, y2 ; x3, y3 ; ...] 和第 2 和第 3 点交叉，我们继续序列 [x1,y1 ; x2, y3 ; x3, y2 ; ...]
你能想到什么算法？背后的观念是什么？你有一些参考的提示吗？
注册表
如果我正确理解了这个问题，您希望对输入点集进行排序，以便它们以某些可能凹多边形的顺时针顺序出现。这可以通过以下方式解决。
设 p1 和 p2 是最左边和最右边的点。找到点的下凸包 S。S 包含 p1、p2 和线 p1p2 下方的所有凸包点。现在按 x 坐标对剩余的点（不在 S 中的点）进行排序。此排序顺序与 S 的顺序（由下凸包算法生成）将为您提供所有顶点的所需顺时针顺序。
在构建多边形时有一些信息必须使用，除非多边形的定义比我认为可能是凹多边形的一组点更好。
例如，如果顶点取自形状或图像，则形状中的填充像素可能会有所帮助。对于一个项目，我需要在 blob 的周长上排序点，所以我得到 blob 的边界像素（可以通过多种方式完成），然后我使用 DFS 样式遍历这些点以将它们按顺序排列。然后我编写了算法来合并边缘并在交叉点做出决策。