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

• 作者: 刘建新 卢新明 岳昊
• 来源期刊: 计算机技术与发展
• 学科: 工学
• 关键词: 多边形 三角形权值 Delaunay三角剖分 时间复杂度 计算几何
• 年，卷（期）: 2006,（7）
• 所属期刊栏目: 智能、算法、软件工程
• 页码范围: 126-128,185
• 页数: 4页
• 分类号: O18|TP301.6
• 字数: 3121字
• 语种: 中文
• DOI: 10.3969/j.issn.1673-629X.2006.07.044

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	刘建新	山东科技大学信息科学与工程学院	9	69	5.0	8.0
2	卢新明	山东科技大学信息科学与工程学院	26	385	11.0	19.0
3	岳昊	山东科技大学信息科学与工程学院	9	57	5.0	7.0