一种采用流计算的Delaunay三角网切块剖分算法

针对海量LiDAR点云Delaunay三角网剖分的时间与空间性能的矛盾问题，提出了一种采用切块的流计算Delaunay构网算法。首先利用三角网墙（DeWall）从点云上切割特定大小与形状的独立数据块，避免分治算法的深度递归与内存溢出；然后运用分治算法对切块剖分，并给出了切块边界错误三角形删除算法；重复上述过程完成子网剖分，并依据非耦合区域分解模式合并为最终三角网。引入流计算的思想，以进一步提高算法的空间性能。分析与实验表明:该算法占用了较低内存，并取得了接近为O（nlg（δ））（δ为一个切块点数，且δ≤n）的时间复杂度。

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).