第一步:如果给定点 z 在八叉树包围盒内就从所属的最末端的子包围盒叶子节点开始,如果在八叉树外的话就从任意最靠近的叶子节点开始,先找一个最靠近 z 的候选点 A,如果叶子节点包围盒是空的,就递归向上,总之先找到第一个候选点 A。
第二步:以 z 为圆心,z 到 A 的距离为半径,做一个球体 S,把球体 S 同八叉树求交(离 z 最近的点一定落在这个球体范围内),筛选出有交集的叶子节点包围盒,然后迭代这些叶子节点包围盒里的点,一旦找到更近的就缩小球的范围,这样就能找到离 z 最近的点了。
如果要找前 k 个距离最近的点,你需要维护一个长度为 K 的优先队列(或者最大堆),在找到最近邻居的基础上,将兄弟节点邻近的候选点都填充到队列里,直到队列里装满 k 个点,此时以 z 为圆心,队列里第 k 个离 z 最近的点为半径,对八叉树做一次范围搜索(前 k 个点一定落在该范围内),搜索过程中不断更新优先队列并及时根据最新的第 k 个点离 z 的距离调整半径。