9.4. TIN的生成方法¶

由于相同的离散点集可以生成多个不同的三角网，因此也就有着多种不同的三角网的构网算法。一般三角网法未考虑地形线的骨架作用，同时在构网时有一定盲目性或任意性，有的三角形边不是贴在地面上，而是“架空”在河谷上或是“贯穿”于山体中。因此这种方法不能用来建立“地貌上”精确的数字地面模型，而只能用于精度要求不高且瞬时性较强的三维空间模型（如气压、气温、磁场等地理现象）。为了使三角网能够顾及地性线关系，可用人工的方法和程序自动建立的两种方法建立TIN模型。

9.4.1. 人工方法¶

地形测量员注意选取地面上的转折点并且在测量中携带一幅野外草图，用以表示由哪些测点构成地性线，例如山脊线及谷底线。在这些资料的基础上，人工构成三角形时，以可能的最短的边来构成三角形，并保证每条边位于地面上而不是悬空通过或贯穿地球表面。只要上述条件满足，三角形的形状是无关紧要的，因此，取得高质量等高线的关键在于获得地性线资料。如果没有它，任何自动化的处理都不能指望达到常规的人工勾绘等高线的质量。

9.4.2. 程序自动建立¶

Delaunay三角网构网算法可归纳为两大类，即静态三角网和动态三角网。静态三角网指的是在整个建网过程中，已建好的三角网不会因新增点参与构网而发生改变；而对于动态三角网则相反，在构网时，当一个点被选中参与构网时，原有的三角网被重构以满足Delaunay外切圆规则。

静态三角网（李志林，2000）构网法主要有辐射扫描算法、递归分裂算法、分解吞并算法、逐步扩展算法、改进层次算法等。动态三角网构网算法主要有增量式算法和增量式动态生成和修改算法。以上算法基本上反映了构建Delaunay三角网的各种途径。在生成TIN的算法中数据结构的设计和选择对算法的运行效率紧密相关。

1. 三角网生长算法

三角形生长算法是一种典型的静态三角网生长算法。

（1）递归生长算法

递归生长算法的基本过程如图9-10所示：

① 在所有数据中取任意一点l(一般从几何中心附近开始)，查找距离此点最近的点2，相连后作为初始基线1-2；

② 在初始基线右边应用Delaunay法则搜寻第三点3，形成第一个Delaunay三角形；

③ 并以此三角形的两条新边(2-3，3-1)作为新的初始基线；

④ 重复步骤②和③直至所有数据点处理完毕。

该算法主要的工作是在大量数据点中搜寻给定基线符合要求的邻域点。一种比较简单的搜索方法是通过计算三角形外接圆的圆心和半径来完成对邻域点的搜索。为减少搜索时间，还可以预先将数据按X或Y坐标分块并进行排序。使用外接圆的搜索方法限定了基线的待选邻域点，因而降低了用于搜寻Delaunay三角网的计算时间。如果引入约束线段，则在确定第三点时还要判断形成的三角形边是否与约束线段交叉。

（2）凸闭包收缩算法

与递归生长算法相反。凸闭包搜索法的基本思想是首先找到包含数据区域的最小凸多边形。并从该多边形开始从外向里逐层形成三角形网络。平面点凸闭包的定义是包含这些平面点的最小凸多边形。在凸闭包中，连接任意两点的线段必须完全位于多边形内。凸闭包是数据点的自然极限边界。相当于包围数据点的最短路径。显然，凸闭包是数据集标准Delaunay三角网的一部分。计算凸闭包算法步骤包括：

① 搜寻分别对应x-y，x+y最大值及x-y，x+y最小值的各两个点。这些点为凸闭包的顶点，且总是位于数据集的四个角上，如图9-11(a)中曲点7，9，12，6；

② 将这些点以逆时针方向存储于循环链表中；

③ 搜索线段IJ及其右边的所有点，计算对IJ有最大偏移量的点K作为IJ之间新的凸闭包顶点，如点11对边7―9。

④ 重复①~②，直至找不到新的顶点为止。

一旦提取出数据区域的凸闭包，就可以从其中的一条边开始逐层构建三角网，具体算法如下：

① 将凸多边形按逆时针顺序存入链表结构，左下角点附近的顶点排第一；

② 选择第一个点作为起点，与其相邻点的连线作为第一条基边，如图9-12(a)中的9―5；

③ 从数据点中寻找与基边左最邻近的点8作为三角形的顶点。这样便形成了第一个Delaunay三角形；

④ 将起点9与顶点8的连线换做基边。重复③即可形成第二个三角形；

⑤ 重复第④步，直到三角形的顶点为另一个边界点11。这样，借助于一个起点9便形成了一层Delaunay三角形；

⑥ 适当修改边界点序列。依次选取前一层三角网的顶点作为新起点，重复前面的处理，便可建立起连续的一层一层的三角网。