避免在距离比较中嵌套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中的对象继续查找最近邻居，直到到下一个邻居的距离超出边界。