octree - 八分木で指定された半径内の範囲検索

Question

N体やSPHのような粒子アルゴリズムに興味があります。これらのアプリケーションでの重要な手順の1つは、クエリポイントを指定して、半径'h'の指定された球内にある粒子を見つけることです。

Octreesは、N体やSPHなどの問題に適した空間データ構造であると聞いています。

しかし、八分木を構築した後、「半径内に粒子を配置する」ステップがどのように実行されるのか理解できません。このステップを実行するための参考資料、論文、または記事を誰かに教えてもらえますか？

Answer 1

Octreeに3dPointオブジェクトが含まれていると推測する：「Pointpの半径3内に粒子を配置する」は、「Sphere（center p、radius r）に接触または交差するOctreecellに含まれるすべてのポイントを返す」と表現できます。セルが球と交差するかどうかをテストします。 ：

dx,dy,dz = 0;
if (pX < minX of Cell)
    dx = |px - minX|
else if (px > maxX of Cell)
    dx = |px-maxX|
Same for other dimensions

return (|dx,dy,dz|<=r)

Answer 2

kd木は、これに使用するのに適したデータ構造でもあり、最近傍探索に一般的に使用されます。