|
|
Delaunay算法的实现与应用
摘 要
数字地形模型是针对地形地貌的一种数字建模,这种建模的结果通常就是一个数字高程模型（DEM）。不规则三角网（TIN）模型是DEM中存储和表示非规则数据的理想模型，它既减少规则网格方法造成的数据冗余，同时在计算效率方面又优于纯粹基于等高线的方法，所以寻求一种好的TIN算法更能快速逼真的显示与模拟出地貌三维信息。在所有可能的三角网中，狄洛尼（Delaunay）三角网在地形拟合方面表现最为出色，因此常常用于TIN的生成。依据Delaunay三角剖分准则，直接以边为基础向一侧推进,而不是以凸包为基础向内推进,从而极大地提高了Delaunay三角网推进的速度。仿真实验表明，改进后的算法效率有了显著的提高。
关键词：数字地形模型；数字高程模型；不规则三角网；Delaunay三角网
Delaunay Triangulation Algorithm Realization & Application
Abstract
Digital Elevation Model(DEM) is a digital modeling process which aims at terrain and physiognomy. Irregular triangulation TIN is the best model when DEM data are stored and expressed. Besides reducing the redundancy of the data caused by regular raster model, it also presents the method purely based on contour lines in calculate efficiency. So a well developed arithmetic can show and simulated 3-Dimension information of terrain and geomorphology more quickly and vividly. Among all the available ones, Dlaunay triangulation is the best to simulate the terrain. And so it is used to create TIN usually. According to the analyse rule, the edges were used as the base when going forward ,other than Vononoi figure as the base. Consequently, the speed of constructing Delaunay triangle was greatly improved . The result of simulating shows that the efficiency of mended algorithm is evidently enhanced.http://www.16sheji8.cn/
Key words: Digital Elevation Model；Digital Terrain Model；Triangulated Irregular Network；Triangulated Delaunay Network
目 录
论文总页数：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 程序运行结果 7http://www.16sheji8.cn/
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）是一种表示数字高程模型的方法，它既减少规则网格方法造成的数据冗余，同时在计算效率方面又优于纯粹基于等高线的方法。
