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

摘要

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