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

来源期刊：昆明理工大学学报(自然科学版)2016年第5期

论文作者：陈明晶 方源敏 李国柱 陈杰

文章页码：33 - 38

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

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