Delaunay算法的实现与应用
资料包括： 论文(23页8884字)
说明：
摘 要：数字地形模型是针对地形地貌的一种数字建模,这种建模的结果通常就是一个数字高程模型（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 Irregular Network；Triangulated Delaunay Network
1 引言
1.1 课题背景
三角网格化问题可以追朔到1907年,G.Voronoi首先提出了此问题.后来Delaunay在1932年首次提出了解决这一问题的方法.近年来,平面任意点集的三角网格化(triangulation)问题一直是人们密切关注的问题.真三维的地理信息系统的实现仍然存在诸多尚未解决的技术难题。首先，空间三维数据的采集，其成本相当昂贵；其次，空间数据量大，种类多，结构复杂；第三，三维空间的点、线、面和体之间的拓扑关系复杂，技术尚不成熟；第四，空间分析困难。因此，在地理信息的三维可视化（特别是地形三维可视化）的研究中，通常采用2.5维的GIS可视化的方法来实现地理信息的三维可视化。而该方法主要又是以高质量的数字高程模型（DEM）和高逼真度的三维显示技术为基础，其中DEM的质量，对地形三维可视化的效果有着不容忽视的影响；而影响DTM质量的关键是生成DEM的算法。所以，采用一种实用性高、精度较高、生成速度快、使用方便的DEM的生成算法十分必要。不规则三角网（TIN-Triangulated Irregular Network）是一种表示数字高程模型的方法，它既减少规则网格方法造成的数据冗余，同时在计算效率方面又优于纯粹基于等高线的方法。
1.2 国内外研究现状
自1934年,俄国数学家Delaunay提出三角形最小内角最大的三角化准则,并证明在四点或四点以上共圆条件下的平面散乱点存在的三角化方式后,近年来,有很多学者都致力于三角化理论及各种应用的研究, 比如: Lawson等人提出三角化的最大角最小化原则,使得三角化局部更为均匀。Amenta等人提出的外壳(C rust)算法即基于计算几何中voronoi图和Delaunay三角化的全新的曲面重建算法。Hoppe提出的累进网格 ProgressiveMesh简称PM)表示方法,率先讨论了多分辨率流形三角网格累进传输问题。Aumann用三角网格近似给定的曲面，把三角网格的面积作为原曲面的近似，进而给出了斜直纹曲面近似保面积展开的一个简单算法。Azevedo针对Delaunay三角网的特点,提出的使三角网最大外接圆最小的优化方法,Rajan则将这种方法应用到了三维空间。国内方面，周培德教授提出的最小权三角划分方法(三角网格划分中各三角形边的权值之和为最小值的方法)对三角网格进行了优化等等。由此可见，目前国际上关于三角化问题及其应用的研究很多,而国内这方面研究还为数不多,因此开展这方面的研究很有必要。
1引言1
1.1课题背景1
1.2国内外研究现状1
1.3本课题研究的意义1
1.4本课题的研究方法2
2DELAUNAY方法的基本原理2
2.1VORONOI图与DELAUNAY三角网的基本概念2
2.2DELAUNAY的重要性质3
2.3传统DELAUNAY生成步骤3
3三角剖分改进法4
3.1算法基本流程4
3.2GRAHAM扫描法求凸包5
3.3详细算法描述5
3.4程序运行结果7
4SUPER三角改进算法8
4.1算法基本流程8
4.2SUPER三角形的生成9
4.3详细算法描述9
4.4程序运行结果10
4.5面向对象计算机的实现11
4.6测试结果与算法分析12
5DELAUNAY算法的应用13
5.1插值基本原理13
5.2笔者源程序14
5.3基于网格插值的等值线生成15
结 论16
参考文献16
致 谢18
声 明19
参考文献：
胡金星,马照亭,吴焕萍,潘懋.基于格网划分的海量数据Delaunay三角剖分[J].测绘学报,2004,33(2):163-167。
李志林,朱庆.数字高程模型[M].武汉:武汉大学出版社,2001。
吴立新,史文中.地理信息系统原理与算法[M].北京:科学出版社,2003。
杨杰.基于凹凸顶点判定单多边形的三角剖分[J].小型微型计算机系统,2000,21(9):974-975。
周培德.计算机几何——算法分析与设计[M].清华大学出版社、广西科学技术出版社,2000。
候俊杰.深入浅出WINDOWS MFC程序设计[M].华中理工大学出版社,1998。
杨钦.限定Delaunay三角网格剖分技术[M].电子工业出版社,2005。
邬吉明,沈隆钧,张景琳.Delaunay三角网格的一种快速生成法[J].数值计算与计算机应用,2001(7):267-275。
胡恩球,张新访等.有限元网格生成方法发展综述[J].计算机辅助设计与图形学学报，1997,9(4):378-383。
作者点评：
Delaunay三角剖分是国际三大流行的全自动网格生成方法之一，它的最主要特点之一就是它自动避免了生成小内角的长薄单元。经过几十年不懈的研究，在二维欧氏空间上的Delaunay自动网格生成技术已经趋于完善，理论的完备性和实践的多样化均给这一有限元网格剖分方法以新的活力。时至今日，如何评价一种Delaunay网格剖分程序的优劣，该程序的时间、空间复杂度以及强壮性仍是人们热切关注的话题。同时，针对Delaunay三角网格的不同评价标准，人们仍会有设计出许多新的方法来更好的适应实际的需求。另外，在向三维欧氏空间拓展的形势下，Delaunay三角剖分还有极大的发展空间。
就本设计的以上两种算法示例方法而言仍有许多可以改进的地方，如点集加密技术的讨论、优化方法设计的时间与空间复杂性研究、针对各类实际数据的模拟和剖分状态比较、与其他网格剖分技术的对比研究等等，这里我所给出的仅是一种Delaunay三角剖分的尝试，还有许多后续工作可以继续讨论。总之，Delaunay三角网格自动剖分技术作为一种成熟的有限元网格剖分方法，在实践中有着极其广泛的应用，因此对它的研究也是具有实际价值、意义深远的科研工作。