论文部分内容阅读
针对海量LiDAR点云Delaunay三角网剖分的时间与空间性能的矛盾问题,提出了一种采用切块的流计算Delaunay构网算法。首先利用三角网墙(DeWall)从点云上切割特定大小与形状的独立数据块,避免分治算法的深度递归与内存溢出;然后运用分治算法对切块剖分,并给出了切块边界错误三角形删除算法;重复上述过程完成子网剖分,并依据非耦合区域分解模式合并为最终三角网。引入流计算的思想,以进一步提高算法的空间性能。分析与实验表明:该算法占用了较低内存,并取得了接近为O(nlg(δ))(δ为一个切块点数,且δ≤n)的时间复杂度。
Aiming at the contradiction between time and space performance of Delaunay triangulation of massive LiDAR point cloud, this paper proposes a Delaunay network construction algorithm using dice flow. First, DeWall is used to cut the independent data blocks of specific size and shape from the point cloud to avoid the deep recursion and memory overflow of the partition algorithm. Then, the partition algorithm is used to divide the data and give the cut Boundary error triangle delete algorithm; repeat the above process to complete the subnetting, and decomposed mode according to the uncoupled region into the final triangular network. The idea of stream computing is introduced to further improve the spatial performance of the algorithm. The analysis and experiments show that this algorithm takes up less memory and achieves a time complexity close to O (nlg (δ)) (δ is a dice point, and δ≤n).