平面散乱点集约束Delaunay三角形剖分切割算法

文章提出了一种基于切割的平面散乱点集约束Delaunay三角剖分算法。该算法的基本思路是首先对平面散乱点集作约束最大空圆凸多边形剖分，然后对多边形的内部再作约束Delaunay三角形剖分。文章还证明了平面散乱点集的约束最大空圆凸多边形剖分是唯一的以及约束Delaunay三角剖分的不唯一性仅仅体现在约束最大空圆凸多边形的内部。使用约束最大空圆凸多边形的概念消除了由于“退化”现象（三个以上的点共圆）带来的算法上的潜在错误。

Constrained Delaunay Triangulation Cutting Algorithm on A Set of Irregularly Located Planar Points

： A constrained Delaunay triangulation cutting algorithm is proposed for computing the triangulated irrgular network of a set of irregularly located planar points．The algorithm is designed to create a constrained maximum empty－circle convex polygon network firstly，then constrained Delaunay triangulation inside these polygons is followed．It is demonstrated in this paper that the constrained maximum empty－circle convex polygon network of a set of planar points is unique，and the ambiguty of constrained Delaunay triangulation exists only in the inside of the polygons．The introduction of constrained maximum empty－circle convex polygon successfully solves the degeneracy problem．