《GIS数据结构作业.ppt》由会员分享，可在线阅读，更多相关《GIS数据结构作业.ppt（68页珍藏版）》请在三一办公上搜索。
1、写出下图的拓扑数据结构文件（55图2-18）。,DIME：Dual lndependent Map Encoding，双重（对偶）独立地图编码。链状DIME：是对DIME的一种改进。在DIME中，一条边只能用直线两端点的序号及相邻的面域来表示，而在链状DIME中，将若干直线段合为一个弧段（或链段），每个弧段可以有许多中间点。,矢量数据结构的特点,用离散的点描述空间对象与特征，定位明显，属性隐含用拓扑关系描述空间对象之间的关系面向目标操作，精度高，数据冗余度小与遥感等图象数据难以结合输出图形质量号，精度高,第三节 空间数据结构的类型,栅格数据结构含义 栅格数据结构将空间分割成有规则的网格，在各个
2、网格上给出相应的属性值来表示地理实体的一种数据组织形式。,二、栅格数据结构,第三节 空间数据结构的类型,栅格结构中空间实体的表示点：由一个单元网格表。其数值与近邻网格值明显不同。线段：由一串有序的相连单元网格表示，每个单元最多只有两个相邻单元。各个网格的值比较一致，但与邻域的值差异较大。多边形：由聚集在一起的相互连接的单元网格组成。区域内部的网格值相同或差异较小，但与邻域网格的值差异较大。,空间实体表示示例,第三节 空间数据结构的类型,特点：属性明显，定位隐含。获取方法：(1)手工网格法；(2)扫描数字化法；(3)分类影像输入法；(4)数据结构转换法。,第三节 空间数据结构的类型,手工网格法(
3、透明网格)采集输入步骤,A 确定栅格单元大小B 准备栅格网C 对栅格单元进行编码D 读取栅格单元值E 数据录入,第三节 空间数据结构的类型,1 H=(min Ai)1/2 2,栅格数据的精度 在栅格数据结构中，网格通常是正方形，有时也采用矩形、等边三角形和六边形等，网格边长决定了栅格数据的精度。合理的格网尺寸：为研究区最小图班的1/2长。,第三节 空间数据结构的类型,栅格结构数据中混合像元的处理,方案一,方案二：缩小栅格单元的面积,第三节 空间数据结构的类型,百分比法,中心点法用处于栅格中心处的地物类型或现象特性决定栅格代码。,中心点法,第三节 空间数据结构的类型,栅格面积占优法以占栅格最大的
4、地物类型或现象特征决定栅格代码。,第三节 空间数据结构的类型,长度占优法当覆盖的格网过中心部位时，横线占据该格中的大部分长度的属性值定为该栅格的代码。,第三节 空间数据结构的类型,重要性法根据栅格内不同地物的重要性，选取最主要的地物类型决定相应的栅格单元代码。对于特别重要的地理实体，其所在的区域尽管面积很小或不在中心，也采取保留的原则，如机场、稀有金属矿区域等。,重要性法,第三节 空间数据结构的类型,栅格数据的优点 地理要素表达比较直观，直接记录空间实体的属性值，数据存储结构简单，并容易实现多元数据的叠合操作等。栅格数据的缺点数据冗余度大，造成存储空间的浪费像元大小的变化，对数据精度、长度、面
5、积等的度量有较大影响。栅格结构的主要类型完全栅格结构游程编码结构四叉树数据结构块状编码和链式编码,第三节 空间数据结构的类型,1、栅格矩阵结构最简单的一种栅格结构，栅格数据被看作为一个距阵，逐行或逐列记录属性代码。常用的方法是限制一个栅格只存储栅格的一种属性，并且把属性限制在0255的整数范围内（双字节对应一个像元）。,第三节 空间数据结构的类型,第三节 空间数据结构的类型,栅格矩阵结构,栅格矩阵结构特点数据存储简单，数据无压缩，无损失。数据存储量大，如果每个像元用二个字节表示，存储空间为：m(行)n(列)(字节)。,游程指相邻同值网格的数量，游程编码结构是逐行将相邻同值的网格合并，并记录合并
6、后网格的值及合并网格的长度，其目的是压缩栅格数据量，消除数据间的冗余。,第三节 空间数据结构的类型,2 游程(行程、变长)编码结构,第三节 空间数据结构的类型,游程编码,完全栅格编码,游程编码的主要规则有相同属性值的邻近像元被合并在一起称为一个游程，游程用一对数字表达；每个游程对中的第一个值表示游程属性值(类别)，第二个值表示游程长度。,第三节 空间数据结构的类型,游程编码存储(文件)方法采用索引顺序文件的方法来组织数据。,游程编码结构可以压缩图象存储空间，压缩效果与图幅的属性变化有关，图幅属性的变化越小，行程越长，压缩比例越大，即压缩比与图的复杂程度成反比。一般通过事先预测来估算数据的冗余度
7、：,QRe=1 m.n,式中：Q为图层内相邻属性值变化次数的累加和，m为图层网格的行数，n为图层网格的列数当 Re 1/5时，表明栅格数据的压缩可取得明显的效果。,第三节 空间数据结构的类型,m*n/K,压缩效果可由压缩比表示：,式中：为流程总数（图层内相邻属性值变化次数的累加和），m为图层网格的行数，n为图层网格的列数。压缩比越大，表明压缩效果越显著。,四叉树编码,1、基本思想：将2n2n象元组成的图像按四个象限进行递归分割，判断属性是否单一：单一：不分；不单一：递归分割。最后得到一颗四分叉的倒向树。,一种可变分率的非均匀网格系统。是最有效的栅格数据压缩编码方法之一。,2、四叉树的树形表示：
8、用一倒立树表示这种分割和分割结果根（根节点）：整个区域树叉（父结点）：还需分割的块叶（叶节点）：不能再分割的块高：深度、分几级，几次分割每个树叉均有4个分叉，叫四叉树。,第三节 空间数据结构的类型,、建立四叉树结构的方式自上而下方式(top-down):常规四叉树 从顶层开始，即先检测全区域，其值不单调时再四划分，直到数值或内容单调为止。自下而上方式(bottom-up):线性四叉树 从底层开始，即以像元大小为结点，每记录四个结点时，即生成父结点。4、四叉树结构类型根据四叉树存储结构的不同，可以将四叉树结构类型分为:常规四叉树：自上而下方式线性四叉树：自下而上方式,常规四叉树编码,第3层,第2
9、层,第1层,第0层,根结点,叶结点,父结点,（a）顺序分解表示,（b）常规四叉树形表示,上图所示，图(a)表示区域划分的过程；图(b)为该区域对应的常规四叉树,（1）常规四叉树及编码,常规四叉树编码,1,6,2,3,4,5,叶结点编号,11,12,13,7,8,9,10,常规四叉树编码,从上例中可以看到：一幅2n 2n栅格阵列的图用四叉树分割时，具有的最大深度为N，即可分为0，1，2，n层。如上图n=3，具有的最大深度为3。,从四叉树的分解过程看：被分解的图必须为2n 2n 个栅格，对于不满足2n 2n的图，在分解前需用0补足。如：；确定n的值，使得大于或等于行、列数中的大者，取合乎要求的最小
10、自然数n。建树时对补足部分生成的叶结点可不存储，这样存储量不会增加。,1,0,2,3,10,11,12,13,30,结点编码,31,32,33,300,301,302,303,常规四叉树编码,分割一次，增加一位数字，大分割在前，小分割在后；码的位数表示分割的次数。每一个位均是不大于3的四进制数表达位置，由此找出四叉树叶结点的具体位置。,完全栅格结构扫描顺序示意图,常规四叉树编码,常规四叉树编码,常规四叉树编码,常规四叉树的数据存储结构特点,在常规四叉树的数据存储时，每个结点需要六个变量加以表达：一个变量表示父结点指针四个变量代表四个子结点指针一个变量代表结点的灰度或属性值。,指针不仅增加了数据
11、的存储量，还增加了操作的复杂性：如层次数（分割次数）由从父结点移到根结点的次数来确定，结点所代表的图像块的位置需要从根节点开始逐步推算下来。常规四叉树并不广泛用于存储数据，其价值在于建立索引文件，进行数据检索。,特点及意义,线性四叉树编码,（2）线性四叉树,它不存储树中结点的关系，只是通过编码四叉树的叶结点，表示数据块的层次和空间关系。每个叶结点都具有一个反映位置的关键字，该关键字的码也称为位置码，以表示它所处的位置。记录叶结点的地址码（定位码、Morton码）和属性。四进制、十进制 深度、几次分割,优点：(1)只存储三个值，比常规四叉树节省存储空间；(2)由于记录节点地址，既能直接找到其在四
12、叉树中的走向路径，又可以换算出它在整个栅格区域内的行列位置；(3)压缩和解压缩比较方便，各部分的分辨率可不同，既可精确地表示图形结构，又可减少存储量，易于进行大部分图形操作和运算。,地址码,线性四叉树编码,10,线性四叉树,线性四叉树进行四进制编码叶结点位置采用基于四进制的Morton码表示，这种编码由加拿大学者Morton于1966年提出，称Morton码或Peano键，四进制的Morton码又称为MQ码。MQ码是一串数字组成，每分割一次增加一位数，其中每位数字都是不大于3的四进制数。以行为序，以左下角为起点，按从左到右，从下到上的顺序进行编码,四进制线性四叉树编码(MQ码),编码表,MQ编
13、码计算方法1：四叉树从上而下（形成）（从整体开始）由叶结点找Morton码。A、分割一次，增加一位数字，大分割在前，小分割在后。所以，码的位数表示分割的次数。B、每一个位均是不大于3的四进制数，表达位置。由Morton找出四叉树叶结点的具体位置。,B,A,四进制线性四叉树编码(MQ码),四进制线性四叉树编码(MQ码),MQ编码计算方法:四叉树自下而上合并的方法MQ=2IB+JB（IB、JB分别为栅格单元行列号的二进制数，其始行列号从0计。P55图2-18）,如：已知十进制第一行、第五列的栅格单元，求它的MQ码。首先将十进制第一行、第五列转成二进制形式，得到 行Ib=(001)列Jb=(101)
14、其地址码为:MQ=2Ib+Jb=21+101=103,例:求256*256第20行，第200列的?11021200表示,图(a)所示为88列图，即栅格单元2323，其位置码的最长位数是3位。现对图(a)按MQ码的编码表，依次检查每四个相邻的MQ对应的属性值，相同合并（不同码位去掉），不同则存盘,直到没有能够合并的子块为止。然后进行排序归并得到图(b)MQ码。最后再写成四进制线性四叉树。,四进制线性四叉树编码(MQ码),a.区域栅格表示,b.区域MQ码,四进制线性四叉树,方法,图像大小,两种建立四叉树方法效率的比较,常规四叉树：自上而下方法线性四叉树：自下而上方法,四进制Morton码直观上切合
15、四叉树分割，但许多语言不支持四进制变量，需用十进制表示Morton码。线性四叉树的十进制编码简称MD编码，它同线性四叉树的四进制编码主要不同在于编码值是十进制自然数，其合并过程可直接按自然数顺序进行。,十进制线性四叉树编码(M码),像元顺序以行为序，以左下角为起点，按从左到右，从下到上的顺序扫描。扫描栅格单元的顺序代码称为十进制莫顿码(Morton码)或Peano键。,完全栅格结构扫描顺序示意图（图221）,十进制线性四叉树编码(M码),十进制线性四叉树编码(M码),方法：按位操作的方法如行为2、列为3的栅格的MD步骤：(1)行、列号为二进制：IB=1 0 JB=1 1(2)I行J列交叉：1
16、1 0 1=13(3)再化为十进制.,例:求256*256第20行，第200列的D?,如行为20、列为200的栅格的MD步骤：(1)行、列号为二进制：IB=10100 JB=11001000 二进制计算(2)I行J列交叉：附件计算器(3)再化为十进制.,M与MQ,线性四叉树编码的优点,(1)只存储三个值，比常规四叉树节省存储空间；(2)由于记录节点地址，既能直接找到其在四叉树中的走向路径，又可以换算出它在整个栅格区域内的行列位置；(3)压缩和解压缩比较方便，各部分的分辨率可不同，既可精确地表示图形结构，又可减少存储量，易于进行大部分图形操作和运算。,.写出下图的四叉树结构文件（57图2-20）
17、,?补原则?能使四叉树最简单,2.写出下图的四叉树结构文件（55图2-18右图）。,2.写出下图的四叉树结构文件（55图2-18右图）。,0,1,2,3,03,13,20,030,310,115,113,114,112,110,111,0,1,2,3,03,13,20,030,310,115,113,114,112,110,111,线性四叉树编码,线性四叉树游程编码（二维行程编码表）,线性四叉树游程编码（二维行程编码表）,上表不能用线性四叉树游程编码表示，因为属性没有表示。,带指针的二维行程表,线性四叉树游程编码（二维行程编码表）,用循环指针将同属于一个目标的叶结点链接起来：只要进入第一块就可
18、以顺着指针直接提取该地物的所有子块，从而避免像栅格数据那样为查询某一个目标需遍历整个矩阵，大大提高了查询速度,0,8,32,40,46,带指针的二维行程表,带指针的二维行程表,循环指针指向该地物下一个子块的地址码，并在最后指向该地物本身,3块码-游程编码向二维扩展,采用方形区域作为记录单元，每个记录单元包括相邻的若干栅格。数据对组成：初始行、列，半径，属性值依次扫描，编过的不重复。,特点：具有可变分辨率。即当属性变化小时图块大，对于大块图斑记录单元大，分辨率低，压缩比高。小块图斑记录单元小，分辨率高，压缩比低。因此，与行程编码类似，随图形复杂程度的提高而降低分辩率。,8 0 4 4 7 7 7
19、 7 77 4 4 4 4 4 7 7 76 4 4 4 4 8 8 7 7 5 0 0 4 8 8 8 7 74 0 0 8 8 8 8 7 83 0 0 0 8 8 8 8 82 0 0 0 0 8 8 8 81 0 0 0 0 0 8 8 8 1 2 3 4 5 6 7 8,如：（1,1,0,3),(1,4,1,0),(1,5,1,0),(1,6,3,8)(2,4,1,0),(2,5,1,8),(3,4,2,8),(4,1.),第三节 空间数据结构的类型,（1，1，3，0），（1，4，1，0），（1，5，1，0），（1，6，3，3），（2，4，1，0），（2，5，1，3）；（3，4，2，
20、3），（4，1，2，0），（4，3，1，3），（4，6，1，3）；（4，7，1，5），（4，8，1，3），（5，3，1，2），（5，4，1，3）；（5，5，2，3），（5，7，2，5），（6，1，1，2）；（6，2，1，2），（6，3，1，2），（6，4，1，2），（7，1，1，2），（7，2，2，2）；（7，4，1，2），（7，5，1，2）；（7，6，2，5），（7，8，1，5）；（8，1，1，0），（8，4，1，5）；（8，5，1，5），（8，8，1，5）；,第三节 空间数据结构的类型,4 链式编码或Freeman(弗里曼)链码或边界链码,将栅格数据（线状地物、面域边界）表示为矢量链的记录
21、。编辑方法：首先定义一个3x3窗口，中间栅格的走向有8种可能，并将这8种可能07进行编码；再记下地物属性码和起点行、列后，进行追踪，得到矢量链表。,a,a,a,a,a,a,b,优点：链码可有效地存贮压缩栅格数据，便于面积、长度、转折方向和边界、线段凹凸度的计算。缺点：不易做边界合并，插入操作、编辑较困难（对局部修改将改变整体结构）。区域空间分析困难，相邻区域边界被重复存储。,第三节 空间数据结构的类型,直接栅格编码：简单直观，是压缩编码方法的逻辑原型（栅格文件）；游程长度编码：在很大程度上压缩数据，又最大限度的保留了原始栅格结构，编码解码十分容易，十分适合于微机地理信息系统采用；链码：压缩效率
22、较高，以接近矢量结构，对边界的运算比较方便，但不具有区域性质，区域运算较难；块码和四叉树编码：具有区域性质，又具有可变的分辨率，有较高的压缩效率，四叉树编码可以直接进行大量图形图象运算，效率较高，是很有前途的编码方法。,第三节 空间数据结构的类型,矢量与栅格数据结构的比较80,矢量与栅格数据结构的选择,在GIS建立过程中，应根据应用目的和应用特点、可能获得的数据精度以及地理信息系统软件和硬件配置情况，选择合适的数据结构。栅格结构:大范围小比例尺的自然资源、环境、农林业等区域问题的研究。矢量结构：城市分区或详细规划、土地管理、公用事业管理等方面的应用。,(1)矢量数据编码的2种方式：拓扑数据结构
23、(2)栅格数据编码的5种方式。(3)游程编码的含义及编码。(4)四叉树数据结构的含义及分解过程。(5)矢量和栅格数据结构的优缺点及选择。,矢栅数据结构内容及重点,3、曲面数据结构,第三节 空间数据结构的类型,曲面是指连续分布现象的覆盖表面，如地形、降水量、温度、磁场等要素。表示和存储这些要素的基本要求是必须便于连续现象在任一点的内插计算，因此经常采用不规则三角网来拟合连续分布现象的覆盖表面，称为TIN数据结构。Triangulated lrregular Network-三角形不规则网络、不规则三角网,三角形不规则网的表达,三角形不规则网的表达,不规则三角网将各种来源的高程点连接成一系列无重叠
24、的三角形。这种基于TIN的曲面数据结构，通常用于数字地形的表示，或者按照曲面要素的实测点分布，将它们连接起来。由于连接的原则不同，可以有多种TIN的生成方法。,不规则三角网的自动联结(又称三角剖分)算法中，主要遵循以下两条准则：在所形成的三角形网格中，每个三角形的最小内角尽量大，即每个三角形尽量接近等边；保证最邻近的点构成三角形，即三角形的边长之和最小。,在满足上述要求、而又可能建立三角网的方法中，D-TIN（Delaunay狄洛尼三角网）在地形拟合方面表现最为出色，因此常被用于TIN的生成。,构成不规则三角形网的基本准则,表面三角网中的每个三角形要求尽量接近等边形状；并保证三角形的边长之和最
25、小。每个不规则三角形可被视为一个平面，平面的几何特性完全由三个顶点的空间坐标值(X，Y，Z)决定。,狄洛尼Delaunay三角网的构成,三角形文件,结点文件,每个三角形的选取要代表某一斜平面的临界点。在地形图上可以人为直接的或按着一定规定确定出三角形，进而建立起不规则三角形网络模型。TIN的模型不受事先规定布点方式的限制，能够较好的表达地形特点。需要建立拓扑关系时，用两个数据文件就可以表达出所需要的拓扑关系。即结点文件和三角形文件。这种数据结构的相邻三角形信息可以自动生成，而且利用这种相邻三角形信息，便于连续分布现象的顺序追踪和查询检索。例如：对地形结构线的追踪，是非常便捷的。利用这种数据结构，可以方便地进行地形分析，如坡度和坡向信息提取，填挖方计算，阴影和地形通视分析，等高线自动生成和三维显示等。因此，TIN数据结构被广泛应用于各种地理信息系统，如ArcGIS、MGE等。,不规则三角形网的特点,规则格网的曲面数据结构(GRID),规则格网的曲面数据结构类似于矩阵形式的栅格数据，只是其属性值为地面的高程或其他连续分布现象的数据,
