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

摘要：

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

关键词：多边形、三角形权值、Delaunay三角剖分、时间复杂度、计算几何

所属期刊栏目：16

分类号：O18;TP301.6(几何、拓扑)

在线出版日期：2006-08-11（万方平台首次上网日期，不代表论文的发表时间）

页数：共4页

页码：126-128,185