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

问题描述

我想找到具有百万个顶点的两个多边形之间的最小距离(不是它们顶点之间的最小距离).我必须找到第一个形状的每个顶点与另一个形状的所有顶点之间的最短距离的最小值.类似于 Hausdorff 距离，但我需要最小值而不是最大值.

I want to find the minimum distance between two polygons with million number of vertices(not the minimum distance between their vertices). I have to find the minimum of shortest distance between each vertex of first shape with all of the vertices of the other one. Something like the Hausdorff Distance, but I need the minimum instead of the maximum.

推荐答案

也许你应该检查一下(PDF 警告！还要注意，由于某种原因，页面顺序颠倒了)"计算两个有限平面集之间最小距离的最优算法" Toussaint 和 Bhattacharya:

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:

本文表明，两个有限之间的最小距离如果 [sic] n 个点可以是平面集在 O(n log 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 警告！再次，页面顺序颠倒了)一种计算两个交叉凸多边形之间最小顶点距离的最佳算法" 作者 Toussaint:

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₁,p₂,..., p_m} 和 Q = {q₁, q₂,...,q_n} 是指定顶点的两个相交多边形通过他们的笛卡尔坐标命令.最优 O(m + n)算法被提出用于计算之间的最小欧几里得距离P 中的一个顶点 p_i 和一个q中的顶点q_j.

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屋！