一、八叉树

八叉树是专为三维数据设计的空间索引结构，其名称源于每个节点具有八个分支。八分支结构源于三维空间中每个维度均分形成的二的三次方组合。与二叉树和KD树相比，八叉树在最近邻搜索中的核心优势在于支持提前终止搜索。传统二叉树类结构需回溯至根节点确认搜索范围，而八叉树通过立方体空间划分可直接判定：当查询点为中心的球体完全落入某立方体时，仅需搜索该立方体内部数据。此特性依赖三维空间的完整切割信息，而KD树单维度切割无法实现同等效果。

1.八叉树的构建

八叉树构建逻辑与二叉树、KD树相似，均采用递归分割策略。

1) 八叉树元素

八叉树基础单元为立方体（三维）或正方形（二维简化模型）。二维演示时退化为四叉树结构，其基本元素为平面正方形。

2) 确定八叉树的外围

构建初始阶段需通过fdg三元素确定最大包围立方体/正方形的空间边界。

3) 切割条件

空间分割受双重条件约束：

• 元素数量阈值：当立方体内元素数超过预设值（如live_size=1）时触发分割
• 最小边长限制：立方体边长达到下限时终止分割。此限制可避免重复坐标点导致的无限递归问题。示例中第一层分割产生四个子区域，空区域直接终止构建，非空区域继续递归分割直至满足终止条件。

4) 八叉树节点定义

八叉树节点包含以下核心属性：

• 8个子节点指针（区别于二叉树的2个子节点）
• 立方体中心坐标
• 空间范围参数extent（定义为半边长）
• 包含数据点的索引集合
• 是否为叶节点标记

5) 构建八叉树的代码

构建流程分为三阶段：

• 根节点初始化：检测根节点存在性，不存在时创建并载入全部数据点

• 分割条件判断：根据当前节点内点数与立方体边长决定是否继续分割

• 递归子节点构建：将当前立方体均分为八个子空间，计算各子空间：

  • 归属点集（通过空间位置判断）
  • 几何中心坐标

新边长参数

• 与KD树的主要差异在于八向空间划分带来的计算复杂度提升，但核心递归逻辑保持一致。

2.八叉树的k近邻搜索

1) 八叉树的k近邻搜索过程

k近邻搜索流程演示：

• 初始搜索：从根节点开始，无先验距离时需遍历所有可能区域（示例中s2/s3/s4）
• 优先级搜索：优先处理查询点所在子区域（s2→s8），获取初始最近邻距离
• 动态剪枝：根据当前最近邻距离绘制球体，当球体完全包含于某立方体时（如s2），立即终止其他分支搜索。此机制显著减少计算量，体现八叉树对三维数据的高效适配性。

2) 八叉树的k近邻搜索代码

搜索算法实现分为三类处理逻辑：

• 空节点处理：直接返回

• 叶节点处理：遍历节点内所有点更新最近邻集合

• 非叶节点处理：

  • 优先搜索最邻近子节点 - 按空间相交性筛选其他待查子节点（通过overlaps函数）
  • 触发提前终止条件（通过inside函数验证球体完全包含）

• inside函数

球体包含判定标准：在全部坐标轴上，球心到立方体边界的距离（蓝色虚线）均大于球体半径（绿色+红色线段）。关键参数query_offset表示球心指向立方体中心的向量。

• overlaps函数

立方体与球体相交判定需处理三种情况：

判定类型	几何条件	数学表达
空间分离	球心在某维度偏移量超过（立方体半边长+球半径）	abs(query_offset[i]) > (extent + radius)
面接触	球心在至少两个维度位于立方体投影范围内	sum(维度符合数) ≥ 2
顶点/边接触	球心到顶点距离小于（球半径+对角线长）	‖query_offset‖ < (radius + √3*extent)
边接触通过投影降维转化为顶点接触问题处理，使用max函数消除已满足条件的维度影响。

3.八叉树的半径近邻搜索

1) 半径近邻搜索简单方法

• 半径近邻搜索方法：将k近邻搜索中的knn resource set替换为radius resource set即可实现。

2) 半径近邻搜索更好方法

• 优化原理：在三维空间中，若已知查询球的半径固定且完全包含某个正方体，则无需递归切割该正方体。
• 操作步骤：直接遍历被包围正方体内的所有点进行距离对比，可显著减少计算量。

3) contains函数

• 函数作用：通过计算查询点（红点）到正方体边角点的最短距离（绿色虚线），与查询半径对比判断球体是否完全包围正方体。
• 判定条件：若绿色虚线长度小于半径，则正方体被球体包围，可提前终止该区域的递归搜索。

4.八叉树搜索复杂性

• 时间复杂度：

  • 最理想情况：近似O(log n)。
  • k近邻或半径搜索：取决于点分布和树结构，范围在O(log n)到O(n)之间。
  • 工程实践：通常按O(log n)估算，极端情况出现概率较低。

二、总结

• 空间分割方法对比：

  • 二叉树：适用于一维空间分割。
  • kd树：适用于任意维度空间分割。
  • 八叉树：专用于三维空间分割。

• 核心思想：通过区域分割实现搜索优化，可跳过或提前终止部分区域搜索。