文档介绍：源程序代码等全套设计联系QQ 695132052 各专业都有
分类号: U D C:D10621-408-(2007)5855-0
密级:公开编号:2003031303
成都信息工程学院
学位论文
Delaunay算法的实现与应用
论文作者姓名:
刘明瓒
申请学位专业:
计算机科学与技术
申请学位类别:
工学学士
指导教师姓名(职称):
欧晓聪
论文提交日期:
2007年06月10日
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.
Key words: Digital Elevation Model;Digital Terrain Model;Triangulated work;Triangulated work
目录
论文总页数:19页
1 引言 1
课题背景 1
国内外研究现状 1
本课题研究的意义 1
本课题的研究方法 2
2 DELAUNAY方法的基本原理 2
Voronoi图与Delaunay三角网的基本概念 2
Delaunay的重要性质 3
传统Delaunay生成步骤 3
3 三角剖分改进法 4
算法基本流程 4
Graham扫描法求凸包 5
详细算法描述 5
程序运行结果 7
4 SUPER三角改进算法 8
算法基本流程 8
Super三角形的生成 9
详细算法描述 9
程序运行结果 10
面向对象计算机的实现 11
4