一种快速相容三角剖分算法

• 作者: 刘海涛 叶修梓 张三元
• 来源期刊: 计算机应用研究
• 关键词: 相容三角剖分 多边形分解 计算几何
• 年，卷（期）: 2007,（1）
• 所属期刊栏目: 图形图像
• 页码范围: 235-237
• 页数: 3页
• 分类号: TP391
• 语种: 中文
• DOI: 10.3969/j.issn.1001-3695.2007.01.075

摘要

提出了一种基于凹多边形凸分解的相容三角剖分方法.先将凹边形分解成凸多边形,再对子多边形进行三角剖分,即可实现相容三角剖分.在最坏的情况下添加O(jk)个辅助点,时间复杂度为O(jn+n log n+jk log n)