A Delaunay Triangulation Algorithm Based on Dual-Spatial Data Organization

• DOI: 10.1007/s41064-019-00067-y
• Publication Date: 2019-05-09T21:15:49Z
• Authors: Niantao Liu; Bingxian Lin; Guonian Lv; A-Xing Zhu; Liangchen Zhou
• Keywords: 0202 electrical engineering, electronic engineering, information engineering; 02 engineering and technology

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.