A Cutting Block Algorithm for Constructing Delaunay Triangulation Based on Streaming Computation

In order to solve the difficulty that the existing algorithms can't give attention to both the capability of time and space when constructing Delaunay triangulation with massive LiDAR points cloud, a cutting block Delaunay triangulation algorithm using streaming computation is presented. DeWall (Delaunay wall) is constructed firstly to cut an independent point cloud data block with specific size and shape, which is suitable for the divide-and-conquer algorithm and can avoid deep recursion and memory overflow. Then the cutting block is triangulated with a divide-and-conquer algorithm, and an algorithm is proposed to delete the wrong triangles on the boundary of the cutting block triangulation. The process described above is repeated to construct all the sub-triangulations, which can be merged directly according to the property of the decoupled domain decomposition mode finally. Meanwhile, the streaming computation is introduced so that the algorithm has a more excellent capability of space. The analysis and experiments show that the algorithm has a low memory footprint and is efficient with a time complexity close to O(nlg(δ))(δ is the number of points in a cutting block and δ ≤ n).