基于LiDAR点云数据的三角网构建算法
作者:
基金项目:

Supported by the International (Regional) Cooperation and Exchange Project in National Natural Science Foundation of China under Grant No.60573174 (国家自然科学基金国际(地区)合作交流项目); the National Natural Science Foundation of China under Grant No.60673028 (国家自然科学基金); the Open Project Foundation in Key Laboratory of Special Display Technology for the Ministry of Education of China (特种显示技术教育部重点实验室开放课题)

  • 摘要
  • | |
  • 访问统计
  • |
  • 参考文献 [23]
  • |
  • 相似文献 [20]
  • | | |
  • 文章评论
    摘要:

    在现有Delaunay三角网生长法的基础上进行改进,提出了一种三角网生长算法.该算法对大规模点云进行等格网分块,自适应确定搜索范围.通过在构建过程中对生成的基线进行分组和排序,动态删除封闭点,提高了构建三角网的速度;通过在整个点集范围内进行搜索,避免了通过插值所产生的误差和模块之间的拼接过程.利用此算法对大规模LiDAR点云数据进行构网,结果表明了该算法的有效性.

    Abstract:

    Based on the existing Delaunay triangulation method, an algorithm of triangulation growth is presented. This algorithm divides the large-scale point clouds into uniform grids and determines the searching scope self-adaptively. During the process of building a triangulated irregular network (TIN) model, the generated base-lines in groups are grouped, and the close-points are removed dynamically, which improved the speed of reconstructing TIN in large-scale scenes dramatically. By searching the triangular vertices in the scope of the whole data set, this method avoided errors caused by interpolation and the process of stitching between grids. The efficiency and effectiveness of this algorithm are verified by using real world data to build TIN model with large scale LiDAR point clouds.

    参考文献
    [1] Liang XL, Zhang JX, Li HT. Regular building model reconstruction from airborne laser scanning data. Journal of Image and Graphics, 2007,12(4):641(647 (in Chinese with English abstract).
    [2] Sithole G, Vosselman G. Filtering of airborne laser scanner data based on segmented point clouds. In: Proc. of the Laser Scanning 2005. Enschede, 2005.
    [3] Hu JX, Wu HP, Pan M, Ma ZT. Massive DEM creation with grid partitioning approach. Journal of Computer-Aided Design & Computer Graphics, 2004,16(1):41(44 (in Chinese with English abstract).
    [4] Wu YG, Du Y, Wang XM, You X. Lod-Based algorithm of TIN model for large terrain simulation. Journal of System Simulation, 2005,17(3):665(669 (in Chinese with English abstract).
    [5] Maus A. Delaunay triangulation and the convex hull of n points in expected linear time. BIT, 1984,24(2):151(163.
    [6] Wu XB, Wang SX, Xiao CS. A new study of Delaunay triangulation creation. Acta Geodaetica et Cartographica Sinica, 1999,28(1): 28(35 (in Chinese with English abstract).
    [7] He J, Dai H, Xie YQ, Liu BS. Fast improved Delaunay triangulation algorithm. Journal of System Simulation, 2006,18(11): 3055(3057 (in Chinese with English abstract).
    [8] Luan XY. The method of building TIN and its three-dimensional display. Hydrographic Surveying and Charting, 2004,24(5): 39(41 (in Chinese with English abstract).
    [9] Xu Q, Chang G, Yang L. The algorithm of TIN generation based on self-adapt clump organization. Journal of Image and Graphics, 2000,5(6):461(465 (in Chinese with English abstract).
    [10] Jin WH, He T, Liu XP, Tang WQ, Tang RX. A fast convex hull algorithm of planar point set based on sorted simple polygon. Chinese Journal of Computers, 1998,21(6):533(539 (in Chinese with English abstract).
    [11] Zhao WF. Improvement of generation algorithm of Delaunay triangulation network for the whole scatter points and software development. Engineering of Surveying and Mapping, 2003,12(4):22(25 (in Chinese with English abstract).
    [12] Fang TP, Pieql LA. Delaunay triangulation using a uniform grid. IEEE Computer Graphics and Application, 1993,13(3):36(47.
    [13] Chen MB, Chuang TR, Wu JJ. Parallel divide-and-conquer scheme for 2D Delaunay triangulation. Concurrency and Computation: Practice and Experience, 2006,18:1595(1612.
    [14] Lee S, Park CI, Park CM. An improved parallel algorithm for Delauany triangulation on distribution memory parallel computers. In: Proc. of the 1997 Advances in Parallel and Distributed Computing Conf. (APDC'97). 1997. 131(138.
    [15] Chen MB, Chuang TR, Wu JJ. A parallel divide-and-conquer scheme for Delaunay triangulation. In: Proc. of the 9th Int'l Conf. on Parallel and Distributed Systems (ICPADS). 2002. 571(576. 附中文参考文献: [1] 梁欣廉,张继贤,李海涛.机载激光雷达数据的简单规则建筑物模型重建.中国图象图形学报,2007,12(4):641(647.
    [3] 胡金星,吴焕萍,潘懋,马照亭.基于格网划分的海量DEM数据生成.计算机辅助设计与图形学学报,2004,16(1):41(44.
    [4] 武玉国,杜莹,王晓明,游雄.大规模地形TIN模型的LOD算法设计与实现.系统仿真学报,2005,17(3):665(669.
    [6] 武晓波,王世新,肖春生.Delaunay三角网的生成算法研究.测绘学报,1999,28(1):28(35.
    [7] 何俊,戴浩,谢永强,刘宝生.一种改进的快速Delaunay三角剖分算法.系统仿真学报,2006,18(11):3055(3057.
    [8] 栾晓岩.一种TIN生成算法及其三维显示.海洋测绘,2004,24(5):39(41.
    [9] 徐青,常歌,杨力.基于自适应分块的TIN三角网建立算法.中国图象图形学报,2000,5(6):461(465.
    [10] 金文华,何涛,刘晓平,唐卫清,唐荣锡.基于有序简单多边形的平面点集凸包快速求取算法.计算机学报,1998,21(6):531(539.
    [11] 赵文芳.离散点集Delaunay三角网生成算法改进与软件开发.测绘工程,2003,12(4):22(25.
    引证文献
    网友评论
    网友评论
    分享到微博
    发 布
引用本文

刘晓平,朱晓强,余 烨,袁晓辉,Bill P. BUCKLES.基于LiDAR点云数据的三角网构建算法.软件学报,2008,19(zk):1-9

复制
分享
文章指标
  • 点击次数:5758
  • 下载次数: 10424
  • HTML阅读次数: 0
  • 引用次数: 0
历史
  • 收稿日期:2008-04-20
  • 最后修改日期:2008-11-14
文章二维码
您是第19795250位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京市海淀区中关村南四街4号,邮政编码:100190
电话:010-62562563 传真:010-62562533 Email:jos@iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号