限制性Delaunay三角网的剖分算法

An Algorithm for the Constraint Delaunay Triangulation

通过对Delaunay三角剖分的凸壳特点分析 ,通过划分与限制条件相关的点集为左、右两个点集 ,并分别对上述两个点集进行Delaunay三角剖分的方法 。

Based on the analysis to the convex property of Delaunay triangulation, one algorithm for the constraint Delaunay triangulation has been presented in this paper, which includes four main steps as follows: 1) do a standard Delaunay triangulation for the point set; 2) add the constraint edge to the triangulations and dismember the points in the related polygon with the constraint edge to the left and right point sets; 3) do standard Delaunay triangulations for the left and right point sets separately; 4)delete the conflict triangulations. With the four steps above, standards of the Delaunay triangulation can be applied with.