第五章不规则三角网TIN的建立.ppt

9/15/20241第五章第五章 不规则三角网不规则三角网(TIN)的建的建立立数字高程模型数字高程模型9/15/20242本章主要内容本章主要内容数字高程模型数字高程模型数字高程模型数字高程模型第第第第5 5章章章章 不规则三角网不规则三角网不规则三角网不规则三角网(TIN)(TIN)的建的建的建的建立立立立5.1 TIN概述概述 5.2 TIN的建立的建立 5.3 TIN建立过程中的几个问题建立过程中的几个问题 9/15/202435.1 TIN概述 Ø5.1.1 TIN的理解的理解Ø5.1.2 TIN的三角剖分准则的三角剖分准则 Ø5.1.3 三角剖分算法分类与特点三角剖分算法分类与特点 第第第第5 5章章章章 不规则三角网不规则三角网不规则三角网不规则三角网(TIN(TIN) )的建的建的建的建立立立立数字高程模型数字高程模型数字高程模型数字高程模型9/15/202445.1.1 TIN的理解的理解 ØTIN的基本概念的基本概念 不规则三角网不规则三角网（（Triangulated Irregular Network 简称简称TIN）：是用一系列互不交叉、互不重叠的连接在一起）：是用一系列互不交叉、互不重叠的连接在一起的三角形来表示地形表面。

的三角形来表示地形表面TIN既是矢量结构又有栅格既是矢量结构又有栅格的空间铺盖特征，能很好地描述和维护空间关系的空间铺盖特征，能很好地描述和维护空间关系5.1 TIN概述 第第第第5 5章章章章 不规则三角网不规则三角网不规则三角网不规则三角网(TIN)(TIN)的建的建的建的建立立立立9/15/20245T：：三角化（三角化（ Triangulated ）是离散数据的三角剖分过）是离散数据的三角剖分过程，也是程，也是TIN的建立过程位于三角形内的任意一点的的建立过程位于三角形内的任意一点的高程值均可以通过三角形平面方程唯一确定高程值均可以通过三角形平面方程唯一确定I：：不规则性（不规则性（ Irregular ），指用来构建），指用来构建TIN的采样点的采样点的分布形式的分布形式TIN具有可变分辨率，比格网具有可变分辨率，比格网DEM能更能更好反映地形起伏好反映地形起伏N：：网（网（ Network ），表达整个区域的三角形分布形态，），表达整个区域的三角形分布形态，即三角形之间不能交叉和重叠三角形之间的拓扑关即三角形之间不能交叉和重叠三角形之间的拓扑关系隐含其中系隐含其中。

5.1 TIN概述 第第第第5 5章章章章 不规则三角网不规则三角网不规则三角网不规则三角网(TIN(TIN) )的建的建的建的建立立立立9/15/202465.1.1 TIN的理解的理解 ØTIN的基本元素的基本元素l节点（节点（Node）：）：是相邻三角形的公共顶点，也是用来构是相邻三角形的公共顶点，也是用来构建建TIN的采样数据；的采样数据；l边（边（Edge）：）：指两个三角形的公共边界，是指两个三角形的公共边界，是TIN不光滑不光滑性的具体反映边同时还包含特征线、断裂线以及区域边性的具体反映边同时还包含特征线、断裂线以及区域边界l面（面（Face）：）：由最近的三个节点所组成的三角形面，是由最近的三个节点所组成的三角形面，是TIN描述地形表面的基本单元描述地形表面的基本单元TIN中的每一个三角形都描中的每一个三角形都描述了局部地形倾斜状态，具有唯一的坡度值三角形在公述了局部地形倾斜状态，具有唯一的坡度值三角形在公共节点和边上是无缝的，或者说三角形不能交叉和重叠共节点和边上是无缝的，或者说三角形不能交叉和重叠5.1 TIN概述 第第第第5 5章章章章 不规则三角网不规则三角网不规则三角网不规则三角网(TIN(TIN) )的建的建的建的建立立立立9/15/20247z节点节点x边边面面yTIN的基本元素的基本元素5.1 TIN概述 第第第第5 5章章章章 不规则三角网不规则三角网不规则三角网不规则三角网(TIN)(TIN)的建的建的建的建立立立立9/15/202485.1.1 TIN的理解的理解 Ø数据和数据和TIN的类型的类型l用来进行用来进行TIN构建的原始数据根据数据点之间的约束构建的原始数据根据数据点之间的约束条件可分为条件可分为无约束数据域无约束数据域和和约束数据域约束数据域两种类型。

两种类型 l无约束数据域无约束数据域是指数据点之间不存在任何关系，即数是指数据点之间不存在任何关系，即数据分布完全呈离散状态，数据点之间在物理上相互独据分布完全呈离散状态，数据点之间在物理上相互独立l约束数据约束数据域域则是部分数据点之间存在着某种联系，这则是部分数据点之间存在着某种联系，这种联系一般通过线性特征来维护，如地形数据中的山种联系一般通过线性特征来维护，如地形数据中的山脊线、山谷线上的点等脊线、山谷线上的点等 5.1 TIN概述 第第第第5 5章章章章 不规则三角网不规则三角网不规则三角网不规则三角网(TIN(TIN) )的建的建的建的建立立立立9/15/202495.1.1 TIN的理解的理解 ØTIN的体系结构的体系结构 TIN对三角形的几何形状有严格的要求对三角形的几何形状有严格的要求 TIN模型一般有三个基本要求：模型一般有三个基本要求：1）三角形的格网唯一；）三角形的格网唯一；2）最佳三角形形状，尽量接近正三角形；）最佳三角形形状，尽量接近正三角形；3）三角形边长之和最小，保证最近的点形成）三角形边长之和最小，保证最近的点形成 三角形。

三角形5.1 TIN概述 第第第第5 5章章章章 不规则三角网不规则三角网不规则三角网不规则三角网(TIN(TIN) )的建的建的建的建立立立立9/15/2024105.1.1 TIN的理解的理解 ØTIN的体系结构的体系结构 良好的数据结构和三角形剖分准则，必须良好的数据结构和三角形剖分准则，必须由高效的算法和程序实现由高效的算法和程序实现5.1 TIN概述 第第第第5 5章章章章 不规则三角网不规则三角网不规则三角网不规则三角网(TIN)(TIN)的建的建的建的建立立立立面结构、点结面结构、点结构、点面结构、构、点面结构、边结构、边面边结构、边面结构结构9/15/2024115.1.2 TIN的三角剖分准则的三角剖分准则 l TIN的三角剖分准则是指的三角剖分准则是指TIN中三角形的中三角形的形成法则，它决定着三角形的几何形状和形成法则，它决定着三角形的几何形状和TIN的质量l 目前，在目前，在GIS、计算机和图形学领域常用、计算机和图形学领域常用的三角剖分准则有的三角剖分准则有6种5.1 TIN概述 第第第第5 5章章章章 不规则三角网不规则三角网不规则三角网不规则三角网(TIN(TIN) )的建的建的建的建立立立立9/15/2024125.1.2 TIN的三角剖分准则的三角剖分准则 5.1 TIN概述 第第第第5 5章章章章 不规则三角网不规则三角网不规则三角网不规则三角网(TIN(TIN) )的建的建的建的建立立立立空外接圆准则：空外接圆准则：在在TIN中，过每个三角形的外接圆均不包含点集的中，过每个三角形的外接圆均不包含点集的其余任何点；其余任何点；最大最小角准则：最大最小角准则：在在TIN中的两相邻三角形形成的凸四边形中，这中的两相邻三角形形成的凸四边形中，这两三角形中的最小内角一定大于交换凸四边形对角线后所形成的两三角两三角形中的最小内角一定大于交换凸四边形对角线后所形成的两三角形的最小内角；形的最小内角；最短距离和准则：最短距离和准则：指一点到基边的两端的距离和为最小。

指一点到基边的两端的距离和为最小9/15/202413张角最大准则：张角最大准则：一点到基边的张角为最大一点到基边的张角为最大面积比准则：面积比准则：三角形内切圆面积与三角形面积或三角形面积与周长三角形内切圆面积与三角形面积或三角形面积与周长平方之比最小平方之比最小 对角线准则：对角线准则：两三角形组成的凸四边形的两条对角线之比这一准两三角形组成的凸四边形的两条对角线之比这一准则的比值限定值，须给定，即当计算值超过限定值才进行优化则的比值限定值，须给定，即当计算值超过限定值才进行优化5.1 TIN概述 第第第第5 5章章章章 不规则三角网不规则三角网不规则三角网不规则三角网(TIN(TIN) )的建的建的建的建立立立立5.1.2 TIN的三角剖分准则的三角剖分准则 9/15/202414l1）三角形准则是建立三角形格网的基本原则，应）三角形准则是建立三角形格网的基本原则，应用不同的准则将会得到不同的三角网用不同的准则将会得到不同的三角网l2）一般而言，应尽量保持三角网的唯一性，即在）一般而言，应尽量保持三角网的唯一性，即在同一准则下由不同的位置开始建立三角形格网，其最同一准则下由不同的位置开始建立三角形格网，其最终的形状和结构应是相同的终的形状和结构应是相同的。

l3）空外接圆准则、最大最小角准则下进行的三角）空外接圆准则、最大最小角准则下进行的三角剖分称为剖分称为Delaunay (译为狄洛尼或德劳内译为狄洛尼或德劳内)三角剖分三角剖分（（Triangulation）），简称，简称DT空外接圆准则也叫空外接圆准则也叫Delaunay法则说明：说明：5.1 TIN概述 第第第第5 5章章章章 不规则三角网不规则三角网不规则三角网不规则三角网(TIN)(TIN)的建的建的建的建立立立立9/15/202415•关于关于delaunay三角网三角网•Dirichlet （（1850年）和年）和Voronoi （（1908年）最早讨论空年）最早讨论空间散点的关系问题间散点的关系问题•Voronoi图的定义（图的定义（P105））–Voronoi图把平面分成图把平面分成N个区，每一个区包括一个点，该点所个区，每一个区包括一个点，该点所在的区域是距离该点最近的点的集合在的区域是距离该点最近的点的集合5.1 TIN概述 第第第第5 5章章章章 不规则三角网不规则三角网不规则三角网不规则三角网(TIN)(TIN)的建的建的建的建立立立立9/15/202416•关于关于delaunay三角网三角网•1934年年Delaunay提出了提出了Voronoi图的对称图，即图的对称图，即Delaunay三角网（用直线段连接两个相邻多边形内的离三角网（用直线段连接两个相邻多边形内的离散点而生成的三角网）。

散点而生成的三角网）–Delaunay三角网的特性：三角网的特性：•不存在四点共圆；不存在四点共圆；•每个三角形对应于一个每个三角形对应于一个Voronoi图顶点；图顶点；•每个三角形边对应于一个每个三角形边对应于一个Voronoi图边；图边；•每个结点对应于一个每个结点对应于一个Voronoi图区域；图区域；•Delaunay图的边界是一个凸壳；图的边界是一个凸壳；•三角网中三角形的最小角最大三角网中三角形的最小角最大5.1 TIN概述 第第第第5 5章章章章 不规则三角网不规则三角网不规则三角网不规则三角网(TIN)(TIN)的建的建的建的建立立立立9/15/2024175.1.3 三角剖分算法分类与特点三角剖分算法分类与特点 Ø 不规则分布采样数据三角剖分不规则分布采样数据三角剖分 Ø 规则分布采样数据三角剖分规则分布采样数据三角剖分Ø 从混合数据生成三角网从混合数据生成三角网Ø 基于等高线采样数据三角剖分基于等高线采样数据三角剖分 5.1 TIN概述 第第第第5 5章章章章 不规则三角网不规则三角网不规则三角网不规则三角网(TIN(TIN) )的建的建的建的建立立立立9/15/2024185.1.3 三角剖分算法分类与特点三角剖分算法分类与特点 Ø 不规则分布采样数据三角剖分（不规则分布采样数据三角剖分（P64-67）） 在目前所有的三角化算法中，以在目前所有的三角化算法中，以Delaunay三角网的应三角网的应用最为广泛。

用最为广泛Delaunay 三角网为相互邻接且互不重叠的三角形的集三角网为相互邻接且互不重叠的三角形的集合，每一个三角形的外接圆内不包含其它的点合，每一个三角形的外接圆内不包含其它的点DT的主要特点是它能自动地避免狭长的三角形，保证的主要特点是它能自动地避免狭长的三角形，保证了良好的三角形形状了良好的三角形形状DT的两个显著特性的两个显著特性最大最小角最大最小角特性特性和和空外接圆特性空外接圆特性是构成各种是构成各种DT剖分的基础剖分的基础5.1 TIN概述 第第第第5 5章章章章 不规则三角网不规则三角网不规则三角网不规则三角网(TIN)(TIN)的建的建的建的建立立立立9/15/202419 新插入点与已知三角网存在四种关系（新插入点与已知三角网存在四种关系（P66）：　）：　（（a）在三角形内）在三角形内（（b）在三角形外接圆内）在三角形外接圆内（（c）在三角形外接圆上）在三角形外接圆上（（d）在三角形外接圆外）在三角形外接圆外9/15/202420局部几何形状最优，采用局部几何形状最优，采用LOP算法算法（局部优化过程，（局部优化过程，Local Optimal Procedure）。

　）　其基本思想：运其基本思想：运用用DT三角网的空三角网的空外接圆性质对两外接圆性质对两个公共边的三角个公共边的三角形组成的四边形形组成的四边形进行判断，如果进行判断，如果其中一个三角形其中一个三角形的外接圆中含有的外接圆中含有第四点，则交换第四点，则交换四边形的对角线四边形的对角线 　　9/15/2024215.1.3 三角剖分算法分类与特点三角剖分算法分类与特点 Ø 规则分布采样数据三角剖分规则分布采样数据三角剖分（（P68-70）） l规则数据生成规则数据生成TIN，一般有两种方式：，一般有两种方式：1）直接将格网分解组合即可得到三角网；）直接将格网分解组合即可得到三角网； 2）通过一定法则，选择）通过一定法则，选择“重要重要”点点( very important points，，VIPs )建立三角形建立三角形根据规则数据建成的三角形格网根据规则数据建成的三角形格网5.1 TIN概述 第第第第5 5章章章章 不规则三角网不规则三角网不规则三角网不规则三角网(TIN)(TIN)的建的建的建的建立立立立9/15/2024225.1.3 三角剖分算法分类与特点三角剖分算法分类与特点 Ø 规则分布采样数据三角剖分规则分布采样数据三角剖分l 重要点法重要点法DEM建模有两个关键步骤：建模有两个关键步骤： 1）确定格网点的）确定格网点的“重要程度重要程度”：全局最重要或局：全局最重要或局部最重要；部最重要； 2）确定终止条件：达到预设的点数或预设的精度、）确定终止条件：达到预设的点数或预设的精度、或两者折中。

或两者折中l目前这类算法主要有目前这类算法主要有地形骨架法、地形滤波法地形骨架法、地形滤波法等等5.1 TIN概述 第第第第5 5章章章章 不规则三角网不规则三角网不规则三角网不规则三角网(TIN)(TIN)的建的建的建的建立立立立9/15/202423•地形骨架法：–利用地形特征点、线建立地形的骨架模型，然后对其进行插点，达到预定的精度；•地表滤波法：–将格网DEM看作为一幅数字图像，可使用空间高通滤波器对其滤波，保留图像中的高频信息，即为地形特征点，滤掉低频信息也即对地形特征而言不重要的点，在此基础上建立TIN模型9/15/2024245.1.3 三角剖分算法分类与特点三角剖分算法分类与特点 Ø从混合数据生成三角网从混合数据生成三角网（（P70）） l 混合数据：是指链状数据混合数据：是指链状数据（如断裂线、河流线等）与规（如断裂线、河流线等）与规则格网采样数据结合形成的一则格网采样数据结合形成的一种数据l 此种数据建立三角网的方法：此种数据建立三角网的方法：首先分解规则三角形，然后考首先分解规则三角形，然后考虑特征线上的点，在格网中生虑特征线上的点，在格网中生成不规则三角形。

成不规则三角形5.1 TIN概述 第第第第5 5章章章章 不规则三角网不规则三角网不规则三角网不规则三角网(TIN(TIN) )的建的建的建的建立立立立9/15/2024255.1.3 三角剖分算法分类与特点三角剖分算法分类与特点 Ø基于等高线采样数据三角剖分基于等高线采样数据三角剖分l 由于数据沿等高线分布，常会出现一些不希望的现由于数据沿等高线分布，常会出现一些不希望的现象，如三角形三顶点在同一条等高线上（称为象，如三角形三顶点在同一条等高线上（称为平三角平三角形形）l对这类问题有两种处理方案：一是把等高线数据当对这类问题有两种处理方案：一是把等高线数据当作特征线处理，按约束作特征线处理，按约束DT进行剖分，一是局部优化进行剖分，一是局部优化内插增加地形特征点内插增加地形特征点5.1 TIN概述 第第第第5 5章章章章 不规则三角网不规则三角网不规则三角网不规则三角网(TIN(TIN) )的建的建的建的建立立立立9/15/2024265.2 TIN的建立 Ø5.2.1 无约束散点域的三角剖分算法与实现无约束散点域的三角剖分算法与实现 Ø5.2.2 约束散点数据域的三角剖分算法与实现约束散点数据域的三角剖分算法与实现 Ø5.2.3 基于等高线数据的基于等高线数据的TIN的建立的建立Ø5.2.4 基于栅格数据的三角网建立基于栅格数据的三角网建立第第第第5 5章章章章 不规则三角网不规则三角网不规则三角网不规则三角网(TIN(TIN) )的建的建的建的建立立立立数字高程模型数字高程模型数字高程模型数字高程模型9/15/2024275.2.1 无约束散点域的三角剖分算法与实现无约束散点域的三角剖分算法与实现 l 目前散点域的三角剖分使用最为广泛的算法是目前散点域的三角剖分使用最为广泛的算法是Delaunay直接三角剖分算法。

直接三角剖分算法l 根据实现过程，把根据实现过程，把DT分成三类：分成三类：1）三角网生长）三角网生长算法算法2）逐点插入算法）逐点插入算法 3））分割合并算法分割合并算法5.2 TIN的建立 第第第第5 5章章章章 不规则三角网不规则三角网不规则三角网不规则三角网(TIN)(TIN)的建的建的建的建立立立立9/15/2024281、三角网生长算法、三角网生长算法l 三角网生长算法就是从一个三角网生长算法就是从一个“源源”开始，逐步形成开始，逐步形成覆盖整个数据区域的三角网覆盖整个数据区域的三角网l 从生长过程角度，三角网生长算法分为从生长过程角度，三角网生长算法分为收缩生长算收缩生长算法法和和扩张生长算法扩张生长算法两类l 收缩生长算法是先形成整个数据域的数据边界（凸收缩生长算法是先形成整个数据域的数据边界（凸壳），并以此作为源头，逐步缩小以形成整个三角网壳），并以此作为源头，逐步缩小以形成整个三角网l 扩张生长算法与收缩算法过程刚好相反，是从一个扩张生长算法与收缩算法过程刚好相反，是从一个三角形开始向外层层扩展，形成覆盖整个区域的三角三角形开始向外层层扩展，形成覆盖整个区域的三角网。

网5.2 TIN的建立 第第第第5 5章章章章 不规则三角网不规则三角网不规则三角网不规则三角网(TIN(TIN) )的建的建的建的建立立立立9/15/2024291、三角网生长算法、三角网生长算法1）递归生长算法（）递归生长算法（P78））5.2 TIN的建立的建立 第第第第5 5章章章章 不规则三角网不规则三角网不规则三角网不规则三角网(TIN)(TIN)的建的建的建的建立立立立•算法过程如下：–在数据集中任取一点，查找距离此点最近的点，相连后作为初始基线；–在初始基线右边应用Delaunay法则搜索第三点；–生成Delaunay三角形，并以该三角形的两条新边作为新的基线；–重复前面过程直至所有基线处理完毕；•这种算法大量的时间花费在符合要求的邻域点的搜索方面，为了减少搜索时间，许多学者提出了许多不同的方法，如将数据分块并排列，以外接圆的方式限定其搜索范围9/15/20243012121212递归生长算法递归生长算法5.2 TIN的建立 第第第第5 5章章章章 不规则三角网不规则三角网不规则三角网不规则三角网(TIN(TIN) )的建的建的建的建立立立立3339/15/2024311、三角网生长算法、三角网生长算法l该算法的基本思路该算法的基本思路:首先找到包含数据区域的最小凸多边首先找到包含数据区域的最小凸多边形，并从该多边形开始从外向里逐层形成三角形格网。

形，并从该多边形开始从外向里逐层形成三角形格网l平面点平面点凸闭包凸闭包的定义是包含这些平面点的最小多边形的定义是包含这些平面点的最小多边形l在凸闭包中，连接任意两点的线段必须完全位于多边形在凸闭包中，连接任意两点的线段必须完全位于多边形内凸闭包是数据点的自然极限边界，相当于包围数据内凸闭包是数据点的自然极限边界，相当于包围数据点的最短路径点的最短路径l凸闭包是数据集标准凸闭包是数据集标准Delaunay三角网的一部分计算凸三角网的一部分计算凸闭包是该算法的核心闭包是该算法的核心2）凸闭包收缩法）凸闭包收缩法5.2 TIN的建立 第第第第5 5章章章章 不规则三角网不规则三角网不规则三角网不规则三角网(TIN(TIN) )的建的建的建的建立立立立9/15/2024321）计算凸闭包的四个顶点；）计算凸闭包的四个顶点；2）以此四点作为基点，通过边右边最大偏移量搜索其他凸）以此四点作为基点，通过边右边最大偏移量搜索其他凸闭包顶点闭包顶点计算凸闭包的思路（计算凸闭包的思路（P79）：）：9/15/2024331）将凸多边形按逆时针保存记录，以左下角点附近的顶点作为）将凸多边形按逆时针保存记录，以左下角点附近的顶点作为起点；起点；2）确定第一条基边；）确定第一条基边；3）构建第一个）构建第一个Delaunay三角形；三角形；4）重复）重复(3)形成第一层形成第一层Delaunay三角形；三角形；5）重新确定起点，重复）重新确定起点，重复(2)~(4)完成整个区域的三角网构建。

完成整个区域的三角网构建构建三角网的具体算法构建三角网的具体算法（（P80）：）：9/15/2024342、逐点插入算法、逐点插入算法 （（P81）：）：5.2 TIN的建立的建立 •1）定义包含所有数据点的最小外界矩形范围，并以此作）定义包含所有数据点的最小外界矩形范围，并以此作为最简单的凸闭包为最简单的凸闭包•2）按一定规则将数据区域的矩形范围进行格网划分（如）按一定规则将数据区域的矩形范围进行格网划分（如限定每个格网单元的数据点数）限定每个格网单元的数据点数）•3）剖分数据区域的凸闭包形成两个超三角形，所有数据）剖分数据区域的凸闭包形成两个超三角形，所有数据点都一定在这两个三角形范围内点都一定在这两个三角形范围内•4）对所有数据点进行循环，作如下工作（设当前处理的）对所有数据点进行循环，作如下工作（设当前处理的数据点为数据点为P）：）：–搜寻包含点P的三角形，将P与此三角形三个顶点相连，形成三个三角形；–由里到外优化整个三角网；–重复以上过程直到所有点处理完毕；–删除所有包含一个或多个超三角形顶点的三角形•5）处理外围三角形处理外围三角形第第第第5 5章章章章 不规则三角网不规则三角网不规则三角网不规则三角网(TIN)(TIN)的建的建的建的建立立立立9/15/202435逐点插入算法逐点插入算法9/15/2024363、分割合并算法、分割合并算法 分割合并算法的思想很简单，首先将数据点分割分割合并算法的思想很简单，首先将数据点分割成易于进行三角化的子集，然后对每个子集进行三成易于进行三角化的子集，然后对每个子集进行三角剖分，并用角剖分，并用LOP算法保证三角剖分为算法保证三角剖分为Delaunay三三角网。

当每个子集剖分完成后，对每个子集的三角角网当每个子集剖分完成后，对每个子集的三角剖分进行合并，形成最终的整体三角网剖分进行合并，形成最终的整体三角网 5.2 TIN的建立 第第第第5 5章章章章 不规则三角网不规则三角网不规则三角网不规则三角网(TIN)(TIN)的建的建的建的建立立立立9/15/202437分割合并算法分割合并算法9/15/2024385.2.2 约束散点数据域的三角剖分算法与实现约束散点数据域的三角剖分算法与实现 Ø 约束三角网（约束三角网（CDT）的含义）的含义 Ø 约束三角网（约束三角网（CDT）的性质）的性质Ø 在已存在的在已存在的Delaunay三角网中三角网中 插入约束线段插入约束线段5.2 TIN的建立 第第第第5 5章章章章 不规则三角网不规则三角网不规则三角网不规则三角网(TIN)(TIN)的建的建的建的建立立立立9/15/2024395.2.2 约束散点数据域的三角剖分算法与实现约束散点数据域的三角剖分算法与实现 Ø 约束三角网（约束三角网（CDT）的含义）的含义 有不相交的地形特征线、特殊边界线等作为预有不相交的地形特征线、特殊边界线等作为预先定义的限制条件作用生成先定义的限制条件作用生成TIN，则要考虑约束条，则要考虑约束条件的件的Delaunay三角网（三角网（Constrained Delaunay Triangulation ）。

5.2 TIN的建立 第第第第5 5章章章章 不规则三角网不规则三角网不规则三角网不规则三角网(TIN)(TIN)的建的建的建的建立立立立9/15/2024405.2.2 约束散点数据域的三角剖分算法与实现约束散点数据域的三角剖分算法与实现 Ø 带约束条件的带约束条件的Delaunay法则（法则（P83））u只有当三角形外接圆内不包含任何其他点，且只有当三角形外接圆内不包含任何其他点，且其三个顶点相互通视（其三个顶点相互通视（Mutually Visible）时，此）时，此三角形才是一个带约束条件的三角形才是一个带约束条件的Delaunay三角形5.2 TIN的建立 第第第第5 5章章章章 不规则三角网不规则三角网不规则三角网不规则三角网(TIN)(TIN)的建的建的建的建立立立立9/15/202441–在已存在的在已存在的Delaunay三角网中插入约束线段；三角网中插入约束线段；具体过程如下：具体过程如下：•确定边界与确定边界与约束线段约束线段相交的三角形，如果两个这样的相交的三角形，如果两个这样的三角形有公共边，则将此公共边删除，最后形成约束三角形有公共边，则将此公共边删除，最后形成约束线段的线段的影响多边形影响多边形；；•将将影响多边形影响多边形其他各顶点与其他各顶点与约束线段约束线段的起始结点相连；的起始结点相连；•应用带约束条件的应用带约束条件的Delaunay优化法则，更新优化法则，更新影响多影响多边形边形内的三角网，使约束边成为三角网中的一边；内的三角网，使约束边成为三角网中的一边；•重复以上步骤直到所有重复以上步骤直到所有约束线段约束线段都加入到三角网中。

都加入到三角网中5.2.2 约束散点数据域的三角剖分算法与实现约束散点数据域的三角剖分算法与实现 5.2 TIN的建立 第第第第5 5章章章章 不规则三角网不规则三角网不规则三角网不规则三角网(TIN)(TIN)的建的建的建的建立立立立Ø 约束约束线段插入（线段插入（P83-84））9/15/202442约束线段插入过程约束线段插入过程搜索约束线段的影响多边形搜索约束线段的影响多边形连接约束线段的起始连接约束线段的起始节点和影响多边形的节点和影响多边形的各个顶点各个顶点应用带约束条件的应用带约束条件的delaunay优优化法则，更新化法则，更新影响多边形影响多边形内的内的三角网，使约束边成为三角网三角网，使约束边成为三角网中的一边中的一边重复以上步骤直到所重复以上步骤直到所有有约束线段约束线段都加入到都加入到三角网中三角网中9/15/2024435.2.3 基于等高线数据的基于等高线数据的TIN的建立（的建立（P84-89））Ø 等高线离散点直接生成等高线离散点直接生成TIN；；Ø 将等高线作为特征线的方法；将等高线作为特征线的方法；Ø 自动增加特征点及优化自动增加特征点及优化TIN的方法。

的方法5.2 TIN的建立 第第第第5 5章章章章 不规则三角网不规则三角网不规则三角网不规则三角网(TIN)(TIN)的建的建的建的建立立立立9/15/2024445.2.3 基于等高线数据的基于等高线数据的TIN的建立的建立等高线离散点直接生成等高线离散点直接生成TIN方法方法 l 该方法直接将等高线离散化，然后利用常用该方法直接将等高线离散化，然后利用常用TIN的生成的生成算法，该方法没有考虑离散点间原有的连接关系，模拟的算法，该方法没有考虑离散点间原有的连接关系，模拟的地形就会失真，具体表现为地形就会失真，具体表现为三角形的边穿越等高线三角形的边穿越等高线和存在和存在平三角形平三角形的两种情况的两种情况 l 在实际应用中该方法较少使用在实际应用中该方法较少使用5.2 TIN的建立 第第第第5 5章章章章 不规则三角网不规则三角网不规则三角网不规则三角网(TIN(TIN) )的建的建的建的建立立立立9/15/2024455.2.3 基于等高线数据的基于等高线数据的TIN的建立的建立等高线作为特征线建立等高线作为特征线建立TIN l将等高线作为断将等高线作为断裂线或结构线；裂线或结构线；l使用等高线上的使用等高线上的特征点，并将等高特征点，并将等高线段作为约束线段线段作为约束线段处理。

处理5.2 TIN的建立 第第第第5 5章章章章 不规则三角网不规则三角网不规则三角网不规则三角网(TIN(TIN) )的建的建的建的建立立立立9/15/2024465.2.3 基于等高线数据的基于等高线数据的TIN的建立的建立自动增加特征点及优化自动增加特征点及优化TIN的方法的方法l 该方法实质仍将等高线该方法实质仍将等高线离散化建立离散化建立TIN，但采用，但采用增加特征点的方式来消除增加特征点的方式来消除TIN中的平三角形，并使中的平三角形，并使用优化用优化TIN的方式来消除的方式来消除不合理的三角化；不合理的三角化；l特征点的增加需要利用特征点的增加需要利用一定的算法自动提取，这一定的算法自动提取，这些算法原理大都基于原始些算法原理大都基于原始等高线的拓扑关系等高线的拓扑关系5.2 TIN的建立 第第第第5 5章章章章 不规则三角网不规则三角网不规则三角网不规则三角网(TIN(TIN) )的建的建的建的建立立立立9/15/2024475.2.4 基于栅格数据的三角网建立（基于栅格数据的三角网建立（P89-91））l 在栅格方式下，数学形态学方法生成三角网在栅格方式下，数学形态学方法生成三角网 是一种比较好的方法；是一种比较好的方法；l数学形态学（数学形态学（Mathematic Morphology）由法）由法国统计学家国统计学家Matheron和其学生和其学生Serra于于1965年创年创立，主要用于研究数字影像形态结构特征与快立，主要用于研究数字影像形态结构特征与快速并行处理方法；速并行处理方法； l 数学形态学是基于集合论发展而来，通过目标数学形态学是基于集合论发展而来，通过目标影像进行形态变换来实现影像分析与识别。

影像进行形态变换来实现影像分析与识别5.2 TIN的建立 第第第第5 5章章章章 不规则三角网不规则三角网不规则三角网不规则三角网(TIN)(TIN)的建的建的建的建立立立立9/15/2024485.2.4 基于栅格数据的三角网建立基于栅格数据的三角网建立Ø数学形态学方法建立数学形态学方法建立TIN的一般过程的一般过程 1）建立最小分辨率影像）建立最小分辨率影像 取两点间最小距离作为栅格基本单元，将所处理取两点间最小距离作为栅格基本单元，将所处理区域转为一幅二值图像（参考点所在像素灰度值为区域转为一幅二值图像（参考点所在像素灰度值为1，，其他像素灰度值为其他像素灰度值为0） 5.2 TIN的建立 第第第第5 5章章章章 不规则三角网不规则三角网不规则三角网不规则三角网(TIN(TIN) )的建的建的建的建立立立立9/15/2024492）） 形成泰森多边形形成泰森多边形 设设X为参考点像素集合，则除去这些参考后的剩余部为参考点像素集合，则除去这些参考后的剩余部分的骨架，即为建立分的骨架，即为建立TIN的泰森多边形；的泰森多边形； 3）） 形成形成TIN 设设X为参考点集，为参考点集，P是是X中任一参考点，将与中任一参考点，将与P所在的所在的泰森多边形相邻的泰森多边形中的参考点与泰森多边形相邻的泰森多边形中的参考点与P相连，即相连，即构成以构成以P为顶点的所有三角形的边。

为顶点的所有三角形的边 5.2 TIN的建立 第第第第5 5章章章章 不规则三角网不规则三角网不规则三角网不规则三角网(TIN(TIN) )的建的建的建的建立立立立9/15/202450数学形态学方法用于数学形态学方法用于TINTIN的生成的生成参考点参考点二值化二值化去除参考点去除参考点提取骨架提取骨架形成泰森形成泰森多边形多边形生成生成TIN9/15/2024515.3 TIN建立过程中的几个问题 Ø 周围点的提取周围点的提取 Ø 点在三角形中的查找点在三角形中的查找Ø 空外接圆判断准则空外接圆判断准则Ø 线段求交问题线段求交问题第第第第5 5章章章章 不规则三角网不规则三角网不规则三角网不规则三角网(TIN)(TIN)的建的建的建的建立立立立数字高程模型数字高程模型数字高程模型数字高程模型9/15/202452Ø 周围点的提取周围点的提取 l给定一点，找出分布在其周围的采样点，是给定一点，找出分布在其周围的采样点，是TIN构构建过程中经常碰到的问题建过程中经常碰到的问题l一般地，利用各种空间索引方法，如四叉树，一般地，利用各种空间索引方法，如四叉树，R树，树，B+树，排序树等可解决此类问题。

树，排序树等可解决此类问题l对数字高程模型而言，其主要问题归结为空间位置对数字高程模型而言，其主要问题归结为空间位置信息的查找，利用空间对象的栅格索引机制解决这一信息的查找，利用空间对象的栅格索引机制解决这一问题比较合适问题比较合适5.3 TIN建立过程中的几个问题 第第第第5 5章章章章 不规则三角网不规则三角网不规则三角网不规则三角网(TIN(TIN) )的建的建的建的建立立立立9/15/202453Ø点在三角形中的查找点在三角形中的查找l一般将点在三角形中的查找算法称为三角形的定位问一般将点在三角形中的查找算法称为三角形的定位问题此类问题在逐点插入算法、题此类问题在逐点插入算法、TIN的高程内插，的高程内插，TIN的编辑，模型叠加等中也经常碰到的编辑，模型叠加等中也经常碰到l解决这一问题的最直接的办法就是利用计算几何中点解决这一问题的最直接的办法就是利用计算几何中点在多边形（此处多边形为三角形）中的测试方法、拓扑在多边形（此处多边形为三角形）中的测试方法、拓扑关系5.3 TIN建立过程中的几个问题 第第第第5 5章章章章 不规则三角网不规则三角网不规则三角网不规则三角网(TIN(TIN) )的建的建的建的建立立立立9/15/202454Ø 空外接圆判断准则空外接圆判断准则l在在DT以及以及LOP优化过程中，每一个三角形都优化过程中，每一个三角形都要经过空外接圆检测，空外接圆检测过程是一要经过空外接圆检测，空外接圆检测过程是一恒定过程，具有累积性。

恒定过程，具有累积性l目前常用的方法是计算三角形外接圆的圆心和目前常用的方法是计算三角形外接圆的圆心和半径，然后计算圆心和其它点的距离半径，然后计算圆心和其它点的距离5.3 TIN建立过程中的几个问题 第第第第5 5章章章章 不规则三角网不规则三角网不规则三角网不规则三角网(TIN)(TIN)的建的建的建的建立立立立9/15/202455Ø 线段求交问题线段求交问题l 在约束在约束CDT构建中的约束边嵌入，边界非法构建中的约束边嵌入，边界非法三角形裁剪过程中，经常要判断所给线段是否三角形裁剪过程中，经常要判断所给线段是否与三角形边相交与三角形边相交 5.3 TIN建立过程中的几个问题 第第第第5 5章章章章 不规则三角网不规则三角网不规则三角网不规则三角网(TIN)(TIN)的建的建的建的建立立立立9/15/202456思考与练习思考与练习•三角剖分有哪些标准？Delaunay三角形符合哪些标准？•简述递归生长算法、凸闭包收缩法、逐点插入法生成TIN的基本思路•什么是Delaunay法则法则和带约束条件的Delaunay法则？•在TIN的生成中，如何考虑地形特征线？数字高程模型数字高程模型数字高程模型数字高程模型第第第第5 5章章章章 不规则三角网不规则三角网不规则三角网不规则三角网(TIN)(TIN)的建的建的建的建立立立立9/15/2024579/15/202458。