Delaunay三角网剖分中的约束边嵌入算法  

Algorithm of Inserting Constrained Edge into Delaunay Triangulation

作　　者：陈学工[1] 黄晶晶[1] 

机构地区：[1]中南大学信息科学与工程学院,长沙410083

出　　处：《计算机工程》2007年第16期56-58,共3页Computer Engineering

基　　金：国家"863"计划基金资助项目(2002AA135160)

摘　　要：约束边嵌入是解决D-三角网转变为CD-三角网的一种非常有效的方法,而CD-三角网才能真实地虚拟地形地貌。该文研究了约束边嵌入D-三角网的问题,介绍了约束边嵌入算法的一些基本概念,分析了现存算法的特点,提出了改进的约束边嵌入算法——"插入-交换"算法。该算法能有效地处理各种特殊情况,程序实现简单,符合工程需求。This paper focuses on the problem of inserting constrained edge into D-triangulation. It is a very effective method of changing D-triangulation into CD-triangulation that constrained edge is inserted into D-triangulation, and only CD-triangulation can present real terrain and relief. It introduces some basic conceptions about the algorithm of inserting constrained edge, analyses present algorithms＇ characteristics and presents a better algorithm of inserting constrained edge ＂inserting-swapping＂ algorithm. The algorithm can effectively deal with all kinds of instances, and can be implemented by programs easily, and can accord with requirements of the project.

关 键 词：约束边 DELAUNAY三角剖分 对角线 

分 类 号：TP391.9[自动化与计算机技术—计算机应用技术]