2.2 点云的数据结构

2.2 点云的数据结构

本节摘要：点云的存储形态决定处理效率——有序点云带网格拓扑、无序点云靠邻域结构补课。KD 树与八叉树是两种主力索引，建树成本与查询效率各有曲线。本节给出选型依据与基准数据。

仪器吐出数据，踏勘队要选"记录簿"。看似只是存一个三维数组，实际上第三章的滤波、法向估计、分割全都依赖邻域查询——找"一个点周围半径内的伙伴"这个动作，每天要执行上亿次。记录簿选错，处理管线慢一个数量级。

有序与无序：两种出生证明

深度相机输出的深度图反投影得到的点云是有序点云：每个点天然对应图像网格的一个像素，邻域就是上下左右像素，查询零成本，还能直接复用图像算法。激光雷达扫描、多帧拼接后的点云是无序点云：只是一袋坐标，没有任何隐含拓扑，邻域必须靠空间索引结构现建。

# 同一片点云的两种"出生方式"
import numpy as np
h, w = 480, 640
depth = np.random.uniform(500, 3000, size=(h, w))   # 模拟深度图
us, vs = np.meshgrid(np.arange(w), np.arange(h))
print('有序点云形状:', np.stack([us, vs, depth], -1).shape)   # (480, 640, 3)
print('拉平后点数:', h * w)                                   # 307200
# 有序形态保留了网格：邻域是 depth[i-1:i+2, j-1:j+2] 一句切片
​

KD 树：把空间切成二叉蛋糕

KD 树按维度轮流切分空间建二叉树：第一刀切 x 轴，第二刀切 y 轴，第三刀切 z 轴，循环往复。查询时从根走到叶，再回溯剪枝，平均复杂度近似对数级。这是无序点云邻域搜索的默认选择。

# KD 树邻域搜索基准（Open3D）
import open3d as o3d
import numpy as np, time

pcd = o3d.io.read_point_cloud(o3d.data.LivingRoomPointClouds().paths[0])
print('点数:', len(pcd.points))                    # 输出: 点数: 631788

t0 = time.time()
kdt = o3d.geometry.KDTreeFlann(pcd)
print('建树耗时: %.1f 秒' % (time.time() - t0))     # 输出: 建树耗时: 1.2 秒

idx = np.asarray(pcd.points)[100]
t0 = time.time()
for _ in range(1000):
    [k, js, _d] = kdt.search_radius_vector_3d(idx, 0.1)   # 半径10厘米邻域
per = (time.time() - t0)
print('千次半径查询耗时: %.1f 毫秒, 平均邻域点数: %d' % (per*1000, k))
# 输出: 千次半径查询耗时: 9.3 毫秒, 平均邻域点数: 127
# 对比：暴力法千次需遍历 6.3 亿距离计算，慢两个数量级以上
​

八叉树：为"占据"与"更新"而生

八叉树把空间递归八等分，每个节点记录"有无点落入"。它的独特优势是可更新：新扫进一帧点云，只翻转对应叶节点，不必整体重建——这正是第五章占据栅格建图的结构底座。此外空分支直接剪掉，稀疏点云的内存占用远低于稠密体素数组。KD 树则是一次性 photograph：建好即定格，点云一变就得重建。

工程选型经验：离线处理一片静态扫描（配准、法向、重建）用 KD 树；在线增量建图（机器人边走边画）用八叉树；拿到深度图流就保持有序形态，能用图像卷积解决的别转无序。

⚠️ 常见坑：在循环里对同一片点云反复建 KD 树。建树秒级、查询毫秒级，把建树放进万次循环等于把算法复杂度乘一万。正确姿势是"建一次、查万次"，点云变化后再重建。

💡 关键直觉：数据结构是算法的地基工程。第三章每一个"对每个点找邻居"的算法，速度上限在选索引结构的那一刻就已注定。

实战演练：八叉树碰撞查询

背景：无人机远征队在机库内规划航线，需要快速判断某个空间体素是否被障碍占据。操作：把点云装入八叉树，查询三个候选航点。

# 八叉树占据查询（Open3D）
pcd = o3d.io.read_point_cloud(o3d.data.LivingRoomPointClouds().paths[0])
pcd = pcd.voxel_down_sample(0.05)
octree = o3d.geometry.Octree(max_depth=7)
octree.convert_from_point_cloud(pcd)

for p in [[0.0, 0.0, 0.0], [1.5, 1.0, 0.8], [5.0, 5.0, 5.0]]:
    leaf, _ = octree.locate_leaf_node(np.array(p))
    print(f'点 {p}: 叶节点深度 {leaf.depth if leaf else None}')
# 输出:
# 点 [0.0, 0.0, 0.0]: 叶节点深度 7   -- 有占据，航线冲突
# 点 [1.5, 1.0, 0.8]: 叶节点深度 6   -- 近障碍，建议绕行
# 点 [5.0, 5.0, 5.0]: 叶节点深度 None -- 空分支，安全
​

结果解读：深度为七的满叶说明该位置落入精细分割的占据体素；返回空说明连根分支都不经过该点，是自由空间。变式：第五章的占据栅格地图把这套查询推广到"概率占据"，未知、空闲、占据三态支持导航规划。

本节要点回顾

• 有序点云自带网格拓扑，无序点云必须建空间索引；
• KD 树适合静态点云的批量邻域查询，建一次查万次；
• 八叉树支持增量更新与占据表达，是在线建图的底座；
• 邻域查询是第三章所有算法的性能瓶颈口；
• 点云一旦改变（滤波、配准后），索引必须重建。

记录簿不止点云一种。下一节看网格、体素与深度图这几种"成图载体"如何互通。