一种Delaunay三角剖分的改进算法

An Improvement Algorithm for Delaunay Triangulation

Delaunay三角网的构建算法和设计在GIS分析管理及可视化等方面有着重要的作用。本文将逐点插入法和凸包法进行融合,利用Akl-Toussaint启发式函数来剔除原始数据点集中的多余点,以便快速高效地实现凸包的构建,利用角度判别对角线法对生成的初始三角网进行优化,在此基础之上提出生成Delaunay三角网的改进算法。实践表明,该算法对于小量或大量数据集均有较好的适应性,不仅具有与分治算法一致的高效性,还具有易于理解和实现的算法思路。