Delaunay算法的实现与应用

摘 ?要 数字地形模型是针对地形地貌的一种数字建模,这种建模的结果通常就是一个数字高程模型（DEM）。不规则三角网（TIN）模型是DEM中存储和表示非规则数据的理想模型，它既减少规则网格方法造成的数据冗余，同时在计算效率方面又优于纯粹基于等高线的方法，所以寻求一种好的TIN算法更能快速逼真的显示与模拟出地貌三维信息。在所有可能的三角网中，狄洛尼（Delaunay）三角网在地形拟合方面表现最为出色，因此常常用于TIN的生成。依据Delaunay三角剖分准则，直接以边为基础向一侧推进,而不是以凸包为基础向内推进,从而极大地提高了Delaunay三角网推进的速度。仿真实验表明，改进后的算法效率有了显著的提高。 关键词：数字地形模型；数字高程模型；不规则三角网；Delaunay三角网 三角网格化问题在许多领域有广泛应用.例如,在有限元分析中,它是有限元网格生成的有效方法之一;在计算机辅助几何设计中,它可以简化几何模型和实体模型的数据结构及内部表示;在计算机图形显示中,它可以加速光线跟踪算法和光照模型的处理以及图形图像插值应用;在地理学中,它可以快速的生成地理模型。Delaunay三角剖分甚至在无线Ad Hoc通信网络中，可以用于构建发现移动节点间通信路径的在线路由算法。目前，在计算流体力学、统计学、气象学、固体物理学、计算几何学、图形图像学、三维仿真等多个邻域，都能见到它的踪影。我们可以举一些简单的应用：近年来，随着网上购物越来越走入人们的生活，我们可以把某些商品建成可视又可“触”的模型，人们在选购的时候不仅可以看到商品的样子，还可以通过鼠标和键盘对商品模型进行各种操作，查看它的弹性、柔软度等性质，从而用更直观、更便捷的方法来了解商品的性能，而不是对着大篇幅的数字指标发呆。又如，我们可以建立仿真的地理模型，来做大量的地震、暴雨 等的灾难模拟实验，为灾难预测提供理论依据，从而节省大量开支。所以，我相信三角网格化的研究工作一定有着良好的发展和应用前景。 本课题的研究方法 三角网格化主要有两种准则:一种称为 Delaunay三角剖分,即在生成的三角形网格中,各三角形的最小内角和为最大;另一种是在生成的三角网格中,所有三角形的边长和最小.其中, Delaunay三角剖分是目前研究应用最广的一种剖分方法.本课题的研究方法主要是以Delaunay三角网的两个重要性质（空外接圆性质和最大最小角度性质）以及Delaunay三角网的基本原理为基础，参照传统算法思路，在构建三角网的过程中，改进算法的实现方法，数据结构，以达到提高效率的目的。