《数字高程模型》课件.ppt

数字高程模型DigitalElevationModel 长安大学杨宏志 主要内容 一 DTM和DEM的概念二 DEM的主要表示模型三 DEM的数据采集方法四 DEM的建模方法五 DEM的分析与应用 一 DTM和DEM的概念 数字地形模型 DTM DigitalTerrainModel 是描述地形表面形态空间位置和地形属性分布的有序数值阵列 DTM以离散分布的平面点来模拟连续分布的地形 数字地形模型中地形属性为高程时称为数字高程模型 DigitalElevationModel DEM 不过 被描述的地形属性也可以是地理空间上的地价 污染负荷量 绿化率 降雨量 气温 人口密度等 显然 DEM是DTM的一个子集 是DTM的一个特例 数字高程模型的表示方法 使用三维函数模拟复杂曲面 将一个完整曲面分解成方格网或面积上大体相等的不规则格网 每个格网中有一个点的观测值 即为格网值 适用于曲面插值来表示地下水或土壤的特性 二 DEM的主要表示模型 1 规则格网模型规则网格 通常是正方形 也可以是矩形 三角形等规则网格 规则网格将区域空间切分为规则的格网单元 每个格网单元对应一个数值 数学上可以表示为一个矩阵 在计算机实现中则是一个二维数组 2 等高线模型等高线模型表示高程 高程值的集合是已知的 每一条等高线对应一个已知的高程值 这样一系列等高线集合和它们的高程值一起就构成了一种地面高程模型 3 不规则三角网 TIN 模型规则格网DEM的缺陷 1 在地形平坦的地方 存在大量的数据冗余 2 在不改变格网大小的情况下 难以表达复杂地形的突变现象 TIN TriangulatedIrregularNetwork TIN 模型根据区域有限个点集将区域划分为相连的三角面网络 区域中任意点落在三角面的顶点 边上或三角形内 如果点不在顶点上 该点的高程值通常通过线性插值的方法得到 在边上用边的两个顶点的高程 在三角形内则用三个顶点的高程 4 层次模型层次地形模型 LayerofDetails LOD 是一种表达多种不同精度水平的数字高程模型 层次地形模型允许根据不同的任务要求选择不同精度的地形模型 三 DEM的数据采集方法 1 地面测量利用自动记录的测距经纬仪 常用电子速测经纬仪或全站经纬仪 在野外实测 这种速测经纬仪一般都有微处理器 可以自动记录和显示有关数据 还能进行多种测站上的计算工作 其记录的数据可以通过串行通讯 输入计算机中进行处理 2 现有地图数字化利用数字化仪对已有地图上的信息 如等高线 进行数字化的方法 目前常用的数字化仪有手扶跟踪数字化仪和扫描数字化仪 3 空间传感器利用全球定位系统GPS 结合雷达和激光测高仪等进行数据采集 4 数字摄影测量方法这是DEM数据采集最常用的方法之一 利用附有的自动记录装置 接口 的立体测图仪或立体坐标仪 解析测图仪及数字摄影测量系统 进行人工 半自动或全自动的量测来获取数据 四 DEM的建模方法 1 DEM的生成流程DEM生成的全过程包括 原始数据获取 DEM模型构造 数据插值 在所定数据结构支持下的数据存储和模型输出 2 DEM的空间插值方法由于DEM采样的数据点呈离散分布形式 或是数据点虽按格网排列 但格网的密度不能满足使用的要求 这就需要以数据点为基础进行插值运算 DEM内插按插点分布范围 可分为分块内插 剖分内插和单点移面内插三类 分块内插 是把需要建立DEM的地区 切割成一定大小的规则方块 形状通常为正方形 在每一个分块上展铺一张数学面 相邻分块之间有适当宽度的重叠带 以使重叠带内全部数据点成为相邻块展铺数学面时的共用数据 保证一张数学面能够较平滑地与相邻分块的数学面拼接 剖分内插是把需要建立DTM的地区切割成大小和形状不同的子区 剖分 子区间拥有公共边但不重叠 在该区内展铺一个数学面 内插剖分区内任意点的高程 单点移面内插是以待插点为中心 以适当半径或边长的圆或正方形作为移动面去捕捉适当数目的数据点 并以此展播一张数学面 内插该中心的高程 3 TIN建模方法 不规则三角网 TIN TriangulatedIrregularNetwork 通过从不规则分布的数据点生成的连续的三角面来逼近地形表面 TIN模型的优点是它能以不同层次的分辨率来描述地形表面 对于TIN模型 其基本要求有三点 TIN是唯一的 力求最佳的三角形形状 每个三角形尽量接近等边形状 保证最临近的点构成三角形 即三角形的边长之和最小 在所有可能的三角形方案中 Delaunay三角网在地形拟和方面表现最为出色 因此常常被用于TIN的生成 而当不相交的断裂线等被作为预先定义的限制条件作用于TIN的生成当中时 则必须考虑带约束条件的Delaunay三角网 Delaunay三角网的定义 假设 是欧几里德平面上的一个点集 并且这些点不共线 任意四点不共圆 用表示点间的欧几里德距离 设P为平面上的点 则区域 称为Voronoi多边形 简称V 多边形 平面点集中的点则称为V 多边形的生长核 Voronoi多边形描述了一个轨迹 即多边形中的点到本多边形生长核的距离小于等于到其它生长核的距离 各点的Voronoi多边形共同组成了Voronoi图 如图虚线所示 连接所有相邻的V 多边形的生长核所形成的三角网称为Delaunay三角网 如图实线所示 Delaunay三角网的外边界是一个凸多边形 它由节点集中的凸集形成 通常称为凸壳或凸包 ConvexHull Delaunay三角网的基本特性 Delaunay三角网具有两个非常重要的性质 空外接圆性质 在由点集V所形成的Delaunay三角网中 其每个三角形的外接圆均不包含点集V中的其他任意点 最大最小角度性质 每两个相邻的三角形构成凸四边形的对角线 在相互交换后 六个内角的最小角不再增大 局部优化算法LOP LocalOptimizationProcedure Lawson 1977 提出了根据最大最小角度性质建立局部几何形状最优的三角网 在由两相邻三角形构成的凸四边形中 交换此四边形的两条对角线 不会增加这两个三角形六个内角总和的最小值 Lawson据此提出了局部最优算法LOP 交换凸四边形的对角线 可获得等角性最好的三角网 Delaunay三角网生成算法综述 根据构建三角网的步骤 可以将三角网生成算法分为三类 1 分而治之算法 DivideandConquerAlgorithm 2 逐点插入算法 IncrementalInsertionAlgorithm 3 三角网生长算法分而治之算法Lewis和Robinson于1978年提出了建立Delaunay三角网的分而治之算法 基本步骤是 1 把点集V以横坐标为主 纵坐标为辅按升序排序 将V分成大小相等的网格 用VL包含数据左半部分点 VR表示右半部分点 然后递归地执行一下步骤 2 在VL和VR中生成三角网 3 用LOP算法优化所生成的三角网 使之成为Delaunay三角网 4 找出连接VL和VR中两个凸包的顶线和底线 5 由底线至顶线合并VL和VR中的两个三角网 以上步骤显示 分治算法的基本思路是使问题简化 将点集划分的足够小 使其易于生成三角网 然后把子集中的三角网合并成最终的三角网 用LOP算法保证其成为Delaunay三角网 算法演示 2 逐点插入算法逐点插入算法的基本步骤是 1 定义一个包含所有数据点的初始多边形或超级三角形 建立初始三角网 然后迭代以下步骤 直至所有数据点都被处理 3 插入一个数据点P 在三角网中找出包含P的三角形 把P与三角形T的三个顶点相连 生成三个新的三角形 4 用LOP算法优化三角网 3 三角网生长算法三角网生长算法的基本步骤是 1 以任一点为起始点 2 找出离起始点最近的数据点相互连接成Delaunay三角形的一条边作为基边 按Delaunay三角网的判别法则 找出与基线构成Delaunay三角形的第三点 3 基线的两个端点与第三点相连 成为新的基线 4 迭代以上两步直至所有基线都被处理 三角网生长算法 逐点插入算法 4 综述从时间复杂度看 分而治之算法最好 其缺点也是显而易见的 表现在 1 需要占用较大的内存空间 其原因主要是分治算法需一次性读入所有参加构网的数据 2 数据预处理工作量较大 由于在构建三角网前要对数据进行排序 故分治算法的预处理工作量较大 3 优化工作量较大 逐点插入算法实现比较简单 占用内存小 但时间复杂度较差 主要制约因素在于点在三角形中的判断 LOP局部优化过程的拓扑更新以及空外接圆检测 三角网生成算法速度最慢 目前已很少使用 但刘学军在 TIN数模的点单位算法及网形优化 提出的TBP算法可以提高算法的效率 但从其以后文章看 也抛弃了这种算法 目前研究较多的算法是合成算法 即将逐点插入法与分而治之法融合 即对数据进行分块 子网建立采用逐点插入法 子网间合并采用凸包合并算法 从而解决二者不足 实际 逐点插入法在解决了以上问题后 其速度基本与合成算法接近 合成算法较为复杂 实现比较困难 因此 本文主要讨论逐点插入算法 逐点插入法的基本思路及伪代码描述 ProcedureFormTinByAddPoint V V代表建模的点集DivideMesh 对点进行划分网络处理InitialBox 创建包围盒 形成初始三角网Foreachpointpt VDo if LocateTriangle pt T 0 定位三角形 并确定点是否在三角形内 LinkTriangle pt T pt与三角形三个顶点相连TopoInsideTriangle 点在三角形内的拓扑更新 else 点在三角形某一边上 linkTriangle pt T1 T2 连接pt所在边对的两个顶点TopoEdgeTriangle 点在三角形边上的拓扑更新EndifWhile NoEmpty T 对pt影响域中每个三角形执行以下过程 If InCircle pt T1 执行影响域内的空外接圆测试 LOP pt T1 执行LOP局部变换TopoLOPTriangle 执行LOP拓扑更新 DelBox 删除与包围盒顶点连接的多余三角形End 数据网格化和预处理 数据网格化设空间对象集合为V 如图所示 V可按平面位置范围划分为M N个方格块 每一块称为子块 用Bin表示 属于该子块的空间数据则放于该块中 子块单元大小size可按需要确定 数据预处理滤波 为防止测图过程中错误的点直接参与构建DTM 可在提取地形数据时设置 点过滤器 由设计者设定路线行经地区内的高程合理范围 将未在合理范围内的地形点过滤出来 提请设计者修改 压缩 利用坐标平移压缩点列坐标串数据 以每个矩形网格的左下角点为相对坐标原点 并注明该原点在绝对坐标系中的坐标 各分块内部的点列坐标采用相对坐标存储 这样可大量压缩数据 数据结构 散点数据structPOINT doublex y z 三维坐标intNextPtNo 下一个落入同一网格的散点号charattribute 点的属性信息intTriNo 指向以该点为顶点的任意一个三角形号 将随着网形的变化动态更新 点号即为数组的下标 故不需存储 三角形数据structTriangle intvertex 3 按逆时针方向记录的顶点号intAjt 3 按逆时针方向记录的邻接三角形号charattribute 三角形的属性信息charEdgeInf 3 标识三边是否为约束边 扩展属性 目前暂不需要 三角形号为数组下标 不需存储 网格索引intGridArray 指向落在该网格内的首点号 若为空则值为 1 基本算法 拓扑关系的维护 约束Delaunay三角网 CDT CDT的定义标准的Delaunay三角网是满足无任何约束条件的散点域的三角形剖分 而在实际应用中 部分散点之间常常存在着某种约束关系 如道路边界 山脊线 山谷线 断裂线等 在对此种数据域进行三角形剖分时 三角形剖分的结果应保持原有的约束关系 此即约束数据域下的三角剖分 所形成的三角网称为约束Del