吴波涛，张 煜，陈文龙，沈定涛，魏思奇

(1.云南省水利水电勘测设计研究院，昆明 650021；2.长江科学院 空间信息技术应用研究所，武汉 430010)



基于红黑树与K-D树的LiDAR数据组织管理

吴波涛1，张 煜2，陈文龙2，沈定涛2，魏思奇2

(1.云南省水利水电勘测设计研究院，昆明 650021；2.长江科学院 空间信息技术应用研究所，武汉 430010)

LiDAR点云是由海量的激光离散脚点组成的三维点集，在平面以及垂直方向上均分布有数量不均的离散点。LiDAR点云离散点相互之间缺乏空间拓扑关系，所以建立适当的数据组织结构对LiDAR点云进行组织是对LiDAR点云进行处理的基础。根据LiDAR点云的数据结构特点，利用红黑树与K-D树建立一种“非空”规则立方体格网和K-D树相结合的双层次数据结构，用于LiDAR点云的组织管理，从而降低结构冗余和提高索引效率。

LiDAR；红黑树；K-D树；数据结构；数据组织；立方体网格

1 研究背景

LiDAR点云是由海量的激光离散脚点组成的三维点集，每个三维坐标点除了空间坐标外还有与扫描地物相关的额外属性，使得一个扫描区的LiDAR点云数据的信息量一般非常巨大。此外与栅格数据的二维结构不同，LiDAR点云是一种三维的空间数据，即在各个垂直方向上还分布有数量不均的离散点。LiDAR点云这种不同于以往的新特性，无论是在数据存储方式上还是在数据组织管理上都带来了颇具难度的挑战。

以往LiDAR点云数据的存储格式都是由各个LiDAR系统制造商自行决定的，有采用ASCII形式直接提供原始点云数据的，也有提供已经插过值的格网数据的，提供的属性和占用空间也是各不相同，这给LiDAR数据在不同硬件和软件下的共享和处理带来许多不便。……