纯数学计算求多边形之间最小距离

llsheng_73 · 发表于 2013-11-2 20:37

本帖最后由 llsheng_73 于 2013-11-9 03:02 编辑

   假设有两个点表pt1(p1,p2,...,pn)和pt2(p1,p2,...,pm)分别表示两个多形，其p1~pn,p1~pm分别为它们各自的顶点坐标，现在的问题是怎么用纯数学计算的方法求出其最近距离(不是顶点间而是所代表的多边形之间，虽然都是直线边，但也很可能其中一个点在某两个点所定的线上，另一个在顶点上)。
   希望大家指点下，给点思路，谢谢了！

   再次感谢各位热心指点的大大们，在你们的帮助下问题已经解决了，基本思路是直接求pt1中pi(i=1~n)到pt2中相邻两个点所组成线段的垂距来进行比较得到pt1上的点到pt2的最小距离，再用同样的办法求出pt2上的点到pt1的最小距离，两个最小距离进行比较得到最终结果。算法很笨，只是能算出来。

   不过附件被挂到11楼了,也不知道怎么把它弄到楼顶来，只能麻烦下感兴趣的朋友了

llsheng_73 · 发表于 2013-11-3 05:37

本帖最后由 llsheng_73 于 2013-11-9 03:04 编辑

熬了一晚上，总算能计算出来了,至于算法的优化，限于水平，只能期待各位版主大人，各位兄弟姐妹们多提建议了
其实就用了个最笨的办法，分别以两个多边形的顶点P与另一个多边形的相邻两个顶点p的对边L)组成三角形，计算p到L的垂足,如果垂足在L延长线上则的返回P到L最近的端点p1的距离d及这两个点组成的表(d p p1),否则返回垂距(d p 垂足)最后对表进行排序选出最短距离，由于返回了顶点及垂足，因此可以在后边的应用中方便的利用最短距离所在的两个点的坐标。

ZZXXQQ · 发表于 2013-11-2 20:43

(defun NearPt (pl1 pl2)
(setq dist 1e100)
(foreach x pt1
(foreach y pt2
(if (< (distance x y) dist) (setq dist (distance x y)))
)
)
dist
)

emk · 发表于 2013-11-2 20:47

Z版高速高效，大侠也

llsheng_73 · 发表于 2013-11-2 20:49

ZZXXQQ 发表于 2013-11-2 20:43

谢谢ZZXXQQ 的热心解答，不过要求的不是点之间的距离，是要它们之间的最近距离，所以不能只计算顶点到顶点的距离，不过还是谢谢你的热心帮助

mccad · 发表于 2013-11-2 21:40

只要知道了哪两个点距离最近，如果再存在着点到另外多边形的边最近的话，则很容易求了。因为那条边的一个端点肯定是那个最近点。

logoin · 发表于 2013-11-2 21:47

这个做出来容易，想要执行速度快是很难啊...

328302216 · 发表于 2013-11-2 21:52

llsheng_73 发表于 2013-11-2 20:49
谢谢ZZXXQQ 的热心解答，不过要求的不是点之间的距离，是要它们之间的最近距离，所以不能只计算顶点到顶点 ...

应该点到线之间的最小距离就是你要求的最近距离了！

llsheng_73 · 发表于 2013-11-2 23:11

本帖最后由 llsheng_73 于 2013-11-3 23:38 编辑

mccad 发表于 2013-11-2 21:40
只要知道了哪两个点距离最近，如果再存在着点到另外多边形的边最近的话，则很容易求了。因为那条边的一个端 ...

也就是说然后只需要再分别从两个端点求所对应的另一个端点上的两条直线的距离，总共4个距离中最短的那一个就是我所需要的了，而这个距离可能通过三角形面积去除顶点的对边边长得出来，当然这样算应该没通过计算垂线与直线的交点来得快,不过方位角也气人，不好生弄它会往反方向跑，算了，还是解三角形去吧，那个应该没角度麻烦
谢谢明总的关注和指点

llsheng_73 · 发表于 2013-11-2 23:16

本帖最后由 llsheng_73 于 2013-11-2 23:35 编辑

logoin 发表于 2013-11-2 21:47
这个做出来容易，想要执行速度快是很难啊...

我觉得只是取表中的元素出来纯计算，不需要生成图元以辅助计算然后删除，也不对表本身进行操作，就算慢也不会慢到哪去，这应该跟表的大小成线性关系吧，不至于无法忍受吧

llsheng_73 · 发表于 2013-11-3 04:25

本帖最后由 llsheng_73 于 2013-11-3 23:51 编辑

mccad 发表于 2013-11-2 21:40
只要知道了哪两个点距离最近，如果再存在着点到另外多边形的边最近的话，则很容易求了。因为那条边的一个端 ...

两个多边形距离最近的点虽然其中一个必然是顶点之一，另一个是这个顶点到另一个多这形的某条边的垂足，但实际上是它们可以线很近而顶点却比别的相隔得远些，所以通过距离最近的两个点很可能找出来的垂边并不是最短边
象下边这样两个多边形，距离最近的顶点是红线连上的两个，而它们的最短距离却在绿线那里

账号		自动登录	找回密码
密码			注册

[已解答] 纯数学计算求多边形之间最小距离

本帖子中包含更多资源

浏览过的版块