网格总分并行式Delaunay三角网建模方法

doi:10.11947/j.AGCS.2015.20140113

摘要/Abstract

摘要： 针对大规模点云数据,提出了Delaunay三角网构建的一种算法,算法通过自适应网格空间分割,实现了海量点云数据的规模均衡网格化逻辑分割;对网格内的顶点按距中距离进行排序,通过各网格由外而内的插入法建立三角网;按先总后分的方式优先保障网格之间三角网的生成,避免了分治-综合建模算法复杂而低效的三角网整合过程;建立了网格的拓扑闭包检测机制,针对各个子网格适时启动独立并行的线程对余下的内部点按传统的拓扑插入算法进行独立建模,从而并行高效、由总到分地实现了海量点集数据的三角网建模工作,显著地提高了空间大数据的三角网建模能力。

关键词: 三角网建模, 总分式构TIN, Delaunay三角网, 多线程构TIN, 大数据

Abstract: This paper achieves out a new Delaunay triangulation algorithm. Firstly, the self-adaptation grid space division was proposed to realize the balanced logical grid division for massive point cloud data. Secondly, from far to near order the sequence of points in each grid by distance to the grid center and find out the nearest point and mark it as the central point. Thirdly, the TIN was built with by a new general-division Delaunay triangulation algorithm, which uses traditional insertion method to build TIN and add only one point from each grid at one times to form new TIN. When building TIN we use find-insertion method firstly and hereafter use topology-insertion method to keep high efficiency. This algorithm has good efficiency because it successfully avoided the merge process of sub grid triangulation mesh. Finally, the topological closure detection mechanism was established, and the independent parallel multithreading was started to model the rest points by topology-insertion algorithm limit to every grid space, which made the triangulation modeling of the whole space efficient. The method of this paper improved the support capacity of space modeling for massive point cloud data obviously.

Key words: triangulation modeling, general-division pattern TIN construction, Delaunay triangulation, multithreading construction, massive data

中图分类号:

P208

韩元利. 网格总分并行式Delaunay三角网建模方法[J]. 测绘学报, 2015, 44(6): 702-708.

HAN Yuanli. A General-division Grid Pattern Delaunay-TIN Parallel Algorithm[J]. Acta Geodaetica et Cartographica Sinica, 2015, 44(6): 702-708.

参考文献

[1] DELAUNAY B. Sur la sphère vide, Izvestia Akademii Nauk SSSR[J]. Otdelenie Matematicheskikh i Estestven-nykh Nauk, 1934(7): 793-800.
[2] WU Xiaobo, WANG Shixin, XIAO Chunsheng. A New Study of Delaunay Triangulation Creation[J]. Acta Geodaetica et Cartographica Sinica, 1999, 28(1): 28-35. (武晓波, 王世新, 肖春生. Delaunay三角网的生成算法研究[J]. 测绘学报, 1999, 28(1): 28-35.)
[3] LEWIS B A, ROBINSON J S. Triangulation of Planar Regions with Applications[J]. The Computer Journal, 1978, 21(4): 324-332.
[4] GREEN P J, SIBSON R. Computing Dirichlet Tesselations in the Plane[J]. The Computer Journal, 1978, 21(2): 168-173.
[5] LEE D T, SCHACHTER B J. Two Algorithms for Constructing a Delaunay Triangulation[J]. International Journal of Computer & Information Sciences, 1980, 9(3): 219-242.
[6] HU Jinxing, MA Zhaoting, WU Huanping, et al. Massive Data Delaunay Triangulation Based on Grid Partition Method[J]. Acta Geodaetica et Cartographica Sinica, 2004, 33(2): 163-167. (胡金星, 马照亭, 吴焕萍, 等. 基于格网划分的海量数据Delaunay三角剖分[J]. 测绘学报, 2004, 33(2): 163-167.)
[7] RUI Yikang, WANG Jiechen. A New Study of Compound Algorithm Based on Sweepline and Divide-and-conquer Algorithms for Constructing Delaunay Triangulation[J]. Acta Geodaetica et Cartographica Sinica, 2007, 33(2): 163-167. (芮一康, 王结臣. Delaunay三角形构网的分治扫描线算法[J]. 测绘学报, 2007, 33(2): 163-167.)
[8] DWYER R A. A Faster Divide-and-conquer Algorithm for Constructing Delaunay Triangulations[J]. Algorithmica, 1987, 2(1-4): 137-151.
[9] MOSTAFAVI M A, GOLD C M, DAKOWICZ M. Delete and Insert Operations in Voronoi/Delaunay Methods and Applications[J]. Computers & Geosciences, 2003, 29(4): 523-530.
[10] CHEN Chujiang, WANG Defeng. CDT Fast Generation from Mass Geographic Data and Real Time Updating[J]. Acta Geodaetica et Cartographica Sinica, 2002, 31(8): 262-265. (陈楚江, 王德峰. 海量数据CDT快速建立及其实时更新[J]. 测绘学报, 2002, 31(8): 262-265.)
[11] ZHANG Fan, HUANG Xianfeng, LI Deren. Spherical Projection Based Triangulation for One Station Terrestrial Laser Scanning Point Cloud[J]. Acta Geodaetica et Cartographica Sinica, 2009, 38(1): 48-54. (张帆, 黄先锋, 李德仁. 基于球面投影的单站地面激光扫描点云构网方法[J]. 测绘学报, 2009, 38(1): 48-54.)
[12] CUI Xueseng, YANG Shenglong, FAN Wei. Grid Based Local Subdivision Algorithms for Constructing Triangulated Irregular Network under Restriction Conditions[J]. Acta Geodaetica et Cartographica Sinica, 2008, 37(2): 196-199. (崔雪森, 杨胜龙, 樊伟. 基于栅格局部细分的带约束条件的不规则三角网生成算法[J]. 测绘学报, 2008, 37(2): 196-199.)
[13] PU Hao, SONG Zhanfeng, ZHAN Zhenyan. On the Method for Fast Constructing Delaunay Triangulation DTM[J]. China Railway Science, 2001, 22(6): 100-105. (蒲浩, 宋占峰, 詹振炎. 快速构建三角网数字地形模型方法的研究[J]. 中国铁道科学, 2001, 22(6): 100-105.)
[14] XIA Shaofang, CHEN Lichao, LIU Jia. High Efficient Algorithm for Building Delaunay Triangulation Based on Virtual Grid[J]. Computer Engineering and Design, 2009, 30(1): 238-240. (夏少芳, 陈立潮, 刘佳. 基于虚拟网格的高效Delaunay三角网生成算法研究[J]. 计算机工程与设计, 2009, 30(1): 238-240.)
[15] LI Jian, LI Deren, SHAO Zhenfeng. A Streaming Data Delaunay Triangulation Algorithm Based on Parallel Computing[J]. Geomatics and Information Science of Wuhan University, 2013. 7, 38(7): 794-798. (李坚, 李德仁, 邵振峰. 一种并行计算的流数据Delaunay构网算法[J]. 武汉大学学报: 信息科学版, 2013, 38(7): 794-798.)
[16] WU H Y, GUAN X F, GONG J Y. Para Stream: A Parallel Streaming Delaunay Triangulation Algorithm for LiDAR Points on Multicore Architectures[J]. Computers & Geosciences, 2011, 37(9): 1355-1363.
[17] ISENBURG M, LIU Y X, SHEWCHUK J, et al. Streaming Computation of Delaunay Triangulations[J]. ACM Transactions on Graphics, 2006, 25(3): 1049-1056.
[18] SONG Zhanfeng, PU Hao, ZHAN Zhenyan. Study on an Algorithm for Fast Constructing Delaunay Triangulation[J]. Journal of the China Railway Society, 2001, 23(5): 85-91. (宋占峰, 蒲浩, 詹振炎. 快速构建Delaunay 三角网算法研究[J]. 铁道学报, 2001, 23(5): 85-91.)
[19] MILES R E. Solution to Problem 67-15 (Probability Distribution of a Network of Triangles)[J]. Society for Industrial and Applied Mathematics, 1969, 11(3): 399-402.