空间数据结构

第五章第五章 空间数据结构空间数据结构 数据结构即指数据组织的形式， 是适合于计算机存储、管理和处理的数据逻 辑结构。地理信息系统空间数据结构是指空间数据在系统内的组织和编码形式 （GIS 数据结构也可称为图形数据格式） ，它是指适合于计算机系统存储、管理 和处理地理图形的逻辑结构。GIS 中，空间数据一般有着较为复杂的数据结构， 目前，主要有两种数据模型表示空间数据，即矢量数据模型和栅格数据模型。 4.14.1 栅格数据结构栅格数据结构 4.1.14.1.1 概述概述 栅格数据是计算机和其它信息输入输出设备广泛使用的一种数据模型， 如电 视机、显示器、打印机等的空间寻址。甚至专门用于矢量图形的输入输出设备， 如数字化仪、矢量绘图仪及扫描仪等，其内部结构实质上是栅格的。遥感数据也 是采用特殊扫描平台获得的栅格数据。 栅格数据就是用数字表示的像元阵列， 其中，栅格的行和列规定了实体所在 的坐标空间， 而数字矩阵本身则描述了实体的属性或属性编码。栅格数据最显著 的特点就是存在着最小的、不能再分的栅格单元，在形式上常表现为整齐的数字 矩阵，因而便于计算机进行处理，特别是存储和显示。 4.1.24.1.2 编码方案编码方案 以图 4-1 为例，介绍几种编码方法的编码思路、方案和特点。 A A A A A A A A A A A A A A R R A A A A A A A A A A R R R R A A A A A A A A A A R R A A A A A A A A R R R R R R A A A A A A A A R R A A A A A A G G G G G G A A A A A A G G G G G G G G G G A A A A A A G G G G G G G G G G A A A A A A A A A A G G A A A A A A 图 4-1 栅格数据结构 1.1. 游程长度编码游程长度编码 地理数据往往有较强的相关性，也就是说相邻象元的值往往是相同的。游程 长度编码的基本思想是按行扫描，将相邻等值的象元合并，并记录代码的重复 个数。 游程长度编码的数据结构 行号,属性,重复次数。 图 4-1 的游程长度编码 为 1,A,4,R,1,A,6 对于游程长度编码， 区域越大， 数据的相关性越强， 则压缩越大。 其特点是， 压缩效率较高，叠加、合并等运算简单，编码和解码运算快。 2.2. 块式编码块式编码 块式编码是将游程扩大到二维情况， 把多边形范围划分成若干具有同一属性 的正方形，然后对各个正方形进行编码。块式编码的基本思想由初始位置（行 列号） 、半径和属性代码组成。图 4-1 的块状编码为 1,1,3,A,1,5,1,R,1,6,2,A, 块状编码对大而简单的多边形更为有效， 对一些虽不较多的复杂多边形效果 并不好。块状编码在合并、插入、检查延伸型、计算面积等操作时有明显的优越 性，而对某些运算不适应，必须在转换成简单的数据形式才能顺利进行运算。 3.3. 四叉树编码四叉树编码 四叉树编码是最有效的栅格数据压缩编码方法之一， 是一种可变分率的非均 匀网格系统，在 GIS 中有广泛的应用。其基本思路为2n2n象元组成的图像不 足的用背景补上按四个象限进行递归分割， 直到子象限的数据单调为止,最后得 到一棵四分叉的倒向树（图 4-1）。四叉树有两种,一种是常规四叉树,在子节点 与父节点之间设立指针,由于指针占用空间较大,难以达到数据压缩的目的。所 以，常规四叉树并不广泛用于存储数据，其价值在于建立索引文件，进行数据检 索。另一种是线性四叉树,它不需要记录中间节点和使用指针,仅记录叶节点,并 用地址码表示叶节点的位置。因而,线性四叉树广泛应用于数据压缩和 GIS 中的 数据结构。下面介绍最常用的线性四叉树编码。 图 4-1 四分叉的倒向树 线性四叉树编码的基本思想是 不需记录中间结点和使用指针，仅记录叶结 点，并用地址码（定位码、Morton 码）表示叶结点的位置深度（几次分割） 和属性。 为了得到线性四叉树的地址码，首先将二维栅格数据的行列号转化为二 进制数，然后交叉放入 Morton 码中，即为线性四叉树的地址码。实质上是按左 上、右上、左下、右下的顺序，从零开始对每个栅格进行自然编码。这样，在一 个 2n2n的图像中，每个像元点都给出一个 Morton 码，当 n＝3 时即为表 3 1 表 31 Morton 码 行 列 0 1 2 0 0 2 8 1 1 3 2 4 6 34567 516172021 718192223 9121324252829 31011141526273031 43233363748495253 53435383950515455 64041444556576061 74243464758596263 这样就可将用行列表示的二维图像， 用 Morton 码写成一维数据， 通过 Morton 码就可知道象元的位置。把一幅 2n2n的图像压缩成线性四叉树的过程为 1、按 Morton 码把图象读入一维数组。第一维为 Morton 码，第二维为象元 值。 2、相邻的四个象元比较，一致的合并，只记录第一个象元的Morton 码。循 环比较所形成的大块，相同的再合并，直到不能合并为止。 3、进一步用游程长度编码压缩。压缩时只记录第一个象元的 Morton 码。 解码时，根据Morton 码就可知道象元在图像中的位置左上角，本Morton 码和下一个 Morton 码之差即为象元个数。知道了象元的个数和象元的位置就可 恢复出图像了。 4.1.34.1.3 栅格数据结构的特点栅格数据结构的特点 （1） 离散的量化栅格值表示空间对象 （2） 位置隐含,属性明显 （3） 几何和属性偏差 （4） 数据结构简单,易于遥感数据结合,但数据量大 （5） 面向位置的数据结构,难以建立空间对象之间的关系 此外，栅格数据存在着的“最小数据单元”，非常适宜于地理信息的“模型 化”。因为无论怎样复杂的模型算法，在一个栅格单元内就成为了纯粹的属性运 算。 4.24.2 矢量数据结构矢量数据结构 4.1.14.1.1 概述概述 矢量数据结构是另一种常见的图形数据结构，它是用一系列有序的 x、y 坐 标对表示地理实体的空间位置。GIS 的矢量数据模型可以用相对较少的数据量， 记录大量的地理信息，而且精度高，制图效果好，在地理信息系统发展早期，受 计算机存储能力及计算速度的限制， 其扮演了更为重要的角色，是地理信息系统 基本的数据模型之一。 矢量型数据结构按其是否明确表示各地理实体的空间相互 关系可分为实体型（简单的数据结构）和拓扑型（拓扑数据结构）两大类。 4.1.24.1.2 实体型数据结构实体型数据结构 实体型数据结构通常以坐标来定义 一个点的位置可以二维或者三维中的坐 标的单一集合来描述。一条线通常由有序的两个或者多个坐标对集合来表示。一 个面通常由一个边界来定义， 而边界是由形成一个封闭的环状的一条或多条线所 组成。我们又把这种结构称为“面条” （SPAGHETTI）结构。 实体型编码