最接近点对的变化算法

最接近的一对点问题在计算几何中是众所周知的：给定点列表（x，y）找到具有最小欧几里得距离的点对。现在我对这个问题有一个变化，要求：给定一个n个点（xi，yi）（n + 1> i> 0）的列表，找出每个点（xi，yi）的最近的欧几里德距离，然后计算所有点的平均最近欧几里德距离。我知道的蛮力方法：最接近点对的变化算法

all_distance = []; 
for i= 1 to n 
    p = (xi,yi); 
    dis = []; 
    for j= 1 to n 
     if j==i 
      continue; 
     else 
      q = (xj,yj); 
      pt_dis = distance(p,q); 
     end 
     dis = [dis; pt_dis]; 
    end 
    all_distance = [all_distance; nearest(dis)] 

end 
mean_distance = all_distance/n;

这种方法很简单，但计算速度慢。我想知道是否有一些快速算法来解决这个问题。谢谢！

来源

2012-07-17 feelfree

此问题通常是最好由kd-tree或quadtree解决了，但是如果你想要的东西快速和肮脏的，那么你应该尝试以某种方式瓢泼大雨您的观点。也就是说，假设你的点数大致均匀地分布在范围（0,0）到（10,10）中，那么在这种情况下，可以使存储桶的数量为1个单位平方。现在通过查找桶中最近的点和所有八个相邻的桶来处理一个点。如果发现任何距离为1个单位或更少的点，则您知道它是最近的点，因为更近的点不得位于相邻的一个桶中，这意味着它必须超过1个单位。如果你没有找到这个关闭点，那么你需要检查所有点，或者你可以扩展到下一圈的桶。

来源

2012-07-17 16:20:00

如果分布间隔相对均匀但非均匀分布失败，则方法工作正常。 kd树或四叉树方法在所有情况下都更快，包括均匀分布。 – atb 2012-07-18 18:17:33

您可以计算O（n log n）时间内的Delaunay triangulation，并且对于每个顶点，最近的点将是三角测量中相邻点之一。将会有O（n）个边缘检查，所以它主要由O（n log n）三角测量成本决定。

来源

2012-07-17 16:32:42 Larry

最接近点对的变化算法

回答

相关问题