Monthly Archives: July 2021

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