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

doi:10.11988/ckyyb.20160854

院报 ›› 2016, Vol. 33 ›› Issue (11): 32-35.DOI: 10.11988/ckyyb.20160854

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

吴波涛¹,张煜²,陈文龙²,沈定涛²,魏思奇²

1.云南省水利水电勘测设计研究院,昆明 650021;2. 空间信息技术应用研究所,武汉 430010

收稿日期:2016-08-20 出版日期:2016-11-20 发布日期:2016-11-08
通讯作者: 张煜(1971-),男,山东阳谷人,高级工程师,博士,研究方向为摄影测量与遥感,(电话)18986061273(电子信箱)zhangyu_1999@126.com。
作者简介:吴波涛(1970-),男,云南呈贡人,高级工程师,研究方向为工程测量与摄影测量,(电话)13987116160(电子信箱)wbt5190523@126.com。
基金资助:
云南省水利厅水资源费项目(41501558);云南省水利重大科技项目(CKSK2015852/KJ)

Data Organization and Management of LiDAR Based onRed-black Tree and K-D Tree

WU Bo-tao¹ , ZHANG Yu² , CHEN Wen-long², SHEN Ding-tao², Wei Si-qi²

1.Yunnan Institute of Water & Hydropower Engineering Investigation, Design and Research, Kunming650021, China;
2.Spatial Information Technology Application Department, Yangtze River Scientific Research Institute, Wuhan 430010, China

Received:2016-08-20 Online:2016-11-20 Published:2016-11-08

摘要/Abstract

摘要：

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

关键词: LiDAR, 红黑树, K-D树, 数据结构, 数据组织, 立方体网格

Abstract:

LiDAR point cloud is a 3D point set composed of massive discrete laser dots which exist in both plane and vertical directions. Because of lacking space topological relations among the discrete dots of LiDAR point cloud, it is important to establish an appropriate data structure for LiDAR point cloud as the foundation of LiDAR processing. According to the structural characteristics of LiDAR point cloud data, a two-level data structure with “non-null” regular cube grid and K-D tree is established for the organization and management LiDAR point cloud using red-black tree and K-D tree to build. The structure could reduce the structural redundancy and improve indexing efficiency.

Key words: LiDAR, red-black tree, K-D tree, data structure, data organization, regular cube grid

中图分类号:

TP317.4

吴波涛,张煜,陈文龙,沈定涛,魏思奇. 基于红黑树与K-D树的LiDAR数据组织管理[J]. 院报, 2016, 33(11): 32-35.

WU Bo-tao,ZHANG Yu,CHEN Wen-long, SHEN Ding-tao, Wei Si-qi. Data Organization and Management of LiDAR Based onRed-black Tree and K-D Tree[J]. JOURNAL OF YANGTZE RIVER SCIENTIFIC RESEARCH INSTI, 2016, 33(11): 32-35.

[1]	夏雄彬, 谯立家, 许万忠. 基于机载LiDAR及无人机影像的高位危岩体调查和成因分析[J]. 院报, 2023, 40(9): 188-194.
[2]	李昂, 黄煌, 夏煜, 沈定涛, 王结臣. 基于改进分水岭算法的农村地区LiDAR点云建筑物提取[J]. 院报, 2021, 38(3): 149-154.
[3]	吴鹏飞,柳林,乔骁,周杰,刘金涛,李晓鹏,韩小乐. 基于LiDAR的青藏高原山坡小流域地形提取方法[J]. 院报, 2019, 36(9): 155-160.
[4]	许颖,岳东杰,孟德友. 基于特征差异的机载LiDAR侵蚀沟点云分割方法[J]. 院报, 2018, 35(2): 151-154.
[5]	李云帆,谭德宝,高广,刘瑞. 双阈值Alpha Shapes算法提取点云建筑物轮廓研究[J]. 院报, 2016, 33(11): 1-4.
[6]	姚春静,胡唯. 基于特征约束的LiDAR点云等高线自动生成方法[J]. 院报, 2014, 31(12): 113-116.
[7]	周力峰，王奔. 《长江水利科技网》的数据组织与运行维护[J]. 院报, 2013, 30(3): 89-92.
[8]	韩文军. 机载LiDAR数据的电力塔建模方法研究[J]. 院报, 2012, 29(10): 122-126.
[9]	谢鸿宇, 陈华, 吴建红, 鄢忠清, 朱积军. 基于GIS的清丰山流域综合查询系统的设计与开发[J]. 院报, 2005, 22(4): 34-36.

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

Data Organization and Management of LiDAR Based onRed-black Tree and K-D Tree

PDF

可视化

摘要/Abstract

引用本文

使用本文

相关文章 9

编辑推荐

Metrics

本文评价