高效构建Delaunay三角网数字地形模型算法研究

Study on Faster Algorithm for Constructing Delaunay Triangulations DTM

在对传统构建Delaunay三角剖分 (尤其是分割 合并 )算法进行分析的基础上 ,采用自适应格网划分方法对点集进行排序、分割 ,并按照逆序合并Delaunay子三角网 ,然后进行约束处理 ,快速、高效地实现了Delaunay三角网的构建 ;对Delaunay子三角网合并、地性线处理、平三角形处理等关键问题进行了描述。实测结果表明 ,该算法的时间复杂度接近于O(n)。

Based on the analysis of common Delaunay triangulations methods,especially the divide-and-conquer method,a faster algorithm for constructing Delaunay triangulations is presented.It divides the point set by self-adaptive grid,constructs and merges the sub-triangulations.The key problems of merging sub-triangulations,dealing with the terrain features and the flat triangles are described.The experiments show that the expected time of the algorithm is O(n).