algorithm - 距離比較でネストされた for ループを避ける

Question

オブジェクトのリストが 2 つあります。現在のリスト 1 オブジェクトの境界内にある場合にのみ、特定のリスト 2 オブジェクトに対して操作を実行したいと考えています。

このようなもの ：

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

私はあなたが常に距離を計算しなければならないと言うかもしれません。唯一の解決策は、ポイントを空間的にソートするか、ある種の事前計算を行うことです。たとえば、空間グリッドを作成し、どのポイントよりも同じ象限に属するすべてのポイントを破棄します。