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

A Triangulation Algorithm Based on Edge-pointer Search and Region-division

作　　者：张俊[1] 田慧敏 ZHANG Jun;TIAN Hui-Min(School of Automation,Central South University,Chang-sha 410083;School of Computer Science and Engineering,Central South University,Changsha 410083)

机构地区：[1]中南大学自动化学院,长沙410083 [2]中南大学计算机学院,长沙410083

出　　处：《自动化学报》2021年第1期100-107,共8页Acta Automatica Sinica

基　　金：国家自然科学基金(61571466)资助。

摘　　要：针对大规模数据处理时Delaunay三角剖分过于耗时的问题,本文提出了一种基于边指针搜索及区域划分的三角剖分算法.基于边指针设计了一种能够反映三角形之间位置关系的数据结构,并优化了目标三角形的搜索路径.基于该数据结构,利用区域划分进一步降低目标三角形的搜索深度.超级三角形所在的正方形被划分成具有相同尺寸的区域,目标三角形的搜索从插入点所在的区域的入口三角形开始,这大大缩小了目标三角形的搜索范围.实验证明,与传统的Delaunay三角剖分算法相比,该算法的效率显著提升.To solve the problem of taking too much time when dealing with large-scale data,a triangulation algorithm based on edge-pointer search and region-division is proposed.A data structure based on the edge-pointer is designed to reflect the positional relationship between triangles,and the search path of the target triangle is also optimized.Moreover,region-division is utilized to reduce the search depth.The square which contains the super triangle is divided into some regions of the equal size.The search for the target triangle begins with the entry triangle of the region where the insertion point is located.As a result,the search scope of the target triangle is narrowed.Experiment results show that the algorithm is much more efficient than the traditional Delaunay triangulation algorithm.

关 键 词：DELAUNAY 三角剖分 三维重建 边指针 区域划分 

分 类 号：TP391.41[自动化与计算机技术—计算机应用技术]