一种动态构建Delaunay三角网的算法.pdf.pdf

文档介绍：第17卷第3期2008年6月测绘工程ENGINEERINGOFSURVEYINGANDMAPPINGVoL17№.3JuIL,2008种动态构建Delaunay三角网的算法赵岩,张子平(河南理工大学测绘与国土信息工程学院,河南焦作454003)摘要:Delaunay三角剖分算法是构建数字高程模(DEM)的主要算法。在分析现有的Delaunay三角剖分的3种算法之后,指出现有算法存在的不足。并提出一种TIN的动态建模方法,利用分块技术来改进搜索方法,大大提高了Delaunay三角网的构建速度。实验结果表明,此算法和前面3种算法相比,效率有了很大提高。关键词:DEM~Delaunay三角剖分;动态建模;数据分块;中图分类号:P208文献标识码:A文章编号:1006—7949(2008)03—0024—04OnedynamicalgorithmofconstructingDelaunaytriangulationZHAOYan,ZHANGZi~ping(SchoolofSurveyingandLandInformationEngineering,HenanPolytechnicUniversity,Jiaozuo454003,China)Abstract:ThealgorithmofDelaunaytriangulationisthemainalgorithmwhenestablishingDEM。Inthispaper,;:DEM;Delaunaytriangulation;dynamicmodeling;datasetpartition在所有可能的三角网中,狄洛尼(Delaunay)三角网在地形拟合方面表现最为出色,因此,常常被用于TIN的生成,目前,这方面的研究成果十分丰富[1-5~。Lawson在1977年提出了根据最大最小(MAX—MIN)角度法则建立局部几何形状最优的三角网,即在两相邻三角形的凸四边形中,交换此四边形的两条对角线,不会增加这两个三角形内角总和的最小值[6]。Lawson据此提出了局部最优方法LOP(Local,OptimizationProcedure):交换凸四边形的对角线,可获得等角性最好的三角网。如何快速、高效地构建Delaunay三角网,一直是众多学者研究和关注的焦点。Tsai于1994年根据实现过程,把狄洛尼三角剖分分成3类,即三角网生长算法、逐点插入算法和分割合并算法[7]。