空间数据结构

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

1、第五章 空间数据结构数据结构即指数据组织的形式，是适合于计算机存储、管理和处理的数据逻 辑结构。地理信息系统空间数据结构是指空间数据在系统内的组织和编码形式 （GIS 数据结构也可称为图形数据格式），它是指适合于计算机系统存储、管理 和处理地理图形的逻辑结构。GIS中，空间数据一般有着较为复杂的数据结构， 目前，主要有两种数据模型表示空间数据，即矢量数据模型和栅格数据模型。4.1 栅格数据结构4.1.1 概述栅格数据是计算机和其它信息输入输出设备广泛使用的一种数据模型，如电 视机、显示器、打印机等的空间寻址。甚至专门用于矢量图形的输入输出设备， 如数字化仪、矢量绘图仪及扫描仪等，其内部结构实质

2、上是栅格的。遥感数据也 是采用特殊扫描平台获得的栅格数据。栅格数据就是用数字表示的像元阵列，其中，栅格的行和列规定了实体所在 的坐标空间，而数字矩阵本身则描述了实体的属性或属性编码。栅格数据最显著 的特点就是存在着最小的、不能再分的栅格单元，在形式上常表现为整齐的数字 矩阵，因而便于计算机进行处理，特别是存储和显示。4.1.2 编码方案以图 4-1 为例，介绍几种编码方法的编码思路、方案和特点。AAAARAAAAAARAAAAAAARAGGAAAARAGGAAARAGGGGARAAGGGAARAAGGGARAAAAAAA图 4-1 栅格数据结构1. 游程长度编码地理数据往往有较强的相关性，也就

3、是说相邻象元的值往往是相同的。游程 长度编码的基本思想是：按行扫描，将相邻等值的象元合并，并记录代码的重复 个数。游程长度编码的数据结构: 行号,属性,重复次数。图 4-1 的游程长度编码 为：1, A,4,R,1,A,6 对于游程长度编码，区域越大，数据的相关性越强，则压缩越大。其特点是， 压缩效率较高，叠加、合并等运算简单，编码和解码运算快。2. 块式编码块式编码是将游程扩大到二维情况，把多边形范围划分成若干具有同一属性 的正方形，然后对各个正方形进行编码。块式编码的基本思想：由初始位置(行 列号)、半径和属性代码组成。图4-1 的块状编码为：(1,1,3,A),(1,5,1,R),(1,

4、6,2,A), 块状编码对大而简单的多边形更为有效，对一些虽不较多的复杂多边形效果 并不好。块状编码在合并、插入、检查延伸型、计算面积等操作时有明显的优越 性，而对某些运算不适应，必须在转换成简单的数据形式才能顺利进行运算。3. 四叉树编码四叉树编码是最有效的栅格数据压缩编码方法之一，是一种可变分率的非均 匀网格系统，在GIS中有广泛的应用。其基本思路为：2nX2n象元组成的图像(不 足的用背景补上）按四个象限进行递归分割，直到子象限的数据单调为止,最后得 到一棵四分叉的倒向树（图 4-1）。四叉树有两种,一种是常规四叉树,在子节点 与父节点之间设立指针,由于指针占用空间较大,难以达到数据压缩

5、的目的。所 以，常规四叉树并不广泛用于存储数据，其价值在于建立索引文件，进行数据检 索。另一种是线性四叉树,它不需要记录中间节点和使用指针,仅记录叶节点,并 用地址码表示叶节点的位置。因而,线性四叉树广泛应用于数据压缩和 GIS 中的 数据结构。下面介绍最常用的线性四叉树编码。b)图 4-1 四分叉的倒向树线性四叉树编码的基本思想是：不需记录中间结点和使用指针，仅记录叶结 点，并用地址码（定位码、Mor ton码）表示叶结点的位置一一深度（几次分割） 和属性。为了得到线性四叉树的地址码，首先将二维栅格数据的行列号转化为二 进制数，然后交叉放入Mor ton码中，即为线性四叉树的地址码。实质上是

6、按左 上、右上、左下、右下的顺序，从零开始对每个栅格进行自然编码。这样，在一 个2nX2n的图像中，每个像元点都给出一个Mor ton码，当n = 3时即为（表3一1）：表 3 一1 Morton 码列、01234567001451617202112367181922232891213242528293101114152627303143233363748495253534353839505154556404144455657606174243464758596263这样就可将用行列表示的二维图像，用Mor ton码写成一维数据，通过Mor ton 码就可知道象元的位置。把一幅2nX2n的图像

7、压缩成线性四叉树的过程为：1、按Mor ton码把图象读入一维数组。第一维为Mor ton码，第二维为象元 值。2、相邻的四个象元比较，一致的合并，只记录第一个象元的Mor ton码。循 环比较所形成的大块，相同的再合并，直到不能合并为止。3、进一步用游程长度编码压缩。压缩时只记录第一个象元的Mor ton码。 解码时，根据Mor ton码就可知道象元在图像中的位置（左上角），本Mor ton码和下一个Mor ton码之差即为象元个数。知道了象元的个数和象元的位置就可 恢复出图像了。4.1.3 栅格数据结构的特点（1）离散的量化栅格值表示空间对象（2）位置隐含,属性明显（3）几何和属性偏差（4

8、）数据结构简单,易于遥感数据结合,但数据量大（5）面向位置的数据结构,难以建立空间对象之间的关系 此外，栅格数据存在着的“最小数据单元”，非常适宜于地理信息的“模型化”。因为无论怎样复杂的模型算法，在一个栅格单元内就成为了纯粹的属性运4.2 矢量数据结构4.1.1 概述矢量数据结构是另一种常见的图形数据结构，它是用一系列有序的 x、 y 坐 标对表示地理实体的空间位置。 GIS 的矢量数据模型可以用相对较少的数据量， 记录大量的地理信息，而且精度高，制图效果好，在地理信息系统发展早期，受 计算机存储能力及计算速度的限制，其扮演了更为重要的角色，是地理信息系统 基本的数据模型之一。矢量型数据结构

9、按其是否明确表示各地理实体的空间相互 关系可分为实体型（简单的数据结构）和拓扑型（拓扑数据结构）两大类。4.1.2 实体型数据结构实体型数据结构通常以坐标来定义：一个点的位置可以二维或者三维中的坐 标的单一集合来描述。一条线通常由有序的两个或者多个坐标对集合来表示。一 个面通常由一个边界来定义，而边界是由形成一个封闭的环状的一条或多条线所 组成。我们又把这种结构称为“面条” （SPAGHETTI）结构。实体型编码的优点结构简单、直观，编码容易；缺点：数据冗余，相邻多 边形的公共边易产 生 分歧； 实体互 相 独立，缺 乏联系 。代表商用 软件 Arcview3.2 的 shapefile 数据

10、格式为实体型数据结构。特征个数定位点10X Y（单点）线23X Y，X Y， X Y （线段）多边形63X Y， X Y， X Y （闭合环）64X Y， X Y， X Y （闭合环）图 4-2 实体型数据结构4.1.3 拓扑型数据结构带有拓扑结构的编码方法，我们称之为拓扑型编码。双重独立编码是著名的 拓扑编码结构，这种数据结构最早是由美国人口统计局研制来进行人口普查分析 和制图的，简称为DIME（Dual lndependent Map Encoding）系统或双重独立式的 地图编码法。它以城市街道为编码的主体。其特点是采用了拓扑编码结构。双重独立式数据结构是对图上网状或面状要素的任何一条线

11、段，用其两端的 节点及相邻面域来予以定义。例如对图 4-3 所示的多边形数据，用双重独立数据 结构表示如表4-1 所示。我们在前面已经介绍过了拓扑结构表以及其描述的空间 关系，这里不在赘述。表4-1双重独立式（DIME）编码线号左多边形右多边形起点终占八、aOA18bOA21cOB32dOB43eOB54fOC65gOC76hOC87iCA89jCB95kCD1210lCD1112mCD1011nBA92拓扑型代表软件为ARC/INFO, Coverage是ESRI公司在公布Shapefile文件 格式之后，推出的又一矢量数据的存贮格式，其特点是拓扑型的数据编码。目前 ArcGIS 中仍然有一

12、些分析操作只能基于这种数据格式进行操作。实体型与拓扑型数据结构各有特点：（1）实体型虽然会产生数据冗余和歧 异,但易于编辑；（2）拓扑型消除了数据的冗余和歧异,但操作复杂,甚至会 产生新的数据冗余。4.1.4 矢量数据结构的特点1) 用离散的点描述空间对象与特征，定位明显，属性隐含2) 用拓扑关系描述空间对象之间的关系3) 面向目标操作，精度高，数据冗余度小4) 与遥感等图象数据难以结合5) 输出图形质量号，精度高4.3 本章小结通过对空间数据两种主要数据结构的介绍，我们可以把这两种数据结构比较如下：(1) 矢量模型用(x,y)坐标来代表地理对象，而栅格模型通过单元的行和列值 来确定位置。(2) 矢量模型精确地表现地理对象的形状，而栅格模型用小的矩形即单元(Cell) 组合构成，因此精度上不如矢量模型高。(3) 利用矢量模型进行空间分析的过程比较复杂，而栅格模型则在此方面有优 势。(4) 矢量模型中的地理对象容易与多种专题属性信息产生关联，而栅格模型只 能给相应的位置联接一种属性。选择何种数据结构存贮空间数据，需要结合特定的分析和应用来决定。