Delaunay算法的实现与应用

分类号：TP311.1UDC：D10621-408-(2007)5855-0密级：公开编号：2003031303成都信息工程学院学位论文Delaunay算法的实现与应用论文作者姓名：申请学位专业：计算机科学与技术申请学位类别：工学学士指导教师姓名（职称）：论文提交日期：Delaunay算法的实现与应用摘要数字地形模型是针对地形地貌的一种数字建模,这种建模的结果通常就是一个数字高程模型（DEM）。不规则三角网（TIN）模型是DEM中存储和表示非规则数据的理想模型，它既减少规则网格方法造成的数据冗余，同时在计算效率方面又优于纯粹基于等高线的方法，所以寻求一种好的TIN算法更能快速逼真的显示与模拟出地貌三维信息。在所有可能的三角网中，狄洛尼（Delaunay）三角网在地形拟合方面表现最为出色，因此常常用于TIN的生成。依据Delaunay三角剖分准则，直接以边为基础向一侧推进,而不是以凸包为基础向内推进,从而极大地提高了Delaunay三角网推进的速度。仿真实验表明，改进后的算法效率有了显著的提高。关键词：数字地形模型；数字高程模型；不规则三角网；Delaunay三角网DelaunayTriangulationAlgorithmRealization&ApplicationAbstractDigitalElevationModel(DEM)isadigitalmodelingprocesswhichaimsatterrainandphysiognomy.IrregulartriangulationTINisthebestmodelwhenDEMdataarestoredandexpressed.Besidesreducingtheredundancyofthedatacausedbyregularrastermodel,italsopresentsthemethodpurelybasedoncontourlinesincalculateefficiency.Soawelldevelopedarithmeticcanshowandsimulated3-Dimensioninformationofterrainandgeomorphologymorequicklyandvividly.Amongalltheavailableones,Dlaunaytriangulationisthebesttosimulatetheterrain.AndsoitisusedtocreateTINusually.Accordingtotheanalyserule,theedgeswereusedasthebasewhengoingforward,otherthanVononoifigureasthebase.Consequently,thespeedofconstructingDelaunaytrianglewasgreatlyimproved.Theresultofsimulatingshowsthattheefficiencyofmendedalgorithmisevidentlyenhanced.Keywords:DigitalElevationModel；DigitalTerrainModel；TriangulatedIrregularNetwork；TriangulatedDelaunayNetwork目录论文总页数：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.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声明.....................................................................................................