Delaunay算法的实现与应用(有源程序代码)（可编辑）.doc

Delaunay算法的实现与应用(有源程序代码) 关键词:数字地形模型;数字高程模型;不规则三角网;Delaunay三角网 Delaunay Triangulation Algorithm Realization Application Abstract Digital Elevation ModelDEM 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 improvedThe 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 目 录 论文总页数:19页 1 引言 5 1.1 课题背景 5 1.2 国内外研究现状 5 1.3 本课题研究的意义 5 1.4 本课题的研究方法 5 2 Delaunay方法的基本原理 5 2.1 Voronoi图与Delaunay三角网的基本概念 5 2.2 Delaunay的重要性质 5 2.3 传统Delaunay生成步骤 5 3 三角剖分改进法 5 3.1 算法基本流程 5 3.2 Graham扫描法求凸包 5 3.3 详细算法描述 5 3.4 程序运行结果 5 4 Super三角改进算法 5 4.1 算法基本流程 5 4.2 Super三角形的生成 5 4.3 详细算法描述 5 4.4 程序运行结果 5 4.5 面向对象计算机的实现 5 4.6 测试结果与算法分析 5 5 Delaunay算法的应用 5 5.1 插值基本原理 5 5.2 笔者源程序 5 5.3 基于网格插值的等值线生成 5 结 论 5 参考文献 5 致 谢 5 声 明 5 引言 课题背景 三角网格化问题可以追朔到1907年,G.Voronoi首先提出了此问题.后来Delaunay在1932年首次提出了解决这一问题的方法.近年来,平面任意点集的三角网格化triangulation问题一直是人们密切关注的问题.真三维的地理信息系统的实现仍然存在诸多尚未解决的技术难题。首先,空间三维数据的采集,其成本相当昂贵;其次,空间数据量大,种类多,结构复杂;第三,三维空间的点、线、面和体之间的拓扑关系复杂,技术尚不成熟;第四,空间分析困难。因此,在地理信息的三维可视化(特别是地形三维可视化)的研究中,通常采用2.5维的GIS可视化的方法来实现地理信息的三维可视化。而该方法主要又是以高质量的数字高程模型(DEM)和高逼真度的三维显示技术为基础,其中DEM的质量,对地形三维可视化的效果有着不容忽视的影响;而影响DTM质量的关键是生成DEM的算法。所以,采用