Delaunay三角网原理及应用介绍

在地学领域，经常需要处理大量分布于地域内的离散数据。由于这些数据分布的不均匀性，就产生了一个如何合理有效地使用这些宝贵数据的问题。1908年，G.Voronoi首先在数学上限定了每个离散点数据的有效作用范围，即其有效反映区域信息的范围，并定义了二维平面上的Voronoi图。1911年，A.H.Thiessen应用Voronoi图进行了大区域内的平均降水量研究。1934年，B.Delaunay由Voronoi图演化出了更易于分析应用的Delaunay三角网，Voronoi图与Delaunay三角网的关系如图4-4所示（虚线代表Voronoi图，实线代表Delaunay三角网）。从此，Voronoi图和Delaunay三角网就成了被普遍接受和广泛采用的分析研究区域离散数据的有力工具，被广泛应用于各个领域。

图4-4　Voronoi图与Delaunay三角网(www.xing528.com)

带约束Delaunay三角剖分是指对点集进行剖分时，应满足某种约束条件。如：对象重建中的模型边界，道路、施工场地等，地表模型中的山脊线、山谷线和断裂线等。在不允许改变原有点集的场合，约束Delaunay三角剖分的一种有效算法是先将所有点进行标准Delaunay三角剖分，然后强行嵌入不在剖分中的约束边，也可以通过交换对角线的方法强行嵌入约束边。这里介绍的方法的工作原理是：首先建立标准Delaunay三角剖分，然后将复杂区域的边界线作为一种约束线，对嵌入的所有约束边所影响的三角形进行局部调整，使约束边成为三角剖分中的一条边，且满足约束Delaunay三角网（CDT）的基本性质，然后将区域边界外的三角形从三角形链表中删除，即得任意复杂边界的带约束Delaunay三角网。