简单多边形快速Delaunay三角剖分算法

摘要

简单多边形的Delaunay三角剖分,在计算机图形学及地学问题三维建模领域有着广泛的应用.文中在借鉴他人的基础上,提出了一种时间复杂度为O(mn)的基于三角形权值最大的简单多边形Delaunay 三角剖分算法.三角剖分结果中的三角形形态达到了最优或次优,并进行了理论上的严格证明,对算法的时间复杂度进行了分析,并给出了一个实例.实验结果表明,该方法对于随机生成的简单多边形域三角化速度快,平均计算时间呈近似线性.