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

西安科技大学 计算机科学与技术学院,陕西 西安 710054

Delaunay三角剖分; 混合算法; 加密; 断层约束

Mixed algorithm of delaunay triangular subdivision with fault constraint
ZHANG Qun-hui,XIE Zi-yi

(College of Computer Science and Technology,Xi'an University of Science and Technology,Xi'an 710054,China)

delaunay triangular subdivision; mixed algorithm; encrypt; fault constraint

备注

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

Triangulation is the basis of building a high-precision digital elevation model(DEM). It has been widely applied in various fields. Especially, triangulation in constrained data under the domain Delaunay has more significant research value. Many scholars have done a great job, and put forward a series of classic triangulation algorithms. After researching and analyzing the traditional algorithms, the advantages and disadvantages of traditional algorithms are summed up. Combined with incremental insertion algorithm, triangulation growth algorithm as well as the ideological divide and conquer algorithm, a highly efficient mixed algorithm of Delaunay triangular subdivision with fault constraint is presented. On the basis of establishing unconstrained Delaunay triangulation(DT), this mixed algorithm generates constrained Delaunay triangulation(CDT)by embedding the encrypted fault data. It is illustrated with experiment that this mixed algorithm is better than the traditional algorithms in network quality and time efficiency.