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

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

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

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.