vc毕业论文delaunay算法的实现与应用

《vc毕业论文delaunay算法的实现与应用》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、Delaunay算法的实现与应用Delaunay算法的实现与应用摘要数字地形模型是针对地形地貌的一种数字建模,这种建模的结果通常就是一个数字高程模型（DEM）。不规则三角网（TIN）模型是DEM中存储和表示非规则数据的理想模型，它既减少规则网格方法造成的数据冗余，同时在计算效率方面又优于纯粹基于等高线的方法，所以寻求一种好的TIN算法更能快速逼真的显示与模拟出地貌三维信息。在所有可能的三角网中，狄洛尼（Delaunay）三角网在地形拟合方面表现最为出色，因此常常用于TIN的生成。依据Delaunay三角剖分准则，直接以边为基础向一侧推进,而不是以凸包为基础向内推进,从而极大地提高了Dela

2、unay三角网推进的速度。仿真实验表明，改进后的算法效率有了显著的提高。关键词：数字地形模型；数字高程模型；不规则三角网；Delaunay三角网第19页共19页DelaunayTriangulationAlgorithmRealization&ApplicationAbstractDigitalElevationModel(DEM)isadigitalmodelingprocesswhichaimsatterrainandphysiognomy.IrregulartriangulationTINisthebestmodelwhenDEMdataarestoredandexpressed.B

3、esidesreducingtheredundancyofthedatacausedbyregularrastermodel,italsopresentsthemethodpurelybasedoncontourlinesincalculateefficiency.Soawelldevelopedarithmeticcanshowandsimulated3-Dimensioninformationofterrainandgeomorphologymorequicklyandvividly.Amongalltheavailableones,Dlaunaytriangulationistheb

4、esttosimulatetheterrain.AndsoitisusedtocreateTINusually.Accordingtotheanalyserule,theedgeswereusedasthebasewhengoingforward,otherthanVononoifigureasthebase.Consequently,thespeedofconstructingDelaunaytrianglewasgreatlyimproved.Theresultofsimulatingshowsthattheefficiencyofmendedalgorithmisevidentlye

5、nhanced.Keywords:DigitalElevationModel；DigitalTerrainModel；TriangulatedIrregularNetwork；TriangulatedDelaunayNetwork第19页共19页目录论文总页数：19页1引言11.1课题背景11.2国内外研究现状11.3本课题研究的意义11.4本课题的研究方法22DELAUNAY方法的基本原理22.1Voronoi图与Delaunay三角网的基本概念22.2Delaunay的重要性质32.3传统Delaunay生成步骤33三角剖分改进法43.1算法基本流程43.2Graham扫描法求凸包53

6、.3详细算法描述53.4程序运行结果74SUPER三角改进算法84.1算法基本流程84.2Super三角形的生成94.3详细算法描述94.4程序运行结果104.5面向对象计算机的实现114.6测试结果与算法分析125DELAUNAY算法的应用135.1插值基本原理135.2笔者源程序145.3基于网格插值的等值线生成15结论16参考文献16致谢18声明19第19页共19页1引言1.1课题背景三角网格化问题可以追朔到1907年,G.Voronoi首先提出了此问题.后来Delaunay在1932年首次提出了解决这一问题的方法.近年来,平面任意点集的三角网格化(triangulation)问题一

7、直是人们密切关注的问题.真三维的地理信息系统的实现仍然存在诸多尚未解决的技术难题。首先，空间三维数据的采集，其成本相当昂贵；其次，空间数据量大，种类多，结构复杂；第三，三维空间的点、线、面和体之间的拓扑关系复杂，技术尚不成熟；第四，空间分析困难。因此，在地理信息的三维可视化（特别是地形三维可视化）的研究中，通常采用2.5维的GIS可视化的方法来实现地理信息的三维可视化。而该方法主要又是以高质量的数字高程模型（DEM）和高