避免在距離比較中嵌套for循環

Question

我有兩個對象列表;我想對給定的列表2對象執行操作，只要它在當前列表1對象的邊界內。

事情是這樣的：

for k=1:size(object_list1) 
    for l=1:size(object_list2) 
     if euclideanDstSqt(object_list1(k).centroid,object_list2(l).centroid) < toleranceRadius then 
      // do something ... 
     end 
    end   
end 

什麼是錯，是我將每一次檢查的距離，即使對於彼此很遠的物體。有算法更聰明的方法嗎？某種樹可能？

此算法可能會被轉換爲C++，因此我必須忘記所有面向矩陣的Matlab技巧。

Answer 1

我可以說你總是要計算距離。唯一的解決方案是讓點在空間上排序，或者做一些預先計算。例如，創建一個空間網格，並放棄屬於與任何點相同象限的所有點。

Answer 2

也許把列表2中的對象放入k-d tree，然後對列表1中的對象繼續查找最近鄰居，直到到下一個鄰居的距離超出邊界。