第八章2 空间数据结构

《第八章2 空间数据结构》由会员分享，可在线阅读，更多相关《第八章2 空间数据结构（97页珍藏版）》请在金锄头文库上搜索。

1、空间数据结构,数据结构即指数据组织的形式，是适合于计算机存储、管理和处理的数据逻辑结构。 对于空间数据而言，则是地理实体的空间排列方式和相互关系的抽象描述。 数据结构是对数据的一种理解和解释，不说明数据结构的数据是毫无用处的，不仅用户无法理解，计算机程序也不能正确的处理，对同样一组数据，按不同的数据结构去处理，得到的可能是截然不同的内容。,空间数据结构是地理信息系统沟通信息的桥梁，只有充分理解地理信息系统所采用的特定数据结构，才能正确有效地使用系统。 地理信息系统的空间数据结构主要有栅格结构（显式表示）和矢量结构(隐式表示 ) 。,第一节 栅格数据结构 第二节 矢量数据结构 第三节 两种数据结

2、构的比较和转换,第一节 栅格数据结构,一、简单栅格数据结构 二、栅格数据压缩存储的编码方法,一、简单栅格数据结构,1、定义 2、栅格结构中，点线面的表示 3、栅格数据的特点 4、栅格结构数据获取途径 5、保持原图或原始数据精度的方法,1、定义：,栅格结构是最简单最直观的空间数据结构，又称为网格结构(raster或grid cell)或像元结构(pixel)，是指将地球表面划分为大小均匀紧密相邻的网格阵列，每个网格作为一个像元或像素，由行、列号定义，并包含一个代码，表示该像素的属性类型或量值，或仅仅包含指向其属性记录的指针。 因此，栅格结构是以规则的阵列来表示空间地物或现象分布的数据组织，组织中

3、的每个数据表示地物或现象的非几何属性特征。,栅格结构表示的地表是不连续的，是量化和近似离散的数据。在栅格结构中，地表被分成相互邻接、规则排列的矩形方块(特殊的情况下也可以是三角形或菱形、六边形等），每个地块与一个栅格单元相对应。 栅格数据的比例尺就是栅格大小与地表相应单元大小之比。在许多栅格数据处理时，常假设栅格所表示的量化表面是连续的，以便使用某些连续函数。,2、栅格结构中，点线面的表示,点用一个栅格单元表示； 线状地物则用沿线走向的一组相邻栅格单元表示，每个栅格单元最多只有两个相邻单元在线上； 面或区域用记有区域属性的相邻栅格单元的集合表示，每个栅格单元可有多于两个的相邻单元同属一个区域。

4、任何以面状分布的对象(土地利用、土壤类型、地势起伏、环境污染等)，都可以用栅格数据逼近。,3、栅格数据的特点,（1）用离散的量化栅格值表示空间实体； （2）描述区域属性明显，位置隐含； （3）数据结构简单，易于与遥感数据结合； （4）难于建立地物间拓扑关系 （5）图形质量低且数据量大。,4、栅格结构数据获取途径,栅格结构数据主要可由四个途径得到，即 1、目读法：在专题图上均匀划分网格，逐个网格地决定其代码，最后形成栅格数字地图文件； 2、数字化仪手扶或自动跟踪数字化地图，得到矢量结构数据后，再转换为栅格结构； 3、扫描数字化：逐点扫描专题地图，将扫描数据重采样和再编码得到栅格数据文件； 4、分

5、类影像输入：将经过分类解译的遥感影像数据直接或重采样后输入系统，作为栅格数据结构的专题地图。,5、保持原图或原始数据精度的方法,在转换和重新采样时，需尽可能保持原图或原始数据精度，通常有两种办法： 第一，在决定栅格代码时尽量保持地表的真实性，保证最大的信息容量。 中心点法 重要性法 面积占优法 百分比法 第二，缩小单个栅格单元的面积，即增加栅格单元的总数。,目前有一系列栅格数据压缩编码方法，如键码、游程长度编码、块码和四叉树编码等。其目的，就是用尽可能少的数据量记录尽可能多的信息。 类型：信息无损编码、信息有损编码 信息无损编码是指编码过程中没有任何信息损失，通过解码操作可以完全恢复原来的信息

6、。 在地理信息系统中多采用信息无损编码，而对原始遥感影像进行压缩编码时，有时也采取有损压缩编码方法。,二、栅格数据压缩存储的编码方法,1、链式编码 2、游程长度编码 3、块状编码 4、四叉树编码,链式编码又称为弗里曼链码(Freeman，1961)或边界链码。链式编码主要是记录线状地物和面状地物的边界。它把线状地物和面状地物的边界表示为：由某一起始点开始并按某些基本方向确定的单位矢量链。 基本方向可定义为：东0，东南l，南2，西南3，西4，西北5，北6，东北7等八个基本方向。,1、链式编码（Chain Codes）,链式编码的方向代码,链式编码的编码方法,链式编码的前两个数字表示起点的行、列数

7、，从第三个数字开始的每个数字表示单位矢量的方向，八个方向以07的整数代表。 如果对于右图所示的线状地物确定其起始点为像元(1，5)。 则其链式编码为：1，5，3，2，2，3，3，2，3 对于右图所示的面状地物，假设其原起始点定为像元（5，8）。 则该多边形边界按顺时针方向的链式编码为：5，8，3，2，4，4，6，6，7，6，0，2，1,链式编码的优缺点,优点：链式编码对线状和多边形的表示具有很强的数据压缩能力，且具有一定的运算功能，如面积和周长计算等，探测边界急弯和凹进部分等都比较容易，类似矢量数据结构，比较适于存储图形数据。,缺点：对叠置运算如组合、相交等则很难实施，对局部修改将改变整体结构

8、，效率较低，而且由于链码以每个区域为单位存储边界，相邻区域的边界则被重复存储而产生冗余。,2、游程长度编码(RunLength Codes),其编码方案是，只在各行(或列)数据的代码发生变化时依次记录该代码以及相同代码重复的个数，从而实现数据的压缩。,游程长度编码是栅格数据压缩的重要编码方法，它的基本思路是：对于一幅栅格图像，常常有行(或列)方向上相邻的若干点具有相同的属性代码，因而可采取某种方法压缩那些重复的记录内容。,游程长度编码在栅格数据压缩时，数据量没有明显增加，压缩效率较高，且易于检索、叠加合并等操作，运算简单，适用于机器存储容量小、数据需大量压缩，而又要避免复杂的编码解码运算增加处

9、理和操作时间的情况。,3、块式编码(Block Codes),块码是游程长度编码扩展到二维的情况，采用方形区域作为记录单元，每个记录单元包括相邻的若干栅格，数据结构由初始位置(行、列号)和半径，再加上记录单元的代码组成。,数据编码组成：（初始行、列，半径，属性值）,（1，1，1，0），（1，2，2，2），（1，4，1，5），（1，5，1，5），（1，6，2，5），（1，8，1，5）；（2，1，1，2），（2，4，1，2），（2，5，1，2），（2，8，1，5）；（3，3，1，2），（3，4，1，2），（3，5，2，3），（3，7，2，5）；（4，1，2，0），（4，3，1，2），（4，4，1，

10、3）；（5，3，1，3），（5，4，2，3），（5，6，1，3），（5，7，1，5），（5，8，1，3）；（6，1，3，0），（6，6，3，3）；（7，4，1，0），（7，5，1，3）；（8，4，1，0），（8，5，1，0）。,4、四叉树编码(Quad-tree Codes),1）定义： 四叉树结构的基本思想是将一幅栅格地图或图像等分为四部分。逐块检查其格网属性值(或灰度)。如果某个子区的所有格网值都具有相同的值，则这个子区就不再继续分割，否则还要把这个子区再分割成四个子区。这样依次地分割，直到每个子块都只含有相同的属性值或灰度为止。,四叉树编码又称为四分树、四元树编码。它是一种更有效地压编数

11、据的方法。它将2n2n像元阵列连续进行4等分，一直分到正方形的大小正好与象元的大小相等为止而块状结构则用四叉树描述，习惯上称为四叉树编码。,四叉树的树状表示,四叉树编码示意图,2）四叉树结构的建立方法,建立四叉树有两种方法，即自上而下方式（topdown）自下而上方式（bottomup） 自上而下方式的分割需要大量的运算，因为大量数据需要重复检查才能确定划分。当nn的矩阵比较大，且区域内容要素又比较复杂时，建立这种四叉树的速度比较慢。 自下而上方式是对栅格数据按如下的顺序进行检测：如果每相邻四个网格值相同则进行合并，逐次往上递归合并，直到符合四叉树的原则为止。这种方法重复计算较少，运算速度较快

12、。,3）四叉树编码法的优缺点,四叉树编码法的优点： （1）容易而有效地计算多边形的数量特征； （2）阵列各部分的分辨率是可变的，边界复杂部分四叉树较高即分级多，分辨率也高，而不需表示许多细节的部分则分级少，分辨率低，因而既可精确表示图形结构又可减少存贮量； （3）栅格到四叉树及四叉树到简单栅格结构的转换比其它压缩方法容易； （4）多边形中嵌套异类小多边形的表示较方便。 四叉树编码的最大缺点是转换的不定性。,第二节 矢量数据结构,矢量数据结构是通过记录坐标的方式，尽可能地将点、线、面地理实体表现得精确无误。其坐标空间假定为连续空间，不必像栅格数据结构那样进行量化处理。因此矢量数据能更精确地定义位

13、置、长度和大小。 除数学上的精确坐标假设外，矢量数据存储是以隐式关系以最小的存储空间存储复杂的数据。,一、矢量数据结构编码的基本内容,矢量数据结构通过记录空间对象的坐标及空间关系来表达空间对象的位置。 点：空间的一个坐标点； 线：多个点组成的弧段； 面：多个弧段组成的封闭多边形。,多边形矢量编码，不但要表示位置和属性，更重要的是能表达区域的拓扑特征，如形状、邻域和层次结构等，以便使这些基本的空间单元可以作为专题图的资料进行显示和操作。,矢量数据结构编码的基本内容,标识码,属性码,空间对象编码 唯一 连接空间和属性数据,数据库,独立编码,点: ( x ,y ) 线: ( x1 , y1 ) ,

14、(x2 , y2 ) , , ( xn , yn ) 面: ( x1 , y1 ) , (x2 , y2 ) , , ( x1 , y1 ),点位字典,点: 点号文件,线: 点号串,面: 点号串,存储方法,二、矢量数据结构的类型,1、简单的矢量数据结构面条结构（实体式） 只记录空间对象的位置坐标和属性信息，不记录拓扑关系。,存储： 独立存储：空间对象位置直接跟随空间对象； 点位字典：点坐标独立存储，线、面由点号组成。 适用范围： 制图及一般查询，不适合复杂的空间分析 特征： 无拓扑关系，主要用于显示、输出及一般查询； 公共边重复存储，存在数据冗余，难以保证数据独立性和一致性； 多边形分解和合并

15、不易进行，邻域处理较复杂； 处理嵌套多边形比较麻烦。,2、索引式,索引式数据结构采用树状索引以减少数据冗余并间接增加邻域信息，具体方法是对所有边界点进行数字化，将坐标对以顺序方式存储，由点索引与边界线号相联系，以线索引与各多边形相联系，形成树状索引结构。,树状索引法,多边形文件 多边形号 边界线号 1 ， 2 ， 3 ,树状索引法,树状索引结构消除了相邻多边形边界的数据冗余和不一致的问题，在简化过于复杂的边界线或合并多边形时可不必改造索引表，邻域信息和岛状信息可以通过对多边形文件的线索引处理得到，但是比较繁琐，因而给邻域函数运算、消除无用边、处理岛状信息以及检查拓扑关系等带来一定的困难，而且两

16、个编码表都要以人工方式建立，工作量大且容易出错。,3、双重独立式（DIME）,这种数据结构最早是由美国人口统计局研制来进行人口普查分析和制图的，简称为DIME(Dual lndependent Map Encoding)系统或双重独立式的地图编码法。它以城市街道为编码的主体。其特点是采用了拓扑编码结构。,双重独立式数据结构是对图上网状或面状要素的任何一条线段，用其两端的节点及相邻面域来予以定义。 在双重独立式数据结构中，节点与节点或者面域与面域之间为邻接关系，节点与线段或者面域与线段之间为关联关系。,点文件：,线文件:线文件是以线段为记录单位,面文件：,关联,邻接,关联,连通,拓扑关系明确,4、链状双重独立式,链状双重独立式数据结构是DIME数据结构的一种改进。在DIME中，一条边只能用直线两端点的序号及相邻的面域来表示，而在链状数据结构中，将若干直线段合为一个弧段（或链段），每个弧段可以有许多中间点。 在链状双重独立数据