第三章-测绘师空间数据结构

空间数据结构

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

)

。

数据结构第三章空间数据结构第一节栅格数据结构第二节矢量数据结构第三节两种数据结构的比较和转换第一节栅格数据结构一、简单栅格数据结构二、栅格数据压缩存储的编码方法

一、简单栅格数据结构1、定义2、栅格结构中，点线面的表示3、栅格数据的特点4、栅格结构数据获取途径5、保持原图或原始数据精度的方法

1、定义：栅格结构是最简单最直观的空间数据结构，又称为网格结构(raster或gridcell)或像元结构(pixel)，是指将地球表面划分为大小均匀紧密相邻的网格阵列，每个网格作为一个像元或像素，由行、列号定义，并包含一个代码，表示该像素的属性类型或量值，或仅仅包含指向其属性记录的指针。因此，栅格结构是以规则的阵列来表示空间地物或现象分布的数据组织，组织中的每个数据表示地物或现象的非几何属性特征。栅格结构表示及比例；ichi

栅格结构表示的地表是不连续的，是量化和近似离散的数据。在栅格结构中，地表被分成相互邻接、规则排列的矩形方块(特殊的情况下也可以是三角形或菱形、六边形等），每个地块与一个栅格单元相对应。栅格数据的比例尺就是栅格大小与地表相应单元大小之比。在许多栅格数据处理时，常假设栅格所表示的量化表面是连续的，以便使用某些连续函数。

2、栅格结构中，点线面的表示

点用一个栅格单元表示；

线状地物则用沿线走向的一组相邻栅格单元表示，每个栅格单元最多只有两个相邻单元在线上；

面或区域用记有区域属性的相邻栅格单元的集合表示，每个栅格单元可有多于两个的相邻单元同属一个区域。任何以面状分布的对象(土地利用、土壤类型、地势起伏、环境污染等)，都可以用栅格数据逼近。

3、栅格数据的特点（1）用离散的量化栅格值表示空间实体；（2）描述区域属性明显，位置隐含；（3）数据结构简单，易于与遥感数据结合；（4）难于建立地物间拓扑关系（5）图形质量低且数据量大。

4、栅格结构数据获取途径栅格结构数据主要可由四个途径得到，即1、目读法：在专题图上均匀划分网格，逐个网格地决定其代码，最后形成栅格数字地图文件；2、数字化仪手扶或自动跟踪数字化地图，得到矢量结构数据后，再转换为栅格结构；3、扫描数字化：逐点扫描专题地图，将扫描数据重采样和再编码得到栅格数据文件；4、分类影像输入：将经过分类解译的遥感影像数据直接或重采样后输入系统，作为栅格数据结构的专题地图。

5、保持原图或原始数据精度的方法

在转换和重新采样时，需尽可能保持原图或原始数据精度，通常有两种办法：

第一，在决定栅格代码时尽量保持地表的真实性，保证最大的信息容量。

中心点法重要性法

面积占优法百分比法

逼近原始精度的第二种方法是缩小单个栅格单元的面积，即增加栅格单元的总数。

压缩方法概述目前有一系列栅格数据压缩编码方法，如键码、游程长度编码、块码和四叉树编码等。其目的，就是用尽可能少的数据量记录尽可能多的信息。类型：信息无损编码、信息有损编码信息无损编码是指编码过程中没有任何信息损失，通过解码操作可以完全恢复原来的信息。压缩方法概述信息有损编码是指为了提高编码效率，最大限度地压缩数据，在压缩过程中损失一部分相对不太重要的信息，解码时这部分难以恢复。在地理信息系统中多采用信息无损编码，而对原始遥感影像进行压缩编码时，有时也采取有损压缩编码方法。二、栅格数据压缩存储的编码方法1、链式编码2、游程长度编码3、块状编码4、四叉树编码

链式编码又称为弗里曼链码(Freeman，1961)或边界链码。链式编码主要是记录线状地物和面状地物的边界。它把线状地物和面状地物的边界表示为：由某一起始点开始并按某些基本方向确定的单位矢量链。基本方向可定义为：东＝0，东南＝l，南＝2，西南＝3，西＝4，西北＝5，北＝6，东北＝7等八个基本方向。1、链式编码（ChainCodes）链式编码的方向代码链式编码的编码方法链式编码的前两个数字表示起点的行、列数，从第三个数字开始的每个数字表示单位矢量的方向，八个方向以0—7的整数代表。如果对于右图所示的线状地物确定其起始点为像元(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链式编码的优缺点优点：链式编码对线状和多边形的表示具有很强的数据压缩能力，且具有一定的运算功能，如面积和周长计算等，探测边界急弯和凹进部分等都比较容易，类似矢量数据结构，比较适于存储图形数据。缺点：是对叠置运算如组合、相交等则很难实施，对局部修改将改变整体结构，效率较低，而且由于链码以每个区域为单位存储边界，相邻区域的边界则被重复存储而产生冗余。

2、游程长度编码(Run—LengthCodes)其编码方案是，只在各行(或列)数据的代码发生变化时依次记录该代码以及相同代码重复的个数，从而实现数据的压缩。（举两个例子）游程长度编码是栅格数据压缩的重要编码方法，它的基本思路是：对于一幅栅格图像，常常有行(或列)方向上相邻的若干点具有相同的属性代码，因而可采取某种方法压缩那些重复的记录内容。游程长度编码游程长度编码在栅格数据压缩时，数据量没有明显增加，压缩效率较高，且易于检索、叠加合并等操作，运算简单，适用于机器存储容量小、数据需大量压缩，而又要避免复杂的编码解码运算增加处理和操作时间的情况。

3、块式编码(BlockCodes)

块码是游程长度编码扩展到二维的情况，采用方形区域作为记录单元，每个记录单元包括相邻的若干栅格，数据结构由初始位置(行、列号)和半径，再加上记录单元的代码组成。根据块状编码的原则，对如图所示的图像进行块式编码。

4、四叉树编码(Quad-treeCodes)

1）定义：四叉树结构的基本思想是将一幅栅格地图或图像等分为四部分。逐块检查其格网属性值(或灰度)。如果某个子区的所有格网值都具有相同的值，则这个子区就不再继续分割，否则还要把这个子区再分割成四个子区。这样依次地分割，直到每个子块都只含有相同的属性值或灰度为止。

四叉树分割与块式分割的区别四叉树编码2

四叉树编码又称为四分树、四元树编码。它是一种更有效地压编数据的方法。它将2n×2n像元阵列连续进行4等分，一直分到正方形的大小正好与象元的大小相等为止（如图），而块状结构则用四叉树描述，习惯上称为四叉树编码。右图表示对左图的分割过程及其关系。这四个等分区称为四个子象限，按左上(NW)、右上(NE)、左下(SW)，右下(SE)。用—个树结构表示如下图所示2）四叉树结构的建立方法

建立四叉树有两种方法，即自上而下方式（top—down）自下而上方式（bottom—up）自上而下方式的分割需要大量的运算，因为大量数据需要重复检查才能确定划分。当n×n的矩阵比较大，且区域内容要素又比较复杂时，建立这种四叉树的速度比较慢。 自下而上方式是对栅格数据按如下的顺序进行检测：如果每相邻四个网格值相同则进行合并，逐次往上递归合并，直到符合四叉树的原则为止。这种方法重复计算较少，运算速度较快。3）四叉树编码法的优缺点四叉树编码法的优点：（1）容易而有效地计算多边形的数量特征；（2）阵列各部分的分辨率是可变的，边界复杂部分四叉树较高即分级多，分辨率也高，而不需表示许多细节的部分则分级少，分辨率低，因而既可精确表示图形结构又可减少存贮量；（3）栅格到四叉树及四叉树到简单栅格结构的转换比其它压缩方法容易；（4）多边形中嵌套异类小多边形的表示较方便。四叉树编码的最大缺点是转换的不定性。

第二节矢量数据结构

矢量数据结构是通过记录坐标的方式，尽可能地将点、线、面地理实体表现得精确无误。其坐标空间假定为连续空间，不必象栅格数据结构那样进行量化处理。因此矢量数据能更精确地定义位置、长度和大小。

除数学上的精确坐标假设外，矢量数据存储是以隐式关系以最小的存储空间存储复杂的数据。一、矢量数据结构编码的基本内容

矢量数据结构通过记录空间对象的坐标及空间关系来表达空间对象的位置。点：空间的一个坐标点；线：多个点组成的弧段；面：多个弧段组成的封闭多边形。

一、矢量数据结构编码的基本内容-2

多边形矢量编码，不但要表示位置和属性，更重要的是能表达区域的拓扑特征，如形状、邻域和层次结构等，以便使这些基本的空间单元可以作为专题图的资料进行显示和操作。

矢量数据结构编码的基本内容

标识码属性码空间对象编码唯一连接空间和属性数据数据库独立编码点:(x,y)线:(x1,y1),(x2,y2),…,(xn,yn)面:(x1,y1

),(x2,y2

),…,(x1,y1

)点位字典点:点号文件线:点号串面:点号串点号XY1112223344………n5566存储方法

二、矢量数据结构的类型

1、简单的矢量数据结构—面条结构（实体式）只记录空间对象的位置坐标和属性信息，不记录拓扑关系。存储：独立存储：空间对象位置直接跟随空间对象；点位字典：点坐标独立存储，线、面由点号组成。适用范围：制图及一般查询，不适合复杂的空间分析

二、矢量数据结构的类型

简单的矢量数据结构—面条结构（实体式）特征无拓扑关系，主要用于显示、输出及一般查询；公共边重复存储，存在数据冗余，难以保证数据独立性和一致性；多边形分解和合并不易进行，邻域处理较复杂；处理嵌套多边形比较麻烦。2、索引式索引式数据结构采用树状索引以减少数据冗余并间接增加邻域信息，具体方法是对所有边界点进行数字化，将坐标对以顺序方式存储，由点索引与边界线号相联系，以线索引与各多边形相联系，形成树状索引结构。2、索引式2树状索引结构消除了相邻多边形边界的数据冗余和不一致的问题，在简化过于复杂的边界线或合并多边形时可不必改造索引表，邻域信息和岛状信息可以通过对多边形文件的线索引处理得到，但是比较繁琐，因而给邻域函数运算、消除无用边、处理岛状信息以及检查拓扑关系等带来一定的困难，而且两个编码表都要以人工方式建立，工作量大且容易出错。3、双重独立式（DIME）这种数据结构最早是由美国人口统计局研制来进行人口普查分析和制图的，简称为DIME(DuallndependentMapEncoding)系统或双重独立式的地图编码法。它以城市街道为编码的主体。其特点是采用了拓扑编码结构。

3、双重独立式（DIME）2

双重独立式数据结构是对图上网状或面状要素的任何一条线段，用其两端的节点及相邻面域来予以定义。在双重独立式数据结构中，节点与节点或者面域与面域之间为邻接关系，节点与线段或者面域与线段之间为关联关系。4、链状双重独立式

链状双重独立式数据结构是DIME数据结构的一种改进。在DIME中，一条边只能用直线两端点的序号及相邻的面域来表示，而在链状数据结构中，将若干直线段合为一个弧段（或链段），每个弧段可以有许多中间点。在链状双重独立数据结构中，主要有四个文件：多边形文件、弧段文件、弧段坐标文件、结点文件。

三、矢量数据结构的属性数据表达属性特征类型类别特征：是什么说明信息：同类目标的不同特征属性特征表达类别特征：类型编码说明信息：属性数据结构和表格属性表的内容取决于用户图形数据和属性数据的连接通过目标识别符或内部记录号实现。四、矢量数据结构的特点1、用离散的点描述空间对象与特征，定位明显，属性隐含；2、用拓扑关系描述空间对象之间的关系；3、面向目标操作，精度高，数据冗余度小；4、输出图形质量好，精度高；5、与遥感等图象数据难以结合。作业1试对右图进行直接栅格编码、链式数据编码、块式编码、游程压缩编码以及四叉树编码，比较各种压缩编码的压缩程度。333331111111333331111111333311114411333111144441332221114441322221111411222222111111222222111111222222211111222222211111作业2：对P51的图2－14中的多边形P2进行多边形连接编辑；对N5进行结点连接编辑。Back第三节两种数据结构的比较与转换栅格结构与矢量结构似乎是两种截然不同的空间数据结构，栅格结构“属性明显、位置隐含”，而矢量结构“位置明显、属性隐含”，栅格数据操作总的来说比较容易实现，尤其是作为斑块图件的表示更易于为人们接受；而矢量数据操作则比较复杂，许多分析操作（如两张地图的覆盖操作，点或线状地物的邻域搜索等）用矢量结构实现十分困难，矢量结构表达线状地物是比较直观的，而面状地物则是通过对边界的描述而表达。两种数据结构的比较与转换2无论哪种结构，数据精度和数据量都是一对矛盾，要提高精度，栅格结构需要更多的栅格单元，而矢量结构则需记录更多的线段结点。一般来说，栅格结构只是矢量结构在某种程度上的一种近似，如果要使栅格结构描述的图件取得与矢量结构同样的精度，甚至仅仅在量值上接近，则数据也要比后者大得多。

栅格、矢量数据结构特点比较

比较内容矢量格式栅格格式数据量小大图形精度高低图形运算复杂、高效简单、低效遥感影像格式不一致一致或接近输出表示抽象、昂贵直观、便宜数据共享不易实现容易实现拓扑和网络分析容易实现不易实现两种数据结构的比较

栅格结构在某些操作上比矢量结构更有效更易于实现，如按空间坐标位置的搜索，对于栅格结构是极为方便的，而对矢量结构则搜索时间要长得多；在给定区域内的统计指标运算，包括计算多边形形状、面积、线密度、点密度，栅格结构可以很快算得出结果，而采用矢量结构则由于所在区域边界限制条件难以提取而降低效率，对于给定范围的开窗、缩放栅格结构也比矢量结构优越；两种数据结构的比较另一方面，矢量结构用于拓扑关系的搜索则更为高效，即诸如计算多边形形状搜索邻域、层次信息等；对于网络信息只有矢量结构才能完全描述；矢量结构在计算精度与数据量方面的优势也是矢量结构比栅格结构受到欢迎的原因之一。具体特点－栅格结构－－矢量结构栅格与矢量数据结构比较栅格结构特点

许多实践证明，栅格结构和矢量结构在表示空间数据上可以是同样有效的，对于一个GIS软件，较为理想的方案是采用两种数据结构，即栅格结构与矢量结构并存，对于提高地理信息系统的空间分辨率、数据压缩率和增强系统分析、输入输出的灵活性十分重要。1、矢量数据结构的优缺点优点：表示地理数据的精度较高数据结构紧凑，冗余度低，数据量小拓扑结构有利于网络分析、空间查询等便于面向实体的数据表达图形输出精确美观缺点：数据结构复杂多边形叠合等分析相对困难数学模拟比较困难软件实现的技术要求比较高Back2、栅格数据结构的优缺点优点：数据结构简单空间数据的叠置和组合方便各类空间分析很易于进行有利于遥感数据的匹配应用和分析缺点：图形数据量大，冗余度高，需要压缩处理拓扑关系难以表达定位精度比矢量低难以建立网络连接关系地图输出不美观Back3、两种数据结构的特点比较栅格数据结构优点：数据结构简单空间数据的叠置和组合方便各类空间分析很易于进行有利于遥感数据的匹配应用和分析矢量数据结构优点：表示地理数据的精度较高数据结构紧凑，冗余度低，数据量小拓扑结构有利于网络分析、空间查询等便于面向实体的数据表达图形输出精确美观3、两种数据结构的特点比较栅格数据结构缺点：图形数据量大，冗余度高，需要压缩处理拓扑关系难以表达定位精度比矢量低难以建立网络连接关系地图输出不美观矢量数据结构缺点：数据结构复杂多边形叠合等分析相对困难数学模拟比较困难软件实现的技术要求比较高Back二、数据结构选择原则要素还是位置可获取的数据定位要素的必要精度需要什么类型的要素需要什么类型的拓扑关联所需空间分析类型生产地图类型三、空间数据结构的转换矢量结构与网格结构的相互转换，是地理信息系统的基本功能之一，目前已经发展了许多高效的转换算法；但是，从栅格数据到矢量数据的转换，特别是扫描图像的自动识别，仍然是目前研究的重点。对于点状实体，每个实体仅由一个坐标对表示，其矢量结构和栅格结构的相互转换基本上只是坐标精度变换问题，不存在太大的技术问题。三、空间数据结构的转换线实体的矢量结构由一系列坐标对表示，在变为栅格结构时，除把序列中坐标对变为栅格行列坐标外，还需根据栅格精度要求，在坐标点之间插满一系列栅格点，这也容易由两点式直线方程得到。线实体由栅格结构变为矢量结构与将多边形边界表示为矢量结构相似，因此以下重点讨论多边形（面实体）的矢量结构与栅格结构相互转换。1、矢量格式向栅格格式的转换矢量格式向栅格格式转换又称为多边形填充，就是在矢量表示的多边形边界内部的所有栅格点上赋以相应的多边形编码，从而形成栅格数据阵列。几种主要的算法描述如下：1）内部点扩散算法2）复数积分算法3）射线算法和扫描算法

2、栅格格式向矢量格式的转换

多边形栅格格式向矢量格式转换就是提取以相同的编号的栅格集合表示的多边形区域的边界和边界的拓扑关系，并表示由多个小直线段组成的矢量格式边界线的过程。栅格格式向矢量格式转换通常包括