A PARALLELED DELAUNAY TRIANGULATION ALGORITHM FOR PROCESSING LARGE LIDAR POINTS

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.