机载LiDAR点云的Delaunay三角网快速生成算法

为了提高机载激光点云的Delaunay三角网生成效率及稳定性,基于分块算法的思想,改进了点云数据的分块方式,利用点云的凸包及重心点进行数据分块,并结合子块中激光点个数阈值进行三角形子块的细分,从而避免了传统子块合并过程中复杂的相邻三角形搜索及优化处理,仅需简单的一步优化即可完成相邻子块的合并,大大提高了算法的效率。经实验证明,该算法简单、高效且稳定性好,尤其对于大数据量的机载LiDAR点云Delaunay三角网生成具有明显的优势。

An Algorithm for Quick Generation of Delaunay Triangular Net for Airborne LiDAR Point Cloud

In order to improve the efficiency and stability of the Delaunay triangular net generation for the airborne LiDAR point cloud,a new algorithm based on the idea of division-mergence is proposed in the paper.The algorithm improves the method of block division by connecting the convex hull points with the areal center point,and the block is further subdivided when the number of LiDAR points in this block is larger than the quantity threshold.The algorithm needs only one step of LOP optimizing to merge two adjacent blocks without complex adjacent triangles searching which is generally existent in the traditional methods,and the efficiency and stability of the algorithm has been greatly improved.Tested by the experiment,the algorithm is simple,efficient and stable,and has obvious advantages especially for the large amount of data airborne LiDAR points.