三维点云处理 2.3 Octree

一、八叉树八叉树是专为三维数据设计的空间索引结构其名称源于每个节点具有八个分支。八分支结构源于三维空间中每个维度均分形成的二的三次方组合。与二叉树和KD树相比八叉树在最近邻搜索中的核心优势在于支持提前终止搜索。传统二叉树类结构需回溯至根节点确认搜索范围而八叉树通过立方体空间划分可直接判定当查询点为中心的球体完全落入某立方体时仅需搜索该立方体内部数据。此特性依赖三维空间的完整切割信息而KD树单维度切割无法实现同等效果。1.八叉树的构建八叉树构建逻辑与二叉树、KD树相似均采用递归分割策略。1) 八叉树元素八叉树基础单元为立方体三维或正方形二维简化模型。二维演示时退化为四叉树结构其基本元素为平面正方形。2) 确定八叉树的外围构建初始阶段需通过fdg三元素确定最大包围立方体/正方形的空间边界。3) 切割条件空间分割受双重条件约束元素数量阈值当立方体内元素数超过预设值如live_size1时触发分割最小边长限制立方体边长达到下限时终止分割。此限制可避免重复坐标点导致的无限递归问题。示例中第一层分割产生四个子区域空区域直接终止构建非空区域继续递归分割直至满足终止条件。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树适用于任意维度空间分割。八叉树专用于三维空间分割。核心思想通过区域分割实现搜索优化可跳过或提前终止部分区域搜索。作业要求任务对三维点云数据中每个点查找其8个最近邻点。实现方法暴力搜索。scikit-learn提供的kd树API。自主实现的kd树或八叉树支持Python/C。评分标准自主实现方法的耗时与暴力搜索耗时的比值比值越小性能优化越显著。