第五章-不规则三角网TIN的建立课件.ppt
2023/3/14,1,第五章 不规则三角网(TIN)的建立,数字高程模型,2023/3/14,2,本章主要内容,数字高程模型,第5章 不规则三角网(TIN)的建立,5.1 TIN概述 5.2 TIN的建立 5.3 TIN建立过程中的几个问题,2023/3/14,3,5.1 TIN概述,5.1.1 TIN的理解5.1.2 TIN的三角剖分准则 5.1.3 三角剖分算法分类与特点,第5章 不规则三角网(TIN)的建立,数字高程模型,2023/3/14,4,5.1.1 TIN的理解,TIN的基本概念,不规则三角网（Triangulated Irregular Network 简称TIN）：是用一系列互不交叉、互不重叠的连接在一起的三角形来表示地形表面。TIN既是矢量结构又有栅格的空间铺盖特征，能很好地描述和维护空间关系。,5.1 TIN概述,第5章 不规则三角网(TIN)的建立,2023/3/14,5,T：三角化（Triangulated）是离散数据的三角剖分过程，也是TIN的建立过程。位于三角形内的任意一点的高程值均可以通过三角形平面方程唯一确定。I：不规则性（Irregular），指用来构建TIN的采样点的分布形式。TIN具有可变分辨率，比格网DEM能更好反映地形起伏。N：网（Network），表达整个区域的三角形分布形态，即三角形之间不能交叉和重叠。三角形之间的拓扑关系隐含其中。,5.1 TIN概述,第5章 不规则三角网(TIN)的建立,2023/3/14,6,5.1.1 TIN的理解,TIN的基本元素,节点（Node）：是相邻三角形的公共顶点，也是用来构建TIN的采样数据；边（Edge）：指两个三角形的公共边界，是TIN不光滑性的具体反映。边同时还包含特征线、断裂线以及区域边界。面（Face）：由最近的三个节点所组成的三角形面，是TIN描述地形表面的基本单元。TIN中的每一个三角形都描述了局部地形倾斜状态，具有唯一的坡度值。三角形在公共节点和边上是无缝的，或者说三角形不能交叉和重叠。,5.1 TIN概述,第5章 不规则三角网(TIN)的建立,2023/3/14,7,TIN的基本元素,5.1 TIN概述,第5章 不规则三角网(TIN)的建立,2023/3/14,8,5.1.1 TIN的理解,数据和TIN的类型,用来进行TIN构建的原始数据根据数据点之间的约束条件可分为无约束数据域和约束数据域两种类型。无约束数据域是指数据点之间不存在任何关系，即数据分布完全呈离散状态，数据点之间在物理上相互独立。约束数据域则是部分数据点之间存在着某种联系，这种联系一般通过线性特征来维护，如地形数据中的山脊线、山谷线上的点等。,5.1 TIN概述,第5章 不规则三角网(TIN)的建立,2023/3/14,9,5.1.1 TIN的理解,TIN的体系结构,TIN对三角形的几何形状有严格的要求。TIN模型一般有三个基本要求：,1）三角形的格网唯一；2）最佳三角形形状，尽量接近正三角形；3）三角形边长之和最小，保证最近的点形成 三角形。,5.1 TIN概述,第5章 不规则三角网(TIN)的建立,2023/3/14,10,5.1.1 TIN的理解,TIN的体系结构,良好的数据结构和三角形剖分准则，必须由高效的算法和程序实现。,5.1 TIN概述,第5章 不规则三角网(TIN)的建立,面结构、点结构、点面结构、边结构、边面结构,2023/3/14,11,5.1.2 TIN的三角剖分准则,TIN的三角剖分准则是指TIN中三角形的形成法则，它决定着三角形的几何形状和TIN的质量。目前，在GIS、计算机和图形学领域常用的三角剖分准则有6种。,5.1 TIN概述,第5章 不规则三角网(TIN)的建立,2023/3/14,12,5.1.2 TIN的三角剖分准则,5.1 TIN概述,第5章 不规则三角网(TIN)的建立,空外接圆准则：在TIN中，过每个三角形的外接圆均不包含点集的其余任何点；最大最小角准则：在TIN中的两相邻三角形形成的凸四边形中，这两三角形中的最小内角一定大于交换凸四边形对角线后所形成的两三角形的最小内角；最短距离和准则：指一点到基边的两端的距离和为最小。,2023/3/14,13,张角最大准则：一点到基边的张角为最大。面积比准则：三角形内切圆面积与三角形面积或三角形面积与周长平方之比最小。对角线准则：两三角形组成的凸四边形的两条对角线之比。这一准则的比值限定值，须给定，即当计算值超过限定值才进行优化。,5.1 TIN概述,第5章 不规则三角网(TIN)的建立,5.1.2 TIN的三角剖分准则,2023/3/14,14,1）三角形准则是建立三角形格网的基本原则，应用不同的准则将会得到不同的三角网。2）一般而言，应尽量保持三角网的唯一性，即在同一准则下由不同的位置开始建立三角形格网，其最终的形状和结构应是相同的。3）空外接圆准则、最大最小角准则下进行的三角剖分称为Delaunay(译为狄洛尼或德劳内)三角剖分（Triangulation），简称DT。空外接圆准则也叫Delaunay法则。,说明：,5.1 TIN概述,第5章 不规则三角网(TIN)的建立,2023/3/14,15,关于delaunay三角网Dirichlet（1850年）和Voronoi（1908年）最早讨论空间散点的关系问题。Voronoi图的定义（P105）Voronoi图把平面分成N个区，每一个区包括一个点，该点所在的区域是距离该点最近的点的集合。,5.1 TIN概述,第5章 不规则三角网(TIN)的建立,2023/3/14,16,关于delaunay三角网1934年Delaunay提出了Voronoi图的对称图，即Delaunay三角网（用直线段连接两个相邻多边形内的离散点而生成的三角网）。Delaunay三角网的特性：不存在四点共圆；每个三角形对应于一个Voronoi图顶点；每个三角形边对应于一个Voronoi图边；每个结点对应于一个Voronoi图区域；Delaunay图的边界是一个凸壳；三角网中三角形的最小角最大。,5.1 TIN概述,第5章 不规则三角网(TIN)的建立,2023/3/14,17,5.1.3 三角剖分算法分类与特点,不规则分布采样数据三角剖分 规则分布采样数据三角剖分 从混合数据生成三角网 基于等高线采样数据三角剖分,5.1 TIN概述,第5章 不规则三角网(TIN)的建立,2023/3/14,18,5.1.3 三角剖分算法分类与特点,不规则分布采样数据三角剖分（P64-67）,在目前所有的三角化算法中，以Delaunay三角网的应用最为广泛。Delaunay 三角网为相互邻接且互不重叠的三角形的集合，每一个三角形的外接圆内不包含其它的点。DT的主要特点是它能自动地避免狭长的三角形，保证了良好的三角形形状。DT的两个显著特性最大最小角特性和空外接圆特性是构成各种DT剖分的基础。,5.1 TIN概述,第5章 不规则三角网(TIN)的建立,2023/3/14,19,新插入点与已知三角网存在四种关系（P66）：,（a）在三角形内,（b）在三角形外接圆内,（c）在三角形外接圆上,（d）在三角形外接圆外,2023/3/14,20,局部几何形状最优，采用LOP算法（局部优化过程，Local Optimal Procedure）。,其基本思想：运用DT三角网的空外接圆性质对两个公共边的三角形组成的四边形进行判断，如果其中一个三角形的外接圆中含有第四点，则交换四边形的对角线。,2023/3/14,21,5.1.3 三角剖分算法分类与特点,规则分布采样数据三角剖分（P68-70）,规则数据生成TIN，一般有两种方式：,1）直接将格网分解组合即可得到三角网；2）通过一定法则，选择“重要”点(very important points，VIPs)建立三角形。,根据规则数据建成的三角形格网,5.1 TIN概述,第5章 不规则三角网(TIN)的建立,2023/3/14,22,5.1.3 三角剖分算法分类与特点,规则分布采样数据三角剖分,重要点法DEM建模有两个关键步骤：1）确定格网点的“重要程度”：全局最重要或局部最重要；2）确定终止条件：达到预设的点数或预设的精度、或两者折中。目前这类算法主要有地形骨架法、地形滤波法等。,5.1 TIN概述,第5章 不规则三角网(TIN)的建立,2023/3/14,23,地形骨架法：利用地形特征点、线建立地形的骨架模型，然后对其进行插点，达到预定的精度；地表滤波法：将格网DEM看作为一幅数字图像，可使用空间高通滤波器对其滤波，保留图像中的高频信息，即为地形特征点，滤掉低频信息也即对地形特征而言不重要的点，在此基础上建立TIN模型。,2023/3/14,24,5.1.3 三角剖分算法分类与特点,从混合数据生成三角网（P70）,混合数据：是指链状数据（如断裂线、河流线等）与规则格网采样数据结合形成的一种数据。此种数据建立三角网的方法：首先分解规则三角形，然后考虑特征线上的点，在格网中生成不规则三角形。,5.1 TIN概述,第5章 不规则三角网(TIN)的建立,2023/3/14,25,5.1.3 三角剖分算法分类与特点,基于等高线采样数据三角剖分,由于数据沿等高线分布，常会出现一些不希望的现象，如三角形三顶点在同一条等高线上（称为平三角形）。对这类问题有两种处理方案：一是把等高线数据当作特征线处理，按约束DT进行剖分，一是局部优化内插增加地形特征点。,5.1 TIN概述,第5章 不规则三角网(TIN)的建立,2023/3/14,26,5.2 TIN的建立,5.2.1 无约束散点域的三角剖分算法与实现 5.2.2 约束散点数据域的三角剖分算法与实现 5.2.3 基于等高线数据的TIN的建立5.2.4 基于栅格数据的三角网建立,第5章 不规则三角网(TIN)的建立,数字高程模型,2023/3/14,27,5.2.1 无约束散点域的三角剖分算法与实现,目前散点域的三角剖分使用最为广泛的算法是Delaunay直接三角剖分算法。根据实现过程，把DT分成三类：,1）三角网生长算法2）逐点插入算法 3）分割合并算法,5.2 TIN的建立,第5章 不规则三角网(TIN)的建立,2023/3/14,28,1、三角网生长算法,三角网生长算法就是从一个“源”开始，逐步形成覆盖整个数据区域的三角网。从生长过程角度，三角网生长算法分为收缩生长算法和扩张生长算法两类。收缩生长算法是先形成整个数据域的数据边界（凸壳），并以此作为源头，逐步缩小以形成整个三角网。扩张生长算法与收缩算法过程刚好相反，是从一个三角形开始向外层层扩展，形成覆盖整个区域的三角网。,5.2 TIN的建立,第5章 不规则三角网(TIN)的建立,2023/3/14,29,1、三角网生长算法,1）递归生长算法（P78）,5.2 TIN的建立,第5章 不规则三角网(TIN)的建立,算法过程如下：在数据集中任取一点，查找距离此点最近的点，相连后作为初始基线；在初始基线右边应用Delaunay法则搜索第三点；生成Delaunay三角形，并以该三角形的两条新边作为新的基线；重复前面过程直至所有基线处理完毕；这种算法大量的时间花费在符合要求的邻域点的搜索方面，为了减少搜索时间，许多学者提出了许多不同的方法，如将数据分块并排列，以外接圆的方式限定其搜索范围。,2023/3/14,30,1,2,1,2,1,2,1,2,递归生长算法,5.2 TIN的建立,第5章 不规则三角网(TIN)的建立,3,3,3,2023/3/14,31,1、三角网生长算法,该算法的基本思路:首先找到包含数据区域的最小凸多边形，并从该多边形开始从外向里逐层形成三角形格网。平面点凸闭包的定义是包含这些平面点的最小多边形。在凸闭包中，连接任意两点的线段必须完全位于多边形内。凸闭包是数据点的自然极限边界，相当于包围数据点的最短路径。凸闭包是数据集标准Delaunay三角网的一部分。计算凸闭包是该算法的核心。,2）凸闭包收缩法,5.2 TIN的建立,第5章 不规则三角网(TIN)的建立,2023/3/14,32,1）计算凸闭包的四个顶点；2）以此四点作为基点，通过边右边最大偏移量搜索其他凸闭包顶点。,计算凸闭包的思路（P79）：,2023/3/14,33,1）将凸多边形按逆时针保存记录，以左下角点附近的顶点作为起点；2）确定第一条基边；3）构建第一个Delaunay三角形；4）重复(3)形成第一层Delaunay三角形；5）重新确定起点，重复(2)(4)完成整个区域的三角网构建。,构建三角网的具体算法（P80）：,2023/3/14,34,2、逐点插入算法（P81）：,5.2 TIN的建立,1）定义包含所有数据点的最小外界矩形范围，并以此作为最简单的凸闭包。2）按一定规则将数据区域的矩形范围进行格网划分（如限定每个格网单元的数据点数）。3）剖分数据区域的凸闭包形成两个超三角形，所有数据点都一定在这两个三角形范围内。4）对所有数据点进行循环，作如下工作（设当前处理的数据点为P）：搜寻包含点P的三角形，将P与此三角形三个顶点相连，形成三个三角形；由里到外优化整个三角网；重复以上过程直到所有点处理完毕；删除所有包含一个或多个超三角形顶点的三角形。5）处理外围三角形。,第5章 不规则三角网(TIN)的建立,2023/3/14,35,逐点插入算法,2023/3/14,36,3、分割合并算法,分割合并算法的思想很简单，首先将数据点分割成易于进行三角化的子集，然后对每个子集进行三角剖分，并用LOP算法保证三角剖分为Delaunay三角网。当每个子集剖分完成后，对每个子集的三角剖分进行合并，形成最终的整体三角网。,5.2 TIN的建立,第5章 不规则三角网(TIN)的建立,2023/3/14,37,分割合并算法,2023/3/14,38,5.2.2 约束散点数据域的三角剖分算法与实现,约束三角网（CDT）的含义 约束三角网（CDT）的性质 在已存在的Delaunay三角网中 插入约束线段,5.2 TIN的建立,第5章 不规则三角网(TIN)的建立,2023/3/14,39,5.2.2 约束散点数据域的三角剖分算法与实现,约束三角网（CDT）的含义,有不相交的地形特征线、特殊边界线等作为预先定义的限制条件作用生成TIN，则要考虑约束条件的Delaunay三角网（Constrained Delaunay Triangulation）。,5.2 TIN的建立,第5章 不规则三角网(TIN)的建立,2023/3/14,40,5.2.2 约束散点数据域的三角剖分算法与实现,带约束条件的Delaunay法则（P83）,只有当三角形外接圆内不包含任何其他点，且其三个顶点相互通视（Mutually Visible）时，此三角形才是一个带约束条件的Delaunay三角形。,5.2 TIN的建立,第5章 不规则三角网(TIN)的建立,2023/3/14,41,在已存在的Delaunay三角网中插入约束线段；具体过程如下：确定边界与约束线段相交的三角形，如果两个这样的三角形有公共边，则将此公共边删除，最后形成约束线段的影响多边形；将影响多边形其他各顶点与约束线段的起始结点相连；应用带约束条件的Delaunay优化法则，更新影响多边形内的三角网，使约束边成为三角网中的一边；重复以上步骤直到所有约束线段都加入到三角网中。,5.2.2 约束散点数据域的三角剖分算法与实现,5.2 TIN的建立,第5章 不规则三角网(TIN)的建立,约束线段插入（P83-84）,2023/3/14,42,约束线段插入过程,搜索约束线段的影响多边形,连接约束线段的起始节点和影响多边形的各个顶点,应用带约束条件的delaunay优化法则，更新影响多边形内的三角网，使约束边成为三角网中的一边,重复以上步骤直到所有约束线段都加入到三角网中。,2023/3/14,43,5.2.3 基于等高线数据的TIN的建立（P84-89）,等高线离散点直接生成TIN；将等高线作为特征线的方法；自动增加特征点及优化TIN的方法。,5.2 TIN的建立,第5章 不规则三角网(TIN)的建立,2023/3/14,44,5.2.3 基于等高线数据的TIN的建立,等高线离散点直接生成TIN方法,该方法直接将等高线离散化，然后利用常用TIN的生成算法，该方法没有考虑离散点间原有的连接关系，模拟的地形就会失真，具体表现为三角形的边穿越等高线和存在平三角形的两种情况。在实际应用中该方法较少使用。,5.2 TIN的建立,第5章 不规则三角网(TIN)的建立,2023/3/14,45,5.2.3 基于等高线数据的TIN的建立,等高线作为特征线建立TIN,将等高线作为断裂线或结构线；使用等高线上的特征点，并将等高线段作为约束线段处理。,5.2 TIN的建立,第5章 不规则三角网(TIN)的建立,2023/3/14,46,5.2.3 基于等高线数据的TIN的建立,自动增加特征点及优化TIN的方法,该方法实质仍将等高线离散化建立TIN，但采用增加特征点的方式来消除TIN中的平三角形，并使用优化TIN的方式来消除不合理的三角化；特征点的增加需要利用一定的算法自动提取，这些算法原理大都基于原始等高线的拓扑关系。,5.2 TIN的建立,第5章 不规则三角网(TIN)的建立,2023/3/14,47,5.2.4 基于栅格数据的三角网建立（P89-91）,在栅格方式下，数学形态学方法生成三角网 是一种比较好的方法；数学形态学（Mathematic Morphology）由法国统计学家Matheron和其学生Serra于1965年创立，主要用于研究数字影像形态结构特征与快速并行处理方法；数学形态学是基于集合论发展而来，通过目标影像进行形态变换来实现影像分析与识别。,5.2 TIN的建立,第5章 不规则三角网(TIN)的建立,2023/3/14,48,5.2.4 基于栅格数据的三角网建立,数学形态学方法建立TIN的一般过程,1）建立最小分辨率影像 取两点间最小距离作为栅格基本单元，将所处理区域转为一幅二值图像（参考点所在像素灰度值为1，其他像素灰度值为0）。,5.2 TIN的建立,第5章 不规则三角网(TIN)的建立,2023/3/14,49,2）形成泰森多边形 设X为参考点像素集合，则除去这些参考后的剩余部分的骨架，即为建立TIN的泰森多边形；3）形成TIN 设X为参考点集，P是X中任一参考点，将与P所在的泰森多边形相邻的泰森多边形中的参考点与P相连，即构成以P为顶点的所有三角形的边。,5.2 TIN的建立,第5章 不规则三角网(TIN)的建立,2023/3/14,50,数学形态学方法用于TIN的生成,参考点,二值化,去除参考点,提取骨架,形成泰森多边形,生成TIN,2023/3/14,51,5.3 TIN建立过程中的几个问题,周围点的提取 点在三角形中的查找 空外接圆判断准则 线段求交问题,第5章 不规则三角网(TIN)的建立,数字高程模型,2023/3/14,52,周围点的提取,给定一点，找出分布在其周围的采样点，是TIN构建过程中经常碰到的问题。一般地，利用各种空间索引方法，如四叉树，R树，B+树，排序树等可解决此类问题。对数字高程模型而言，其主要问题归结为空间位置信息的查找，利用空间对象的栅格索引机制解决这一问题比较合适。,5.3 TIN建立过程中的几个问题,第5章 不规则三角网(TIN)的建立,2023/3/14,53,点在三角形中的查找,一般将点在三角形中的查找算法称为三角形的定位问题。此类问题在逐点插入算法、TIN的高程内插，TIN的编辑，模型叠加等中也经常碰到。解决这一问题的最直接的办法就是利用计算几何中点在多边形（此处多边形为三角形）中的测试方法、拓扑关系。,5.3 TIN建立过程中的几个问题,第5章 不规则三角网(TIN)的建立,2023/3/14,54,空外接圆判断准则,在DT以及LOP优化过程中，每一个三角形都要经过空外接圆检测，空外接圆检测过程是一恒定过程，具有累积性。目前常用的方法是计算三角形外接圆的圆心和半径，然后计算圆心和其它点的距离。,5.3 TIN建立过程中的几个问题,第5章 不规则三角网(TIN)的建立,2023/3/14,55,线段求交问题,在约束CDT构建中的约束边嵌入，边界非法三角形裁剪过程中，经常要判断所给线段是否与三角形边相交。,5.3 TIN建立过程中的几个问题,第5章 不规则三角网(TIN)的建立,2023/3/14,56,思考与练习,三角剖分有哪些标准？Delaunay三角形符合哪些标准？简述递归生长算法、凸闭包收缩法、逐点插入法生成TIN的基本思路。什么是Delaunay法则法则和带约束条件的Delaunay法则？在TIN的生成中，如何考虑地形特征线？,数字高程模型,第5章 不规则三角网(TIN)的建立,2023/3/14,57,
