Octreeで指定された範囲内で範囲を検索

Question

N-BodyやSPHなどのパーティクルアルゴリズムに興味があります。これらのアプリケーションで重要なステップの1つは、クエリポイントが与えられたときに、半径「h」の指定された範囲内にある粒子 を見つけることです。

ここで、OctreesはN-bodyやSPHのような問題の良い空間データ構造であると聞いたことがあります。

しかし、オクトリー構成の後、「半径内の粒子の位置を特定する」ステップがどのように実行されるのか理解できません。誰かがこのステップを実行するための参考資料、論文または記事を私に指摘してもらえますか？

Answer 1

k-d treesもこれに使用するのに適したデータ構造であり、最近隣の検索によく使用されます。

Answer 2

オクツリーは3dPointオブジェクトが含まれていることを推測： 「は点Pの半径3内見つけ粒子」 「球を触れること、又は交差Octreecellsに含まれるすべての点を返す（中心P、半径R）」のように表すことができる にセルが球と交差するかどうかをテストします。

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)