最接近點對的變化算法

最接近的一對點問題在計算幾何中是衆所周知的：給定點列表（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

最接近點對的變化算法

回答

相關問題