八叉树中指定半径范围内的搜索

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)