平面上多边形边的最小间距算法
给定平面上一组不相交也无包含关系的多边形，多边形的边绝大多数都是水平或垂直边，只有少数45度，135度的边。
e1是多边形1中的一条边，e2是多边形2中的一条边，给定一个最小间距S。
求：所有间距小于S的边组（边组中的2条边属于不同的多边形）。
有没有效率高一点的算法？？？
问题点数：100、回复次数：4Top
1 楼lins（Anders*小明）回复于 2002-11-18 23:54:31 得分 100
我大概的看了一下！有一个大概的思路。如下：
由于大多数边是水平或垂直的，可以用两组平行线来做。其中一组是垂直平行线如下：第一条线在最左端的多边形的左端点。两条平行线的距离是s。这样每次向右平移一条边，如果有两个不属于同一个多边形的而且垂直的边在这两条平行线中，那么这两条边的距离小于s。同理可以找到水平的线。对于45度，135度的边，可以用一个对角线长为s的正方形，来平移查找。
不知道行不行？我的电脑有问题，那位大哥可以实现一下。Top
2 楼akiko（弥弥）回复于 2002-11-19 21:31:23 得分 0
补充说明一下，两条边间距的概念：
有两条边边1和边2，p1是边1上一点，p2是边2上一点，则p1p2是一条线段，当p1p2的长度最小时这个长度就是边1和边2的间距。
感谢lins提供的的思路,我想想.
能否再提示提示,头一回做这样的算法,没什么经验.Top
3 楼akiko（弥弥）回复于 2002-11-27 20:32:38 得分 0
把您的思路改进一下：把多边形的顶点按X坐标从小到大排列，如果有相临X坐标的差小于s，则检查在这相临X坐标上的垂直边的距离。对水平边的处理类似，对于斜边也只有扩展成正方形（以斜边为对角线作正方形，再把这正方形外扩s作为结果），检测落在正方形内的边。
这样怎么样？Top
4 楼akiko（弥弥）回复于 2002-12-04 21:58:20 得分 0
这么久了没人回复,感谢lins(*有为青年*) 提供的思路,给分了!Top
