数字高程模型.pptx

《数字高程模型.pptx》由会员分享，可在线阅读，更多相关《数字高程模型.pptx（34页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、一、DTM和DEM的概念数 字 地 形 模 型（DTM，Digital Terrain Model）是描述地形表面形态空间位置和地形属性分布的有序数值阵列。DTM 以离散分布的平面点来模拟连续分布的地形。数字地形模型中地形属性为高程时称 为 数 字 高 程 模 型（Digital Elevation Model，DEM）。不过，被描述的地形属性也可以是地理空间上的地价、污染负荷量、绿化率、降雨量、气温、人口密度等。显然，DEM是DTM的一个子集，是DTM的一个特例。第1页/共34页数字高程模型的表示方法使用三维函数模拟复杂曲面；将一个完整曲面分解成方格网或面积上大体相等的不规则格网，每个格网中

2、有一个点的观测值，即为格网值；适用于曲面插值来表示地下水或土壤的特性；第2页/共34页二、DEM的主要表示模型1.规则格网模型规则网格，通常是正方形，也可以是矩形、三角形等规则网格。规则网格将区域空间切分为规则的格网单元，每个格网单元对应一个数值。数学上可以表示为一个矩阵，在计算机实现中则是一个二维数组。第3页/共34页2.等高线模型等高线模型表示高程，高程值的集合是已知的，每一条等高线对应一个已知的高程值，这样一系列等高线集合和它们的高程值一起就构成了一种地面高程模型。第4页/共34页3.不规则三角网（TIN）模型规则格网DEM的缺陷：1）在地形平坦的地方，存在大量的数据冗余；2）在不改变格

3、网大小的情况下，难以表达复杂地形的突变现象。TIN（Triangulated Irregular Network,TIN）模型根据区域有限个点集将区域划分为相连的三角面网络，区域中任意点落在三角面的顶点、边上或三角形内。如果点不在顶点上，该点的高程值通常通过线性插值的方法得到（在边上用边的两个顶点的高程，在三角形内则用三个顶点的高程）。第5页/共34页4.层次模型层次地形模型（Layer of Details，LOD）是一种表达多种不同精度水平的数字高程模型。层次地形模型允许根据不同的任务要求选择不同精度的地形模型。第6页/共34页三、DEM的数据采集方法1.地面测量利用自动记录的测距经纬仪（

4、常用电子速测经纬仪或全站经纬仪）在野外实测。这种速测经纬仪一般都有微处理器，可以自动记录和显示有关数据，还能进行多种测站上的计算工作。其记录的数据可以通过串行通讯，输入计算机中进行处理。2.现有地图数字化利用数字化仪对已有地图上的信息（如等高线）进行数字化的方法，目前常用的数字化仪有手扶跟踪数字化仪和扫描数字化仪。3.空间传感器利用全球定位系统GPS，结合雷达和激光测高仪等进行数据采集。4.数字摄影测量方法这是DEM数据采集最常用的方法之一。利用附有的自动记录装置（接口）的立体测图仪或立体坐标仪、解析测图仪及数字摄影测量系统，进行人工、半自动或全自动的量测来获取数据。第7页/共34页第8页/共

5、34页四、DEM的建模方法1.DEM的生成流程 DEM生成的全过程包括：原始数据获取、DEM模型构造、数据插值、在所定数据结构支持下的数据存储和模型输出。第9页/共34页2.DEM的空间插值方法 由于DEM采样的数据点呈离散分布形式，或是数据点虽按格网排列，但格网的密度不能满足使用的要求，这就需要以数据点为基础进行插值运算。DEM内插按插点分布范围，可分为分块内插、剖分内插和单点移面内插三类。分块内插，是把需要建立DEM的地区，切割成一定大小的规则方块，形状通常为正方形。在每一个分块上展铺一张数学面，相邻分块之间有适当宽度的重叠带，以使重叠带内全部数据点成为相邻块展铺数学面时的共用数据，保证一

6、张数学面能够较平滑地与相邻分块的数学面拼接。剖分内插 是把需要建立DTM的地区切割成大小和形状不同的子区（剖分），子区间拥有公共边但不重叠，在该区内展铺一个数学面，内插剖分区内任意点的高程。单点移面内插 是以待插点为中心，以适当半径或边长的圆或正方形作为移动面去捕捉适当数目的数据点，并以此展播一张数学面，内插该中心的高程。第10页/共34页3.TIN建模方法不规则三角网（TIN-Triangulated Irregular Network）通过从不规则分布的数据点生成的连续的三角面来逼近地形表面。TIN模型的优点是它能以不同层次的分辨率来描述地形表面。对于TIN模型，其基本要求有三点：TIN是

7、唯一的；力求最佳的三角形形状，每个三角形尽量接近等边形状；保证最临近的点构成三角形，即三角形的边长之和最小。在所有可能的三角形方案中，Delaunay三角网在地形拟和方面表现最为出色，因此常常被用于TIN的生成，而当不相交的断裂线等被作为预先定义的限制条件作用于TIN的生成当中时，则必须考虑带约束条件的Delaunay三角网。第11页/共34页Delaunay三角网的定义 假设，是欧几里德平面上的一个点集，并且这些点不共线，任意四点不共圆。用 表示点间的欧几里德距离，设P为平面上的点，则区域：称为Voronoi多边形（简称V多边形），平面点集中的点则称为V多边形的生长核。Voronoi多边形描

8、述了一个轨迹，即多边形中的点到本多边形生长核的距离小于等于到其它生长核的距离。各点的Voronoi多边形共同组成了Voronoi图。如图虚线所示。连接所有相邻的V-多边形的生长核所形成的三角网称为Delaunay三角网，如图实线所示。Delaunay三角网的外边界是一个凸多边形，它由节点集中的凸集形成，通常称为凸壳或凸包（Convex Hull）。第12页/共34页Delaunay三角网的基本特性Delaunay三角网具有两个非常重要的性质。空外接圆性质：在由点集V所形成的Delaunay三角网中，其每个三角形的外接圆均不包含点集V中的其他任意点。最大最小角度性质：每两个相邻的三角形构成凸四边

9、形的对角线，在相互交换后，六个内角的最小角不再增大。局部优化算法LOP（Local Optimization Procedure）Lawson（1977）提出了根据最大最小角度性质建立局部几何形状最优的三角网：在由两相邻三角形构成的凸四边形中，交换此四边形的两条对角线，不会增加这两个三角形六个内角总和的最小值。Lawson据此提出了局部最优算法LOP：交换凸四边形的对角线，可获得等角性最好的三角网。第13页/共34页Delaunay三角网生成算法综述 根据构建三角网的步骤，可以将三角网生成算法分为三类：（1）分而治之算法（Divide and Conquer Algorithm）、（2）逐点插

10、入算法（Incremental Insertion Algorithm）、（3）三角网生长算法 分而治之算法 Lewis和Robinson于1978年提出了建立Delaunay三角网的分而治之算法，基本步骤是：（1）把点集V以横坐标为主，纵坐标为辅按升序排序，将V分成大小相等的网格，用VL包含数据左半部分点，VR表示右半部分点，然后递归地执行一下步骤；（2）在VL和VR中生成三角网；（3）用LOP算法优化所生成的三角网，使之成为Delaunay三角网；（4）找出连接VL和VR中两个凸包的顶线和底线；（5）由底线至顶线合并VL和VR中的两个三角网。以上步骤显示，分治算法的基本思路是使问题简化，将

11、点集划分的足够小，使其易于生成三角网，然后把子集中的三角网合并成最终的三角网，用LOP算法保证其成为Delaunay三角网。第14页/共34页2.逐点插入算法逐点插入算法的基本步骤是：（1）定义一个包含所有数据点的初始多边形或超级三角形，建立初始三角网，然后迭代以下步骤，直至所有数据点都被处理；（3）插入一个数据点P，在三角网中找出包含P的三角形，把P与三角形T的三个顶点相连，生成三个新的三角形；（4）用LOP算法优化三角网。3.三角网生长算法三角网生长算法的基本步骤是：（1）以任一点为起始点；（2）找出离起始点最近的数据点相互连接成Delaunay三角形的一条边作为基边，按Delaunay三

12、角网的判别法则，找出与基线构成Delaunay三角形的第三点；（3）基线的两个端点与第三点相连，成为新的基线；（4）迭代以上两步直至所有基线都被处理。第15页/共34页4.综述从时间复杂度看，分而治之算法最好，其缺点也是显而易见的，表现在：（1）需要占用较大的内存空间。其原因主要是分治算法需一次性读入所有参加构网的数据；（2）数据预处理工作量较大。由于在构建三角网前要对数据进行排序，故分治算法的预处理工作量较大；（3）优化工作量较大。逐点插入算法实现比较简单，占用内存小，但时间复杂度较差，主要制约因素在于点在三角形中的判断、LOP局部优化过程的拓扑更新以及空外接圆检测。三角网生成算法速度最慢，

13、目前已很少使用，但刘学军在TIN数模的点单位算法及网形优化提出的TBP算法可以提高算法的效率，但从其以后文章看，也抛弃了这种算法。目前研究较多的算法是合成算法，即将逐点插入法与分而治之法融合，即对数据进行分块，子网建立采用逐点插入法，子网间合并采用凸包合并算法，从而解决二者不足。实际，逐点插入法在解决了以上问题后，其速度基本与合成算法接近。合成算法较为复杂，实现比较困难，因此，本文主要讨论逐点插入算法。第16页/共34页逐点插入法的基本思路及伪代码描述 Procedure FormTinByAddPoint(V)/V代表建模的点集DivideMesh();/对点进行划分网络处理InitialB

14、ox();/创建包围盒，形成初始三角网For each point ptV Doif(LocateTriangle(pt,T0);/定位三角形,并确定点是否在三角形内LinkTriangle(pt,T);/pt与三角形三个顶点相连TopoInsideTriangle（）/点在三角形内的拓扑更新else/点在三角形某一边上linkTriangle(pt,T1,T2);/连接pt所在边对的两个顶点TopoEdgeTriangle（）；/点在三角形边上的拓扑更新End ifWhile(NoEmpty(T)/对pt影响域中每个三角形执行以下过程If（InCircle(pt,T1)）;/执行影响域内的空

15、外接圆测试 LOP(pt,T1);/执行LOP局部变换TopoLOPTriangle();/执行LOP拓扑更新DelBox();/删除与包围盒顶点连接的多余三角形End第17页/共34页数据网格化和预处理 数据网格化 设空间对象集合为V，如图所示，V可按平面位置范围划分为MN个方格块，每一块称为子块，用Bin表示，属于该子块的空间数据则放于该块中。子块单元大小size可按需要确定。数据预处理 滤波，为防止测图过程中错误的点直接参与构建DTM，可在提取地形数据时设置“点过滤器”，由设计者设定路线行经地区内的高程合理范围，将未在合理范围内的地形点过滤出来，提请设计者修改。压缩，利用坐标平移压缩点列

16、坐标串数据，以每个矩形网格的左下角点为相对坐标原点，并注明该原点在绝对坐标系中的坐标，各分块内部的点列坐标采用相对坐标存储，这样可大量压缩数据。第18页/共34页数据结构 散点数据struct POINTdouble x,y,z;/三维坐标int NextPtNo;/下一个落入同一网格的散点号char attribute;/点的属性信息int TriNo;/指向以该点为顶点的任意一个三角形号，将随着网形的变化动态更新/点号即为数组的下标，故不需存储；三角形数据struct Triangleint vertex3;/按逆时针方向记录的顶点号int Ajt3;/按逆时针方向记录的邻接三角形号cha

17、r attribute;/三角形的属性信息char EdgeInf3;/标识三边是否为约束边，扩展属性，目前暂不需要。/三角形号为数组下标，不需存储；网格索引int GridArray；/指向落在该网格内的首点号，若为空则值为1。第19页/共34页基本算法第20页/共34页第21页/共34页第22页/共34页第23页/共34页拓扑关系的维护第24页/共34页第25页/共34页第26页/共34页第27页/共34页第28页/共34页第29页/共34页约束Delaunay三角网（CDT）CDT的定义 标准的Delaunay三角网是满足无任何约束条件的散点域的三角形剖分，而在实际应用中，部分散点之间常

18、常存在着某种约束关系，如道路边界、山脊线、山谷线、断裂线等，在对此种数据域进行三角形剖分时，三角形剖分的结果应保持原有的约束关系，此即约束数据域下的三角剖分，所形成的三角网称为约束Delaunay三角网(Constrained Delaunay Triangulation，缩写为CDT)。第30页/共34页第31页/共34页第32页/共34页两步法建立CDT的算法 设当前处理的约束线段（有向）为 ，在一已存在的CDT中加入该连续线段，这一过程可分为两步完成，即：在CDT中加入约束线段顶点 ；对三角网进行局部调整以满足的 可见性及空外接圆法则。对于步骤2，基本思路如下：设当前处理的线段为 ，由与相交的三角形组成的区域 称为的三角形影响域,而由MT中三角形的外围边组成的多边形称为影响多边形 。线段将Q分为左右两部分QL和QR，如图所示，可分别对QL和QR进行三角形剖分和优化。第33页/共34页感谢您的观看！第34页/共34页