Rapid 2D Delaunay triangulation algorithm for random distributed point cloud data

CORC > 自然资源部第一海洋研究所 > 自然资源部第一海洋研究所 > 支撑保障部门 > 海洋信息与计算中心

	Rapid 2D Delaunay triangulation algorithm for random distributed point cloud data
	Wang, Wen 1; Su, Tianyun 2; Wang, Guoyu 1
刊名	Jisuanji Fuzhu Sheji Yu Tuxingxue Xuebao/Journal of Computer-Aided Design and Computer Graphics
	2015
卷号	27 期号:9 页码:1653-1660
关键词	Efficiency
ISSN号	10039775
英文摘要	Given the enormous scale and diverse distribution of 2D point cloud data, a multi-grid combined with Hilbert curve insertion algorithm is proposed for improving the efficiency of Delaunay Triangulation. First of all, the division problem caused by regular grid insertion scheme for non-uniform distributed point set can be resolved by the multi-grid one. Then, a large amount of conflicting elongated triangles, which have to be created and deleted many times, can be avoided by adding control points and adopting Hilbert curve traversing grids. Lastly, searching steps for positioning inserting point can be reduced by adjusting the Hilbert curve in adjacent grids for the avoided "jumping" phenomenon. The experimental results show that the efficiency of Delaunay triangulation by multi-grid combined with Hilbert curve insertion algorithm can be improved significantly for both uniform and non-uniform distributed point cloud data compared with CGAL, regular grid insertion and multi-grid insertion algorithm. ©, 2015, Institute of Computing Technology. All right reserved.
语种	中文
出版者	Institute of Computing Technology
内容类型	期刊论文
源URL	[http://ir.fio.com.cn/handle/2SI8HI0U/6635]
专题	支撑保障部门_海洋信息与计算中心
作者单位	1.College of Information Science and Engineering, Ocean University of China, Qingdao; 266100, China;; 2.Marine Information and Computation Center, First Institute of Oceanography, State Oceanic Administration, Qingdao; 266061, China
推荐引用方式 GB/T 7714	Wang, Wen,Su, Tianyun,Wang, Guoyu. Rapid 2D Delaunay triangulation algorithm for random distributed point cloud data[J]. Jisuanji Fuzhu Sheji Yu Tuxingxue Xuebao/Journal of Computer-Aided Design and Computer Graphics,2015,27(9):1653-1660.
APA	Wang, Wen,Su, Tianyun,&Wang, Guoyu.(2015).Rapid 2D Delaunay triangulation algorithm for random distributed point cloud data.Jisuanji Fuzhu Sheji Yu Tuxingxue Xuebao/Journal of Computer-Aided Design and Computer Graphics,27(9),1653-1660.
MLA	Wang, Wen,et al."Rapid 2D Delaunay triangulation algorithm for random distributed point cloud data".Jisuanji Fuzhu Sheji Yu Tuxingxue Xuebao/Journal of Computer-Aided Design and Computer Graphics 27.9(2015):1653-1660.