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

Question

我对 N-Body 和 SPH 等粒子算法很感兴趣。这些应用程序中的一个重要步骤是，给定一个查询点，找到位于半径为“h”的指定球体内的粒子。

现在我听说八叉树是解决 N 体或 SPH 等问题的良好空间数据结构。

但是在八叉树构造之后，我无法理解“在半径内定位粒子”步骤是如何执行的。有人可以指点我做这一步的一些参考资料、论文或文章吗？

Answer 1

猜测Octree包含3dPoint对象：“定位点p的半径3内的粒子”可以表示为“返回Octreecells中包含的所有与Sphere接触或相交的点（中心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)

Answer 2

kd 树也是很好的数据结构，通常用于最近邻搜索。