A Delaunay Triangulation Algorithm Based on Dual-Spatial Data Organization

被引：1
作者：
Niantao Liu
Bingxian Lin
Guonian Lv
A-Xing Zhu
Liangchen Zhou
机构：
[1] Nanjing Normal University,Key Laboratory of Virtual Geographic Environment
[2] Ministry of Education,undefined
[3] State Key Laboratory Cultivation Base of Geographical Environment Evolution,undefined
[4] Jiangsu Center for Collaborative Innovation in Geographical Information Resource Development and Application,undefined
来源：
PFG – Journal of Photogrammetry, Remote Sensing and Geoinformation Science | 2019年 / 87卷
关键词：
Delaunay; Triangulation; Grid partition; KD-tree sort; Pipeline scheduling;
D O I：
暂无
中图分类号：
学科分类号：
摘要：
Existing Delaunay triangulation algorithms for LiDAR data can only guarantee the efficiency of a certain reconstruction step, but cannot guarantee the overall efficiency. This paper presents a Delaunay triangulation algorithm which integrates two existing approaches to improve the overall efficiency of LiDAR data triangulation. The proposed algorithm consists of four steps: (1) dividing a point cloud into grid cells, (2) sorting a point cloud using a KD-tree, (3) triangulating the point cloud and exporting inactive triangles in main memory, and (4) scheduling the above steps. The proposed algorithm was tested using three LiDAR data sets. The LiDAR data was used for comparing the proposed algorithm with the Streaming Delaunay algorithm with respect to both time efficiency and memory usage. Results from the experiments suggest that the proposed algorithm is three to four times faster than Streaming Delaunay while using nearly the same memory space.
引用
收藏
页码：19 / 31
页数：12
相关论文
共 16 条
  • [1] Bowyer A(1981)Computing Dirichlet tessellations Comput J 24 162-166
  • [2] Cendes Z(1983)Magnetic field computation using Delaunay triangulation and complementary finite element methods IEEE Trans Magn 19 2551-2554
  • [3] Shenton D(2011)Efficient mesh optimization schemes based on optimal Delaunay triangulations Comput Methods Appl Mech Eng 200 967-984
  • [4] Shahnasser H(1996)Incremental topological flipping works for regular triangulations Algorithmica 15 223-241
  • [5] Chen L(2013)A new insertion sequence for incremental Delaunay triangulation Acta Mech Sin 29 99-109
  • [6] Holst M(2013)Quadtree- and octree-based approach for point data selection in 2D or 3D Ann GIS 19 37-44
  • [7] Edelsbrunner H(1993)Delaunay triangulations in TIN creation: an overview and a linear-time algorithm Geogr Inf Syst 7 501-524
  • [8] Shah NR(1981)Computing the n-dimensional Delaunay tessellation with application to Voronoi polytopes Comput J 24 167-172
  • [9] Jian-Fei L(2011)ParaStream: a parallel streaming Delaunay triangulation algorithm for LiDAR points on multicore architectures Comput Geosci 37 1355-1363
  • [10] Jin-Hui Y(undefined)undefined undefined undefined undefined-undefined
12