A Cutting Block Algorithm for Constructing Delaunay Triangulation Based on Streaming Computation

ZHANG Chunkang; ZHAO Xuesheng; WANG Hongbin

doi:10.13203/j.whugis20150375

Volume 42 Issue 7

Jul. 2017

Turn off MathJax

Article Contents

Abstract

References

Geomatics and Information Science of Wuhan University > 2017 > 42(7): 931-936. > DOI: 10.13203/j.whugis20150375

ZHANG Chunkang, ZHAO Xuesheng, WANG Hongbin. A Cutting Block Algorithm for Constructing Delaunay Triangulation Based on Streaming Computation[J]. Geomatics and Information Science of Wuhan University, 2017, 42(7): 931-936. DOI: 10.13203/j.whugis20150375

Citation:

PDF (2070 KB)

A Cutting Block Algorithm for Constructing Delaunay Triangulation Based on Streaming Computation

1.
Mining College, Guizhou University, Guiyang 550025, China
2.
College of Geoscience & Surveying Engineering, China University of Mining & Technology(Beijing), Beijing 100083, China
3.
Beijing Research Institute of Uranium Geology, Beijing 100029, China

Funds:

The National Natural Science Foundation of China 41171306

the Specialized Research Fund for the Doctoral Program of Higher Education 20130023110001

More Information

Author Bio:
ZHANG Chunkang, PhD candidate, specializes in LiDAR point cloud data processing etc. E-mail:chkang.chd@163.com
Corresponding author:
ZHAO Xuesheng, PhD, professor. E-mail:zxs@cumtb.edu.cn
Received Date: October 12, 2015
Published Date: July 04, 2017

Graphical Abstract

Abstract

Abstract

In order to solve the difficulty that the existing algorithms can't give attention to both the capability of time and space when constructing Delaunay triangulation with massive LiDAR points cloud, a cutting block Delaunay triangulation algorithm using streaming computation is presented. DeWall (Delaunay wall) is constructed firstly to cut an independent point cloud data block with specific size and shape, which is suitable for the divide-and-conquer algorithm and can avoid deep recursion and memory overflow. Then the cutting block is triangulated with a divide-and-conquer algorithm, and an algorithm is proposed to delete the wrong triangles on the boundary of the cutting block triangulation. The process described above is repeated to construct all the sub-triangulations, which can be merged directly according to the property of the decoupled domain decomposition mode finally. Meanwhile, the streaming computation is introduced so that the algorithm has a more excellent capability of space. The analysis and experiments show that the algorithm has a low memory footprint and is efficient with a time complexity close to O(nlg(δ))(δ is the number of points in a cutting block and δ ≤ n).
- Delaunay triangulation,
- time and space performance,
- cutting block,
- streaming computation,
- decoupled domain decomposition mode

FullText(HTML)

References (15)

References

[1]	李坚, 李德仁, 邵振峰.一种并行计算的流数据Delaunay构网算法[J].武汉大学学报·信息科学版, 2013, 38(7):794-798 http://ch.whu.edu.cn/CN/abstract/abstract2692.shtml 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, 38(7):794-798 http://ch.whu.edu.cn/CN/abstract/abstract2692.shtml
[2]	武晓波, 王世新, 肖春生.Delaunay三角网的生成算法研究[J].测绘学报, 1999, 28(1):28-35 http://cdmd.cnki.com.cn/Article/CDMD-10010-2010170009.htm Wu Xiaobo, Wang Shixin, Xiao Chunsheng.A New Study of Delaunay Triangulation Creation[J].Acta Geodaetica et Cartographica Sinica, 1999, 28(1):28-35 http://cdmd.cnki.com.cn/Article/CDMD-10010-2010170009.htm
[3]	武晓波, 王世新, 肖春生.一种生成Delaunay三角网的合成算法[J].遥感学报, 2000, 4(1):32-35 doi: 10.11834/jrs.20000106 Wu Xiaobo, Wang Shixin, Xiao Chunsheng. A Hybridized Method for Building Delaunay Triangulation[J]. Journal of Remote Sensing, 2000, 4(1):32-35 doi: 10.11834/jrs.20000106
[4]	吴宇晓, 张登荣.生成Delaunay三角网的快速合成算法[J].浙江大学学报(理学版), 2004, 31(3):343-348 http://www.cnki.com.cn/Article/CJFDTOTAL-HZDX200403023.htm Wu Yuxiao, Zhang Dengrong.Improved Algorithm for Building Delaunay Triangulation[J].Journal of Zhejiang University (Science Edition), 2004, 31(3):343-348 http://www.cnki.com.cn/Article/CJFDTOTAL-HZDX200403023.htm
[5]	芮一康, 王结臣.Delaunay三角形构网的分治扫描线算法[J].测绘学报, 2007, 36(3):358-362 http://www.cnki.com.cn/Article/CJFDTOTAL-CHXB200703021.htm Rui Yikang, Wang Jiechen.A New Study of Compound Algorithm Based on Sweep Line and Divide-and-conquer Algorithm for Constructing Delaunay Triangulation[J]. Acta Geodaetica et Cartographica Sinica, 2007, 36(3):358-362 http://www.cnki.com.cn/Article/CJFDTOTAL-CHXB200703021.htm
[6]	胡金星, 潘懋, 马照亭, 等.高效构建Delaunay三角网数字地形模型算法研究[J].北京大学学报(自然科学版), 2003, 39(5):736-741 http://www.cnki.com.cn/Article/CJFDTOTAL-BJDZ200305025.htm Hu Jinxing, Pan Mao, Ma Zhaoting, et al.Study on Faster Algorithm for Constructing Delaunay Triangulations DTM[J].Acta Scientiarum Naturalium Universitatis Pekinensis, 2003, 39(5):736-741 http://www.cnki.com.cn/Article/CJFDTOTAL-BJDZ200305025.htm
[7]	胡金星, 马照亭, 吴焕萍, 等.基于格网划分的海量数据Delaunay三角剖分[J].测绘学报, 2004, 33(2):163-167 http://www.cnki.com.cn/Article/CJFDTOTAL-CHXB200402013.htm Hu Jinxing, Ma Zhaoting, Wu Huanping, et al. Massive Data Delaunay Triangulation Base on Grid Partition Method[J]. Acta Geodaetica et Cartographica Sinica, 2004, 33(2):163-167 http://www.cnki.com.cn/Article/CJFDTOTAL-CHXB200402013.htm
[8]	董箭, 彭认灿, 郑义东.利用局部动态最优Delaunay三角网改进逐点内插算法[J].武汉大学学报·信息科学版, 2013, 38(5):613-617 http://ch.whu.edu.cn/CN/abstract/abstract2648.shtml Dong Jian, Peng Rencan, Zheng Yidong. An Improved Algorithm of Point-by-point Interpolation by Using Local Dynamic Optimal Delaunay Triangulation Network[J]. Geomatics and Information Science of Wuhan University, 2013, 38(5):613-617 http://ch.whu.edu.cn/CN/abstract/abstract2648.shtml
[9]	沈晶, 刘纪平, 林祥国, 等.集成距离变换和区域邻接图生成Delaunay三角网的方法研究[J].武汉大学学报·信息科学版, 2012, 37(8):1000-1003 http://ch.whu.edu.cn/CN/abstract/abstract303.shtml Shen Jing, Liu Jiping, Lin Xiangguo, et al. A Method for Delaunay Triangulation by Integration of Distance Transformation and Region Adjacency Grapuics[J]. Geomatics and Information Science of Wuhan University, 2012, 37(8):1000-1003 http://ch.whu.edu.cn/CN/abstract/abstract303.shtml
[10]	alik B. An Efficient Sweep-line Delaunay Triangulation Algorithm[J].Computer-Aided Design, 2005, 37(10):1027-1038 doi: 10.1016/j.cad.2004.10.004
[11]	Biniaz A, Dastghaibyfard G.A Fast Circle-sweep Delaunay Triangulation Algorithm[J]. Advances in Engineering Software, 2012, 43(1):1-13 doi: 10.1016/j.advengsoft.2011.09.003
[12]	Isenburg M, Liu Y, Shewchuk J, et al. Streaming Computation of Delaunay Triangulations[J]. ACM Trans Graph, 2006, 25:1049-1056 doi: 10.1145/1141911
[13]	王磊, 聂玉峰, 李义强.Delaunay四面体网格并行生成算法研究进展[J].计算机辅助设计与图形学学报, 2011, 23(6):923-932 http://www.cnki.com.cn/Article/CJFDTOTAL-JSJF201106002.htm Wang Lei, Nie Yufeng, Li Yiqiang. Advances of Research on Parallel Delaunay Tetrahedral Mesh Generation[J]. Journal of Computer-Aided Design & Computer Graphics, 2011, 23(6):923-932 http://www.cnki.com.cn/Article/CJFDTOTAL-JSJF201106002.htm
[14]	Cignoni P, Montani C, Scopigno R. DeWall:A Fast Divide & Conquer Delaunay Triangulation Algorithm in E^d[J]. Computer Aided Design, 1998, 30(5):333-341 doi: 10.1016/S0010-4485(97)00082-1
[15]	吴文周, 李利番, 王结臣.平面点集凸包Graham算法的改进[J].测绘科学, 2010, 35(6):123-125 http://www.cnki.com.cn/Article/CJFDTOTAL-CHKD201006044.htm Wu Wenzhou, Li Lifan, Wang Jiechen. An Improved Graham Algorithm for Determining the Convex Hull of Planar Points Set[J].Science of Surveying and Mapping, 2010, 35(6):123-125 http://www.cnki.com.cn/Article/CJFDTOTAL-CHKD201006044.htm

Cited By

Get Citation

PDF

XML

Article views (1922) PDF downloads (411)

A Cutting Block Algorithm for Constructing Delaunay Triangulation Based on Streaming Computation

Abstract

References

Catalog

Related

A Cutting Block Algorithm for Constructing Delaunay Triangulation Based on Streaming Computation

Abstract

References

Catalog

Related

Export File

Citation

Format

Content