最近邻搜索的八叉树算法

Question

问题陈述:使用Octree查找每个粒子的最近GRID ID.

图.1]:

图[2]:

我有一个粒子系统(~6k,可移动),我需要检查哪个网格点(刚性;图中)最接近.有人建议我选择Octree,因为3D Grids的速度很快(可能).

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

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)).