摘要： 约束边嵌入是解决D-三角网转变为CD-三角网的一种非常有效的方法，而CD-三角网才能真实地虚拟地形地貌。该文研究了约束边嵌入D-三角网的问题，介绍了约束边嵌入算法的一些基本概念，分析了现存算法的特点，提出了改进的约束边嵌入算法——“插入－交换”算法。该算法能有效地处理各种特殊情况，程序实现简单，符合工程需求。
关键词:
约束边,
Delaunay三角剖分,
对角线
Abstract: 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.
Key words:
constrained edge,
Delaunay triangulation,
diagonal
中图分类号:
陈学工;黄晶晶. Delaunay三角网剖分中的约束边嵌入算法[J]. 计算机工程, 2007, 33(16): 56-58.
CHEN Xue-gong ; HUANG Jing-jing. Algorithm of Inserting Constrained Edge into Delaunay Triangulation
[J]. Computer Engineering, 2007, 33(16): 56-58.