不规则三角网(TIN)的建立.ppt

2020 6 17 1 不规则三角网 TIN 的建立算法 数字高程模型 1410040222 2020 6 17 2 TIN概述 5 1 1TIN的理解5 1 2TIN的三角剖分准则5 1 3三角剖分算法分类与特点 2020 6 17 3 TIN的基本概念 不规则三角网 TriangulatedIrregularNetwork简称TIN 是用一系列互不交叉 互不重叠的连接在一起的三角形来表示地形表面 TIN既是矢量结构又有栅格的空间铺盖特征 能很好地描述和维护空间关系 2020 6 17 4 T 三角化 Triangulated 是离散数据的三角剖分过程 也是TIN的建立过程 位于三角形内的任意一点的高程值均可以通过三角形平面方程唯一确定 I 不规则性 Irregular 指用来构建TIN的采样点的分布形式 TIN具有可变分辨率 比格网DEM能更好反映地形起伏 N 网 Network 表达整个区域的三角形分布形态 即三角形之间不能交叉和重叠 三角形之间的拓扑关系隐含其中 不规则三角网 TIN 的建立 2020 6 17 5 TIN的基本元素 节点 Node 是相邻三角形的公共顶点 也是用来构建TIN的采样数据 边 Edge 指两个三角形的公共边界 是TIN不光滑性的具体反映 边同时还包含特征线 断裂线以及区域边界 面 Face 由最近的三个节点所组成的三角形面 是TIN描述地形表面的基本单元 TIN中的每一个三角形都描述了局部地形倾斜状态 具有唯一的坡度值 三角形在公共节点和边上是无缝的 或者说三角形不能交叉和重叠 2020 6 17 6 数据和TIN的类型 用来进行TIN构建的原始数据根据数据点之间的约束条件可分为无约束数据域和约束数据域两种类型 无约束数据域是指数据点之间不存在任何关系 即数据分布完全呈离散状态 数据点之间在物理上相互独立 约束数据域则是部分数据点之间存在着某种联系 这种联系一般通过线性特征来维护 如地形数据中的山脊线 山谷线上的点等 2020 6 17 7 TIN的体系结构 TIN对三角形的几何形状一般有三个基本要求 1 三角形的格网唯一 2 最佳三角形形状 尽量接近正三角形 3 三角形边长之和最小 保证最近的点形成三角形 2020 6 17 8 TIN的三角剖分准则 TIN的三角剖分准则是指TIN中三角形的形成法则 它决定着三角形的几何形状和TIN的质量 目前 在GIS 计算机和图形学领域常用的三角剖分准则有6种 2020 6 17 9 空外接圆准则 在TIN中 过每个三角形的外接圆均不包含点集的其余任何点 最大最小角准则 在TIN中的两相邻三角形形成的凸四边形中 这两三角形中的最小内角一定大于交换凸四边形对角线后所形成的两三角形的最小内角 最短距离和准则 指一点到基边的两端的距离和为最小 2020 6 17 10 张角最大准则 一点到基边的张角为最大 面积比准则 三角形内切圆面积与三角形面积或三角形面积与周长平方之比最小 对角线准则 两三角形组成的凸四边形的两条对角线之比 这一准则的比值限定值 须给定 即当计算值超过限定值才进行优化 2020 6 17 11 1 三角形准则是建立三角形格网的基本原则 应用不同的准则将会得到不同的三角网 2 一般而言 应尽量保持三角网的唯一性 即在同一准则下由不同的位置开始建立三角形格网 其最终的形状和结构应是相同的 3 空外接圆准则 最大最小角准则下进行的三角剖分称为Delaunay 译为狄洛尼或德劳内 三角剖分 Triangulation 简称DT 空外接圆准则也叫Delaunay法则 说明 2020 6 17 12 关于delaunay三角网1934年Delaunay提出了Voronoi图的对称图 即Delaunay三角网 用直线段连接两个相邻多边形内的离散点而生成的三角网 Delaunay三角网的特性 不存在四点共圆 每个三角形对应于一个Voronoi图顶点 每个三角形边对应于一个Voronoi图边 每个结点对应于一个Voronoi图区域 Delaunay图的边界是一个凸壳 三角网中三角形的最小角最大 2020 6 17 13 TIN的建立 1无约束散点域的三角剖分算法与实现2约束散点数据域的三角剖分算法与实现3基于等高线数据的TIN的建立4基于栅格数据的三角网建立 2020 6 17 14 无约束散点域的三角剖分算法与实现 目前散点域的三角剖分使用最为广泛的算法是Delaunay直接三角剖分算法 1 三角网生长算法2 逐点插入算法3 分割合并算法 2020 6 17 15 1 三角网生长算法 三角网生长算法就是从一个 源 开始 逐步形成覆盖整个数据区域的三角网 从生长过程角度 三角网生长算法分为收缩生长算法和扩张生长算法两类 收缩生长算法是先形成整个数据域的数据边界 凸壳 并以此作为源头 逐步缩小以形成整个三角网 扩张生长算法与收缩算法过程刚好相反 是从一个三角形开始向外层层扩展 形成覆盖整个区域的三角网 2020 6 17 16 1 三角网生长算法 1 递归生长算法 算法过程如下 在数据集中任取一点 查找距离此点最近的点 相连后作为初始基线 在初始基线右边应用Delaunay法则搜索第三点 生成Delaunay三角形 并以该三角形的两条新边作为新的基线 重复前面过程直至所有基线处理完毕 这种算法大量的时间花费在符合要求的邻域点的搜索方面 为了减少搜索时间 许多学者提出了许多不同的方法 如将数据分块并排列 以外接圆的方式限定其搜索范围 2020 6 17 17 1 2 1 2 1 2 1 2 递归生长算法 3 3 3 2020 6 17 18 1 三角网生长算法 该算法的基本思路 首先找到包含数据区域的最小凸多边形 并从该多边形开始从外向里逐层形成三角形格网 平面点凸闭包的定义是包含这些平面点的最小多边形 在凸闭包中 连接任意两点的线段必须完全位于多边形内 凸闭包是数据点的自然极限边界 相当于包围数据点的最短路径 凸闭包是数据集标准Delaunay三角网的一部分 计算凸闭包是该算法的核心 2 凸闭包收缩法 2020 6 17 19 1 计算凸闭包的四个顶点 2 以此四点作为基点 通过边右边最大偏移量搜索其他凸闭包顶点 计算凸闭包的思路 P79 2020 6 17 20 1 将凸多边形按逆时针保存记录 以左下角点附近的顶点作为起点 2 确定第一条基边 3 构建第一个Delaunay三角形 4 重复 3 形成第一层Delaunay三角形 5 重新确定起点 重复 2 4 完成整个区域的三角网构建 构建三角网的具体算法 2020 6 17 21 2 逐点插入算法 1 定义包含所有数据点的最小外界矩形范围 并以此作为最简单的凸闭包 2 按一定规则将数据区域的矩形范围进行格网划分 如限定每个格网单元的数据点数 3 剖分数据区域的凸闭包形成两个超三角形 所有数据点都一定在这两个三角形范围内 4 对所有数据点进行循环 作如下工作 设当前处理的数据点为P 搜寻包含点P的三角形 将P与此三角形三个顶点相连 形成三个三角形 由里到外优化整个三角网 重复以上过程直到所有点处理完毕 删除所有包含一个或多个超三角形顶点的三角形 5 处理外围三角形 2020 6 17 22 逐点插入算法 2020 6 17 23 3 分割合并算法 分割合并算法的思想很简单 首先将数据点分割成易于进行三角化的子集 然后对每个子集进行三角剖分 并用LOP算法保证三角剖分为Delaunay三角网 当每个子集剖分完成后 对每个子集的三角剖分进行合并 形成最终的整体三角网 2020 6 17 24 分割合并算法 2020 6 17 25 3基于等高线数据的TIN的建立 等高线离散点直接生成TIN 将等高线作为特征线的方法 自动增加特征点及优化TIN的方法 2020 6 17 26 等高线离散点直接生成TIN方法 该方法直接将等高线离散化 然后利用常用TIN的生成算法 该方法没有考虑离散点间原有的连接关系 模拟的地形就会失真 具体表现为三角形的边穿越等高线和存在平三角形的两种情况 在实际应用中该方法较少使用 2020 6 17 27 等高线作为特征线建立TIN 将等高线作为断裂线或结构线 使用等高线上的特征点 并将等高线段作为约束线段处理 2020 6 17 28 自动增加特征点及优化TIN的方法 该方法实质仍将等高线离散化建立TIN 但采用增加特征点的方式来消除TIN中的平三角形 并使用优化TIN的方式来消除不合理的三角化 特征点的增加需要利用一定的算法自动提取 这些算法原理大都基于原始等高线的拓扑关系 。