一种基于边指针搜索及区域划分的三角剖分算法

• 作者: 张俊 田慧敏
• 来源期刊: 自动化学报
• 关键词: Delaunay三角剖分 三维重建 边指针 区域划分
• 年，卷（期）: 2021,（1）
• 所属期刊栏目: 论文与报告
• 页码范围: 100-107
• 页数: 8页
• 语种: 中文
• DOI: 10.16383/j.aas.c190155

摘要

针对大规模数据处理时Delaunay三角剖分过于耗时的问题,本文提出了一种基于边指针搜索及区域划分的三角剖分算法.基于边指针设计了一种能够反映三角形之间位置关系的数据结构,并优化了目标三角形的搜索路径.基于该数据结构,利用区域划分进一步降低目标三角形的搜索深度.超级三角形所在的正方形被划分成具有相同尺寸的区域,目标三角形的搜索从插入点所在的区域的入口三角形开始,这大大缩小了目标三角形的搜索范围.实验证明,与传统的Delaunay三角剖分算法相比,该算法的效率显著提升.