首页 诗词 字典 板报 句子 名言 友答 励志 学校 网站地图
当前位置: 首页 > 教程频道 > 软件管理 > 软件架构设计 >

求教 多边形(凹凸)顶点排序成逆时针或顺时针的有关问题

2012-04-03 
求教 多边形(凹凸)顶点排序成逆时针或顺时针的问题如题,给定一系列的无序的点坐标,由于要画一个多边形出来

求教 多边形(凹凸)顶点排序成逆时针或顺时针的问题
如题,给定一系列的无序的点坐标,由于要画一个多边形出来,所以需要将点排序成顺时针或者逆时针,多边形有可能是凹或者凸。。。

求教啊!

[解决办法]
我觉得楼主这个问题应该再有一些限制条件,否则很多情况下会有多个解的情形出现,按照楼主问题的描述,应该是某个具体的应用时的情形,能否将问题更细化呢。
[解决办法]
设所有点的集合为Vs

1> 先找所有点的外凸包顶点,起始点为X坐标最小值的那个(如果有多个,那么就选Y坐标最小的),设这个凸包的点集合为Va,边集合为Ea。

2> 任意在Ea中选一条边e,从剩下的点集合(Vs-Va)中选取离e最近的点v,分别连接v和e的两个端点,并删除e,形成新的外包点和边集合。

3> 如此重复下去,一直到所有的点都被加入。

热点排行