数字地形模型

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,DEM,表示方法,数学方法,用数学方法来表达，可以采用,整体拟合,方法，即根据区域所有的高程点数据，用傅里叶级数和高次多项式拟合统一的地面高程曲面；,也可用,局部拟合,方法，将地表复杂表面分成正方形规划区域或面积大致相等的不规则区域进行分块搜索，根据有限个点进行拟合形成高程曲面,DEM,表示方法,线模式：,等高线是表示地形最常见的形式。其它的地形特征线也是表达地面高程的重要信息源，如山脊谷底线等；,点模式：,用离散采样数据点建立,DEM,是,DEM,建立常用方法之一。数据采样可按规则格网采样，可以是密度一致的或不一致的；可以是不规则采样，如不规则三角网；也可以有选择性地采样，采集三峰、洼坑、边界等重要特征点。,图形表示法,等高线,DEM,散点,DEM,三角网,DEM,DEM,表示方法,DEM,主要表示模型,规则格网，,通常是正方形，也可以是矩形、三角形等规则格网。规则格网将区域空间切分为规则的格网单元，每个格网单元对应一个数值；,数学上可以表示为一个矩阵，在计算机实现中则是一个二维数组。每个格网单元或数组的一个元素，对应一个高程值。,规则格网模型,DEM,主要表示模型,规则格网的高程矩阵，可以很,容易地用计算机进行处理,。它还可以很容易地计算等高线、坡度坡向、山坡阴影和自动提取流域地形，使得它成为,DEM,最广泛使用的格式；,格网,DEM,的缺点是不能准确表示,地形结构和细部，,为避免这些问题，可采用附加地形特征数据，如地形特征点、三脊线、谷底线、断裂线，以描述地形结构。,DEM,主要表示模型,格网,DEM,的另一个缺点是,数据量过大,，给数据管理带来了不便，通常要进行压缩存储；,DEM,数据的无损压缩可以采用普通的栅格数据压缩方式，如,游程编码、块码,等；,但是由于,DEM,数据反映了地形的连续起伏变化，通常比较“破碎”，普通压缩方式难以达到很好的效果，可以采用哈夫曼编码。,DEM,主要表示模型,等高线模型表示高程，,高程值的集合是已知的,，每一条等高线对应一个已知的高程值，一系列等高线集合和它们的高程值一起就构成了一种地面高程模型,等高线模型,DEM,主要表示模型,等高线模型,等高线通常被存成一个有序的,坐标点对序列,，可以认为是一条带有高程值属性的简单多边形或多边形弧段；,由于等高线模型只表达了区域的,部分高程值,，往往需要一种,插值方法,来计算落在等高线外的其它点高程。,DEM,主要表示模型,不规则三角网（,Triangulated Irregular Network, TIN,）,TIN,模型具有三个基本要求,TIN,是唯一的；,力求最佳的三角形几何形状，每个三角形尽量接近等边形状；,保证最邻近的点构成三角形，即三角形的边长之和最小。,DEM,主要表示模型,TIN,模型根据区域有限个点集将区域划分为相连的三角面网络，区域中任意点落在三角面的顶点、边上或三角形内。如果点不在顶点上，该点的高程值通常通过线性插值的方法得到（在边上用边的两个顶点高程，在三角形内则用三个顶点的高程）。,DEM,主要表示模型,有许多种表达,TIN,拓扑结构的存储方式，一般来讲，对于每一个三角形、边和节点都对应一个记录，三角形的记录包括三个指向它三个边的记录的指针；边的记录有四个指针字段，包括两个指向相邻三角形记录的指针和它的两个顶点的记录的指针；也可以直接对每个三角形记录其顶点和相邻三角形。,DEM,主要表示模型,有许多种表达,TIN,拓扑结构的存储方式，一般来讲，对于每一个三角形、边和节点都对应一个记录，三角形的记录包括三个指向它三个边的记录的指针；边的记录有四个指针字段，包括两个指向相邻三角形记录的指针和它的两个顶点的记录的指针；也可以直接对每个三角形记录其顶点和相邻三角形。,DEM,主要表示模型,空间数据模型通过空间数据组织和空间数据库对空间对象及其关系进行描述，对空间对象进行提取。空间数据模型有两种分类方法：,（,1,）从认知的的角度：分为基于对象（,object based,）的模型、基于网络,(network based),的模型和基于场（,field based,）的模型；,（,2,）从表达的方式上：分为矢量数据模型、镶嵌数据模型和组合数据模型。,DEM,主要表示模型,镶嵌数据模型的基本思想是：可以用相互连接在一起的网络来覆盖和逼近空间对象。数字高程模型通常用于刻画具有连续变化特征的空间对象，目前最典型的应用就是通过连续网格单元来实现地形曲面的模拟，应归类于基于场的镶嵌数据模型,.,DEM,主要表示模型,当地形数据呈规则分布或由格网,DEM,向,TIN,转换时，其三角剖分与不规则数据域的三角剖分有很大的差异。由于规则格网分布采样数据的特性，对其进行三角形剖分可以有两类方法：,（,1,）直接对角线连接三角化,（,2,）,Delaunay,三角剖分法,DEM,主要表示模型,先来简要了解一下与,Delaunay,三角网密切相关的,Voronoi,图：,Voronoi,图又称为,Dirichlet,镶嵌,( tessellation),，其概念由,Dirichlet,于,1850,年首先提出,; 1907,年俄国数学家,Voronoi,对此作了进一步阐述，并提出高次方程化简,; 1911,年荷兰气候学家,A.H.Thiessen,为提高大面积气象预报的准确度，应用,Voronoi,图对气象观测站进行了有效区域划分。因此在二维空间中，,Voronoi,图也称为泰森,(,Thiessen,),多边形。,Voronoi,图是,Delaunay,三角网的对偶，现在已经成为计算几何中的一种通用的基本几何结构。,Voronoi,图,L,L,L,R,P,1,P,2,P,3,P,4,P,5,A,B,C,D,l,1,l,2,l,3,l,4, 空外接圆准则,Delaunay,三角形外接圆内部包含其它点的性质被用作从一系列不重合的平面点建立,Delaunay,三角网的基本法则。,Delaunay,三角形由三个相邻点连接组成，这三个相邻点对应的,Voronoi,多边形有一个公共的顶点，这个顶点同时也是,Delaunay,三角形外接圆的圆心。在进行,Delaunay,三角形剖分的过程中，每一个三角形都要经过空外接圆检测，目前常用的计算方法是计算三角形外接圆的圆心和半径，然后计算圆心和其他点的距离，通过距离和外接圆半径的比较进行判断，这种判断方法的计算包含了开方、除法、平方等复杂的运算。,Delaunay,三角网, 最小角最大准则,有很多种方法可以对三角形进行剖分，无论怎样进行三角剖分，采样点的高程值都是最准确的。就这个层面来看，无论怎样剖分效果差别都不大，但是就其外观的自然性而言，还是能比较出相对较好的一种效果。,Delaunay,三角网,19,20,36,28,0,0,10,6,19,20,36,28,0,0,10,6,1240,1000,980,990,1008,1008,990,980,1000,1240,P,点高程,=985,P,点高程,=23,p,p,翻转边,合法边,非法边,边翻转操作,非法边,地形的模拟方法有多种，可以区分为物理模拟和数字模拟两大类。数字模拟又分为数学描述和图形描述两类，其中不规则三角网（,TIN,）、规则格网（,Grid,）和等高线地形图是三种典型的图形描述方法。,随着计算机技术和计算机图形学的发展，人们处理大量地形数据和进行真实表达的能力得以提高，,Grid,和,TIN,因其直观易用、更新方便而逐渐成为主流的数字地形模拟方法，本节将重点研究如何应用,Grid,型,DEM,数据进行,Delaunay,三角剖分。,D-TIN,的生成算法,分割合并算法,分割合并算法又称分而治之算法，,Shamos,和,Hoey,于,1975,年最早提出了这种算法，他们将该算法应用到了,Vorinoi,图的生成中。三年后,Lewis,和,Robinson,又将该算法应用到了,D-TIN,的构建中，随后,Lee,和,Schachter,、,Dwyer,等相继对,Lewis,和,Robinson,的算法进行了改进，,Lee,和,Schachter,的改进使其可以适用于无约束数据域的三角剖分，而,Dwyer,的改进则能处理带约束条件的数据。,分割合并算法的基本思想是：首先将各数据点分割成易于进行三角剖分的子集，然后对各子集进行,D-TIN,剖分并进行,LOP,优化，最后将各个自己建立的,D-TIN,进行合并生成最终的整体三角网。,分割合并算法的基本步骤为：,第一步：把所有数据点的集合按升序排列。,第二步：将数据集分割成点个数大致相等的左右两个子集，并对每一个子集进行如下操作：,计算子集的凸壳,以凸壳为数据边界，对每一个子集分别进行,D-TIN,三角剖分并进行优化,找到左右两个子集的凸壳的底线和顶线，并由底线到顶线进行三角网合并。,第三步：如果数据集中的数据个数小于给定的阈值，则直接输出三角剖分结果。,三角网生长算法,从生长过程的角度，三角网生长算法分为收缩生长算法和扩张生长算法。收缩生长算法是先形成整个数据域的数据边界（凸壳），并以此开始逐步缩小直至形成整个三角网。收缩生长算法与数据点的分布密度有关，实际情况往往比较复杂，例如当边界收缩后一个完整的区域可能会分解成若干个互相独立的子区域，这就增加了三角剖分的复杂性。扩张生长算法与收缩算法过程刚好相反，该算法是从一个三角形开始向外层层扩展，最终形成覆盖整个区域的三角网,B,A,C,D,E,F,B,A,C,D,初始三角形,直线分区原理,对在直线,Ax+By+C,=0,的同一侧的所有点（,x,，,y,），实数,Ax+By+C,的正负相同,主要步骤为：,第一步，生成初始三角形。在数据点中任取一点,A,（该点一般是位于数据点的几何中心附近），并寻找距离此点最近的点,B,，两者相连形成初始基线,AB,，如图,2.7,所示。利用空外接圆准则或张角最大准则，在数据域中寻找第三点,C,，从而形成第一个,Delaunay,三角形,ABC,。,第二步，扩展形成三角网。以初始三角形的三条边为初始基线，利用利用空外接圆准则或张角最大准则寻找能与该三条初始基线形成,Delaunay,三角形的,D,、,E,、,F,点。,在该过程中要注意：,初始边界将整个区域分成两个部分，搜寻第三点一般是在初始三角形另一个顶点,异侧,范围内进行。例如若初始三角形为,ABC,，初始边界为,AB,，第三个顶点为,C,，能与三角形,ABC,共用,AB,边的另一个三角形为,ABD,，,D,点要位于,AB,边的另一侧，而不能与,C,同侧。,第三步，重复第二步直到所有的数据处理完毕。,三角网生长算法最早由,Green,和,Sibson,在,Voronoi,图中实现，,Brassel,和,Reif,后来也发表了类似的算法，,McCullagh,和,Ross,通过把点集分块和排序来减少搜索时间。该算法思路清晰，算法简单，但实现效率不高，在该算法基础上有许多改进算法，主要集中在第三点的搜索和三角形全等的判定上。,逐点插入算法,从构网过程来看，分割合并算法和三角网生长算法属于静态剖分过程，在整个三角网形成过程中，新点的介入并不会破坏已经形成的三角网。而逐点插入算法则是一种动态的构网过程，新点的插入会导致已有的三角网进行改变。该算法最早由,Lawson,在,1977,年提出，随后,LeeSchachter(1980),、,Bowyer(1981),、,Watson(1981),、,Sloan(1987),、,Macedonio,和,Pareschi(1991),、,Floriani,和,Puppo(1992),、,Tsai(1993),等人先后对其进行了改进。逐点插入算法的基本过程为：,第一步，定义包含所有数据点的初始包容盒，并对该包围盒进行初始三角剖分。形成矩形包容盒的方法是找出数据域的坐标极值点，然后用这些点形成包容盒。,第二步，对所有数据点进行循环（设当前处理的数据点为,P,），在已经存在的三角网中，查找包,含,P,点的三角形,t,，将,P,与,t,的三个顶点相连，形成,t,的三个初始三角剖分，再用,LOP,算法对初始三角剖分进行,优化处理,。,第三步是对外围三角形进行处理。,（,X,min,，,Y,min,）,（,X,min,，,Y,max,）,（,X,max,，,Y,min,）,（,X,max,，,Y,max,）,图,2.9,矩形包围盒,图,2.10,超级三角形,构造矩形包围盒进行初始三角剖分,void,CTiNPrc:getScope,(),pCal,-,getScope(amCurPt,minPt,maxPt,);,get4Ori();,/,初始化三角网，生成两个初始三角形,void,CTiNPrc:initTicell,(),/,包围盒的,4,个边界点,amCurPt0=oriP0;,amCurPt1=oriP1;,amCurPt2=oriP2;,amCurPt3=oriP3;,CTICell,tiCell,;,