逆时针排列凹多边形顶点

Question

我有一组位于凹多边形边界上的点.我想找到一个非交叉多边形,将这些点作为顶点.换句话说,我想以凹面多边形的ccw(或cw)方式排序.

我看一下评估多边形是以ccw还是cw方式排序的方法(计算和求和交叉乘积).这不是我的问题:我有随机序列的顶点,我想订购它们,以便在多边形的外壳上有cw或ccw.

我想到了最初的顶点序列,并连续识别交叉点.如果初始点序列是[x1,y1; x2,y2; x3,y3; ...]和第2和第3点正在交叉,我们继续序列[x1,y1; x2,y3; x3,y2; ...]

你能想到什么算法？什么是背后的概念？你有提示吗？

Regds

Answer 1

如果我正确理解了问题,您需要对输入的点集进行排序,使它们以某些可能的凹多边形的顺时针顺序出现.这可以解决如下.

设p1和p2是最左边和最右边的点.找到点的下凸壳S. S包含p1,p2和位于线p1p2下方的所有凸包点.现在按其x坐标对剩余的点(不在S中的点)进行排序.这个排序顺序连同S的顺序(由下凸壳算法生成)将为您提供所有顶点的所需顺时针顺序.