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

作者：张俊; 田慧敏^*

来源：自动化学报, 2021, 47(01): 100-107.

DOI：10.16383/j.aas.c190155

• Delaunay三角剖分
• 三维重建
• 边指针
• 区域划分

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

• 单位
  中南大学; 自动化学院