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

被引：20

作者：

陈明晶 ^{[1
]}

方源敏 ^{[1
]}

李国柱 ^{[2
]}

陈杰 ^{[1
]}

机构：

[1] 昆明理工大学国土资源工程学院

[2] 昆明市测绘研究院

来源：

昆明理工大学学报(自然科学版) | 2016年 / 41卷 / 05期

关键词：

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

D O I：

10.16112/j.cnki.53-1223/n.2016.05.006

中图分类号：

TP301.6 [算法理论];

学科分类号：

080201 [机械制造及其自动化];

摘要：

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

引用

页码：33 / 38

页数：6

共 18 条

[1]

一种Delaunay三角剖分的改进算法 [J].