第4章 k-d tree 与八叉树

通过雷达、激光扫描、立体摄像机等三维测量设备获取的点云数据，具有数据量大、分布不均匀等特点。作为三维领域里面另一个重要的数据来源，点云数据主要是表征目标表面的海量点集合，并不具备传统实体网格数据的几何拓扑信息。点云数据处理中最为核心的问题就是建立离散点间的拓扑关系，实现基于邻域关系的快速查找。建立空间索引在点云数据处理中已被广泛应用，常见空间索引一般是自顶向下逐级划分空间的各种空间索引结构，比较有代表性的包括BSP树、k-d tree、KDB树、R树、R+树、CELL树、四叉树和八叉树等索引结构，而在这些结构中，k-d tree和八叉树在3D点云数据组织中的应用较为广泛。PCL对八叉树的数据结构建立和索引方法进行了实现，以方便在此基础上的其他点云处理操作。