Delaunay算法的實現(xiàn)與應(yīng)用畢業(yè)設(shè)計畢業(yè)論文

摘  要
數(shù)字地形模型是針對地形地貌的一種數(shù)字建模,這種建模的結(jié)果通常就是一個數(shù)字高程模型（DEM）。不規(guī)則三角網(wǎng)（TIN）模型是DEM中存儲和表示非規(guī)則數(shù)據(jù)的理想模型，它既減少規(guī)則網(wǎng)格方法造成的數(shù)據(jù)冗余，同時在計算效率方面又優(yōu)于純粹基于等高線的方法，所以尋求一種好的TIN算法更能快速逼真的顯示與模擬出地貌三維信息。在所有可能的三角網(wǎng)中，狄洛尼（Delaunay）三角網(wǎng)在地形擬合方面表現(xiàn)最為出色，因此常常用于TIN的生成。依據(jù)Delaunay三角剖分準則，直接以邊為基礎(chǔ)向一側(cè)推進,而不是以凸包為基礎(chǔ)向內(nèi)推進,從而極大地提高了Delaunay三角網(wǎng)推進的速度。仿真實驗表明，改進后的算法效率有了顯著的提高。

關(guān)鍵詞：數(shù)字地形模型；數(shù)字高程模型；不規(guī)則三角網(wǎng)；Delaunay三角網(wǎng)

 
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
 
目  錄
論文總頁數(shù)：19頁
1 引言 1
1.1 課題背景 1
1.2 國內(nèi)外研究現(xiàn)狀 1
1.3 本課題研究的意義 1
1.4 本課題的研究方法 2
2 DELAUNAY方法的基本原理 2
2.1 VORONOI圖與DELAUNAY三角網(wǎng)的基本概念 2
2.2 DELAUNAY的重要性質(zhì) 3
2.3 傳統(tǒng)DELAUNAY生成步驟 3
3 三角剖分改進法 4
3.1 算法基本流程 4
3.2 GRAHAM掃描法求凸包 5
3.3 詳細算法描述 5
3.4 程序運行結(jié)果 7
4 SUPER三角改進算法 8
4.1 算法基本流程 8
4.2 SUPER三角形的生成 9
4.3 詳細算法描述 9
4.4 程序運行結(jié)果 10
4.5 面向?qū)ο笥嬎銠C的實現(xiàn) 11
4.6 測試結(jié)果與算法分析 12
5 DELAUNAY算法的應(yīng)用 13
5.1 插值基本原理 13
5.2 筆者源程序 14
5.3 基于網(wǎng)格插值的等值線生成 15