不规则三角网（TIN）生成的算法
第五章 不规则三角网（TIN）生成的算法
在第四章，基于三角网和格网的建模方法使用较多，被认为是两种基 本的建模方法。三角网被视为最基本的一种网络，它既可适应规则分布数 据，也可适应不规则分布数据，即可通过对三角网的内插生成规则格网网 络，也可根据三角网直接建立连续或光滑表面模型。在第四章中同时也介 绍了 Delaunay 三角网的基本概念及其产生原理，并将三角网构网算法归纳 为两大类：即静态三角网和动态三角网。由于增量式动态构网方法在形成 Delaunay 三角网的同时具有很高的计算效率而被普遍采用。本章主要介绍 静态方法中典型的三角网生长算法和动态方法中的数据点逐点插入算法； 同时，还将给出考虑地形特征线和其他约束线段的插入算法。而其他非 Delaunay 三角网算法如辐射扫描法 Radial Sweep Algorigthm（Mirante & Weingarten, 1982）等本文将不再介绍。
5.1 三角网生长法
5.1.1 递归生长法
递归生长算法的基本过程为如图 5.1.1 所示：
3 2
1
3 2
1
（a）形成第一个三角形 (b) 扩展生成第二个和第三个三角形 图 5.1.1 递归生长法构建 Delaunay 三角网
（1）在所有数据中取任意一点 1（一般从几何中心附近开始），查
1
距离此点最近的点 2，相连后作为初始基线 1-2； （2）在初始基线右边应用 Delaunay 法则搜寻第三点 3，形成第一个
Delaunay 三角形； （3）并以此三角形的两条新边（2-3，3-1）作为新的初始基线； （4）重复步骤（2）和（3）直至所有数据点处理完毕。 该算法主要的工作是在大量数据点中搜寻给定基线符合要求的邻域 点。一种比较简单的搜索方法是通过计算三角形外接圆的圆心和半径来完 成对邻域点的搜索。为减少搜索时间，还可以预先将数据按 X 或 Y 坐标分 块并进行排序。使用外接圆的搜索方法限定了基线的待选邻域点，因而降 低了用于搜寻 Delaunay 三角网的计算时间。如果引入约束线段，则在确定 第三点时还要判断形成的三角形边是否与约束线段交叉。
5.1.2 凸闭包收缩法
与递归生长法相反，凸闭包搜索法的基本思想是首先到包含数据区 域的最小凸多边形，并从该多边形开始从外向里逐层形成三角形网络。平 面点凸闭包的定义是包含这些平面点的最小凸多边形。在凸闭包中，连接 任意两点的线段必须完全位于多边形内。凸闭包是数据点的自然极限边界， 相当于包围数据点的最短路径。显然，凸闭包是数据集标准 Delaunay 三角 网的一部分。计算凸闭包算法步骤包括：
（1）搜寻分别对应 x-y，x+y 最大值及 x-y，x+y 最小值的各二个点。 这些点为凸闭包的顶
点，且总是位于数据集的四个角上，如图 5.1.2（a）中的点 7，9，12，6 所示；
（2）将这些点以逆时针方向存储于循环链表中； （3）对链表中的点 I 及其后续点 J 搜索线段 IJ 及其右边的所有点，计
算对 IJ 有最大偏移量的点 K 作为 IJ 之间新的凸闭包顶点，如点 11 对边 7-9。 （4）重复（2）-（3）直至不到新的顶点为止。
（a）初始边界 7，9，12，6；（b）搜索凸闭包顶点 11，5，4；（c）凸闭包
2
图 5.1.2 凸闭包的计算(引自 Tsai，1993) 一旦提取出数据区域的凸闭包，就可以从其中的一条边开始逐层构建 三角网，具体算法如下：
(a)第一个三角形 (b)第一层三角形 图 5.1.3 凸闭包收缩法形成三角网
(1) 将凸多边形按逆时针顺序存入链表结构，左下角点附近的顶点排 第一；
(2) 选择第一个点作为起点，与其相邻点的连线作为第一条基边，如 图 5.1.3（a）中的 9-5；
(3) 从数据点中寻与基边左最邻近的点 8 作为三角形的顶点。这样 便形成了第一个 Delaunay 三角形；
(4) 将起点 9 与顶点 8 的连线换作基边，重复(3) 即可形成第二个三 角形；
(5) 重复第(4)步，直到三角形的顶点为另一个边界点 11。这样，借助 于一个起点 9 便形成了一层 Delaunay 三角形；
(6) 适当修改边界点序列，依次选取前一层三角网的顶点作为新起点， 重复前面的处理，便可建立起连续的一层一层的三角网。
该方法同样可以考虑约束线段。但随着数据点分布密度的不同，实际 情况往往比较复杂。比如边界收缩后一个完整的区域可能会分解成若干个 相互独立的子区域。当数据量较大时如何提高顶点选择的效率是该方法的 关键。
5.2 数据逐点插入法
5.1 节介绍的三角网生长算法最大的问题是计算的时间复杂性，由于每 个三角形的形成都涉及所有待处理的点，且难于通过简单的分块或排序予
3
以彻底解决。数据点越多，问题越突出。本节将要介绍的数据逐点插入法 在很大程度上克服了数据选择问题。其具体算法如下（见图 5.2.1）：
（1） 首先提取整个数据区域的最小外界矩形范围，并以此作为最简 单的凸闭包。
（2） 按一定规则将数据区域的矩形范围进行格网划分，为了取得比 较理想的综合效率，可以限定每个格网单元平均拥有的数据点 数。
（3） 根据数据点的（x,y）坐标建立分块索引的线性链表。 （4） 剖分数据区域的凸闭包形成两个超三角形，所有的数据点都一
定在这两个三角形范围内。 （5） 按照（3）建立的数据链表顺序往（4）的三角形中插入数据点。
首先到包含数据点的三角形，进而连接该点与三角形的三个 顶点，简单剖分该三角形为三个新的三角形。 （6） 根据 Delaunay 三角形的空圆特性，分别调整新生成的三个三 角形及其相邻的三角形。对相邻的三角形两两进行检测，如果 其中一个三角形的外接圆中包含有另一个三角形除公共顶点 外的第三个顶点，则交换公共边。 （7） 重复（5）-（6）直至所有的数据点都被插入到三角网中。
（a）第一分块数据插入后 (b) 第二分块数据插入后 (c)全部三角形 图 5.2.1 逐点插入法构建 Delaunay 三角网
可见，由于步骤（3）的处理，保证相邻的数据点渐次插入，并通过搜 寻加入点的影响三角网（Influence Triangulation），现存的三角网在局部范
4
正则化几何因子
围内得到了动态更新。从而大大提高了寻包含数据点的三角形的效率。
5.3 带约束条件的 Delaunay 三角网
当不相交的地形特征线、特殊的范围边界线等被作为预先定义的限制 条件作用于 TIN 的生成当中时，必须考虑带约束条件的 Delaunay 三角网。 最简单的处理方法是所谓的“加密法”，即通过加密约束线段上的数据点， 将约束数据转换为普通数据，从而按标准 Delaunay 三角形剖分即可。尽管 该方法加大了数据量并改变了原始数据集，但由于简单易行、稳定可靠， 在许多情况下可以很好地满足需要。该方法唯一的问题在于如何恰当地确 定特征线上加密数据点之间的距离，一般取平均数据点间距的一半或更小 即可。以下内容主要介绍直接处理约束线段的算法。
5.3.1 带约束条件的 Delaunay 三角网的定义
定义 1：给定一个 d 维欧基里德空间 E 和一个 N 点 mi 集 M。那么， 关联的 Voronoi 图 (又称 Thiessen 多边形 )为覆盖 E 的一个凸多边形序列 (V(m1 )，V(m2 )，…，V(m N))，其中，V(mi)包括 E 中所有以 M 中的 mi 为最近点的点，即 V(mi)=p∈E∶ Vj，1≤j≤N，d(p，mi)≤ d(p，mj)，d 表示欧基里德距离。Voronoi 图的几何对偶 (dual)，即把点 mi 联结起来而 得到的邻接格网称为 M 的 Delaunay 三角网。显然，Delaunay 三角网的元 素之并等于 M 的凸包之内部。Delaunay 三角网自然推广到输入数据不仅包 括点集 M，还包括不相交叉的直
线段集 L。在计算几何里，这类问题称约 束 Delaunay 三角网（Constrained Delaunay Triangles，简称 CDT）问题。 对地形数据来说，L 即地形特征线段集（朱庆，陈楚江，1998）。
定义 2：令单点集 M 和线段端点集 E 之并为 V（V=M∪E），如果在 V 的每个 Delaunay 三角形的外接圆范围内不包含任何与三角形的顶点均通 视的其它点，而点 Pi 与 Pj（Pi，Pj∈V）当且仅当连线 PiPj 不与 L 中的任 何约束线段相交叉（除在端点处外）时才互相通视，那么称这个 Delaunay 三角网为 V 由 L 约束的 Delaunay 三角网（朱庆，陈楚江，1998）。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。