不规则三角网不规则三角网(TIN)的建立算法的建立算法数字高程模型数字高程模型马仕航马仕航141004022214100402222024/8/221 TIN概述 Ø5.1.1 TIN TIN的理解的理解Ø5.1.25.1.2 TIN TIN的三角剖分准则的三角剖分准则 Ø5.1.35.1.3 三角剖分算法分类与特三角剖分算法分类与特点点 2024/8/222 ØTINTIN的基本概念的基本概念 不规则三角网不规则三角网（（Triangulated Irregular Network Triangulated Irregular Network 简称简称TINTIN））：是用一系列互不交叉、互不重叠的连接在一：是用一系列互不交叉、互不重叠的连接在一起的三角形来表示地形表面起的三角形来表示地形表面TINTIN既是矢量结构又有栅格既是矢量结构又有栅格的空间铺盖特征，能很好地描述和维护空间关系的空间铺盖特征，能很好地描述和维护空间关系2024/8/223 T T：：三角化（三角化（ Triangulated Triangulated ）是离散数据的三角剖分）是离散数据的三角剖分过程，也是过程，也是TINTIN的建立过程。
位于三角形内的任意一点的建立过程位于三角形内的任意一点的高程值均可以通过三角形平面方程唯一确定的高程值均可以通过三角形平面方程唯一确定I I：：不规则性（不规则性（ Irregular Irregular ），指用来构建），指用来构建TINTIN的采样的采样点的分布形式点的分布形式TINTIN具有可变分辨率，比格网具有可变分辨率，比格网DEMDEM能更好能更好反映地形起伏反映地形起伏N N：：网（网（ Network Network ），表达整个区域的三角形分布形态），表达整个区域的三角形分布形态，即三角形之间不能交叉和重叠三角形之间的拓扑关，即三角形之间不能交叉和重叠三角形之间的拓扑关系隐含其中系隐含其中 不规则三角网不规则三角网不规则三角网不规则三角网(TIN)(TIN)的建立的建立的建立的建立2024/8/224 ØTINTIN的基本元素的基本元素l节点（节点（NodeNode）：）：是相邻三角形的公共顶点，是相邻三角形的公共顶点，也是用来构建也是用来构建TINTIN的采样数据；的采样数据；l边（边（EdgeEdge）：）：指两个三角形的公共边界，是指两个三角形的公共边界，是TINTIN不光滑性不光滑性的具体反映。
边同时还包含特征线、断裂线以及区域边界的具体反映边同时还包含特征线、断裂线以及区域边界l面（面（FaceFace）：）：由最近的三个节点所组成的三角形面，是由最近的三个节点所组成的三角形面，是TINTIN描述地形表面的基本单元描述地形表面的基本单元TINTIN中的每一个三角形都描中的每一个三角形都描述了局部地形倾斜状态，具有唯一的坡度值三角形在公述了局部地形倾斜状态，具有唯一的坡度值三角形在公共节点和边上是无缝的，或者说三角形不能交叉和重叠共节点和边上是无缝的，或者说三角形不能交叉和重叠z节节点点x边边面面y2024/8/225 Ø数据和数据和TINTIN的类型的类型l用来进行用来进行TINTIN构建的原始数据根据数据点之间的约束构建的原始数据根据数据点之间的约束条件可分为条件可分为无约束数据域无约束数据域和和约束数据域约束数据域两种类型两种类型 l无约束数据域无约束数据域是指数据点之间不存在任何关系，即数是指数据点之间不存在任何关系，即数据分布完全呈离散状态，数据点之间在物理上相互独据分布完全呈离散状态，数据点之间在物理上相互独立l约束数据域约束数据域则是部分数据点之间存在着某种联系，这则是部分数据点之间存在着某种联系，这种联系一般通过线性特征来维护，如地形数据中的山种联系一般通过线性特征来维护，如地形数据中的山脊线、山谷线上的点等脊线、山谷线上的点等。
2024/8/226 ØTINTIN的体系结构的体系结构 TINTIN对三角形的几何形状一般有三个基本要求：对三角形的几何形状一般有三个基本要求：1 1）三角形的格网唯一；）三角形的格网唯一；2 2）最佳三角形形状，尽量接近正三角形；）最佳三角形形状，尽量接近正三角形；3 3）三角形边长之和最小，保证最近的点形成）三角形边长之和最小，保证最近的点形成 三角形2024/8/227 TIN的三角剖分准则的三角剖分准则 l TINTIN的三角剖分准则是指的三角剖分准则是指TINTIN中三角形的中三角形的形成法则，它决定着三角形的几何形状和形成法则，它决定着三角形的几何形状和TINTIN的质量l 目前，在目前，在GISGIS、计算机和图形学领域常用、计算机和图形学领域常用的三角剖分准则有的三角剖分准则有6 6种2024/8/228 空外接圆准则：空外接圆准则：在在TINTIN中，过每个三角形的外接圆均不包含点集的其中，过每个三角形的外接圆均不包含点集的其余任何点；余任何点；最大最小角准则：最大最小角准则：在在TINTIN中的两相邻三角形形成的凸四边形中，这中的两相邻三角形形成的凸四边形中，这两三角形中的最小内角一定大于交换凸四边形对角线后所形成的两三角两三角形中的最小内角一定大于交换凸四边形对角线后所形成的两三角形的最小内角；形的最小内角；最短距离和准则：最短距离和准则：指一点到基边的两端的距离和为最小。
指一点到基边的两端的距离和为最小2024/8/229 张角最大准则：张角最大准则：一点到基边的张角为最大一点到基边的张角为最大面积比准则：面积比准则：三角形内切圆面积与三角形面积或三角形面积与周长三角形内切圆面积与三角形面积或三角形面积与周长平方之比最小平方之比最小 对角线准则：对角线准则：两三角形组成的凸四边形的两条对角线之比这一准两三角形组成的凸四边形的两条对角线之比这一准则的比值限定值，须给定，即当计算值超过限定值才进行优化则的比值限定值，须给定，即当计算值超过限定值才进行优化2024/8/2210 l1 1）三角形准则是建立三角形格网的基本原）三角形准则是建立三角形格网的基本原则，应用不同的准则将会得到不同的三角网则，应用不同的准则将会得到不同的三角网l2 2）一般而言，应尽量保持三角网的唯一性，）一般而言，应尽量保持三角网的唯一性，即在同一准则下由不同的位置开始建立三角即在同一准则下由不同的位置开始建立三角形格网，其最终的形状和结构应是相同的形格网，其最终的形状和结构应是相同的l3 3）空外接圆准则、最大最小角准则下进行）空外接圆准则、最大最小角准则下进行的三角剖分称为的三角剖分称为Delaunay Delaunay ( (译为狄洛尼或德译为狄洛尼或德劳内劳内) )三角剖分（三角剖分（TriangulationTriangulation）），简称，简称DTDT。
空外接圆准则也叫空外接圆准则也叫DelaunayDelaunay法则说明：说明：2024/8/2211 •关于关于delaunaydelaunay三角网三角网•19341934年年DelaunayDelaunay提出了提出了VoronoiVoronoi图的对称图，图的对称图，即即DelaunayDelaunay三角网（用直线段连接两个相邻三角网（用直线段连接两个相邻多边形内的离散点而生成的三角网）多边形内的离散点而生成的三角网）–DelaunayDelaunay三角网的特性：三角网的特性：•不存在四点共圆；不存在四点共圆；•每个三角形对应于一个每个三角形对应于一个VoronoiVoronoi图顶点；图顶点；•每个三角形边对应于一个每个三角形边对应于一个VoronoiVoronoi图边；图边；•每个结点对应于一个每个结点对应于一个VoronoiVoronoi图区域；图区域；•DelaunayDelaunay图的边界是一个凸壳；图的边界是一个凸壳；•三角网中三角形的最小角最大三角网中三角形的最小角最大2024/8/2212 TIN的建立 Ø1 无约束散点域的三角剖分算法与实现无约束散点域的三角剖分算法与实现 Ø2 约束散点数据域的三角剖分算法与实现约束散点数据域的三角剖分算法与实现 Ø3 基于等高线数据的基于等高线数据的TIN的建立的建立Ø4 基于栅格数据的三角网建立基于栅格数据的三角网建立2024/8/2213 无约束散点域的三角剖分算法与实现无约束散点域的三角剖分算法与实现 l 目前散点域的三角剖分使用最为广泛的算法是目前散点域的三角剖分使用最为广泛的算法是DelaunayDelaunay直接三角剖分算法。
直接三角剖分算法1 1）三角网生长算法）三角网生长算法2 2）逐点插入算法）逐点插入算法 3 3）分割合并算法）分割合并算法2024/8/2214 1 1、三角网生长算法、三角网生长算法l 三角网生长算法就是从一个三角网生长算法就是从一个“源源”开始，逐步形成开始，逐步形成覆盖整个数据区域的三角网覆盖整个数据区域的三角网l 从生长过程角度，三角网生长算法分为从生长过程角度，三角网生长算法分为收缩生长算收缩生长算法法和和扩张生长算法扩张生长算法两类l 收缩生长算法是先形成整个数据域的数据边界（凸收缩生长算法是先形成整个数据域的数据边界（凸壳），并以此作为源头，逐步缩小以形成整个三角网壳），并以此作为源头，逐步缩小以形成整个三角网l 扩张生长算法与收缩算法过程刚好相反，是从一个扩张生长算法与收缩算法过程刚好相反，是从一个三角形开始向外层层扩展，形成覆盖整个区域的三角三角形开始向外层层扩展，形成覆盖整个区域的三角网2024/8/2215 1 1、三角网生长算法、三角网生长算法1 1）递归生长算法）递归生长算法•算法过程如下：–在数据集中任取一点，查找距离此点最近的点，相连后作为初始基线；–在初始基线右边应用Delaunay法则搜索第三点；–生成Delaunay三角形，并以该三角形的两条新边作为新的基线；–重复前面过程直至所有基线处理完毕；•这种算法大量的时间花费在符合要求的邻域点的搜索方面，为了减少搜索时间，许多学者提出了许多不同的方法，如将数据分块并排列，以外接圆的方式限定其搜索范围。
2024/8/2216 12121212递归生长算法递归生长算法3332024/8/2217 1 1、三角网生长算法、三角网生长算法l该算法的基本思路该算法的基本思路: :首先找到包含数据区域的最小凸多边首先找到包含数据区域的最小凸多边形，并从该多边形开始从外向里逐层形成三角形格网形，并从该多边形开始从外向里逐层形成三角形格网l平面点平面点凸闭包凸闭包的定义是包含这些平面点的最小多边形的定义是包含这些平面点的最小多边形l在凸闭包中，连接任意两点的线段必须完全位于多边形在凸闭包中，连接任意两点的线段必须完全位于多边形内凸闭包是数据点的自然极限边界，相当于包围数据内凸闭包是数据点的自然极限边界，相当于包围数据点的最短路径点的最短路径l凸闭包是数据集标准凸闭包是数据集标准DelaunayDelaunay三角网的一部分计算凸三角网的一部分计算凸闭包是该算法的核心闭包是该算法的核心2 2）凸闭包收缩法）凸闭包收缩法2024/8/2218 1 1）计算凸闭包的四个顶点；）计算凸闭包的四个顶点；2 2）以此四点作为基点，通过边右边最大偏移量搜索其他凸）以此四点作为基点，通过边右边最大偏移量搜索其他凸闭包顶点闭包顶点。
计算凸闭包的思路（计算凸闭包的思路（P79P79）：）：2024/8/2219 1 1）将凸多边形按逆时针保存记录，以左下角点附近的顶点作为）将凸多边形按逆时针保存记录，以左下角点附近的顶点作为起点；起点；2 2）确定第一条基边；）确定第一条基边；3 3）构建第一个）构建第一个DelaunayDelaunay三角形；三角形；4 4）重复）重复(3)(3)形成第一层形成第一层DelaunayDelaunay三角形；三角形；5 5）重新确定起点，重复）重新确定起点，重复(2)~(4)(2)~(4)完成整个区域的三角网构建完成整个区域的三角网构建构建三角网的具体算法构建三角网的具体算法2024/8/2220 2 2、逐点插入算法、逐点插入算法 ：：•1 1）定义包含所有数据点的最小外界矩形范围，并以此作）定义包含所有数据点的最小外界矩形范围，并以此作为最简单的凸闭包为最简单的凸闭包•2 2）按一定规则将数据区域的矩形范围进行格网划分（如）按一定规则将数据区域的矩形范围进行格网划分（如限定每个格网单元的数据点数）限定每个格网单元的数据点数）•3 3）剖分数据区域的凸闭包形成两个超三角形，所有数据）剖分数据区域的凸闭包形成两个超三角形，所有数据点都一定在这两个三角形范围内。
点都一定在这两个三角形范围内•4 4）对所有数据点进行循环，作如下工作（设当前处理的）对所有数据点进行循环，作如下工作（设当前处理的数据点为数据点为P P）：）：–搜寻包含点P的三角形，将P与此三角形三个顶点相连，形成三个三角形；–由里到外优化整个三角网；–重复以上过程直到所有点处理完毕；–删除所有包含一个或多个超三角形顶点的三角形•5 5）处理外围三角形处理外围三角形2024/8/2221 逐点插入算法逐点插入算法2024/8/2222 3 3、分割合并算法、分割合并算法 分割合并算法的思想很简单，首先将数据点分割分割合并算法的思想很简单，首先将数据点分割成易于进行三角化的子集，然后对每个子集进行三成易于进行三角化的子集，然后对每个子集进行三角剖分，并用角剖分，并用LOPLOP算法保证三角剖分为算法保证三角剖分为DelaunayDelaunay三三角网当每个子集剖分完成后，对每个子集的三角角网当每个子集剖分完成后，对每个子集的三角剖分进行合并，形成最终的整体三角网剖分进行合并，形成最终的整体三角网 2024/8/2223 分割合并算法分割合并算法2024/8/2224 3 基于等高线数据的基于等高线数据的TIN的建立的建立Ø 等高线离散点直接生成等高线离散点直接生成TINTIN；；Ø 将等高线作为特征线的方法；将等高线作为特征线的方法；Ø 自动增加特征点及优化自动增加特征点及优化TINTIN的方法。
的方法2024/8/2225 等高线离散点直接生成等高线离散点直接生成TINTIN方法方法 l 该方法直接将等高线离散化，然后利用常用该方法直接将等高线离散化，然后利用常用TINTIN的生成的生成算法，该方法没有考虑离散点间原有的连接关系，模拟的算法，该方法没有考虑离散点间原有的连接关系，模拟的地形就会失真，具体表现为地形就会失真，具体表现为三角形的边穿越等高线三角形的边穿越等高线和存在和存在平三角形平三角形的两种情况的两种情况 l 在实际应用中该方法较少使用在实际应用中该方法较少使用2024/8/2226 等高线作为特征线建立等高线作为特征线建立TINTIN l将等高线作为断将等高线作为断裂线或结构线；裂线或结构线；l使用等高线上的使用等高线上的特征点，并将等高特征点，并将等高线段作为约束线段线段作为约束线段处理2024/8/2227 自动增加特征点及优化自动增加特征点及优化TINTIN的方法的方法l 该方法实质仍将等高该方法实质仍将等高线离散化建立线离散化建立TINTIN，但采，但采用增加特征点的方式来消用增加特征点的方式来消除除TINTIN中的平三角形，并中的平三角形，并使用优化使用优化TINTIN的方式来消的方式来消除不合理的三角化；除不合理的三角化；l特征点的增加需要利用特征点的增加需要利用一定的算法自动提取，这一定的算法自动提取，这些算法原理大都基于原始些算法原理大都基于原始等高线的拓扑关系。
等高线的拓扑关系2024/8/2228 。