以点云数据为研究对象,提出了一种结合K维(KD)树空间切分思想的类八叉树混合点云索引结构,实现了对海量点云的高效管理。对于点云所在空间,首先利用KD树思想进行初步分割,再对所得的子空间利用八叉树做进一步切分,建立类八叉树索引结构。并对传统线性八叉树编码进行改进,利用优化后的编码方式对空间进行编码,以实现更好地空间管理和邻域搜索。最后,以5组数量级递增的点云集为测试数据,通过实验结果和对比分析可知,类八叉树能够使数据组织的整体结构趋于合理,有效地提高了存取效率,降低了内存空间的占用;提升了传统KD树构造索引的速度,也改善了传统八叉树对空间占用过大、邻域搜索耗时过长的问题,实现了对海量点云空间的合理管理。

Taking point cloud data as research object, this paper proposes a hybrid octree mixing point cloud index structure which combines a K-dimensional tree (KD-tree) spatial segmentation idea, and realizes efficient management of mass point cloud. In this paper, the space of the point cloud is first divided by the KD-tree idea. On this basis, octree is used for further segmentation to establish an octree-like index structure. Then, in order to achieve better spatial management and neighborhood search, the traditional linear octree coding is improved and optimized. Finally, using five groups of incremented point cloud set as test data, experimental results and comparison analysis show that the octree can make the overall structure of the data organization more reasonable, effectively improve access efficiency, and reduce the memory space. The index structure not only improves the speed of the traditional KD tree construction index but also improves the problem that the traditional octree takes too much space and the neighborhood search takes too long. It achieves reasonable management of massive point cloud space.