摘 要
数字地形模型是针对地形地貌的一种数字建模,这种建模的结果通常就是一个数字高程模型（DEM）。不规则三角网（TIN）模型是DEM中存储和表示非规则数据的理想模型，它既减少规则网格方法造成的数据冗余，同时在计算效率方面又优于纯粹基于等高线的方法，所以寻求一种好的TIN算法更能快速逼真的显示与模拟出地貌三维信息。在所有可能的三角网中，狄洛尼（Delaunay）三角网在地形拟合方面表现最为出色，因此常常用于TIN的生成。依据Delaunay三角剖分准则，直接以边为基础向一侧推进,而不是以凸包为基础向内推进,从而极大地提高了Delaunay三角网推进的速度。仿真实验表明，改进后的算法效率有了显著的提高。

关键词：数字地形模型；数字高程模型；不规则三角网；Delaunay三角网
 

目 录
论文总页数：19页
1 引言 1
1.1 课题背景 1
1.2 国内外研究现状 1
1.3 本课题研究的意义 1
1.4 本课题的研究方法 2
2 DELAUNAY方法的基本原理 2
2.1 VORONOI图与DELAUNAY三角网的基本概念 2
2.2 DELAUNAY的重要性质 3
2.3 传统DELAUNAY生成步骤 3
3 三角剖分改进法 4
3.1 算法基本流程 4
3.2 GRAHAM扫描法求凸包 5
3.3 详细算法描述 5
3.4 程序运行结果 7
4 SUPER三角改进算法 8
4.1 算法基本流程 8
4.2 SUPER三角形的生成 9
4.3 详细算法描述 9
4.4 程序运行结果 10
4.5 面向对象计算机的实现 11
4.6 测试结果与算法分析 12
5 DELAUNAY算法的应用 13
5.1 插值基本原理 13
5.2 笔者源程序 14
5.3 基于网格插值的等值线生成 15
结 论 16
参考文献 16
致 谢 18
声 明 19

1 引言
1.1 课题背景
三角网格化问题可以追朔到1907年,G.Voronoi首先提出了此问题.后来Delaunay在1932年首次提出了解决这一问题的方法.近年来,平面任意点集的三角网格化(triangulation)问题一直是人们密切关注的问题.真三维的地理信息系统的实现仍然存在诸多尚未解决的技术难题。首先，空间三维数据的采集，其成本相当昂贵；其次，空间数据量大，种类多，结构复杂；第三，三维空间的点、线、面和体之间的拓扑关系复杂，技术尚不成熟；第四，空间分析困难。因此，在地理信息的三维可视化（特别是地形三维可视化）的研究中，通常采用2.5维的GIS可视化的方法来实现地理信息的三维可视化。而该方法主要又是以高质量的数字高程模型（DEM）和高逼真度的三维显示技术为基础，其中DEM的质量，对地形三维可视化的效果有着不容忽视的影响；而影响DTM质量的关键是生成DEM的算法。所以，采用一种实用性高、精度较高、生成速度快、使用方便的DEM的生成算法十分必要。不规则三角网（TIN-Triangulated Irregular Network）是一种表示数字高程模型的方法，它既减少规则网格方法造成的数据冗余，同时在计算效率方面又优于纯粹基于等高线的方法。