求教 多边形(凹凸)顶点排序成逆时针或顺时针的问题
如题,给定一系列的无序的点坐标,由于要画一个多边形出来,所以需要将点排序成顺时针或者逆时针,多边形有可能是凹或者凸。。。
求教啊!
[解决办法]
我觉得楼主这个问题应该再有一些限制条件,否则很多情况下会有多个解的情形出现,按照楼主问题的描述,应该是某个具体的应用时的情形,能否将问题更细化呢。
[解决办法]
设所有点的集合为Vs
1> 先找所有点的外凸包顶点,起始点为X坐标最小值的那个(如果有多个,那么就选Y坐标最小的),设这个凸包的点集合为Va,边集合为Ea。
2> 任意在Ea中选一条边e,从剩下的点集合(Vs-Va)中选取离e最近的点v,分别连接v和e的两个端点,并删除e,形成新的外包点和边集合。
3> 如此重复下去,一直到所有的点都被加入。