改进的构建约束Delaunay三角网的算法  

Improved Algorithm for the Construction of Constrained Delaunay Triangulation

作　　者：颜林[1] 朱永杰[2] 

机构地区：[1]北京化工大学,北京100029 [2]许昌学院,许昌461100

出　　处：《北京石油化工学院学报》2010年第2期41-44,共4页Journal of Beijing Institute of Petrochemical Technology

基　　金：北京市教委科技发展计划资助项目

摘　　要：当前构建约束Delaunay三角网的算法在影响域为凹多边形的情况下不是很稳定,甚至失效。在介绍了Delaunay三角网的相关的概念和算法基础上,重点研究了约束Delaunay三角网生成算法以及影响域为凹多边形的相关问题,提出基于对角线交换的改进算法。实验表明,该算法能够解决影响域为凹多边形等的各种特殊情况,程序稳定简单,易实现。The current algorithm for constructing constrained Delaunay triangulation is not stable or even fails for the case that the influence domain is concave polygon, In this paper some related conceptions and algorithms are introduced first, and then we focuse on the generation algorithm for constrained Delaunay triangulation and some related issues when influence domain is concave polygon. An improved algorithm based on diagonal exchange is presented. The experiments show that the improved algorithm can be used to solve the problem with concave-polygon influence domain and other special circumstances, and can be implemented by programming easily.

关 键 词：DELAUNAY三角网 约束边 对角线 凹多边形 

分 类 号：TP312[自动化与计算机技术—计算机软件与理论]