A General-division Grid Pattern Delaunay-TIN Parallel Algorithm

doi:10.11947/j.AGCS.2015.20140113

Abstract

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

CLC Number:

P208

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

References

[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.