algorithm - 八叉树算法用于最近邻搜索

Question

问题陈述：使用八叉树找到每个粒子最近的 GRID ID。

图。1]：

图[2]：

我有一个粒子系统（~6k，可移动），我需要检查哪个网格点（刚性；在图片中）最接近。有人建议我选择 Octree，因为它对于 3D 网格来说速度很快。

这是递归八叉树获取网格最近网格点的正确算法吗？

1. 获取一个输入作为点 P 起始坐标 C（第一次是 [0,0,0]）
2. 起始尺寸 = [Sx, Sy, Sz]
3. 得到所有 8 个中点 Mi = {M1,..,M8} 得到 Mi 和 P 的最小距离

4. 假设 M 得到 M 的起始位置为 Cn 设置大小 Sn = [Sx/8, Sy/8, Sz/8]

5. 如果 M 和 P 的距离小于 2 *（网格空间 G）：

   5.1。迭代从 Cn 到 Sn 的所有网格点

   5.2. 打印最少作为结果

6. 别的

   6.1。设置起始坐标为 Cn

   6.2. 将大小设置为 Sn

   6.3. 转到 1

问题：如果粒子在边界外或接近边界，最后一次迭代会耗尽所有速度，因为它检查所有 A x B x C。

请建议您是否有更好的方法来解决此问题。

Answer 1

这里不需要使用八叉树。八叉树对于反向问题很有用（给定一个网格点，找到最近的粒子），但在这里完全没用。

假设一个网格单元的大小是(a, b, c)，那么离它最近的网格点(x, y, z)是(a*floor(x/a+0.5), b*floor(y/b+0.5), c*floor(z/c+0.5))。