点算法之间的最短距离

Question

给定平面上的一组点,找到由这两个点中的任何两个点形成的最短线段.

我怎样才能做到这一点？琐碎的方法显然是计算每个距离,但我需要另一种算法进行比较.

Answer 1

http://en.wikipedia.org/wiki/Closest_pair_of_points

使用递归分而治之的方法可以在O(n log n)时间内解决该问题,例如,如下:

• 沿x坐标对点进行排序
• 通过垂直线x = xmid将点集分成两个大小相等的子集
• 在左右子集中递归地解决问题.这将分别给出左侧和右侧最小距离dLmin和dRmin.
• 找到一对点中的最小距离dLRmin,其中一个点位于分割垂直的左侧,第二个点位于右侧.
• 最终答案是dLmin,dRmin和dLRmin中的最小值.

Answer 2

我不能立即想到比蛮力技术更快的替代方案(尽管必须有很多)但是你选择的算法并不能计算每个点之间的距离.如果您需要比较距离,只需比较距离的平方,以避免昂贵且完全冗余的平方根.

Answer 3

一种可能性是按X坐标对点进行排序(或者Y - 并不重要,只是一致).然后,您可以使用它来消除与许多其他点的比较.当你看到点[i]和点[j]之间的距离时,如果单独的X距离大于你当前的最短距离,则点[j + 1] ...点[N]可以被消除为好吧(假设i<j- 如果j<i,那么点[0] ......点[i]被淘汰).

如果您的点以极坐标开始,则可以使用相同的变体 - 按原点的距离排序,如果与原点的距离差异大于当前的最短距离,则可以消除该点,以及与您目前正在考虑的原点相比距原点更远(或更接近原点)的所有其他原因.

Answer 4

您可以从Delaunay三角剖分中提取线性时间中最接近的一对，反之从Voronoi图中提取。