第五章 不规则三角网TIN建立1

1、第一节 概述1.1 TIN的基本概念 基于不规则三角网的数字高程模型（Based on Triangulated Irregular Network DEM）就是用一系列互不交叉、互不重叠的连结在一起的三角形来表示地形表面。什么是TIN？TIN的基本要素用来描述TIN的基本要素有三个：节点、边、面。 节点是相邻三角形的公共顶点，也是用来构建TIN的采样数据。 边是指两个三角形的公共边界，是TIN不光滑性的具体反映。边同时还包含特征线、断裂线及区域边界。 面是由最近的三个顶点所组成的三角形面，是TIN描述地形表面的基本单元。TIN中的每一个三角形都描述了局部地形倾斜状态，具有唯一的坡度值。数据和

2、TIN的类型 构建TIN的原始数据根据数据点之间的约束条件可分为无约束数据域和约束数据域两种类型。 无约束数据域是指数据点之间不存在任何关系，即数据分布完全呈离散状态，数据点之间在物理上相互独立。 约束数据域则指部分数据点之间存在某种关系，这种关系一般通过线性特征来维护。 约束条件又可分为两种：一种是边界约束，指数据点被一多边形所包围，该多变形为边界约束条件；另外一种为内部约束条件，即数据点之间存在某种限制。TIN的体系结构在TIN中，对三角形的几何形状有严格的要求。一般应满足以下三条原则：1、尽量接近正三角形2、保证最近的点形成三角形3、三角形网络唯一 分析可知：TIN的数据组织、三角形划分

3、准则、算法和程序构成了TIN的基本理论体系框架。1.2 TIN的三角剖分准则第一节 概述 TIN的三角剖分准则是指TIN中三角形的形成法则，它决定着三角形的几何形状和TIN的质量。 目前在GIS、计算几何和计算机图形学领域常见的三角剖分准则有以下6种：（1）空外接圆准则：在TIN中，过每个三角形的外接圆均不包含点集的其余任何点。（2）最大最小角准则：在两相邻三角形形成的凸四边形中，这两三角形中的最小内角一定大于交换凸四边形对角线后所形成的两三角形的最小内角。（3）最短距离和准则：指一点到基边两端的距离和为最小。1.2 TIN的三角剖分准则第一节 概述（4）张角最大准则：一点到基边的张角为最大。

4、（5）面积比准则：三角形内切圆面积与三角形面积或三角形面积与周长平方之比最小。（6）对角线准则：两三角形组成的凸四边形的两条对角线之比超过给定限定值时，对三角形进行优化。 通常将在空外接圆准则、最大最小角准则下进行的三角剖分称为Delaunay三角形，简称DT。 事实上，在任何三角剖分准则下得到的TIN，只要通过LOP法则（局部优化过程，Local optimal procedure,LOP）对其进行优化处理，就能得到唯一的DT三角网络。 LOP法则的基本思想是运用DT三角网的空外接圆性质对由两个有公共边的三角形组成的四边形进行判断，如果一个三角形的外接圆中含有第四个顶点，则交换四边形的对角线

5、。第一节 概述1.3 三角剖分算法分类与特点 TIN的三角剖分就是按照三角剖分准则，将地形采样点用互不相交的直线段连接起来，并按一定的结构存储。现以地形采样数据的分布情况为依据对TIN的三角剖分算法进行归类。TIN算法类型不规则分布数据分割合并算法空外接圆算法逐点插入算法三角形增长算法规则分布数据VIPs算法循环迭带算法层次三角形算法沿等高线分布数据特征线算法探测优化算法第二节 TIN的建立5.2.1 无约束散点域的三角剖分算法与实现 Tsai于1994年根据实现过程，把DT三角剖分分成三类：分割合并算法、三角网增长算法和逐点插入算法。分割合并算法 分割合并算法的思想很简单，就是将复杂问题简单

6、化，首先将数据点分割成易于进行三角剖分的子集，然后对每个子集进行三角剖分，并用LOP算法保证三角剖分为DT三角网,最后对各子集根据一定规则进行合并，进而形成整体三角网。分割合并算法的基本步骤：第一步：把数据集以横座标为主，纵坐标为辅按升序进行排序。第二步：对数据集进行分割，如果数据子集中的个数大于给定的阀值，把数据域划分为采样点个数近似相等的左右两个子集，并对每一子集做如下工作：1 计算每一子集的凸壳2 以凸壳为数据边界，对每一数据子集进行三角剖分，并用LOP法则进行优化，使之成为DT三角剖分3找出连接左右子集两个凸壳的底线和顶线4 由底线到顶线合并两个子三角网。子集凸壳的生成 所谓凸壳是指数

7、据点的自然极限边界，为包含所有数据点的最小凸多边形。下面给大家介绍格雷厄姆凸壳生成算法，步骤如下：（1）找出点集中纵坐标最小的点P1（2）将P1点和点集中其他各点用线段相连，并计算这些线段与水平线的夹角（3）按夹角大小对数据点进行排序，如果夹角相同，则按距离排序。设得到的序列为P1、P2、Pn（4）依次连接所有点，得到一多边形，根据凸多边形原理，删去边界序列中的非凸壳顶点。最后，得到凸壳点集。子三角网合并 合并的方式是同层优先，从下至上的递归方式进行。合并时先找出两个相邻子三角网凸壳在上下的公切线，作为三角网的上下边界。然后从下到上在两子三角形中寻找与底线组成Delaunay三角形的第三点，选

8、其中外接圆半径小的一个插入到三角网中，如此类推，完成子网合并。三角网生长算法 故名思议，三角网生长算法就是从一个“源”开始，逐步形成覆盖整个区域的三角网。 以生长过程的角度不同为依据，三角网生长算法分为收缩生长算法和扩张生长算法两种。 收缩生长算法又称凸闭包收缩法，是先形成整个数据域的数据边界（凸壳），并以此作为源头，逐步缩小以形成整个三角网。收缩生长算法与数据点的分布密度有关。 扩张生长算法与收缩生长算法相反，该算法从一个三角形开始向外层层扩展，最终形成覆盖整个区域的三角网。扩张生长算法具体步骤：1 生成初始三角形。2 扩张形成三角网。该方法的主要工作是在大量数据点中搜寻第三点。其中一种比较

9、简单的搜索方法是通过计算三角形的外接圆圆心和半径来完成对邻域点的搜索。扩张生长算法具体步骤：1、在所采集的离散点中任意找一点，然后查找距此点最近的点，连接后作为初始线。、在所采集的离散点中任意找一点，然后查找距此点最近的点，连接后作为初始线。2 2、在初始基线右侧运用在初始基线右侧运用Delaunay法则搜寻第三点，具体的做法是：在初始基线右侧的离法则搜寻第三点，具体的做法是：在初始基线右侧的离散点中查找距此基线距离最短的点，做为第三点。散点中查找距此基线距离最短的点，做为第三点。3 3、生成生成Delaunay三角形，再以三角形的两条新边（从基线起始点到第三点以及第三点到三角形，再以三角形的

10、两条新边（从基线起始点到第三点以及第三点到基线终止点）作为新的基线。基线终止点）作为新的基线。重复步骤（2），（3）直至所有的基线处理完毕。收缩生长算法具体步骤： 一旦提取出数据区域的凸闭包，就可以从其中的一条边开始逐层构建三角网，具体算法如下： (1)将凸多边形按逆时针顺序存入链表结构，左下角点附近的顶点排第一； (2)选择第一个点作为起点，与其相邻点的连线作为第一条基边，如图5.1.3(a)中的9-5； (3)从数据点中寻找与基边最邻近的点8作为三角形的顶点。这样便形成了第一个DT三角形； (4)将起点9与顶点8的连线换做基边，重复(3)即可形成第二个三角形； (5)重复第(4)步，直到三角形的顶点为另一个边界点11。这样，借助于一个起点9便形成了一层Delaunay三角形； (6)适当修改边界点序列，依次选取前一层三角网的顶点作为新起点，重复前面的处理，便可建立起连续的一层一层的三角网。逐点插入算法具体步骤：第一步：首先提取整个数据区域的最小外界矩形范围，并以此作为最简单的凸闭包。并对包容矩形进行初始三角剖分。 第二步：对所有数据点进行循环（设当前处理的数据点为P）。在已存在的三角网中，查找包含P的三角形t。 p与t的三个顶点相连，形成t的三个初始三角剖分。利用LOP算法对初始三角剖分进行优化处理。第三步：处理外围三角形。算法详解：第一步：大家注意了，