超级难的算法,求任意多边形的平行多边形集。
所谓任意多边形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步的情况.