寻找距已知点距离最近的直线

wiseboy · 发表于 2004-2-3 12:48:00

已知一点，数条直线（直线坐标未知），怎样以最快的速度找出离已知点距离最近的那条直线？望高手指点

victory · 发表于 2004-2-6 16:34:00

没什么好办法，还是老老实实地算吧！
如果已知点正好是一个正方形的中心，应该是找到四条直线，而不是其中的一条。如果是正n边形呢？
其实可以根据你的具体要求（比如只找到一条直线即可），参考一下排序和查找的算法思路。譬如按折半查找法的思路：设已知点P，先构造选择集，获取全部的直线，取选择集里的第一条直线，求出距离D1，求D2=D1/2，在以P为中心，边长为2*D2的正方形（用正方形比较方便）范围内构造选择集，如果有直线，则又取选择集里的第一条直线，求出距离，按求D1的方法，继续缩小范围；如果选择集里没有直线，则扩大范围，如：D4=D2+（D1-D2）/2；依次递归（注意：要及时清除选择集，其数目不能大于128个）。如果选择集里的数目不是太大（比如：n<5)时就可以直接遍历选择集，求出距离。
具体可以看看《数据结构》。

wiseboy · 发表于 2004-2-9 16:47:00

谢谢你，我其实是想知道boundary的命令是怎样实现的

寻找距已知点距离最近的直线

发表回复

精选推荐