一种Delaunay三角网的改进生成算法

摘要：

Delaunay三角网在地理信息系统等领域有着广泛的应用,通常被用于生成不规则三角网(Triangular Irregular Network,TIN)模型,并被用于描述地表的形态.基于传统的逐点插入法,提出一种改进的Delaunay三角网生成算法,通过合理的数据结构与拓扑关系,建立新生成的三角形之间以及点插入前后三角形之间的联系,优化三角形定位过程.首先通过点集凸包生成若干个初始三角形,然后依次插入各点,新点的三角形定位从前一插入点所在的三角形开始,可大幅缩短三角形定位过程的搜索路径,快速定位到新点所在的三角形,当所有点均插入后,最后对整个三角网进行局部优化.实践表明了该算法的高效性和稳定性.

关键词：Delaunay三角网、不规则三角网、逐点插入法、三角形定位、局部优化

所属期刊栏目：41

分类号：P208(一般性问题)

资助基金：国家自然科学基金41161071.

在线出版日期：2016-11-18（万方平台首次上网日期，不代表论文的发表时间）

页码：33-38