八叉樹中指定半徑範圍內的搜索

Question

我對N-Body和SPH等粒子算法感興趣。根據查詢點，這些應用程序中的重要步驟之一是找到位於半徑'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)