《第二章空间数据结构及编码ppt课件.ppt》由会员分享，可在线阅读，更多相关《第二章空间数据结构及编码ppt课件.ppt（110页珍藏版）》请在三一办公上搜索。
1、第二章 空间数据结构及编码,1、从现实世界到计算机世界,概念模型,数据模型,数据结构,文件格式,四个层次,按照著名数据库专家E.F.Codd的理论认为数据模型实质上是一组为用户服务的规则,这些规则规定其数据结构如何组织以及应当允许进行何种操作。,一 基本概念,2.Gis中地理空间数据组织的主要对象,从地理空间现象或事物到计算机世界,一般也要有概念模型,数据模型,数据结构和文件格式几个层次.这个过程有时统称为地理空间数据建模,Gis怎样组织数据以模拟地理事物和现象的呢?,举例,我们将gis所抽象,表达的地理事物和现象,称为空间对象;空间对象的位置相互关系,称为空间关系,a空间对象,点状空间对象(
2、0维对象)线状空间对象面状空间对象体状空间对象,除空间维数特性外,空间对象还可以从其复杂性,规则性,人为性等角度认识和区分,b空间关系通常分为3类度量空间关系顺序空间关系拓扑空间关系-连接性-包含-邻接性,3.空间数据结构和空间数据模型两个概念之间的关系,空间数据结构和空间数据模型研究地理空间数据组织和管理.两者之间的关系,与一般的数据结构和数据模型的关系有两点相似之处.其一,空间数据结构所作的数据组织工作,比空间数据模型更基层些,它偏重数据表达的物理实现,而空间数据模型涉及到空间数据管理的层次.其二，同普通数据的数据模型一样,空间数据模型的命名通常与相应的空间数据结构相同.,4.空间分析与非
3、空间分析,5.空间数据 定义 特点：数据的空间性 数据的属性 数据的时间性,6.空间数据的编码,7.空间数据的拓扑关系,地理要素之间的空间区位关系可抽象为点、线（或弧）、多边形（区域）之间的空间几何关系，其关系如下,欧氏平面上实体对象所具有的拓扑和非拓扑属性,弧属性表（AAT）,多边形属性表（PAT）,1.本图有多少个多边形和弧？2.哪个多边形是包含于另一个中？3.哪个多边形和多边形102相邻？4.手工建立一个简单示意图表明本图的空间格局,二、栅格数据结构,定义：又称为网格结构，它是将地表划分成为紧密相邻的网格阵列。每个网格的位置由行列号定义。它包含一个代码，以表示该网格的属性或指向属性记录的
4、指针。注意：栅格数据模型是将连续空间离散化，即用二维铺盖或划分覆盖整个连续空间，这种铺盖可以分为规则的和不规则的,1.概念,三角形、方格和六角形划分,栅格数据模型,2.图形栅格数据结构表示,线,面,点,3.决定栅格单元代码的方式,面积占优法,中心点法,重要性法,4.栅格结构编码方式,直接栅格编码行程编码块码链式编码四叉树结构二维行程编码,基本思路：对于一幅栅格图像，常常有行（或列）方向上相邻的若干点具有相同的属性代码，因而可采取某种方法压缩那些重复的记录内容。,游程长度编码（Run-Length Codes）,1）只在各行（或列）数据的代码发生变化时依次记录该代码以及相同的代码重复的个数，从而
5、实现数据的压缩。,两种方案,（属性值，长度）,例如（0，1）,（4，2）,（7，5）；（4，5）,（7，3）；（4，4）,（8，2）,（7，2）；（0，2）,（4，1）,（8，3）,（7，2）;（0，2）,（8，4）,（7，1）,（8，1）；（0，3）,（8，5）；（0，4）,（8，4）；（0，5）,（8，3）。,压缩比的大小是与图的复杂程度成反比的，在变化多的部分，游程数就多，变化少的部分游程数就少，图件越简单，压缩效率就越高,44：64,2）逐个记录各行（或列）代码发生变化的位置和相应代码,编码如下（沿列方向）（1，0），（2，4），（4，0）；（1，4），（4，0）；（1，4），（5，8
6、），（6，0）；（1，7），（2，4），（4，8），（7，0）；（1，7），（2，4），（3，8），（8，0）；（1，7），（3，8）；（1，7），（6，8）；（1，7），（5，8）。,（属性值，属性发生变化的位置）,特点：属性的变化愈少，行程愈长，则压缩的比例越大，压缩比与图的复杂程度成反比。,块码是游程长度编码扩展到二维的情况，采用方形区域作为记录单元，每个记录单元包括相邻的若干栅格，数据结构由初始位置（行、列号）和半径，再加上记录单位的代码组成。,块 码,对图所示图像的块码编码如下：(1,1,1,0),(1,2,2,4),(1,4,1,7),(1,5,1,7),(1,6,2,7),(1,
7、8,1,7),(2,1,1,4),(2,4,1,4),(2,5,1,4),(2,8,1,7),(3,1,1,4),(3,2,1,4),(3,3,1,4),(3,4,1,4),(3,5,2,8),(3,7,2,7),(4,1,2,0),(4,3,1,4),(4,4,1,8),(5,3,1,8),(5,4,2,8),(5,6,1,8),(5,7,1,7),(5,8,1,8),(6,1,3,0),(6,6,3,8),(7,4,1,0),(7,5,1,8),(8,4,1,0),(8,5,1,0)。,该例中块码用了120个整数，比直接编码还多，这是因为例中为描述方便，栅格划分很粗糙，在实际应用中，栅格划
8、分细，数据冗余多的多，才能显出压缩编码的效果，而且还可以作一些技术处理，如行号可以通过行间标记而省去记录，行号和半径等也不必用双字节整数来记录，可进一步减少数据冗余。,块码具有可变的分辨率，即当代码变化小时图块大，就是说在区域图斑内部分辨率低；反之，分辨率高。块码与游程长度编码相似，随着图形复杂程度的提高而降低效率，就是说图斑越大，压缩比越高；图斑越碎，压缩比越低。块码在合并、插入、检查延伸性、计算面积等操作时有明显的优越性。然而在某些操作时，则必须把游程长度编码和块码解码，转换为基本栅格结构进行。,链码（Chain Codes）,基本思想：将一幅栅格地图或图像等分为四部分，逐块检查其格网属性
9、值（或灰度），如果某个子区的所有格网值都相同，则这个子区就不再继续分割，否则还要把这个子区再分割，直到每个子块都只含有相同的属性值或灰度为止。,四叉树结构,四叉树编码具有可变的分辨率，并且有区域性质，压缩数据灵活，许多运算可以在编码数据上直接实现，大大地提高了运算效率，是优秀的栅格压缩编码之一,1）从四叉树的特点可知，一幅2n*2n 栅格阵列图，具有的最大深度数为n，可能具有的层次为0，1，2，.n,注 意,2）每一层的栅格宽度，即每层边上包含的最大栅格数，反映了所在叶结点表示的正方形集合的大小，其值为：2（最大深度-当前层次）,例如：一幅23 23 的栅格阵列，它具有的最大深度为3，可能层次
10、分别为0，1，2，3。其中：第0层边长上的最大栅格数为2（3-0）8 第1层边长上的最大栅格数为2（3-1）4 第2层边长上的最大栅格数为2（3-2）2 第3层边长上的最大栅格数为2（3-3）1,0层,1层,2层,3层,（1）,（2）,（3）,（4）,（5）,（6）,（7）,（8）,（9）,（10）,（11）,（12）,（13）,（14）,（15）,（16）,（17）,（18）,（19）,常规四叉树除了记录叶结点之外，还要记录中间结点。结点之间借助指针联系，每个结点需要用六个量表达，即四个叶结点指针、一个父结点指针和一个结点的属性或灰度值。这些指针不仅增加了数据储存量，而且增加了操作的复杂性。
11、,常规四叉树与线性四叉树,线性四叉树只存储最后叶结点的信息。包括叶结点的位置、深度和本结点的属性或灰度值线性四叉树叶结点的编号需要遵循一定的规则，这种编号成为地址码，它隐含了叶结点的位置和深度信息。,a.基于深度和层次码的线性四叉树的编码 它是通过记录叶结点的深度码和层次码来描述叶结点的位置码,几种线性四叉树的编码,0层,1层,2层,3层,（1）,（2）,（3）,（4）,（5）,（6）,（7）,（8）,（9）,（10）,（11）,（12）,（13）,（14）,（15）,（16）,（17）,（18）,（19）,该地址码的十进制为：？,0层,1层,2层,3层,（1）,（2）,（3）,（4）,（5）
12、,（6）,（7）,（8）,（9）,（10）,（11）,（12）,（13）,（14）,（15）,（16）,（17）,（18）,（19）,b.基于四进制的线性四叉树编码,0层,1层,2层,3层,（1）,（2）,（3）,（4）,（5）,（6）,（7）,（8）,（9）,（10）,（11）,（12）,（13）,（14）,（15）,（16）,（17）,（18）,（19）,思 考,请为23 23 栅格阵列中的每个栅格建立基于四进制的四叉树编码方式的地址码？你能找出何种规律？,先将栅格的行列号转换为二进制，得二进制行号Iyb，列号Ixb，则M=2IybIxb 如结点7：M=2*011+011033,如果知道基
13、于四进制四叉树编码方式的地址码，你能知道它的行列号码吗？,思 考,若该位的编码值为0，1，则行号Iyb值为0；若该位的编码值为2，3，则行号Iyb值为1；若该位的编码值为0，2，则列号Ixb值为0；若该位的编码值为1，3，则列号Ixb值为1；如：M码为：1 0 3 二进制行值Iyb为：0 0 1 二进制列值Ixb为：1 0 1,规则：首先将二维栅格数据的行列号转换为二进制，然后交叉放入Morton码中，即为线性四叉树的地址码：行号5（1 0 1）；列号7（1 1 1）Morton 1 1 0 1 1 155,c.基于十进制的线性四叉树编码,请快速建立 8*8 栅格阵列中的每个栅格的 Morto
14、n,思 考,二维行程编码,二维行程编码,再议游程编码,a.定义 游程编码结构游程指相邻同值网格的数量，游程编码结构是逐行将相邻同值的网格合并，并记录合并后网格的值及合并网格的长度，其目的是压缩栅格数据量，消除数据间的冗余。游程编码结构的建立方法是：将栅格矩阵的数据序列X1,X2,X3.XN，映射为相应的二元序列（Ai，Pi），i1，k，且k=n.其中，A为属性值，P为游程，k为游程序号,二元映射,这种结构特别适合于二值图数据的表示，如图,二元映射,b.游程编码能否压缩数据量，主要决定于栅格数据的性质，通常可通过事先测试，估算图层的数据冗余度Re：,Re 1Q/(MN),Q：图层内相邻属性值变化
15、次数的累加和M：为图层网格的行数N：为图层网格的列数当的值大于1/5的情况下，表明栅格数据的压缩可取得明显的效果,c.当栅格数据位数字高程时,当栅格数据为规则的数字地形高程即DEM时，由于这种类型数据的相邻的数据具有高度的相关性，可通过差分映射进行预处理，然后在采用游程长度压缩编码法。例如,差分,d.基于游程编码结构的栅格数据文件的数据组织方式,为了提高系统对这些数据的访问效率，通常采用索引顺序文件的方法来组织数据。当由位置参数访问其属性特征时，利用逻辑顺序和逻辑地址的关系，很快在索引文件中找到指向数据文件欲访栅格的指针，并求出其逻辑地址，就能找到该栅格的属性。,索引文件,数据文件,5.多重属
16、性下的栅格数据模型,数据文件,像元1,X 坐标,Y 坐标,层1属性,层2属性,层3属性,层n属性,像元2,像元n,以像元为记录的序列。优点：因为n层中每个像元实际是只存储了一层的像元坐标，节约存储空间；每个网格单元的多主题或多层之间比较相对容易实现。不足之处在于不能完全各主题的空间关系，即由于每个网格单元位置单独编码，要比较不同层的网格单元组是很困难的,以层为基础，每一层又以像元顺序记录它的坐标和属性值，一层记录完后再记录第二层。这种方法较为简单，但需要的存贮空间最大。,数据文件,层1,x坐标,Y坐标,属性值,像元2,像元n,像元1,层2,层n,以层为基础，但每一层内则以多边形（也称制图单元）
17、为序记录多边形的属性值和充满多边形的各像元的坐标。,数据文件,层1,属性值,多边形2,多边形n,多边形1,层2,层n,像元1坐标,像元2坐标,像元n坐标,图形文件如：TIFF、GIF、JPEG文件可用各种图像压缩算法作均称压缩，TIFF和GIF文件用无损压缩，使原图被精确重构，而JPEG采用有损压缩，它可达到很大的压缩比，但不能完整重构原图像。,课 内 作 业,一、右图 1.以第3行，第5列为例说明如何将二维删格数据的行列号转换为Morton码 2.就下列删格数据建立十进制线性四叉树表和二维行程编码表 二、举例说明：与块码相比，四叉树在表示栅格结构时有何不足？,三、编写程序，实现以下功能 1）
18、将直接栅格编码文件转换为RLE格式文件 2）将RLE栅格数据文件转换为线性四叉树编码文件（基于十进制的线性四叉树编码）,课 外 作 业,（a）块码分割,（b）四叉树分割,小知识点 栅格数据类型,卫星影像数字高程模型数字正射影像二进制扫描文件数字栅格图形图形文件特定地理信息系统软件的栅格数据,小知识点 栅格数据文件,为导入要用的栅格数据，GIS软件包必须有数据结构和压缩方法的信息。此类信息通常包含在头文件中，头文件的功能类似于元数据。例如：卫星影像的头文件（常以.hdr为扩展名）包含了有关影像数据的信息，如数据结构方法，行列数，光谱波段数，每个波段每一像元的比特数。,三、矢量数据结构,1.概念,
19、矢量结构：即通过记录坐标的方式尽可能精确地表示点、线、多边形等地理实体.,注意：由于坐标空间设为连续，所以允许任意位置、长度和面积的精确定义。但是，其精度仅受数字化设备的精度和数值记录字长的限制，在一般情况下，比栅格结构精度高得多。,矢量数据模型,对于点实体（0维对象），没有长度和宽度 只记录其在特定坐标系下的坐标和属性代码；,线实体（1维对象），只有长度没有宽度：用一系列足够短的直线首尾相接表示一条曲线。矢量结构中只记录这些小线段的端点坐标，将曲线表示为一个坐标序列，坐标之间认为是以直线段相连，在一定精度范围内可以逼真地表示各种形状的线状地物。,“多边形”在地理信息系统中是指一个任意形状、边
20、界完全闭合的空间区域。其边界将整个空间划分为两个部分：包含无穷远点的部分称为外部，另一部分称为多边形内部。多边形的边界线同线实体一样，可以被看作是由一系列多而短的直线段组成。,2.矢量数据结构,矢量数据结构分为以下几种主要类型简单数据结构拓扑数据结构曲面数据结构,1）简单数据结构 a.面条（Spaghetti方式）在简单数据结构中，空间数据按照以基本的空间对象（点、线、多边形）为单位进行单独组织，不含有拓扑关系数据，最典型的是面条（Spaghetti方式）,由多边形边界的x、y坐标对集合及说明信息组成，是最简单的一种多边形矢量编码，如上图记为以下坐标文件：10：x1,y1；x2,y2；x3,y
21、3；x4,y4；x5,y5；x6,y6；x7,y7；x8,y8；x9,y9；x10,y10；x11,y11；x1,y1；20：x1,y1；x12,y12；x13,y13；x14,y14；x15,y15；x16,y16；x17,y17；x18,y18；x19,y19；x20,y20；x21,y21；x22,y22；x23,y23；x8,y8；x9,y9；x10,y10；x11,y11；x1,y1；30：x33,y33；x34,y34；x35,y35；x36,y36；x37,y37；x38,y38；x39,y39；x40,y40；x33,y33；40：x19,y19；x20,y20；x21,y21
22、；x28,y28；x29,y29；x30,y30；x31,y31；x32,y32；x19,y19；50：x21,y21；x22,y22；x23,y23；x8,y8；x7,y7；x6,y6；x24,y24；x25,y25；x26,y26；x27,y27；x28,y28；x21,y21；,坐标序列法文件结构简单，易于实现以多边形为单位的运算和显示。特点：1.数据按点、线或多边形为单元组织，数据编排直观，数字化操作简单 2多边形之间的公共边界被数字化和存储两次，由此产生冗余和碎屑多边形；3每个多边形自成体系而缺少邻域信息，难以进行邻域处理，如消除某两个多边形之间的共同边界；4.岛只作为一个单个的图形
23、建造，没有与外包多边形的联系；5不易检查拓扑错误。这种方法可用于简单的粗精度制图系统中,该法采用树状索引以减少数据冗余并间接增加邻域信息，方法是对所有边界点进行数字化，将坐标对以顺序方式存储，由点索引与边界线号相联系，以线索引与各多边形相联系，形成树状索引结构,b.树状索引编码法,以下分别为右图的多边形文件和线文件树状索引示意图。其文件结构如下：,线与多边形之间的树状索引,点与边界线之间的树状索引,采用上述的树状结构，前图的多边形数据记录如下：1）点文件,2）线文件,3）多边形文件,树状索引编码消除了相邻多边形边界的数据冗余和不一致的问题，在简化过于复杂的边界线或合并相邻多边形时可不必改造索引
24、表，邻域信息和岛状信息可以通过对多边形文件的线索引处理得到 但是比较繁琐，因而给相邻函数运算，消除无用边，处理岛状信息以及检查拓扑关系带来一定的困难，而且两个编码表都需要以人工方式建立，工作量大且容易出错,2）拓扑数据结构,拓扑型数据结构由弧段坐标文件、结点文件和多边形文件等一系列含拓扑关系的数据文件组成。,结点文件由结点记录组成，存贮每个结点的结点号、结点坐标及与该结点连接的弧段等弧段坐标文件存贮组成弧段的点的坐标弧段文件由弧记录组成，存贮弧段的起止结点号和左右多边形号；多边形文件由多边形记录组成，存贮多边形号、组成多边形的弧段号以及多边形的周长、面积、中心点坐标。,DIME(双重独立坐标地
25、图编码，Dual Independent Map Encoding)编码系统 DIME是美国人口调查局在人口调查的基础上发展起来的，它通过有向编码建立了多边形、边界、节点之间的拓扑关系，DIME编码成为其它拓扑编码结构的基础,拓扑整合的地理编码和参考系统（TIGER)多边形转换器（POLYVRT）,拓扑数据结构最重要的技术特征和贡献是具有拓扑编辑功能。这种拓扑编辑功能，不但保证数字化原始数据的自动差错编辑，而且可以自动形成封闭多边形边界，为由各个单独存储的弧段组成所需要的各类多边形及建立空间数据库奠定基础。拓扑编辑功能包括多边形编辑和结点编辑,a.多边形编辑,b.结点编辑,3）曲面数据结构,曲
26、面是指连续分布现象的覆盖表面，具有这种覆盖表面的要素有地形、降水量、温度、磁场等。表示和存储这些要素的基本要求是必须便于连续现象在任一点的内插计算，因此经常采用不规则三角网来拟合连续分布现象的覆盖表面，称为TIN（Triangulated Irregular Network）数据结构,这种基于TIN的曲面数据结构，通常用于数字地形的表示，或者按照曲面要素的实测点分布，将它们连成三角网，三角网中每个三角形要求尽量接近等边形状，并保证由最邻近的点构成的三角形，即三角形的边长之和最小。在所有可能的三角网中，狄洛尼（Delaunay）三角网在地形拟合方面表现最为出色。,狄洛尼（Delaunay）三角网
27、：为相互邻接且互相不重叠的三角形的集合，每一个三角形的外接圆内不不含其他的点。狄洛尼三角形外接圆不包含其他点的特性被用作从一系列不重合的平面点建立狄洛尼三角网的基本法则，可以称为狄洛尼法则,A,B,C,D,四、矢栅结合的数据结构,1.矢栅混合模式有多种形式，最简单也最实用的是不对矢量结构数据和栅格结构数据做任何特殊处理，直接将他们分别存储在同一个GIS的空间数据库系统中，并通过共同的ID号将各空间对象的矢量数据，栅格数据及属性数据关联在一起。,缺点：矢量和栅格两套数据均要无遗漏的在系统中存储，会给系统的存储空间带来压力,2.矢栅一体化模式 为了解决失栅混合增加存储空间这一问题，并更加有效的将矢
28、量、栅格数据结构结合起来，gongjianya提出了失栅一体化模式，其理论基础是多级格网方法，三个基本约定和线形四叉树编码。,多级格网:包括粗格网，基本格网和细分格网三个层次粗格网建立空间索引。基本格网的大小与常规栅格划分要求一致；细分格网是在点、线经过的基本栅格上在进一步划分为16*16或256*256的小格网，以增加栅格的空间分辨率，从而提高点线表达精度,256,256,粗格网、基本格网和细分格网均采用线性四叉树编码，并采用三个Morton码（M0,M1,M2）表示。其中：M0表示点所在或线所通过的粗格网的Morton码，是研究区的整体编码。M1表示点所在或线通过的基本栅格的morton码
29、，也是研究区内的整体编码。M2表示点所在或线所通过的细分栅格的morton码，是基本栅格内的局部编码,以上编码是基于栅格的，因而据此设计的数据结构必定具有栅格的性质，为了使之具有矢量的特点，gongjianya提出了点状地物，线状地物的三个约定约定一：点状地物仅有空间位置，而无形状和面积，在计算机中仅有一个位置数据约定二：线状地物有形状，但无面积，在计算机中需要组织一组元子（即栅格单元）填满的路径表达；约定三：面状地物有形状和面积，在计算机内有一组元子表达的填满路径的边界线和内部（空洞出外均填满）的区域组成,举例：,据此，点状地物、线状地物和面状地物的“矢量化”数据记录方式如下：,点状地物：用（M1,M2）代替（x，y）,线状地物：用（M1,M2）代替（x，y）记录中间点,面状地物：除了要用Morton码即（M1,M2）代替（x，y）记录面状地物边界原始采样点的“拐点”（即中间点）位置，以及它们所穿过的所有基本格网的交线位置之外，还要用链指针记录多边形的内部栅格。,点状目标及其数据结构,结点及其数据结构,弧段及其数据结构,面状地物及其数据结构,
