data-structures - ポイントを含む領域を見つけるための適切なデータ構造は何ですか?

Question

「n」個の領域のどれに点「p」が含まれているかを見つけることをサポートするデータ構造を探しています。Quadtree と R-tree を見ていましたが、探しているものにぴったり合っているとは思いません。

本質的に、このツリーにいくつかの 3 次元の長方形の領域を追加し、このツリーに対して 3 次元の点をテストして、どの領域が最も厳密に点を拘束しているかを返すことができるようにしたいと考えています。境界が重なる領域はありません。

私が現在使用している素朴なアルゴリズムは、各長方形領域の各次元に対して点「p」を単純にテストすることです。

for(region in regionList):
    if(p.x > region.x1 && p.x < region.x2 && p.y > region.y1 && py < region.y2 && p.z > region.z1 && p.z < region.z2)
        return region
end

これは O(n) 時間で実行されます。n はリージョンの数です。Quadtree が 2 次元の点を見つけるために行う点として、検索で O(log n) を取得したいと思います。

Answer 1

MX-CIF ツリーのような領域を格納する QuadTree をお勧めします。基本的には、2 次元 (x、y) に基づく QuadTree です。(x,y) に関してポイントを含む適切なノードを見つけたら、3 つの (x,y,z) 次元すべてにポイントが含まれているかどうかを確認できます。

私はJava で似たようなことをしました。

3 次元の QuadTree である Octree を調べることもできます。

Answer 2

セグメント ツリーとKD ツリーを確認してください。