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

超级难的算法,求任意多边形的平行多边形集。解决思路

2012-03-14 
超级难的算法,求任意多边形的平行多边形集。所谓任意多边形P(p0,p1,p2...pn)的平行多边形集是这样定义的:1.

超级难的算法,求任意多边形的平行多边形集。
所谓任意多边形P(p0,p1,p2...pn)的平行多边形集是这样定义的:
1.   它是一个多边形集合。
2.   它的所有的边由多边形P(p0,p1,p2...pn)的边距离为D的外平行线组成。
3.   它的所有的顶点由多边形P(p0,p1,p2...pn)的边的距离为D的外平行线的交点组成。

参看下面的图就很明白了。(网易相册里的)。黑色的为任意多边形P(p0,p1,p2...pn),红色的为其平行多边形集。图1是个凸多边形,它的平行多边形集合只有一个多边形。图2是个凹多边形,他的平行多边形集合有两个多边形组成。图3的平行多边形集合只有一个多边形。
http://img823.photo.163.com/pigofeast/115335955/2804967863.jpg


如何求得呢?

[解决办法]
1.先作一个多边形plg平行于原多边形PLG,如以下网页中
http://www.zzwu.net/cscn/_plg.htm
原来的多边形PLG为图三中的ABCDEFGH,
现作的多边形plg是图三中的abcdefgh

2.检查所作多边形plg是否为一凸包?
如果是(如以上网页中图一所示),则plg就是所求的唯一的多边形,问题得解;
如果不是凸包,作下面的第3步;

3.查plg各个边之间是否有交点?
如果没有(如图二那样),则plg也是所求的唯一的多边形,问题得解;
如果有相交,作下面的第4步;

4.求出所有交点;
把plg在交点处断裂开,使plg分成几段;
把这些段拼接成几个小多边形(如图三中共有三个);
检查每个小多边形是否与原来的多边形PLG相交?
把与原来的多边形PLG相交的去掉,剩下的即为所求的多边形。

[注1]上面第一步的plg是PLG右侧平行边所形成,如果预先不知道多边形是
顺时针或逆时针,则还要类似地考察左侧平行边所形成另一个多边形。

[注2]以上第2步可以不要,直接用第3步来代替第2步的工作,但检查多边形
是否凸包比检查它各边之间是否相交要容易多,先做第2步有利于快速排除
一部分无须经历第3步的情况.

热点排行