约束Delaunay三角剖分中强行嵌入约束边的多对角线交换算法

在不允许改变原有点集的场合，实现约束Ｄｅｌａｕｎａｙ 三角剖分的一种有效算法是：将边界点与内点一起进行标准Ｄｅｌａｕｎａｙ 三角剖分，然后强行嵌入不在剖分中的约束边，最后删除域外三角形．其中，任意一条待嵌入约束边所经三角形构成的多边形区域称为该约束边的影响域，影响域内部的每条边称为对角线．文中对一般形状影响域中对角线的可交换性进行了研究，并在此基础上，结合对已有算法的分析和借鉴，提出并证明了两种强行嵌入约束边的多对角线交换算法，即递减算法与循环算法．其中的循环算法具有编程简单和运算速度快的特点

MULTIPLE DIAGONAL EXCHANGING ALGORITHM FOR INSERTING CONSTRAINED BOUNDARY IN CONSTRAINED DELAUNAY TRIANGULATION

When adding points to the original set is not allowed,one of the efficient algorithms for constrained Delaunay triangulation is to calculating the standard Delaunay triangulation of all points first,inserting constrained boundaries into the finished triangulation and,finally,deleting the unwanted triangles out of domain.All the triangles intersecting with a constrained boundary form a polygon called influenced area.The interior boundaries of an influenced area are called diagonals.Based on the exchanging property of the diagonals and the improvement of the existing algorithm,two multiple diagonal exchanging algorithms,for inserting constrained boundary into standard Delaunay triangulation,are proposed and proved in the paper.They are descending algorithm and looping algorithm.The recommended looping algorithm is easier to program yet efficient enough.