算法-算法题:在平面上有两个图形,求这两个图形的最短距离

发布于 12-29 23:40 字数 101 浏览 1381 评论 3

如题,在平面上有两个图形(可以看成是两个闭合曲线),求这两个图形之间的最短距离
要求代码实现,不知道有没有人知道这样的算法,或者是相关的论文,最好是(便于并行化的,可以是串行的)

如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。

评论(3

想挽留2017-09-28 15:19:27

图性先粗分成网格, 把结果明显不可能出现的网格删掉,很快的两个图只剩下很少的网格。然后枚举即可。

分的时候看图的复杂度和计算量。

泛泛之交2017-06-28 09:29:09

如果是多边形的话可以通过穷举端点的方法来找到最短距离,曲线就复杂得多了,即使是两个椭圆(长短轴不平行)的最短距离也是很复杂的问题。一般来说只能用数值计算的方法。比如可以用牛顿法、梯度下降法等等。先通过图形性质找出比较可能是最近距离的位置,然后用数值计算方法让距离极小化。

想挽留2017-04-21 13:17:20

第一次回答问题..
想了个思路:
1. 确定坐标原点, 可以求2图形上任意2点的线段, 取其上不在图形内/上的点, 设改点为坐标原点;
2. 以坐标原点为中心, 建立坐标系, 并将图形坐标投影到新的坐标系上. 分别求每个图形到x轴的最短距离坐标.
2.1 若坐标重合, 则2段距离相加为最短距离;
2.2 若坐标不重合, 则根据二者坐标的大小确定像那个方向旋转坐标系; 以A, B点代表投影坐标, 若A>B, 则坐标轴向远离A的方向旋转;

===

~没有更多了~
我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站,即表示您同意使用 Cookies 和您的相关数据。
原文