一种采用流计算的Delaunay三角网切块剖分算法

发布时间：2018-01-05 04:18

本文关键词：一种采用流计算的Delaunay三角网切块剖分算法　出处：《武汉大学学报(信息科学版)》2017年07期 　论文类型：期刊论文

【摘要】：针对海量LiDAR点云Delaunay三角网剖分的时间与空间性能的矛盾问题,提出了一种采用切块的流计算Delaunay构网算法。首先利用三角网墙(DeWall)从点云上切割特定大小与形状的独立数据块,避免分治算法的深度递归与内存溢出;然后运用分治算法对切块剖分,并给出了切块边界错误三角形删除算法;重复上述过程完成子网剖分,并依据非耦合区域分解模式合并为最终三角网。引入流计算的思想,以进一步提高算法的空间性能。分析与实验表明:该算法占用了较低内存,并取得了接近为O(nlg(δ))(δ为一个切块点数,且δ≤n)的时间复杂度。
[Abstract]:To solve the problem of contradiction between time and space performance of the mass LiDAR point cloud Delaunay triangulation, is presented with a cut flow calculation algorithm of constructing Delaunay triangulation. Firstly, the wall (DeWall) independent data block cutting specific size and shape from the point cloud, can cure the depth of memory and recursive algorithm overflow; and then use the partition algorithm to cut section, and gives the cut boundary error triangle deletion algorithm; repeat the above process to complete the subnet partition, and on the basis of non coupling region decomposition model with triangulation. Finally introduced the thought of stream computing, to further improve the performance of the algorithm. The spatial analysis and experiments show that the algorithm take a low memory, and get close to O (NLG (delta) (8) as a cut point, and delta n) time complexity.

【作者单位】：贵州大学矿业学院;中国矿业大学(北京)地球科学与测绘工程学院;核工业北京地质研究院;
【基金】：国家自然科学基金(41171306) 高等学校博士学科点专项科研基金(20130023110001)~~
【分类号】：TN958.98
【正文快照】： 激光雷达能够在短时间内获取大量的点云,并在GIS、计算机图形学等领域得到了广泛应用,但海量LiDAR点云对Delaunay三角网剖分算法的性能提出了更高的要求[1]。传统的构网算法因不能同时兼顾算法的时间与空间性能,不适合较大点云的三角网剖分。目前在PC机上实现千万级以上的点云

【参考文献】

相关期刊论文前10条

1 董箭;彭认灿;郑义东;;利用局部动态最优Delaunay三角网改进逐点内插算法[J];武汉大学学报(信息科学版);2013年05期

2 沈晶;刘纪平;林祥国;赵荣;;集成距离变换和区域邻接图生成Delaunay三角网的方法研究[J];武汉大学学报(信息科学版);2012年08期

3 王磊;聂玉峰;李义强;;Delaunay四面体网格并行生成算法研究进展[J];计算机辅助设计与图形学学报;2011年06期

4 吴文周;李利番;王结臣;;平面点集凸包Graham算法的改进[J];测绘科学;2010年06期

5 芮一康;王结臣;;Delaunay三角形构网的分治扫描线算法[J];测绘学报;2007年03期

6 吴宇晓,张登荣;生成Delaunay三角网的快速合成算法[J];浙江大学学报(理学版);2004年03期

7 胡金星,马照亭,吴焕萍,潘懋;基于格网划分的海量数据Delaunay三角剖分[J];测绘学报;2004年02期

8 刘强,李德仁;数码城市中建筑物三维CAFM研究[J];武汉大学学报(信息科学版);2004年01期

9 胡金星,潘懋,马照亭,吴焕萍;高效构建Delaunay三角网数字地形模型算法研究[J];北京大学学报(自然科学版);2003年05期

10 武晓波,王世新,肖春生;一种生成Delaunay三角网的合成算法[J];遥感学报;2000年01期

【共引文献】

相关期刊论文前10条

1 曹文涛;何伟;;利用TIN和高程梯度进行高程点抽稀[J];测绘通报;2017年05期

2 刘洋;唐好选;;针对路面建模的Delaunay三角网格分治算法[J];智能计算机与应用;2017年02期

3 陈长波;刘小丁;朱紫阳;周昆;;单波束测深数据的插值精度分析[J];测绘通报;2017年03期

4 张新建;;结合GDI+对分治法生成Delaunay三角网的改进[J];矿山测量;2017年01期

5 马骏;蔺东杰;凌广明;;基于海量数据的二维凸包快速生成算法[J];计算机技术与发展;2017年02期

6 刘琴琴;;平面域Delaunay三角网点定位算法研究综述[J];电子设计工程;2017年01期

7 张春亢;赵学胜;王洪斌;;一种采用流计算的Delaunay三角网切块剖分算法[J];武汉大学学报(信息科学版);2017年07期

8 王卓识;陈根良;王皓;徐勋;孔令雨;;基于误差区域映射的并联机构精度设计研究[J];机械设计与研究;2016年04期

9 李必栋;闫浩文;王中辉;刘虎林;;坐标排序的离散点凸包生成算法[J];测绘科学;2017年02期

10 张晓蒙;陆忠华;张鉴;;三维并行约束Delaunay网格生成算法及实现[J];计算机辅助设计与图形学学报;2016年06期

【二级参考文献】

相关期刊论文前10条

1 周元峰;孙峰;王文平;汪嘉业;张彩明;;基于局部修复的移动数据点Delaunay三角化快速更新方法[J];计算机辅助设计与图形学学报;2011年12期

2 秦志霞;沈炜;刘文昊;;二维Voronoi图删除任意生成点算法研究[J];浙江理工大学学报;2010年03期

3 童晓冲;贲进;秦志远;张永生;;基于全球离散网格框架的局部网格划分[J];测绘学报;2009年06期

4 刘莹;聂玉峰;;泡泡布点方法及其并行性[J];计算物理;2009年06期

5 田峰敏;徐定杰;赵玉新;;一种建立海底格网数字高程模型的插值方法[J];中国航海;2009年03期

6 刘学军;张平;朱莹;;DEM坡度计算的适宜窗口分析[J];测绘学报;2009年03期

7 田峰敏;徐定杰;李宁;;Delaunay三角化中特征约束细分嵌入算法[J];武汉大学学报(信息科学版);2009年03期

8 郑顺义;邓德彦;;基于三角网无缝拼接的三维重建[J];武汉大学学报(信息科学版);2009年01期

9 贾俊涛;翟京生;孟婵媛;申家双;谭冀川;;基于海量多波束数据的海底地形模型的构建与可视化[J];测绘科学技术学报;2008年04期

10 梁义;陈建军;陈立岗;郑耀;;并行平面Delaunay网格生成[J];浙江大学学报(工学版);2008年04期

【相似文献】

相关期刊论文前10条

1 杨雅妹,贺士娟,赵德新,王志欣;基于3D Delaunay定理重构头模型[J];河北工业大学学报;2001年06期

2 胡金星,潘懋,马照亭,吴焕萍;高效构建Delaunay三角网数字地形模型算法研究[J];北京大学学报(自然科学版);2003年05期

3 邓曙光;刘刚;邹帆;;约束数据域Delaunay算法详述及进展[J];沈阳航空工业学院学报;2005年05期

4 ;Quick Approach to Construct Constrained Delaunay TIN for Line-Selection Design of Mountain Road[J];Computer Aided Drafting,Design and Manufacturing;2008年02期

5 梁晶晶;;Delaunay生成算法分类及研究[J];科技信息;2008年29期

6 李艳波;印桂生;张菁;朱长明;倪军;;Delaunay四面体软组织建模方法[J];计算机辅助设计与图形学学报;2010年12期

7 吕超;刘君;刘瑜;;基于Delaunay图的动网格生成方法[J];四川兵工学报;2010年12期

8 梁虎;唐玲艳;宋松和;;二维Delaunay网格的一个约束边恢复算法[J];航空计算技术;2011年02期

9 高远;;Delaunay算法的研究与探讨[J];硅谷;2011年18期

10 段硕;董慧颖;;基于Delaunay图的移动机器人路径规划方法[J];沈阳理工大学学报;2008年03期