Delaunay三角化中特征约束细分嵌入算法 (2009年)

在Delaunay三角化中，以在特征约束上插入附加点的方式对特征约束细分，可使剖分网格在表达特征约束的同时仍满足Delaunay三角网格特性。本文提出了一种改进的细分嵌入算法——端点外接圆法(ETCM)，该算法具有线性时间复杂度。以剖分结果的稳定性、附加点个数、运算耗时和网格质量为评价标准，对ETCM和现有的细分嵌入算法进行了评估。实验结果表明，在运算耗时方面，ETCM受数据分布的影响最小，且耗时最少；在其他方面，与现有算法的最好表现持平。