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

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

Study on Faster Algorithm for Constructing Delaunay Triangulations DTM

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