chapter5 不规则三角网tim建模

1、5.1 概述概述 1 TIN的概念：的概念： （1）基本概念：基于不规则三角网的数字）基本概念：基于不规则三角网的数字高程模型（高程模型（Based on Triangulated Irregular Network DEM，简写为，简写为 Based on TIN DEM，俗称，俗称TIN）就是用一系列互）就是用一系列互不交叉、互不重叠的连接在一起的三角形不交叉、互不重叠的连接在一起的三角形来表示地形表面。来表示地形表面。TIN既是矢量结构又有栅既是矢量结构又有栅格的空间铺盖特征，能很好地描述和维护格的空间铺盖特征，能很好地描述和维护空间关系。空间关系。 T：三角化（三角化（ Triangu

2、lated ）是离散数据的三角剖分过）是离散数据的三角剖分过程，也是程，也是TIN的建立过程。位于三角形内的任意一点的建立过程。位于三角形内的任意一点的高程值均可以通过三角形平面方程唯一确定。的高程值均可以通过三角形平面方程唯一确定。I：不规则性（不规则性（ Irregular ），指用来构建），指用来构建TIN的采样点的采样点的分布形式。的分布形式。TIN具有可变分辨率，比格网具有可变分辨率，比格网DEM能更能更好反映地形起伏。好反映地形起伏。N：网（网（ Network ），表达整个区域的三角形分布形），表达整个区域的三角形分布形态，即三角形之间不能交叉和重叠。三角形之间的拓态，即三角形之

3、间不能交叉和重叠。三角形之间的拓扑关系隐含其中。扑关系隐含其中。 （2）TIN的基本元素的基本元素 节点（节点（Node）：是相邻三角形的公共顶点，也是）：是相邻三角形的公共顶点，也是用来构建用来构建TIN的采样数据的采样数据 边（边（Edge）：指两个三角形公共边界，是）：指两个三角形公共边界，是TIN不光不光滑性的具体反映。边同时还包含特征线、断裂线以滑性的具体反映。边同时还包含特征线、断裂线以及区域边界及区域边界 面（面（Face）：由最近的三个节点所组成的三角形）：由最近的三个节点所组成的三角形面，是面，是TIN描述地形表面的基本单元。描述地形表面的基本单元。TIN中的每中的每一个三角

4、形都描述了局部地形倾斜状态，具有唯一一个三角形都描述了局部地形倾斜状态，具有唯一的坡度值。三角形在公共节点和边上是无缝的，或的坡度值。三角形在公共节点和边上是无缝的，或者说三角形不能交叉和重叠。者说三角形不能交叉和重叠。 （3）数据和）数据和TIN的类型的类型 用来进行用来进行TIN构建的原始数据根据数据点之构建的原始数据根据数据点之间的约束条件可分为无约束数据域和约束数间的约束条件可分为无约束数据域和约束数据域两种类型据域两种类型 无约束数据域是指数据点之间不存在任何关无约束数据域是指数据点之间不存在任何关系，即数据分布完全呈离散状态，数据点之系，即数据分布完全呈离散状态，数据点之间在物理上

5、相互独立。间在物理上相互独立。 约束数据则是部分数据点之间存在着某种联约束数据则是部分数据点之间存在着某种联系，这种联系一般通过线性特征来维护。系，这种联系一般通过线性特征来维护。 约束条件又有两类：约束条件又有两类： 一是边界约束条件，指数据点被一多边形一是边界约束条件，指数据点被一多边形所包围，该多变形即为边界约束条件；另所包围，该多变形即为边界约束条件；另 一为内部约束条件，是数据点之间存在的一为内部约束条件，是数据点之间存在的限制条件。地形数据一般仅存在内部约束限制条件。地形数据一般仅存在内部约束条件而无边界约束条件而无边界约束 TIN对三角形的几何形状有严格的对三角形的几何形状有严格

6、的要求。要求。 TIN模型一般有三个基本要求：模型一般有三个基本要求：1）三角形的格网唯一；）三角形的格网唯一；2）最佳三角形形状，尽量接近正三角形；）最佳三角形形状，尽量接近正三角形；3）三角形边长之和最小，保证最近的点形成）三角形边长之和最小，保证最近的点形成 三角形。三角形。（4）TIN的体系结构的体系结构 在同一准则下，由不同的位置开始建立三角形网络，其最终的形状和结构应是相同的。l TIN的三角剖分准则是指的三角剖分准则是指TIN中三角形的中三角形的形成法则，它决定着三角形的几何形状和形成法则，它决定着三角形的几何形状和TIN的质量。的质量。l 目前，在目前，在GIS、计算机和图形学

7、领域常用、计算机和图形学领域常用的三角剖分准则有的三角剖分准则有6种。种。2 TIN2 TIN的三角剖分准则的三角剖分准则随机分布的四个点构建三角面 空外接圆准则：在空外接圆准则：在TIN中，过每个三角形的外接中，过每个三角形的外接圆均不包含点集的其余任何点；圆均不包含点集的其余任何点； 最大最小角准则：在最大最小角准则：在TIN中的两相邻三角形形成中的两相邻三角形形成的凸四边形中，这两三角形中的最小内角一定大的凸四边形中，这两三角形中的最小内角一定大于交换凸四边形对角线后所形成的两三角形的最于交换凸四边形对角线后所形成的两三角形的最小内角；小内角； 最短距离和准则：指一点到基边的两端的距离和

8、最短距离和准则：指一点到基边的两端的距离和为最小。为最小。 张角最大准则：一点到基边的张角为最大张角最大准则：一点到基边的张角为最大 面积比准则：三角形内切圆面积与三角形面积或面积比准则：三角形内切圆面积与三角形面积或三角形面积与周长平方之比最小。三角形面积与周长平方之比最小。 对角线准则：两三角形组成的凸四边形的两条对对角线准则：两三角形组成的凸四边形的两条对角线之比。这一准则的比值限定值，须给定，即角线之比。这一准则的比值限定值，须给定，即当计算值超过限定值才进行优化。当计算值超过限定值才进行优化。理论上可以证明：张角最大准则、空外接圆准则及最大最小角准则是等价的。同样的点集可能生成不同的

9、TIN 对于对于TINTIN模型，有三点基本要求：模型，有三点基本要求： TIN TIN是唯一的是唯一的 力求最佳的三角形几何形状，每个三角形力求最佳的三角形几何形状，每个三角形尽量接近等边形状。（最大最小角特性：尽量接近等边形状。（最大最小角特性：三角形的最小内角尽量最大三角形的最小内角尽量最大 ） 保证最邻近的点构成三角形，即三角形的保证最邻近的点构成三角形，即三角形的边长之和最小。（空圆特性边长之和最小。（空圆特性：三角形的外三角形的外接圆中不包含其他三角形的顶点）接圆中不包含其他三角形的顶点） 关于关于delaunay三角网三角网Delaunay三角网的特性：三角网的特性：不存在四点共

10、圆；不存在四点共圆；每个三角形对应于一个每个三角形对应于一个Voronoi图顶点；图顶点；每个三角形边对应于一个每个三角形边对应于一个Voronoi图边；图边；每个结点对应于一个每个结点对应于一个Voronoi图区域；图区域；Delaunay图的边界是一个凸壳；图的边界是一个凸壳；三角网中三角形的最小角最大。三角网中三角形的最小角最大。 定义：定义： 狄洛尼狄洛尼(Delaunay)(Delaunay)三角网三角网 狄洛尼三角网为相互邻接且互不重叠的三角形的集合，每一个三角形的外接圆内不包每一个三角形的外接圆内不包含其他的点含其他的点。 Delaunay Delaunay三角形三角形的的一些重

11、要概念一些重要概念： 形态比：指三角形的内切圆半径与外接圆形态比：指三角形的内切圆半径与外接圆半径之比。半径之比。 TIN TIN中所有三角形的形态比的平均值称为中所有三角形的形态比的平均值称为平均形态比。平均形态比。 角度特征向量：将平面离散点集剖分出的角度特征向量：将平面离散点集剖分出的所有三角形的角度按由小到大排队，所构成所有三角形的角度按由小到大排队，所构成的向量。的向量。 凸集凸集(Convex)(Convex)：每两点相互可视的平面点集。：每两点相互可视的平面点集。 设设S S为平面上的点集，则：为平面上的点集，则：如果如果S S中的两中的两点点A A、B B可视，则可视，则A A

12、、B B之直线连线位于之直线连线位于S S中；中；如果点如果点X X为为S S的观察点，则的观察点，则X X与与S S中的每一点均中的每一点均可视；可视；凸集中每一点均是观察点。凸集中每一点均是观察点。 插入区域：外接圆包含待插入点的三角形的插入区域：外接圆包含待插入点的三角形的集合。集合。 空圆法则（狄洛尼法则）空圆法则（狄洛尼法则）: : 狄洛尼三角形外接圆内不包含其他点狄洛尼三角形外接圆内不包含其他点 此法则是此法则是一系列不重合的平面点建立狄洛一系列不重合的平面点建立狄洛尼三角网的基本法则尼三角网的基本法则 局部最优方法局部最优方法: : 交换凸四边形的对角线，可获得等角性交换凸四边形

13、的对角线，可获得等角性最好的三角网最好的三角网。 运用运用DTDT三角网的空外接圆性质对由两个三角网的空外接圆性质对由两个有公共边的三角形组成的四边形进行判断。有公共边的三角形组成的四边形进行判断。如果其中一个三角形的外接圆中含有第四如果其中一个三角形的外接圆中含有第四个顶点，则交换四边形的对角线。个顶点，则交换四边形的对角线。 狄洛尼三角网狄洛尼三角网(D-TIN)(D-TIN)的局部优化的局部优化 在任何三角剖分准则下得到的TIN，只要用LOP法则（局部优化过程，Local Optimal Procedre,LOP）对其进行优化处理，就能得到唯一的DT三角网络。建立建立TIN的算法多种多的

14、算法多种多样样Delaunay三角网或其他三角网或其他三角网三角网 静态或动态方法静态或动态方法无约束或有约束的方法无约束或有约束的方法直接或间接方法直接或间接方法删格法静态式矢量法 动态式TINVoronoi 图3 三角剖分算法分类与特点三角剖分算法分类与特点 （1）不规则分布采样数据三角剖分）不规则分布采样数据三角剖分 （2）规则分布采样数据三角剖分）规则分布采样数据三角剖分 （3）从混合数据生成三角网）从混合数据生成三角网 （4）基于等高线采样数据三角剖分）基于等高线采样数据三角剖分 l 新插入点与已知三角网存在四种关系新插入点与已知三角网存在四种关系（a）在三角形内）在三角形内（b）在

15、三角形外接圆内）在三角形外接圆内（c）在三角形外接圆上）在三角形外接圆上（d）在三角形外接圆外）在三角形外接圆外 规则分布采样数据三角剖分规则分布采样数据三角剖分l b 重要点法重要点法DEM建模有两个关键步骤：建模有两个关键步骤： 1）确定格网点的）确定格网点的“重要程度重要程度”：全局最重要或局：全局最重要或局部最重要；部最重要； 2）确定终止条件：达到预设的点数或预设的精度、）确定终止条件：达到预设的点数或预设的精度、或两者折中。或两者折中。l目前这类算法主要有目前这类算法主要有地形骨架法、地形滤波地形骨架法、地形滤波法等法等。(2)(2)从规则数据生成三角网从规则数据生成三角网a a

16、直接将格网进行分解组合得到三角形直接将格网进行分解组合得到三角形 C C 比较比较VIPsVIPs方式与直接方式方式与直接方式 避免平坦地区的数据冗余避免平坦地区的数据冗余 保持地形的细节保持地形的细节 缺点：缺点：相对比较复杂相对比较复杂 在实际应用中一般釆用直接方式在实际应用中一般釆用直接方式 VIPVIPs s方式的优点：方式的优点：（3 3）从混合数据生成三角网）从混合数据生成三角网 混合数据混合数据 此种数据建立三角网此种数据建立三角网的方法：首先分解规的方法：首先分解规则三角形，然后考虑则三角形，然后考虑特征线上的点，在格特征线上的点，在格网中生成不规则三角网中生成不规则三角形。形

17、。基于等高线采样数据三角剖分基于等高线采样数据三角剖分l 由于数据沿等高线分布，常会出现一些不希望的现由于数据沿等高线分布，常会出现一些不希望的现象，如三角形三顶点在同一条等高线上（称为象，如三角形三顶点在同一条等高线上（称为平三角平三角形形）。）。l对这类问题有两种处理方案：一是把等高线数据当对这类问题有两种处理方案：一是把等高线数据当作特征线处理，按约束作特征线处理，按约束DT进行剖分，一是局部优化进行剖分，一是局部优化内插增加地形特征点。内插增加地形特征点。5.2 TIN的建立的建立 1 无约束散点域的三角剖分算法与实现无约束散点域的三角剖分算法与实现 目前散点域的三角剖分使用最为广泛的

18、目前散点域的三角剖分使用最为广泛的算法是算法是Delaunay直接三角剖分算法。直接三角剖分算法。 分割合并算法分割合并算法 三角网生长算法三角网生长算法 逐点插入算法逐点插入算法 TIN的建立p 分割合并算法第一步把数据集以横坐标为主、纵坐标为辅按升序进行排序(xixi+1且yiyi+1)；第二步如果数据集中的数据个数大于给定的阈值，则把数据域划分为个数近似相等的左右两个子集，并对每一子集做如下的工作：第三步如果数据集中的数据个数小于给定的阈值，则直接输出三角剖分结果。计算每一子集的凸壳；以凸壳为数据边界，对每一数据子集进行三角剖分，并用LOP进行优化，使之成为DT三角形；找出连接左右子集两

19、个凸壳的底线和顶线；由底线到顶线，合并两个子三角网。 （2）三角网生长算法：）三角网生长算法： 三角网生长算法就是从一个三角网生长算法就是从一个“源源”开始，逐步开始，逐步形成覆盖整个数据区域的三角网。形成覆盖整个数据区域的三角网。 从生长过程角度，三角网生长算法分为从生长过程角度，三角网生长算法分为收缩生收缩生长算法长算法和和扩张生长算法扩张生长算法两类。两类。 收缩生长算法是先形成整个数据域的数据边界收缩生长算法是先形成整个数据域的数据边界（凸壳），并以此作为源头，逐步缩小以形成整（凸壳），并以此作为源头，逐步缩小以形成整个三角网。个三角网。 扩张生长算法与收缩算法过程刚好相反，是从扩张生

20、长算法与收缩算法过程刚好相反，是从一个三角形开始向外层层扩展，形成覆盖整个区一个三角形开始向外层层扩展，形成覆盖整个区域的三角网。域的三角网。扩张生长算法扩张生长算法p 三角网生长算法第一步 生成初始三角形生成初始三角形。 在数据点中任取一点A（一般位于数据点的几何中心附近），并寻找距离此点最近的点B，两者相连形成初始基线AB，利用三角剖分准则，在数据域中寻找第三点C，从而形成第一个Delaunay三角形ABC。第二步 扩展形成三角网扩展形成三角网。 以初始三角形的三条边为初始基线，利用空外接圆准则或张角最大准则，寻找能与该三条初始基线形成Delaunay三角形的D、E、F点。ABCDEF第三

21、步 重复第二步，直到所有数据处理完毕重复第二步，直到所有数据处理完毕。1）将凸多边形按逆时针保存记录，以左下角点附近的顶点作为）将凸多边形按逆时针保存记录，以左下角点附近的顶点作为起点；起点；2）确定第一条基边；）确定第一条基边；3）构建第一个）构建第一个Delaunay三角形；三角形；4）重复）重复(3)形成第一层形成第一层Delaunay三角形；三角形；5）重新确定起点，重复）重新确定起点，重复(2)(4)完成整个区域的三角网构建。完成整个区域的三角网构建。构建三角网的具体算法构建三角网的具体算法 （3）逐点插入算法）逐点插入算法 逐点插入算法的过程非常简单，基本步骤为：逐点插入算法的过程

22、非常简单，基本步骤为： 1）定义包含所有数据点的初始包容盒，即定义）定义包含所有数据点的初始包容盒，即定义包含所有数据点的最小外界矩形范围，并以此作包含所有数据点的最小外界矩形范围，并以此作为最简单的凸闭包。为最简单的凸闭包。 2）对该包容盒进行初始三角剖分，按一定规则）对该包容盒进行初始三角剖分，按一定规则将数据区域的矩形范围进行格网划分（如限定每将数据区域的矩形范围进行格网划分（如限定每个格网单元的数据点数）。个格网单元的数据点数）。 3）剖分数据区域的凸闭包形成两个超三角形，）剖分数据区域的凸闭包形成两个超三角形，所有数据点都一定在这两个三角形范围内。所有数据点都一定在这两个三角形范围内

23、。逐点插入算法的过程非常简单逐点插入算法的过程非常简单4）对所有数据点进行循环，作如下工作（设当前）对所有数据点进行循环，作如下工作（设当前处理的数据点为处理的数据点为P）：）： 在已存在的三角网中，查找包含在已存在的三角网中，查找包含P的三角形的三角形T；P与与T的三个顶点相连，形成的三个顶点相连，形成T的三个初始三角剖的三个初始三角剖分；分；用用LOP算法对初始三角剖分进行优化处理；重算法对初始三角剖分进行优化处理；重复以上过程直到所有点处理完毕；删除所有包含复以上过程直到所有点处理完毕；删除所有包含一个或多个超三角形顶点的三角形。一个或多个超三角形顶点的三角形。5）处理外围三角形。）处理

24、外围三角形。 约束线段的处理约束线段的处理 最简单的处理方法是所谓的“加密法”，即通过加密约束线段上的数据点，将约束数据转换为普通数据 唯一的问题在于如何恰当地确定特征线上加密数据点之间的距离，一般取平均数据点间距的一半或更小即可 尽管加大了数据量并改变了原始数据集，但简单易行、稳定可靠，在许多情况下可以很好地满足需要 (a) Data with a feature line (b) Point densification (c) Triangulation result（1）约束三角网（）约束三角网（CDT）的性质）的性质 可见性（可见性（Mutually Visible） 空外接圆性质（空

25、外接圆性质（Empty Circle） 最大最小角性质（最大最小角性质（Max-Min Angle） 局部优化性质（局部优化性质（Locally Optimal） （2）约束三角网的构建算法）约束三角网的构建算法 约束图法约束图法 分割分割-合并算法合并算法 加密算法加密算法 Shell三角化算法。三角化算法。 两步法两步法 TIN的建立的建立p 基于两步法的边交换迭代算法基于两步法的边交换迭代算法第一步第一步 对数据域中每一约束线段，按如下过程进行对数据域中每一约束线段，按如下过程进行 处理。设当前处理的约束线段的两个顶点为处理。设当前处理的约束线段的两个顶点为 Vi和和Vj。第二步第二步

26、检查线段检查线段ViVj是否已存在于三角网中，如果是否已存在于三角网中，如果 ViVj已经是三角形的一条边，则已经是三角形的一条边，则Vi和和Vj的约的约 束关系已满足，返回第一步进行下一条约束束关系已满足，返回第一步进行下一条约束 线段的处理；如果线段的处理；如果ViVj在三角网中不存在，在三角网中不存在， 说明说明Vi和和Vj的约束关系已被破坏，这时要找的约束关系已被破坏，这时要找 出与出与ViVj相交的所有三角形的边，并将与相交的所有三角形的边，并将与 ViVj相交的三角形的边存储于一个边表相交的三角形的边存储于一个边表eList 中。中。基于两步法的边交换迭代算法第三步 交换相交边交换

27、相交边。如果eList中的边VkVl和ViVj相 交，做如下处理。第四步 局部三角网优化处理局部三角网优化处理。重复下列过程直到没有边交换为止。3 3 从等高线生成三角网从等高线生成三角网 等高线是一种特殊的特征线，也可以作为等高线是一种特殊的特征线，也可以作为约束线段。约束线段。 从等高线生成三角网一般有三种算法：从等高线生成三角网一般有三种算法： 等高线离散点直接生成不规则三角网等高线离散点直接生成不规则三角网TINTIN 将将等高线等高线作为特征线作为特征线 自动增加特征点及优化自动增加特征点及优化TINTIN的方法的方法平三角形处理方法平三角形处理方法 （1）预防性措施）预防性措施 建

28、立建立TIN之前现对采样数据进行概化，即通之前现对采样数据进行概化，即通过减少等高线上的采样点数而增加采样点过减少等高线上的采样点数而增加采样点之间的距离，从而使采样点之间的平均距之间的距离，从而使采样点之间的平均距离与等高线之间的平均距离相一致，最大离与等高线之间的平均距离相一致，最大限度地减少平三角形出现的概率。限度地减少平三角形出现的概率。 等高线概化以损失采样点信息为代价减少等高线概化以损失采样点信息为代价减少了平三角形出现的机会，但在极端情况下，了平三角形出现的机会，但在极端情况下，可能导致等高线相交。可能导致等高线相交。 （2）自动修正方法）自动修正方法分交互式修改和自动修正法分交

29、互式修改和自动修正法交互式修正：检测出平三角形后，通过人机交互的方式进行交互式修正：检测出平三角形后，通过人机交互的方式进行平三角形处理，低效平三角形处理，低效自动修正：通过一定算法，实现平三角形的自动检测与消除，自动修正：通过一定算法，实现平三角形的自动检测与消除，一般有基于边交换算法、插入辅助点算法和交换边与插一般有基于边交换算法、插入辅助点算法和交换边与插入辅助点相结合的算法。入辅助点相结合的算法。 平坦区域：指相邻等高线间相毗邻的平三角形集合所构平坦区域：指相邻等高线间相毗邻的平三角形集合所构成的多边形区域，通常以两个或两个以上统一等高线的成的多边形区域，通常以两个或两个以上统一等高线

30、的边作为边界。边作为边界。 分批与分区域处理分批与分区域处理4 基于栅格数据的三角网建立基于栅格数据的三角网建立 1）建立最小分辨率影像）建立最小分辨率影像 取两点间最小距离作为栅格基本单元，取两点间最小距离作为栅格基本单元，将所处理区域转为一幅二值图像（参考点将所处理区域转为一幅二值图像（参考点所在像素灰度值为所在像素灰度值为1，其他像素灰度值为，其他像素灰度值为0）。）。 2） 形成泰森多边形形成泰森多边形 设设X为参考点像素集合，则除去这些参考为参考点像素集合，则除去这些参考后的剩余部分的骨架，即为建立后的剩余部分的骨架，即为建立TIN的泰森的泰森多边形；多边形； 3） 形成形成TIN

31、设设X为参考点集，为参考点集，P是是X中任一参考点，将中任一参考点，将与与P所在的泰森多边形相邻的泰森多边形中所在的泰森多边形相邻的泰森多边形中的参考点与的参考点与P相连，即构成以相连，即构成以P为顶点的所为顶点的所有三角形的边。有三角形的边。TIN建模方法的分类和特点建模方法的分类和特点TIN算法类型算法类型不规则不规则数据分布数据分布规则规则数据分布数据分布沿等高线沿等高线分布数据分布数据VIPs算法、循环迭代算法算法、循环迭代算法层次三角形算法层次三角形算法特征线算法特征线算法探测优化算法探测优化算法辐射扫描算法、模拟退火算法辐射扫描算法、模拟退火算法数学形态算法数学形态算法DT三角三角

32、剖分剖分直接直接DT间接间接DT分割合并算法分割合并算法逐点插入法逐点插入法三角形增长法三角形增长法5.3 DEM模型之间的相互转换模型之间的相互转换5.3.1 5.3.1 不规则点集生成不规则点集生成TIN TIN 5.3.2 5.3.2 格网格网DEMDEM转成转成TIN TIN 5.3.3 5.3.3 等高线转成格网等高线转成格网DEM DEM 5.3.4 TIN5.3.4 TIN转成格网转成格网DEM DEM 5.3.5 5.3.5 从从格网格网DEMDEM生成生成等高线等高线 5.35.3.6 .6 从三角网从三角网DEMDEM生成等高线生成等高线 最常用的方法是Delaunay三角

33、剖分方法，生成过程分两步完成： 利用P中点集的平面坐标产生Delaunay三角网； 给Delaunay三角形中的节点赋予高程值。 5.3.1 5.3.1 不规则点集生成不规则点集生成TINTIN 直接将格网进行分解组合得到三角形 通过一定法则，选择VIPs建立三角形 绝大多数算法都有两个重要的特征： 筛选要保留或丢弃的格网点； 判断停止筛选的条件5.3.2 5.3.2 格网格网DEMDEM转成转成TIN TIN 核心问题：核心问题：从大量的格网点中提取表征地形特征的重要点集，如从大量的格网点中提取表征地形特征的重要点集，如 山顶点、山脊线点、山谷线点、鞍部点等。山顶点、山脊线点、山谷线点、鞍部点等。涉及问题：涉及问题：选点原则与终止条件（精度或循环次数）选点原则与终止条件（精度或循环次数