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

关键词：数字地形模型；数字高程模型；不规则三角网；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.http://www.16sheji8.cn/

Key words: Digital Elevation Model；Digital Terrain Model；Triangulated Irregular Network；Triangulated Delaunay Network
 
目  录
论文总页数：19页
1 引言 1
1.1 课题背景 1
1.2 国内外研究现状 1
1.3 本课题研究的意义 1
1.4 本课题的研究方法 2
2 DELAUNAY方法的基本原理 2
2.1 VORONOI图与DELAUNAY三角网的基本概念 2
2.2 DELAUNAY的重要性质 3
2.3 传统DELAUNAY生成步骤 3
3 三角剖分改进法 4
3.1 算法基本流程 4http://www.16sheji8.cn/
3.2 GRAHAM扫描法求凸包 5
3.3 详细算法描述 5
3.4 程序运行结果 7
4 SUPER三角改进算法 8
4.1 算法基本流程 8
4.2 SUPER三角形的生成 9
4.3 详细算法描述 9
4.4 程序运行结果 10
4.5 面向对象计算机的实现 11
4.6 测试结果与算法分析 12
5 DELAUNAY算法的应用 13
5.1 插值基本原理 13
5.2 笔者源程序 14
5.3 基于网格插值的等值线生成 15
结    论 16
参考文献 16
致    谢 18
声    明 19http://www.16sheji8.cn/
 
1 引言
  1.1 课题背景
    三角网格化问题可以追朔到1907年,G.Voronoi首先提出了此问题.后来Delaunay在1932年首次提出了解决这一问题的方法.近年来,平面任意点集的三角网格化(triangulation)问题一直是人们密切关注的问题.真三维的地理信息系统的实现仍然存在诸多尚未解决的技术难题。首先，空间三维数据的采集，其成本相当昂贵；其次，空间数据量大，种类多，结构复杂；第三，三维空间的点、线、面和体之间的拓扑关系复杂，技术尚不成熟；第四，空间分析困难。因此，在地理信息的三维可视化（特别是地形三维可视化）的研究中，通常采用2.5维的GIS可视化的方法来实现地理信息的三维可视化。而该方法主要又是以高质量的数字高程模型（DEM）和高逼真度的三维显示技术为基础，其中DEM的质量，对地形三维可视化的效果有着不容忽视的影响；而影响DTM质量的关键是生成DEM的算法。所以，采用一种实用性高、精度较高、生成速度快、使用方便的DEM的生成算法十分必要。不规则三角网（TIN-Triangulated Irregular Network）是一种表示数字高程模型的方法，它既减少规则网格方法造成的数据冗余，同时在计算效率方面又优于纯粹基于等高线的方法。http://www.16sheji8.cn/
  1.2 国内外研究现状
    自1934年,俄国数学家Delaunay提出三角形最小内角最大的三角化准则,并证明在四点或四点以上共圆条件下的平面散乱点存在的三角化方式后,近年来,有很多学者都致力于三角化理论及各种应用的研究, 比如: Lawson等人提出三角化的最大角最小化原则,使得三角化局部更为均匀。Amenta等人提出的外壳(C rust)算法即基于计算几何中voronoi图和Delaunay三角化的全新的曲面重建算法。Hoppe提出的累进网格 ProgressiveMesh简称PM)表示方法,率先讨论了多分辨率流形三角网格累进传输问题。Aumann用三角网格近似给定的曲面，把三角网格的面积作为原曲面的近似，进而给出了斜直纹曲面近似保面积展开的一个简单算法。Azevedo针对Delaunay三角网的特点,提出的使三角网最大外接圆最小的优化方法,Rajan则将这种方法应用到了三维空间。国内方面，周培德教授提出的最小权三角划分方法(三角网格划分中各三角形边的权值之和为最小值的方法)对三角网格进行了优化等等。由此可见，目前国际上关于三角化问题及其应用的研究很多,而国内这方面研究还为数不多,因此开展这方面的研究很有必要。http://www.16sheji8.cn/
  1.3 本课题研究的意义
    三角网格化问题在许多领域有广泛应用.例如,在有限元分析中,它是有限元网格生成的有效方法之一;在计算机辅助几何设计中,它可以简化几何模型和实体模型的数据结构及内部表示;在计算机图形显示中,它可以加速光线跟踪算法和光照模型的处理以及图形图像插值应用;在地理学中,它可以快速的生成地理模型。Delaunay三角剖分甚至在无线Ad Hoc通信网络中，可以用于构建发现移动节点间通信路径的在线路由算法。目前，在计算流体力学、统计学、气象学、固体物理学、计算几何学、图形图像学、三维仿真等多个邻域，都能见到它的踪影。我们可以举一些简单的应用：近年来，随着网上购物越来越走入人们的生活，我们可以把某些商品建成可视又可“触”的模型，人们在选购的时候不仅可以看到商品的样子，还可以通过鼠标和键盘对商品模型进行各种操作，查看它的弹性、柔软度等性质，从而用更直观、更便捷的方法来了解商品的性能，而不是对着大篇幅的数字指标发呆。又如，我们可以建立仿真的地理模型，来做大量的地震、暴雨 等的灾难模拟实验，为灾难预测提供理论依据，从而节省大量开支。所以，我相信三角网格化的研究工作一定有着良好的发展和应用前景。
  1.4 本课题的研究方法http://www.16sheji8.cn/
    三角网格化主要有两种准则:一种称为 Delaunay三角剖分,即在生成的三角形网格中,各三角形的最小内角和为最大;另一种是在生成的三角网格中,所有三角形的边长和最小.其中, Delaunay三角剖分是目前研究应用最广的一种剖分方法.本课题的研究方法主要是以Delaunay三角网的两个重要性质（空外接圆性质和最大最小角度性质）以及Delaunay三角网的基本原理为基础，参照传统算法思路，在构建三角网的过程中，改进算法的实现方法，数据结构，以达到提高效率的目的。http://www.16sheji8.cn/