Delaunay算法的实现与应用

论文字数:8741,页数:23

摘  要
数字地形模型是针对地形地貌的一种数字建模,这种建模的结果通常就是一个数字高程模型（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.

Key words: Digital Elevation Model；Digital Terrain Model；Triangulated Irregular Network；Triangulated Delaunay Network

目  录

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