带断层约束的Delaunay三角剖分混合算法

摘要

三角剖分是构建高精度数字高程模型(DEM)的基础,在各个领域都有广泛的应用.特别是在约束数据域下的Delaunay三角剖分更具有重大的研究价值,前人已经做了大量的工作,并提出了一系列经典的剖分算法.在对传统算法进行研究与分析后,总结了传统算法的优缺点,结合了逐点插入法、三角网生长法以及分治法的思想,提出了一种高效的、带断层约束的Delaunay三角剖分混合算法.该算法在建立无约束的DT(Delaunay Triangulation,DT)网格的基础上通过嵌入加密后的断层数据来实现带断层约束的CDT(Constrained Delaunay Triangulation,CDT)网格.通过实例比较,说明了混合算法在构网质量和时间效率上都优于传统算法.