algorithm - 在距离比较中避免嵌套 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

也许将列表 2 中的对象放入kd 树中，然后对于列表 1 中的对象，继续寻找最近的邻居，直到与下一个邻居的距离超出边界。

Answer 2

我可以说你总是要计算距离。唯一的解决方案是对点进行空间排序，或者进行某种预计算。例如，创建一个空间网格，并丢弃所有属于同一象限的点而不是任何点。