空间数据结构课件

,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,Click to edit Master title style,地理信息系统电子教案,任课教师：姚晓军,电子邮箱：,yaoxj_nwnu,西北师范大学地理与环境科学学院,本章内容,1.,矢量数据结构,2.,栅格数据结构,3.,曲面数据结构,4.,空间数据结构的建立,空间数据结构,空间数据结构是指对空间逻辑数据模型描述的数据组织关系和编排方式。,A,B,M,1,A,B,概念模型,逻辑模型,编码,建立关系,物理模型,数据结构,矢量数据结构,概念,基于矢量模型的数据结构简称为矢量数据结构，它是一种利用欧几里德几何学中的点、线、面及其组合体来表示地理实体空间分布的数据组织方式。,类型,实体数据结构,拓扑数据结构,矢量数据结构,实体数据结构,说明,在实体数据结构中，空间数据按照基本的空间对象（点、线或多边形）为单元进行单独组织，其中不包含拓扑关系信息。,典型,Spaghetti,结构,应用,ArcView,的,Shape,文件,MapInfo,的,Tab,文件,矢量数据结构,实体数据结构,矢量数据结构,实体数据结构,特点,数据按点、线或多边形为单元进行组织，数据结构直观简单。,每个多边形都以闭合线段存储，多边形的公共边界被数字化两次和存储两次，容易造成数据冗余和产生不一致。,矢量数据结构,实体数据结构,特点,点、线和多边形有各自的坐标数据，但没有拓扑数据，彼此不关联。,岛或洞只作为一个单个图形，没有建立与外界多边形的联系。,矢量数据结构,拓扑数据结构,定义,拓扑数据结构是指具有拓扑关系的矢量数据结构。,类型,索引式结构,双重独立编码结构,链状双重独立编码结构,矢量数据结构,拓扑数据结构,基本概念,弧段,构成多边形的边称为弧段。,节点,两条弧段相交的点为节点。,岛（洞）,由一条弧段组成的多边形称为岛（或洞）。,简单多边形,不含岛的多边形称为简单多边形。,复合多边形,含岛的多边形称为复合多边形。,矢量数据结构,拓扑数据结构,索引式结构,索引式结构采用树状索引以减少数据冗余并间接增加邻域信息。,具体方法是对所有边界点进行数字化，将坐标对以顺序方式存储，由点索引与边界线号相联系，以线索引与各多边形相联系，形成树状索引结构。,矢量数据结构,拓扑数据结构,点,ID,坐标,1,x,1,y,1,点坐标文件,线段,ID,组成的点,ID,a,1,2,3,4,5,线段文件,多边形,ID,组成的线段,ID,A,a,b,c,多边形文件,矢量数据结构,拓扑数据结构,双重独立编码结构,美国人口统计系统采用的一种编码方式，简称,DIME,（,Dual Independent Map Encoding,）编码系统，它是以城市街道为编码主体，它的特点是采用了拓扑编码结构，这种结构最适合于城市信息系统。,双重独立编码结构是对图上网状或面状要素的任何一条线段，用顺序的点定义以及相邻多边形来予以定义。,矢量数据结构,拓扑数据结构,1,2,3,4,5,6,7,8,9,10,a,b,c,d,e,f,g,h,i,j,k,l,11,12,13,m,n,o,A,B,C,D,Q,点,ID,坐标,1,x,1,y,1,点坐标文件,线段,ID,起点,终点,左多边形,右多边形,a,1,6,Q,A,线段文件,多边形,ID,组成的线段,ID,A,a,b,c,d,e,多边形文件,矢量数据结构,拓扑数据结构,矢量数据结构,拓扑数据结构,链状双重独立编码结构,链状双重独立编码结构是,DIME,数据结构的一种改进。,应用：,ArcGIS,的,Coverage,文件,矢量数据结构,拓扑数据结构,点,ID,坐标,1,x,1,y,1,点坐标文件,弧段,ID,起始点,终结点,左多边形,右多边形,a,1,5,A,弧段文件,弧段,ID,点,ID,A,1,2,3,4,5,弧段点文件,多边形,ID,弧段,ID,面积,周长,A,a,b,c,d,e,多边形文件,栅格数据结构,概念,基于栅格模型的数据结构称为栅格数据结构，它将空间分割成有规则的网格，称为栅格单元，在各个栅格单元上给出相应的属性值来表示地理实体的一种数据组织形式。,栅格数据结构,组织方式,在栅格数据结构中，点用一个栅格单元表示。,线用一串有序的相互连接的单元网格表示，各个网格的值相同。,多边形由聚集在一起的相互连接的单元网格组成，区域内部的网格值相同，但与外部网格的值不同。,栅格数据结构,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,点状地物的表示,栅格数据结构,线状地物的表示,0,0,0,0,0,0,0,0,0,0,0,6,0,0,0,0,0,0,0,6,0,6,0,0,0,0,0,0,6,0,6,0,0,0,0,0,0,0,6,0,0,0,0,0,0,0,6,0,0,0,0,0,0,0,0,6,0,0,0,0,0,0,0,0,栅格数据结构,面状地物的表示,0,4,4,7,7,7,7,7,4,4,4,4,4,7,7,7,4,4,4,4,8,8,7,7,0,0,4,8,8,8,7,7,0,0,8,8,8,8,7,8,0,0,0,8,8,8,8,8,0,0,0,0,8,8,8,8,0,0,0,0,0,8,8,8,栅格数据结构,栅格单元大小,栅格单元大小又称栅格单元的尺寸，即分辨率。,合理的栅格单元尺寸应能有效地逼近空间对象的分布特征，以保证空间数据的精度，通常以,保证最小图斑不丢失,为原则来确定合理的栅格尺寸。,设研究区域某要素的最小图斑面积为,S,，栅格单元的边长,L,用如下公式计算：,栅格数据结构,栅格单元值的选取,中心点法,用位于栅格中心处的地物类型作为栅格属性值。,面积占优法,以占矩形区域面积最大的地物类型作为栅格单元的代码。,重要性法,根据栅格内不用地物的重要性，选取最重要的地物类型作为相应的栅格单元代码。,百分比法,根据矩形区域内各地理要素所占面积的百分比数确定栅格单元的取值。,How Polygon To Raster (Conversion) works,CELL_CENTER METHOD,MAXIMUM_AREA METHOD,MAXIMUM_COMBINED_AREA METHOD,栅格数据结构,类型,完全栅格数据结构,压缩栅格数据结构,链码结构,游程编码结构,四叉树数据结构,影像金字塔结构,栅格数据结构,完全栅格数据结构,完全栅格数据结构将栅格数据看作一个数据矩阵，逐行（或逐列）逐个记录栅格单元的值。,记录方法,每行都从左到右逐个像元记录,奇数行从左到右而偶数行从右向左记录,按其他特殊顺序记录,栅格数据结构,完全栅格数据结构,栅格数据结构,完全栅格数据结构,Morton,码计算方法,将行号和列号的转换为二进制数；,两个二进制数两两交叉，得到新的二进制数；,将新二进制数转换为十进制数。,例如第二行第三列对应的栅格单元，其二进制行号分别为,0010,（行）、,0011,（列），则其莫顿码为（,00001101,）,2=,（,13,）,10,栅格数据结构,完全栅格数据结构,栅格数据存储方式,BSQ,（,Band sequential,）,将图像同一波段的数据逐行存储下来，再以相同方式存储下一波段的数据。,BIP,（,Band interleaved by pixel,）,按顺序存储所有波段的第一个像素，接着是所有波段的第二个像素，交叉存储所有像素。,BIL,（,Band interleaved by line,）,先存储第一个波段的第一行，接着是第二个波段的第一行，交叉存储直到所有波段都存储为止。,栅格数据结构,完全栅格数据结构,完全栅格数据编码,栅格数据结构,完全栅格数据结构,计算栅格数据的大小,如果矩阵的每个元素用一个双字节表示，则一个图层的全栅格数据所需要的存储空间为：,m,（行）,n,（列）,2,（字节）,深入理解,在完全栅格数据结构中，随着空间分辨率的提高，存储数据量将成几何级数递增。,栅格数据结构,链码结构,链码又称为弗里曼链码（,Freeman,）或边界链码，它由某一起始点和在某些基本方向上的单位矢量链组成。,基本方向有东、东南、南、西南、西、西北、北、东北等,8,个，分别用,0,，,1,，,2,，,3,，,4,，,5,，,6,，,7,表示，即可按顺时针也可按逆时针表示。,编码的前两位为地物的起点坐标。,栅格数据结构,链码结构,0,1,2,3,4,5,7,6,栅格数据结构,链码结构,编码过程,起始点的寻找一般遵从从上到下、从左到右的原则。,当发现没有记录过的点，而且数值不为零时，就是一条线或边界线的起点。记下该地物的特征码及起点的行列数；然后按顺时针方向寻迹，找到相邻的等值点，并按,8,个方向编码。如遇不能闭合的线段，结束后可以返回到起始点再开始寻找下一个线段。已经记录过的栅格单元，可将属性代码置为零，以免重复编码。,栅格数据结构,链码结构,优点,链码可以有效地压缩栅格数据，而且对于估算面积、长度、转折方向的凹凸度等运输十分方便，比较适合于存储图形数据。,缺点,对边界进行合并和插入等修改编辑工作比较困难，对局部的修改将改变整体结构，效率较低，而且由于链码以每个区域为单位存储边界，相邻区域的边界将被重复存储而产生冗余。,栅格数据结构,游程编码结构,游程,游程是指栅格矩阵一行内相邻同值栅格的数量，也称为行程（,run-length,）。,游程编码结构,游程编码结构是逐行将相邻同值的栅格合并，记录合并后栅格的值及合并栅格的数量（即游程），其目的是压缩栅格数据量，消除数据间的冗余。,栅格数据结构,游程编码结构,编码方法,将栅格数据的一行数据序列,X,1,X,2,X,n,，映射为相应的二元组序列（,A,i,P,i,），,i=1,K,，且,K,n,。其中,A,i,为属性值，,P,i,为游程，,i,为游程序号。,数据冗余度,其中,Q,为相邻属性值变化次数的累加和，,m,为行数，,n,为列数。,当,R,e,的值大于,1/5,时，表示栅格数据的压缩可取得明显效果。,栅格数据结构,游程编码结构,Grids use a run-length raster compression scheme that is adaptive at the block level. Each block is tested to determine the depth (bits per cell) to be used for the block and to determine which storage technique (cell by cell or run length coded) is more efficient.,栅格数据结构,四叉树数据结构,原理,将空间区域按照四个象限进行递归分割,n,次，每次分割形成,2,n,2,n,个子象限，直到子象限中的属性数值都相同为止，该子象限就不再分割。凡属性值都相同的子象限，不论大小，均作为最后的存储单元。,栅格数据结构,四叉树数据结构,栅格数据结构,四叉树数据结构,生成方法,自上而下方式,先检测全区域，其值不相同时即四叉分割，直到最小栅格都相同为止。,自下而上方式,按照莫顿（,Morton,）码顺序扫描栅格单元，先检测前,4,个单元，若这,4,个单元值相同，则合并；反之作为,4,个叶节点记录。然后是后,4,个单元，依此逐层向上，直到最后生成根节点。,存储方法,常规四叉树,线性四叉树,栅格数据结构,四叉树数据结构,采用四叉树编码时，为了保证四叉树分解能够不断地进行下去，要求图像必须为,2,n,*2,n,的栅格阵列。对于非标准尺寸的图像需首先增加背景的方法将图像扩充为,2,n,*2,n,的图像。,由于四叉树编码能够自动地依照图形变化而调整象限尺寸，即具有可变的分辨率，并且有区域性质，因此它具有极高的压缩效率。,栅格数据结构,影像金字塔结构,概念,影像金字塔是指在统一的空间参照下，根据用户需要以不同分辨率进行存储与显示，形成分辨率由粗到细、数据量由小到大的金字塔结构。,深入理解,影像金字塔结构用于图像编码和渐进式图像传输，是一种典型的分层数据结构形式，适合于栅格数据的多分辨率组织，是一种有损压缩方式。,栅格数据结构与矢量数据结构的比较,位置明显，属性隐含,属性明显，位置隐含,栅格数据结构与矢量数据结构的比较,栅格数据结构,优点,数据结构简单，易于算法实现；,空间数据的叠置和组合容易，有利于与遥感数据的匹配应用和分析；,各类空间分析、地理现象模拟均较为容易；,输出方法快速简便、成本低廉。,栅格数据结构与矢量数据结构的比较,栅格数据结构,缺点,图形数据量大，用大像元减小数据量时，精度和信息量受损失；,难以建立空间网络连接关系；,投影变换实现困难；,图形数据质量低，地图输出不精美。,栅格数据结构与矢量数据结构的比较,矢量数据结构,优点,数据结构严密，冗余度小，数据量小；,空间拓扑关系清晰，易于网络分析；,能够实现图形数据的恢复、更新和综合；,图形显示质量好、精度高。,栅格数据结构与矢量数据结构的比较,矢量数据结构,缺点,数据结构处理算法复杂；,叠置分析与栅格图组合比较难；,数学模拟比较困难；,空间分析技术上比较复杂，需要更复杂的软、硬件条件；,显示与绘图成本比较高。,曲面数据结构,曲面,曲面是指连续分布现象的覆盖表面，具有这种覆盖表面的要素有地形、降水量、温度和磁场等。,曲面数据结构,TIN,（,Triangular Irregular Network,）,TIN,（不规则三角网）是将离散分布的实测数据点连成三角网，网中的每个三角形要求尽量接近等边形状，并保证由最近邻的点构成三角形，即三角形的边长之和最小。,Node,Edge,Triangle,Hull,曲面数据结构,某区域地形等高线,曲面数据结构,某区域栅格,DEM,曲面数据结构,某区域,DEM(TIN),曲面数据结构,TIN,在所有可能的三角网中，,Delaunay,三角网最常用。,Delaunay,三角网是一种满足最大空圆准则的三角网，即任一三角形的外接圆内不包含其他样点。,曲面数据结构,TIN,优点,三角形大小随样点密度的变化而自动变化，即分辨率可变，可以有效的消除数据冗余。,组织形式,点文件：每个样点对应一个记录，给出该点的,x,y,坐标，以及属性值,三角形拓扑文件：组织三角形与样点以及三角形与相邻三角形的邻接关系，每个记录依顺时针方向列出三个顶点号及三个相邻的三角形号，其中相邻三角形的顺序按按每个顶点对边给定的三角形列出。,空间数据结构的建立,概念,空间数据结构的建立是指根据确定的数据结构类型，形成与该数据结构相适应的,GIS,空间数据，为空间数据库的建立提供物质基础。,空间数据结构的建立,空间数据结构的建立,系统功能与数据间的关系,现代地理信息系统数据模式的一个重要特征是数据与功能之间具有密切的联系。,通常每一类数据都包含一系列数据实体，而每种数据实体由许多数据项组成，确定这些类型的数据是由系统的功能所决定的。,空间数据结构的建立,空间数据的分类,概念,空间数据的分类是指根据系统功能及国家规范和标准，将具有不同属性或特征的要素区别开来的过程，以便从逻辑上将空间数据组织为不同的信息层，为数据采集、存储、管理、查询和共享提供依据。,原则,图形原则,对象原则,空间数据结构的建立,空间数据的分类,我国基础地理信息数据分类,测量控制点,水系,居民地,交通管线与垣栅,境界,地形与土质,植被,空间数据结构的建立,空间数据的编码,概念,空间数据的编码，是指将数据分类的结果，用一种易于被计算机和人识别的符号系统表示出来的过程。,结果,编码的结果是形成代码，代码由数字或字符组成，或由它们共同组成混合码。,目的,用来提供空间数据的地理分类和特征描述，同时为了便于地理要素的输入、存储、管理，以及系统之间数据交换和共享的需要。,空间数据结构的建立,空间数据的编码,国家基础地理信息数据的分类代码由六位数字码组成，其结构如下：,空间数据结构的建立,编码,要素名称,10000,测量控制点,11000,平面控制点,12000,高程控制点,13000,其它控制点,20000,水系,21000,河流,22000,运河、渠道,23000,湖泊,24000,水利设施,25000,其它水系要素,26000,海洋要素,27000,水系附属说明,编码,要素名称,30000,居民地,31000,居民地行政等级,32000,居民地建筑物,40000,交通,41000,铁路,42000,公路,43000,铁路和公路主要构筑物,44000,航运,45000,港口,46000,空运,50000,管线与垣栅,引自,GB13923-92,空间数据结构的建立,编码,要素名称,51000,管线,52000,垣栅,60000,境界,61000,行政区划界,62000,其它界线,70000,地形与土质,71000,等高线,72000,高程,73000,冰川地貌,74000,冻土地貌,75000,黄土地貌,76000,岩溶地貌,77000,风成地貌,78000,火山地貌,编码,要素名称,79000,其他地貌形态及土质,80000,植被,81000,耕地,82000,园地,83000,林地,84000,草地,85000,其他植被,86000,地类界线,90000,其它,91000,重要科学测站,92000,文物古迹、具有纪念意义的建筑物,93000,工矿设施,94000,农田设施,95000,公共设施,空间数据结构的建立,矢量数据的输入与编辑,数据采集方式,手扶跟踪数字化仪数字化,屏幕数字化,扫描矢量化,屏幕数字化,打开栅格图像数据,图像配准,输入空间数据,输入属性数据,空间数据结构的建立,矢量数据的输入与编辑,图形数据编辑,叠合比较法,目视检查法,逻辑检查法,属性数据编辑,逻辑检查,人工校对,空间数据结构的建立,矢量数据的输入与编辑,图形数据编辑,叠合比较法,目视检查法,逻辑检查法,属性数据编辑,逻辑检查,人工校对,空间数据结构的建立,栅格数据的输入,数据产生方式,扫描输入,遥感影像解译,数据结构转换,曲面数据输入,数据产生方式,对采集的离散数据点进行空间插值,