一种常用的二维任意域的Delaunay三角剖分算法的健壮性补充

摘要

由于对任意给定的平面点集通过Delaunay三角剖分进行处理可得到具有整体最优性的三角形网格,因而该方法得到了广泛的重视.但研究发现,常用的二维任意域Delaunay三角剖分算法[1,2]是有缺陷的,它在构成Delaunay三角形候选点的选择过程中,可以使候选点出现"位置违约"的错误,即在候选节点链表中,虽然可出现依据算法的判据有条件成为Delaunay三角形的构成点,但采用该点构成Delaunay三角形后,将违背Delaunay三角剖分"约束圆准则",这样会导致不正确的剖分结果,因此,该文就这一问题进行了分析和讨论,并给出了可行的改进方案,即通过调整原算法的数据结构或修改原算法的Delaunay三角剖分判据,以提高算法的健壮性,从而得到令人满意的Delaunay三角剖分网格.前一种改进方案主要是重新调整了算法的数据结构,这虽然对算法的健壮性有较大的帮助,但对于已经将算法进行了应用的情形并不合适,因此可以考虑使用后一种改进方案.