什么是最快的算法来计算两个点集之间的最小距离是多少？ [英] What is the fastest algorithm to calculate the minimum distance between two sets of points?

问题描述

我想找到两个多边形之间的最小距离。我的意思是，我必须找到最小的第一形状的每个顶点之间的最短距离与其他一体的全方位的顶点。像豪斯多夫距离，但我需要的最低，而不是最大的。我AP preciate任何建议。谢谢你。

I wanna find the minimum distance between two polygon. I mean, I have to find the minimum of shortest distance between each vertex of first shape with the all the vertexes of the other one. Something like Hausdorff Distance but I need minimum instead of maximum. I appreciate any suggestion. Thank you.

推荐答案

也许你应该检查（ PDF警告！还要注意的是，由于某些原因，这些页面的顺序颠倒的） 优化算法计算两有限平面的最小距离由杜桑和巴特查亚集

Perhaps you should check out (PDF warning! Also note that, for some reason, the order of the pages is reversed) "Optimal Algorithms for Computing the Minimum Distance Between Two Finite Planar Sets" by Toussaint and Bhattacharya:

有示于本文的   两个有限之间的最小距离   平面设置，如果[原文的] n个点即可   计算在O（ N 的日志的 N 的）最坏情况   运行时间并认为这是最佳的   内恒定的因素。   此外，当套形成一   凸多边形这种复杂性可   降低到O（ N 的）。

It is shown in this paper that the minimum distance between two finite planar sets if [sic] n points can be computed in O(n log n) worst-case running time and that this is optimal to within a constant factor. Furthermore, when the sets form a convex polygon this complexity can be reduced to O(n).

如果两个多边形穿越凸的，也许你应该还检查了（ PDF警告再次，页面的顺序颠倒的！）的An优化算法由杜桑计算的最小点之间的两个路口凸多边形距离：

If the two polygons are crossing convex ones, perhaps you should also check out (PDF warning! Again, the order of the pages is reversed) "An Optimal Algorithm for Computing the Minimum Vertex Distance Between Two Crossing Convex Polygons" by Toussaint:

让 P = { P 的<分> 1 ，    P 的 ₂ ，...， P 的<子>的 M 的}和Q = {问：的<分> 1 ，问：的 ₂ ，...，   问：的<子>的 N 的}是两个相交多边形的顶点使用规定   通过它们在直角坐标系   订购。最优O（ M + N 的）   算法是psented计算$ P $   之间的最小欧氏距离   顶点的 P 的<子>我在 P 的和   顶点的问：的<子>Ĵ中的问：的。

Let P = {p₁, p₂,..., p_m} and Q = {q₁, q₂,..., q_n} be two intersecting polygons whose vertices are specified by their cartesian coordinates in order. An optimal O(m + n) algorithm is presented for computing the minimum euclidean distance between a vertex p_i in P and a vertex q_j in Q.

这篇关于什么是最快的算法来计算两个点集之间的最小距离是多少？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！