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

关键词：数字地形模型；数字高程模型；不规则三角网；Delaunay三角网

 
1.3 本课题研究的意义
三角网格化问题在许多领域有广泛应用.例如,在有限元分析中,它是有限元网格生成的有效方法之一;在计算机辅助几何设计中,它可以简化几何模型和实体模型的数据结构及内部表示;在计算机图形显示中,它可以加速光线跟踪算法和光照模型的处理以及图形图像插值应用;在地理学中,它可以快速的生成地理模型。Delaunay三角剖分甚至在无线Ad Hoc通信网络中，可以用于构建发现移动节点间通信路径的在线路由算法。目前，在计算流体力学、统计学、气象学、固体物理学、计算几何学、图形图像学、三维仿真等多个邻域，都能见到它的踪影。我们可以举一些简单的应用：近年来，随着网上购物越来越走入人们的生活，我们可以把某些商品建成可视又可“触”的模型，人们在选购的时候不仅可以看到商品的样子，还可以通过鼠标和键盘对商品模型进行各种操作，查看它的弹性、柔软度等性质，从而用更直观、更便捷的方法来了解商品的性能，而不是对着大篇幅的数字指标发呆。又如，我们可以建立仿真的地理模型，来做大量的地震、暴雨 等的灾难模拟实验，为灾难预测提供理论依据，从而节省大量开支。所以，我相信三角网格化的研究工作一定有着良好的发展和应用前景。
1.4 本课题的研究方法
三角网格化主要有两种准则:一种称为 Delaunay三角剖分,即在生成的三角形网格中,各三角形的最小内角和为最大;另一种是在生成的三角网格中,所有三角形的边长和最小.其中, Delaunay三角剖分是目前研究应用最广的一种剖分方法.本课题的研究方法主要是以Delaunay三角网的两个重要性质（空外接圆性质和最大最小角度性质）以及Delaunay三角网的基本原理为基础，参照传统算法思路，在构建三角网的过程中，改进算法的实现方法，数据结构，以达到提高效率的目的。
2 Delaunay方法的基本原理
2.1 Voronoi图与Delaunay三角网的基本概念
Voronoi图（以下简称V图），又叫泰森多边形或Dirichlet图，它是由一组由连接两邻点直线的垂直平分线组成的连续多边形组成。N个在平面上有区别的点，按照最邻近原则划分平面；每个点与它的最近邻区域相关联。Delaunay三角形是由与相邻Voronoi多边形共享一条边的相关点连接而成的三角形。Delaunay三角形的外接圆圆心是与三角形相关的Voronoi多边形的一个顶点。Voronoi三角形是Delaunay图的偶图。为清晰V图及Delaunay三角网的概念，如图1，设 为欧几里德平面上的一个点集，则每一个 对应区域 称为点 的Voronoi区域，各点的Voronoi区域共同组成V图（图中用黑色连线）。当 为非共线点集时，若其对应V图中有两个点 ，  的Voronoi区域有公共边，就连接这两个点，以此类推遍历这n个点，可以得到一个连接点集 的唯一确定的网格，就是Delaunay三角网格（图中用红色连线）。
2.2 Delaunay的重要性质
 空外接圆性质：在由点集V生成的Delaunay三角网中,每个三角形的外接圆均不包含该点集的其他任意点。
 最大最小角度性质：在由点集V生成的Delaunay三角网中，所有三角形中的最小角度是最大的，即在生成的三角形网格中,各三角形的最小内角和为最大。
 唯一性：不论从区域何处开始构网，最终都将得到一致的结果。
由于以上特性,决定了Delaunay三角网具有极大的应用价值。Miles证明了Delaunay三角网是“好的”三角网；Lingas进一步论证了“在一般情况下，Delauany三角网是最优的。”同时以上特性也成为建立Delaunay三角网的重要