ISPRS Annals of the Photogrammetry, Remote Sensing and Spatial Information Sciences
Download
Publications Copernicus
Download
Citation
Articles | Volume X-3/W1-2022
https://doi.org/10.5194/isprs-annals-X-3-W1-2022-141-2022
https://doi.org/10.5194/isprs-annals-X-3-W1-2022-141-2022
27 Oct 2022
 | 27 Oct 2022

A PARALLELED DELAUNAY TRIANGULATION ALGORITHM FOR PROCESSING LARGE LIDAR POINTS

Y. Song, M. Li, and X. Liu

Keywords: Paralleled Delaunay Triangular Network, LiDAR, Point Cloud, MapReduce, Multi-core Computer

Abstract. LiDAR is an important data source for disaster prevention and mitigation, its advantages include speediness, penetration, initiative, high-density and high-precision, high efficiency, information-richness. In this paper, we address the design and implementation of a practical parallel algorithm for Delaunay triangulation that works on massive point cloud data acquired by airborne LiDAR. The algorithm is based on the divide and conquer algorithm, Bowyer-Watson algorithm and triangulation-growth and can be easily extended to multi-core or cluster environment. It first divides the point cloud data into blocks at the MapReduce’s Map phase; then the triangulation network of each block is simultaneously constructed using Bowyer-Watson algorithm on different CPU cores; at the reduction phase, the triangular network of each block is merged and optimized using triangulation-growth and Local Optimization Procedure (LOP). Experimental results show that the speed of the paralleled triangulation algorithm can be improved significantly compared to the sequential algorithm on multi-core desktop computer. The speedup depends on partition of the dataset and the number of CPU cores used, and is usually 2–3 times that of sequential algorithms.