妈妈说：“生活就像是一盒巧克力，你永远不知道下一块的味道。”
Forrest Gump
第七章 空间数据管理
导读：本章首先介绍空间数据库、与一般数据库的比较，以及空间数据库的存储方式。
然后介绍了GIS中两种重要的数据结构：栅格结构和矢量结构，以及其具体的存储方式，然后比较了两种结构的特点，并给出了其相互转换算法。
最后介绍了空间检索中常用的技术——空间索引，介绍了一些常用的空间索引方式，如BSP树、R树、CELL树等；以及空间数据的查询功能。
1．空间数据库
一个信息系统及其数据库的组成，决定于系统的应用目的、数据类型和系统的工作方式。关于地理信息系统的内容及其功能，以及地理信息系统的一个重要特点，或者说是与一般管理信息系统的区别，是数据具有空间分布的性质。对地理信息系统来讲，不仅数据本身具有空间属性，系统的分析和应用也无不与地理环境直接关联。系统的这一基本特征，深刻地影响着数据的结构、数据库的设计、分析算法和软件，以及系统的输入和输出。
1．1地理信息系统与一般管理信息系统的比较
从数据源的角度来看，图形和图像数据是地理信息系统数据的一个主要来源，分析处理的结果也常用图形的方式来表示。而一般的管理信息系统，则多以统计数据、表格数据为主。这一点也使地理信息系统在硬件和软件上与一般的管理信息系统有所区别。
1．1．1两者的区别
1）在硬件上，为了处理图形和图像数据，系统需要配置专门的输入和输出设备，如数字化仪、绘图机、图形图像的显示设备等；许多野外实地采集和台站的观测所得到的资源信息是模拟量形式，系统还需要配置模——数转换设备，这些设备往往超过中央处理机的价格，体积也比较大。
2）在软件上，则要求研制专门的图形和图像数据的分析算法和处理软件，这些算法和软件又直接和数据的结构及数据库的管理方法有关。
3）在信息处理的内容和采用目的方面，一般的管理信息系统，主要是查询检索和统计分析，处理的结果，大多是制成某种规定格式的表格数据，而地理信息系统，除了基本的信息检索和统计分析外，主要用于分析研究资源的合理开发利用，制定区域发展规划，地区的综合治理方案，对环境进行动态的监视和预测预报，为国民经济建设中的决策提供科学依据，为生产实践提供信息和指导。
由于地理信息系统是一个复杂的自然和社会的综合体，所以信息的处理必然是多因素的综合分析。系统分析是基本的方法，例如，研究某种地理信息系统中各组成部分间的相互关系，利用统计数据建立系统的数学模型，根据给定的目标函数，进行数学规划，寻求最优方案，使该系统的经济效益为最佳；或者分析系统中各部分之间反馈联系，建立系统的结构模型，采用系统动力学的方法，进行动态分析，研究系统状态的变化和预测发展趋势等。计算机仿真是一种有效而经济的分析方法，便于分析各种因素的影响和进行方案的比较，在自然环境和社会经济的许多应用研究中常被采用。此外，地理信息系统还有分析量算的功能，如计算面积、长度、密度、分布特征等以及地理实体之间的关系运算。
1．1．2两者共同之处
地理信息系统和一般的信息管理系统，也有许多共同之处。两者都是以计算机为核心的信息处理系统，都具有数据量大和数据之间关系复杂的特点，也都随着数据库技术的发展在不断的改进和完善。比较起来，商用的管理信息系统发展快，用户数量大，而且已有定型的软件产品可供选用，这也促进了软件系统的标准化。地理信息系统，由于上述一些特点，多是根据具体的应用要求专门设计，数据格式和组织管理方法各不相同。目前国外已有几百个空间数据处理系统和软件包，几乎没有两个系统是一样的，尽管大家都认为标准化是很重要的，也作了许多努力（例如建立计算机制图的标准和规范），但分析的算法和软件系统还谈不上标准化的问题。事实上，地理信息系统正作为一种空间信息的处理系统，成为一个单独的研究和发展领域。
1．2空间数据库
1．2．1数据库的概念
数据库就是为一定目的服务，以特定的数据存储的相关联的数据集合，它是数据管理的高级阶段，是从文件管理系统发展而来的。地理信息系统的数据库（简称空间数据库或地理数据库）是某一区域内关于一定地理要素特征的数据集合。为了直观地理解数据库，可以把数据库作如下比较：
表7-1：数据库与图书馆比较
数据库
图书馆
数据
图书
数据模型
书卡编目
数据的物理组织
图书存放规则、书架
数据库管理系统
图书管理员
外存
书库
用户
读者
数据存取
图书阅览
1．2．2空间数据库特点
空间数据库与一般数据库相比，具有以下特点：
1）数据量特别大，地理系统是一个复杂的综合体，要用数据来描述各种地理要素，尤其是要素的空间位置，其数据量往往很大。
2）不仅有地理要素的属性数据（与一般数据库中的数据性质相似），还有大量的空间数据，即描述地理要素空间分布位置的数据，并且这两种数据之间具有不可分割的联系。
3）数据应用广泛，例如地理研究、环境保护、土地利用与规划、资源开发、生态环境、市政管理、道路建设等。
1．2．3数据库管理系统
数据库是关于事物及其关系的信息组合，早期的数据库物体本身与其属性是分开存储的，只能满足简单的数据恢复和使用。数据定义使用特定的数据结构定义，利用文件形式存储，称之为文件处理系统。
文件处理系统是数据库管理最普遍的方法，但是有很多缺点：首先每个应用程序都必须直接访问所使用的数据文件，应用程序完全依赖于数据文件的存储结构，数据文件修改时应用程序也随之修改；另外的问题是数据文件的共享。由于若干用户或应用程序共享一个数据文件，要修改数据文件必须征得所有用户的认可。由于缺乏集中控制也会带来一系列数据库的安全问题。数据库的完整性是严格的，信息质量很差比没有信息更糟。
数据库管理系统（Database Management System，DBMS）是在文件处理系统的基础上进一步发展的系统。DBMS在用户应用程序和数据文件之间起到了桥梁作用。DBMS的最大优点是提供了两者之间的数据独立性，即应用程序访问数据文件时，不必知道数据文件的物理存储结构。当数据文件的存储结构改变时，不必改变应用程序。
1）采用标准DBMS存储空间数据的主要问题*
用标准的DBMS来存储空间数据，不如存储表格数据那样好，其主要问题包括：
（1．1）在GIS中，空间数据记录是变长的，因为需要存储的坐标点的数目是变化的，而一般数据库都只允许把记录的长度设定为固定长度。不仅如此，在存储和维护空间数据拓扑关系方面，DBMS也存在着严重的缺陷。因而，一般要对标准的DBMS增加附加的软件功能。
（1．2）DBMS一般都难以实现对空间数据的关联、连通、包含、叠加等基本操作。
（1．3）GIS需要一些复杂的图形功能，一般的DBMS不能支持。
（1．4）地理信息是复杂的，单个地理实体的表达需要多个文件、多条记录、或许包括大地网、特征坐标、拓扑关系、空间特征量测值、属性数据的关键字以及非空间专题属性等，一般的DBMS也难以支持。
（1．5）具有高度内部联系的GIS数据记录需要更复杂的安全性维护系统，为了保证空间数据库的完整性，保护数据文件的完整性，保护系列必须与空间数据一起存储，否则一条记录的改变就会使其他数据文件产生错误。一般的DBMS都难以保证这些。
2）GIS数据管理方法主要4种类型
（2．1）对不同的应用模型开发独立的数据管理服务，这是一种基于文件管理的处理方法。
（2．2）在商业化的DBMS基础上开发附加系统。开发一个附加软件用于存储和管理空间数据和空间分析，使用DBMS管理属性数据。
（2．3）使用现有的DBMS，通常是以DBMS为核心，对系统的功能进行必要扩充，空间数据和属性数据在同一个DBMS管理之下。需要增加足够数量的软件和功能来提供空间功能和图形显示功能。
（2．4）重新设计一个具有空间数据和属性数据管理和分析功能的数据库系统。
1．3数据与文件组织
数据是现实世界中信息的载体，是信息的具体表达形式，为了表达有意义的信息内容，数据必须按照一定的方式进行组织和存储。
1．3．1数据组织的分级
数据库中的数据组织一般可以分为四级：数据项、记录、文件和数据库。
1）数据项
数据项是可以定义数据的最小单位，也叫元素、基本项、字段等，数据项与现实世界实体的属性相对应，数据项有一定的取值范围，称为域，域以外的任何值对该数据项都是无意义的。每个数据项都有一个名称，称为数据项目。数据项的值可以是数值的、字母的、字母数字的、汉字的等形式。数据项的物理特点在于它具有确定的物理长度，可以作为整体看待。
2）记录
记录是由若干相关联的数据项组成，是处理和存储信息的基本单位，是关于一个实体的数据总和，构成该记录的数据项表示实体的若干属性。记录有“型”和“值”的区别，“型”是同类记录的框架，它定义记录；而“值”是记录反映实体的内容。为了唯一标识每个记录，就必须有记录标识符，也叫关键字。记录标识符一般由记录中的第一个数据项担任，唯一标识记录的关键字称主关键字，其它标识记录的关键字称为辅关键字。记录可以分为逻辑记录与物理记录，逻辑记录是文件中按信息在逻辑上的独立意义来划分的数据单位；而物理记录是单个输入输出命令进行数据存取的基本单元。物理记录和逻辑记录之间的对应关系有一个物理记录一对应一个逻辑记录；一个物理记录含有若干个逻辑记录；若干个物理记录存放一个逻辑记录。
3）文件
文件是一给定类型的（逻辑）记录的全部具体值的集合，文件用文件名称标识，文件根据记录的组织方式和存取方法可以分为：顺序文件、索引文件、直接文件和倒排文件等。
4）数据库
数据库是比文件更大的数据组织，数据库是具有特定联系的数据的集合，也可以看成是具有特定联系的多种类型的记录的集合。数据库的内部构造是文件的集合，这些文件之间存在某种联系，不能孤立存在。
1．3．2数据间的逻辑联系
数据间的逻辑联系主要是指记录与记录之间的联系。记录是表示现实世界中的实体的。实体之间存在着一种或多种联系，这样的联系必然要反映到记录之间的联系上来。数据之间的逻辑联系主要有三种：一对一的联系；一对多的联系；多对多的联系。
1．3．3常用数据文件
图7-1：非顺序文件
文件组织是数据组织的一部分，数据组织既指数据在内存中的组织，又指数据在外存中的组织，而文件组织则主要指数据记录在外存设备上的组织，它由操作系统OS进行管理，具体讲在外存设备上如何安排数据和组织数据，以及实施对数据的访问方式等问题。操作系统实现的文件组织方式，可以分为顺序文件、索引文件、直接文件和倒排文件。
1）顺序文件
顺序文件（图7-2）是最简单的文件组织形式，对记录按照主关键字的顺序进行组织。当主关键字是数字型时，以其数值的大小为序；若主关键字是文字型的，则以字母的排列为序。一切存于磁带上的记录，都只能是顺序的，而存于磁盘上的记录，既可以是顺序的，也可以是随机的。顺序文件的记录，逻辑上是按主关键字排序的，而在物理存储上可以有不同的方式，包括向量方式：被存储的文件按地址连续存放，物理结构与逻辑结构一致；链方式：文件不按地址连续存放，文件的逻辑顺序靠链来实现，文件中的每个记录中都含有一个指针，用以指明下一个记录的存放地址；块链方式：把文件分成若干数据块，块之间用指针连接，而块内则是连续存储。
图7-2：顺序文件
2）索引文件
索引文件除了存储记录本身（主文件）以外，还建立了若干索引表，这种带有索引表的文件叫索引文件。索引表中列出记录关键字和记录在文件中的位置（地址）。读取记录时，只要提供记录的关键字值，系统通过查找索引表获得记录的位置，然后取出该记录。索引表一般都是经过排序的，既可以是有顺序的，也可以是非顺序的，可以是单级索引，也可以是多级索引，多级索引可以提高查找速度，但占用的存储空间较大。
3）直接文件
直接文件又称随机文件，其存储是根据记录关键字的值，通过某种转换方法得到一个物理存储位置，然后把记录存储在该位置上。查找时，通过同样的转换方法，可以直接得到所需要的记录。
4）倒排文件
倒排文件是带有辅索引的文件，其中辅索引是按照一些辅关键字来组织索引的（注意：索引文件是按照记录的主关键字来构造索引的，也叫主索引）。倒排文件是一种多关键字的索引文件，其中的索引不能唯一标识记录，往往同一索引指向若干记录。因而，索引往往带有一个指针表，指向所有该索引标识的记录。通过辅索引不能直接读取记录，而要通过主关键字才能查到记录的位置。倒排文件的主要优点是在处理多索引检索时，可以在辅检索中先完成查询的‘交’、‘并’等逻辑运算，得到结果后再对记录进行存取，从而提高查找速度。
1．4 GIS的内部数据结构——矢量结构和栅格结构
描述地理实体的数据本身的组织方法，称为内部数据结构。空间数据结构是指适合于计算机系统存储、管理和处理的地学图形的逻辑结构，是地理实体的空间排列方式和相互关系的抽象描述。它是对数据的一种理解和解释，不说明数据结构的数据是毫无用处的，不仅用户无法理解，计算机程序也不能正确的处理。对同样的一组数据，按不同的数据结构去处理，得到的可能是截然不同的内容。空间数据结构是地理信息系统沟通信息的桥梁，只有充分理解地理信息系统所采用的特定数据结构，才能正确地使用系统。
内部数据结构基本上可分为两大类：矢量结构和栅格结构（也可以称为矢量模型和栅格模型）（图7-3）。两类结构都可用来描述地理实体的点、线、面三种基本类型。
空间数据编码是空间数据结构的实现，即将根据地理信息系统的目的和任务所搜集的、经过审核了的地形图、专题地图和遥感影像等资料按特定的数据结构转换为适合于计算机存储和处理的数据的过程。由于地理信息系统数据量极大，一般采用压缩数据的编码方式以减少数据冗余。
在地理信息系统的空间数据结构中，栅格结构的编码方式主要有直接栅格编码、链码、游程长度编码、块码、四叉树码等；矢量结构主要有坐标序列编码、树状索引编码和二元拓扑编码等编码方法。
图7-3：矢量结构和栅格结构
1．4．1矢量模型
在矢量模型中，现实世界的要素位置和范围可以采用点、线或面表达，与它们在地图上表示相似，每一个实体的位置是用它们在坐标参考系统中的空间位置（坐标）定义。地图空间中的每一位置都有唯一的坐标值。点、线和多边形用于表达不规则的地理实体在现实世界的状态（多边形是由若干直线围成的封闭区域的边界）。一条线可能表达一条道路，一个多边形可能表达一块林地等。矢量模型中的空间实体与要表达的现实世界中的空间实体具有一定的对应关系。
1．4．2栅格模型
在栅格模型中，空间被规则地划分为栅格（通常为正方形）。地理实体的位置和状态是用它们占据的栅格的行、列来定义的。每个栅格的大小代表了定义的空间分辨率。由于位置是由栅格行列号定义的，所以特定的位置由距它最近的栅格记录决定。例如，某个区域被划分成10*10个栅格，那么仅能记录位于这10*10个栅格附近的物体的位置。栅格的值表达了这个位置上物体的类型或状态。采用栅格方法，空间被划分成大量规则格网，而且每个栅格取值可能不一样。空间单元是栅格，每一个栅格对应于一个特定的空间位置，如地表的一个区域，栅格的值表达了这个位置的状态。
与矢量模型不一样，栅格模型最小单元与它表达的真实世界空间实体没有直接的对应关系。栅格数据模型中的空间实体单元不是通常概念上理解的物体，它们只是彼此分离的栅格。例如，道路作为明晰的栅格是不存在的，栅格的值才表达了路是一个实体。道路是被具有道路属性值的一组栅格表达的，这条路不可能通过某一栅格实体被识别出来。在这两种数据结构中，空间信息都是使用统一的单位表达。在栅格方法中，统一的单位是栅格（栅格是不可再分的，其属性用于表达对应位置物体的性质），表达一个区域所用栅格的数量很大，但其栅格单元的大小一样。栅格数据文件包含有上百万个栅格，每个栅格的位置都被严格定义。在矢量方法中，统一的单元是点、线和多边形，与栅格方法相比，在数量上所用的表达单元较少，但大小可变。在矢量文件中，元素的个数或许数千个，但毕竟没有栅格数据那么多。同一类型的矢量单元的位置是用连续坐标值定义。矢量数据提供的坐标位置比栅格数据用行、列号所表达位置更精确。这两种方法各有优缺点，究竟采用何种数据结构，取决于利用数据的目的。有些地理现象用栅格数据表达更合适；有些地理现象则用矢量数据更有利，以便表达它们之间的空间关系。
2．栅格数据结构及其编码
2．1栅格数据结构
2．1．1定义
栅格结构是最简单最直接的空间数据结构，是指将地球表面划分为大小均匀紧密相邻的网格阵列，每个网格作为一个象元或象素由行、列定义，并包含一个代码表示该象素的属性类型或量值，或仅仅包括指向其属性记录的指针。因此，栅格结构是以规则的阵列来表示空间地物或现象分布的数据组织，组织中的每个数据表示地物或现象的非几何属性特征。如图7-4所示，在栅格结构中，点用一个栅格单元表示；线状地物沿线走向的一组相邻栅格单元表示，每个栅格单元最多只有两个相邻单元在线上；面或区域用记有区域属性的相邻栅格单元的集合表示，每个栅格单元可有多于两个的相邻单元同属一个区域。遥感影像属于典型的栅格结构，每个象元的数字表示影像的灰度等级。
（a）点 （b）线 （c）面
图7-4：点、线、区域的格网
2．1．2特点
栅格结构的显著特点是：属性明显，定位隐含，即数据直接记录属性的指针或属性本身，而所在位置则根据行列号转换为相应的坐标，也就是说定位是根据数据在数据集中的位置得到的。如图7-4-（a）所示，数据2表示属性或编码为2的一个点，其位置由其所在的第3行、第4列交叉得到的。由于栅格结构是按一定的规则排列的，所表示的实体的位置很容易隐含在格网文件的存储结构中，在后面讲述栅格结构编码时可以看到，每个存储单元的行列位置可以方便地根据其在文件中的记录位置得到，且行列坐标可以很容易地转为其他坐标系下的坐标。在格网文件中每个代码本身明确地代表了实体的属性或属性的编码，如果为属性的编码，则该编码可作为指向实体属性表的指针。图7-4-（a）表示了代码为2的点实体，图7-4-（b）表示了一条代码为6的线实体，而图7-4-（c）则表示了三个面实体或称为区域实体，代码分别为4、7和8。由于栅格行列阵列容易为计算机存储、操作和显示，因此这种结构容易实现，算法简单，且易于扩充、修改，也很直观，特别是易于同遥感影像的结合处理，给地理空间数据处理带来了极大的方便。
栅格结构表示的地表是不连续的，是量化和近似离散的数据。在栅格结构中，地表被分成相互邻接、规则排列的矩形方块（特殊的情况下也可以是三角形或菱形、六边形等），每个地块与一个栅格单元相对应。栅格数据的比例尺就是栅格大小与地表相应单元大小之比。在许多栅格数据处理时，常假设栅格所表示的量化表面是连续的，以便使用某些连续函数。由于栅格结构对地表的量化，在计算面积、长度、距离、形状等空间指标时，若栅格尺寸较大，则造成较大的误差，由于在一个栅格的地表范围内，可能存在多于一种的地物，而表示在相应的栅格结构中常常是一个代码。也类似于遥感影像的混合象元问题，如Landsat的MSS卫星影像单个象元对应地表79米*79米的矩形区域，影像上记录的光谱数据是每个象元所对应的地表区域内所有地物类型的光谱辐射的总和效果。因而，这种误差不仅有形态上的畸形，还可能包括属性方面的偏差。
2．2决定栅格单元代码的方式
在决定栅格代码时尽量保持地表的真实性，保证最大的信息容量。图7-5所示的一块矩形地表区域，内部含有A、B、C三种地物类型，O点为中心点，将这个矩形区域近似地表示为栅格结构中的一个栅格单元时，可根据需要，采取如下的方式之一来决定栅格单元的代码。
图7-5：栅格单元代码的确定
2．2．1中心点法
用处于栅格中心处的地物类型或现象特性决定栅格代码，在图7-5所示的矩形区域中，中心点O落在代码为C的地物范围内，按中心点法的规则，该矩形区域相应的栅格单元代码为C，中心点法常用于具有连续分布特性的地理要素，如降雨量分布、人口密度图等。
2．2．2面积占优法
以占矩形区域面积最大的地物类型或现象特性决定栅格单元的代码，在图7-5所示的例子中，显见B类地物所占面积最大，故相应栅格代码定为B。面积占优法常用于分类较细，地物类别斑块较小的情况。
2．2．3重要性法
根据栅格内不同地物的重要性，选取最重要的地物类型决定相应的栅格单元代码，假设图7-5中A类最重要的地物类型，即A比B和C类更为重要，则栅格单元的代码应为A。重要性法常用于具有特殊意义而面积较小的地理要素，特别是点、线状地理要素，如城镇、交通枢纽、交通线、河流水系等，在栅格中代码应尽量表示这些重要地物。
2．2．4百分比法
根据矩形区域内各地理要素所占面积的百分比数确定栅格单元的代码，如可记面积最大的两类BA，也可以根据B类和A类所占面积百分比数在代码中加入数字。
2．3编码方法
2．3．1直接栅格编码
这是最简单直观而又非常重要的一种栅格结构编码方法，通常称这种编码的图像文件为网格文件或栅格文件，栅格结构不论采用何种压缩编码方法，其逻辑原型都是直接编码网格文件。直接编码就是将栅格数据看作一个数据矩阵，逐行（或逐列）逐个记录代码，可以每行都从左到右逐个象元记录，也可以奇数行地从左到右而偶数行地从右向左记录，为了特定目的还可采用其他特殊的顺序（图7-6）。
图7-6：一些常用的栅格排列顺序
2．3．2压缩编码方法
目前有一系列栅格数据压缩编码方法，如键码、游程长度编码、块码和四叉树编码等。其目的，就是用尽可能少的数据量记录尽可能多的信息，其类型又有信息无损编码和信息有损编码之分。信息无损编码是指编码过程中没有任何信息损失，通过解码操作可以完全恢复原来的信息，信息有损编码是指为了提高编码效率，最大限度地压缩数据，在压缩过程中损失一部分相对不太重要的信息，解码时这部分难以恢复。在地理信息系统中多采用信息无损编码，而对原始遥感影像进行压缩编码时，有时也采取有损压缩编码方法。
1）链码（Chain Codes）
链码又称为弗里曼链码[Freeman]或边界链码，链码可以有效地压缩栅格数据，而且对于估算面积、长度、转折方向的凹凸度等运算十分方便，比较适合于存储图形数据。缺点是对边界进行合并和插入等修改编辑工作比较困难，对局部的修改将改变整体结构，效率较低，而且由于链码以每个区域为单位存储边界，相邻区域的边界将被重复存储而产生冗余。
2）游程长度编码（Run-Length Codes）
游程长度编码是栅格数据压缩的重要编码方法，它的基本思路是：对于一幅栅格图像，常常有行（或列）方向上相邻的若干点具有相同的属性代码，因而可采取某种方法压缩那些重复的记录内容。其方法有两种方案：一种编码方案是，只在各行（或列）数据的代码发生变化时依次记录该代码以及相同的代码重复的个数，从而实现数据的压缩。例如对图7-4（c）所示栅格数据，可沿行方向进行如下游程长度编码：
（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个整数表示，可见游程长度编码压缩数据是十分有效又简便的。事实上，压缩比的大小是与图的复杂程度成反比的，在变化多的部分，游程数就多，变化少的部分游程数就少，图件越简单，压缩效率就越高。另一种游程长度编码方案就是逐个记录各行（或列）代码发生变化的位置和相应代码，如对图7-4（c）所示栅格数据的另一种游程长度编码如下（沿列方向）：
（1，0），（2，4），（4，0），（1，4），（4，0）；（1，4），（5，8），（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）。
游程长度编码在栅格压缩时，数据量没有明显增加，压缩效率较高，且易于检索，叠加合并等操作，运算简单，适用于机器存储容量小，数据需大量压缩，而又要避免复杂的编码解码运算增加处理和操作时间的情况。
3）块码
块码是游程长度编码扩展到二维的情况，采用方形区域作为记录单元，每个记录单元包括相邻的若干栅格，数据结构由初始位置（行、列号）和半径，再加上记录单位的代码组成。对图7-4（c）所示图像的块码编码如下：
(1,1,1,0),(1,2,2,4),(1,4,1,7),(1,5,1,7),
(1,6,2,7),(1,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个整数，比直接编码还多，这是因为例中为描述方便，栅格划分很粗糙，在实际应用中，栅格划分细，数据冗余多的多，才能显出压缩编码的效果，而且还可以作一些技术处理，如行号可以通过行间标记而省去记录，行号和半径等也不必用双字节整数来记录，可进一步减少数据冗余。
块码具有可变的分辨率，即当代码变化小时图块大，就是说在区域图斑内部分辨率低；反之，分辨率高以小块记录区域边界地段，以此达到压缩的目的。因此块码与游程长度编码相似，随着图形复杂程度的提高而降低效率，就是说图斑越大，压缩比越高；图斑越碎，压缩比越低。块码在合并、插入、检查延伸性、计算面积等操作时有明显的优越性。然而在某些操作时，则必须把游程长度编码和块码解码，转换为基本栅格结构进行。
4）四叉树
四叉树又称四元树或四分树，是最有效的栅格数据压缩编码方法之一，绝大部分图形操作和运算都可以直接在四叉树结构上实现，因此四叉树编码既压缩了数据量，又可大大提高图形操作的效率。四叉树将整个图像区逐步分解为一系列被单一类型区域内含的方形区域，最小的方形区域为一个栅格象元，分割的原则是，将图像区域划分为四个大小相同的象限，而每个象限又可根据一定规则判断是否继续等分为次一层的四个象限，其终止判据是，不管是哪一层上的象限，只要划分到仅代表一种地物或符合既定要求的少数几种地物时，则不再继续划分，否则一直划分到单个栅格象元为止。四叉树通过树状结构记录这种划分，并通过这种四叉树状结构实现查询、修改、量算等操作。图7-7（b）为图7-4（c）图形的四叉树分解，各子象限尺度大小不完全一样，但都是同代码栅格单元，其四叉树如图7-7-（c）所示。
（a）块码分割 （b）四叉树分割
（c）b的四叉树编码
图7-7：四叉树编码
其中最上面的那个结点叫做根结点，它对应整个图形。总共有4层结点，每个结点对应一个象限，如2层4个结点分别对应于整个图形的四个象限，排列次序依次为南西（SW）、南东（SE）、北西（NW）和北东（NE），不能再分的结点称为终止结点（又称叶子结点），可能落在不同的层上，该结点代表的子象限具有单一的代码，所有终止结点所代表的方形区域覆盖了整个图形。从上到下，从左到右为叶子结点编号如图7-7(c)所示，共有40个叶子结点，也就是原图被划分为40个大小不等的方形子区，图7-7(c)的最下面的一排数字表示各子区的代码。
由上面图形的四叉树分解可见，四叉树中象限的尺寸是大小不一的，位于较高层次的象限较大，深度小即分解次数少，而低层次上的象限较小，深度大即分解次数多，这反映了图上某些位置单一地物分布较广而另一些位置上的地物比较复杂，变化较大。正是由于四叉树编码能够自动地依照图形变化而调整象限尺寸，因此它具有极高的压缩效率。
采用四叉树编码时，为了保证四叉树分解能不断地进行下去，要求图像必须为2n×2n的栅格阵列，n为极限分割数，n+1为四叉树的最大高度或最大层数，图7-4（c）为23×23的栅格，因此最多划分三次，最大层数为4，对于非标准尺寸的图像需首先通过增加背景的方法将图像扩充为2n×2n的图像。
为了使计算机既能以最小的冗余存储图像对应的四叉树，又能方便地完成各种图形图像操作，专家们已提出了多种编码方式，下面介绍美国马里兰大学地理信息系统中采用的编码方式，该方法记录了终止结点（或叶子结点）的地址和值，值就是子区的代码，其中地址包括两个部分，共32位（二进制），最右边4位记录该叶子结点的深度，即处于四叉树的第几层上，有了深度可以推知子区的大小；地址由从根结点到该叶子结点的路径表示，0，1，2，3分别表示SW、SE、NW、NE，从右边第5位开始2n字节记录这些方向。如图7-7-（c）表示的第六个结点深度为3，第一层处于SW象限，记为0；第二层处于NE象限，记为3，第三层处于NW象限，记为2，表示为二进制为：
0000… 000(22位)；001110（6位）；0011（4位）
每层象限位置由两位二进制数表示，共6位，十进制整数为227。这样，记录了各个叶子的地址，再记上相应代码值，就记录了这个图像，并可在此编码基础上进行多种图像操作。
事实上，叶结点的地址可以直接由子区左下角的行列坐标，按二进制按位交错得到。如对于6号叶子结点，在以图像左下角为原点的行列坐标系中，其左下角行、列坐标为（3，2），表示为二进制分别为011和010，按位交错就是001110，正是6号地块。
对于只有点状地物或只有线状地物的图件，为了提高效率，设计了略有不同的划分终止条件和记录方法，称为点四叉树和线四叉树。点四叉树对子象限的划分直到每个子象限不含有点或只含有一个点为止，叶子的值则记录是否有点和点在子象限的位置；线四叉树划分子象限直到子象限不含线段或只含有单个线段，对线的结点则划分到单个象素，其叶子值记录更为复杂。
四叉树编码具有可变的分辨率，并且有区域性质，压缩数据灵活，许多运算可以在编码数据上直接实现，大大地提高了运算效率，是优秀的栅格压缩编码之一。
一般说来，对数据的压缩是以增加运算时间为代价的。在这里时间与空间是一对矛盾，为了更有效地利用空间资源，减少数据冗余，不得不花费更多的运算时间进行编码，好的压缩编码方法就是要在尽可能减少运算时间的基础上达到最大的数据压缩效率，并且是算法适应性强，易于实现。链码的压缩效率较高，已经近矢量结构，对边界的运算比较方便，但不具有区域的性质，区域运算困难；游程长度编码既可以在很大程度上压缩数据，又最大限度地保留了原始栅格结构，编码解码十分容易；块码和四叉树码具有区域性质，又具有可变的分辨率，有较高的压缩效率，四叉树编码可以直接进行大量图形图像运算，效率较高，是很有前途的方法。在此基础上已经开始发展了用于三维数据的八叉树编码等。
3．矢量数据结构及其编码
3．1矢量数据结构
3．1．1定义
地理信息系统中另一种最常见的图形数据结构为矢量结构，即通过记录坐标的方式尽可能精确地表示点、线、多边形等地理实体，坐标空间设为连续，允许任意位置、长度和面积的精确定义，事实上，其精度仅受数字化设备的精度和数值记录字长的限制，在一般情况下，比栅格结构精度高得多。
对于点实体，矢量结构中只记录其在特定坐标系下的坐标和属性代码；对于线实体，在数字化时即进行量化，就是用一系列足够短的直线首尾相接表示一条曲线，当曲线被分割成多而短的线段后，这些小线段可以近似地看成直线段，而这条曲线也可以足够精确地由这些小直线段序列表示，矢量结构中只记录这些小线段的端点坐标，将曲线表示为一个坐标序列，坐标之间认为是以直线段相连，在一定精度范围内可以逼真地表示各种形状的线状地物；“多边形”在地理信息系统中是指一个任意形状、边界完全闭合的空间区域。其边界将整个空间划分为两个部分：包含无穷远点的部分称为外部，另一部分称为多边形内部。把这样的闭合区域称为多边形是由于区域的边界线同前面介绍的线实体一样，可以被看作是由一系列多而短的直线段组成，每个小线段作为这个区域的一条边，因此这种区域就可以看作是由这些边组成的多边形了。
跟踪式数字化仪对地图数字化产生矢量结构的数字地图，适合于矢量绘图仪绘出。矢量结构允许最复杂的数据以最小的数据冗余进行存储，相对栅格结构来说，数据精度高，所占空间小，是高效的空间数据结构。
3．1．2特点
矢量结构的特点是：定位明显、属性隐含，其定位是根据坐标直接存储的，而属性则一般存于文件头或数据结构中某些特定的位置上，这种特点使得其图形运算的算法总体上比栅格数据结构复杂的多，有些甚至难以实现，当然有些地方也有所便利和独到之处，在计算长度、面积、形状和图形编辑、几何变换操作中，矢量结构有很高的效率和精度，而在叠加运算、邻域搜索等操作时则比较困难。
3．2编码方法
3．2．1点实体
对于点实体和线实体的矢量编码比较直接，只要能将空间信息和属性信息记录完全就可以了。点是空间上不能再分的地理实体，可以是具体的或抽象的，如地物点、文本位置点或线段网络的结点等，由一对x、y坐标表示。图7-8-a表示了点的矢量编码的基本内容。
3．2．2线实体
线实体主要用来表示线状地物（如公路、水系、山脊线等）符号线和多边形边界，有时也称为“弧”、“链”、“串”等，其矢量编码一般包括以下内容，图7-8-b为线实体矢量编码的基本内容。
其中唯一标识码是系统排列序号；线标识码可以标识线的类型；起始点和终止点号可直接用坐标表示；显示信息是显示时的文本或符号等；与线相联系的非几何属性可以直接存储于线文件中，也可单独存储，而由标识码联接查找。
图7-8：（a）点实体的编码，（b）线实体的编码
3．2．3多边形
多边形数据是描述地理信息的最重要的一类数据。在区域实体中，具有名称属性和分类属性的，多用多边形表示，如行政区、土地类型、植被分布等；具有标量属性的，有时也用等值线描述（如地形、降雨量等）。
多边形矢量编码不但要表示位置和属性，更为重要的是要能表达区域的拓扑性质，如形状、邻域和层次等，以便使这些基本的空间单元可以作为专题图资料进行显示和操作，由于要表达的信息十分丰富，基于多边形的运算多而复杂，因此多边形矢量编码比点和线实体的矢量编码要复杂得多，也更为重要。
多边形矢量编码除有存储效率的要求外，一般还要求所表示的各多边形有各自独立的形状，可以计算各自的周长和面积等几何指标；各多边形拓扑关系的记录方式要一致，以便进行空间分析；要明确表示区域的层次，如岛-湖-岛的关系等。因此，它与机助制图系统仅为显示和制图目的而设计的编码有很大不同。
1）坐标序列法（Spaghetti方式）
图7-9：坐标序列法表示的多边形
由多边形边界的x、y坐标对集合及说明信息组成，是最简单的一种多边形矢量编码，如图7-9记为以下坐标文件：
10：x1,y1；x2,y2；x3,y3；x4,y4；x5,y5；x6,y6；x7,y7；x8,y8；x9,y9；x10,y10；x11,y11；
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；
30：x33,y33；x34,y34；x35,y35；x36,y36；x37,y37；x38,y38；x39,y39；x40,y40；
40：x19,y19；x20,y20；x21,y21；x28,y28；x29,y29；x30,y30；x31,y31；x32,y32；
50：x21,y21；x22,y22；x23,y23；x8,y8；x7,y7；x6,y6；x24,y24；x25,y25；x26,y26；x27,y27；x28,y28；
坐标序列法文件结构简单，易于实现以多边形为单位的运算和显示。这种方法的缺点是：
（1．1）多边形之间的公共边界被数字化和存储两次，由此产生冗余和碎屑多边形；
（1．2）每个多边形自成体系而缺少邻域信息，难以进行邻域处理，如消除某两个多边形之间的共同边界；
（1．3）岛只作为一个单个的图形建造，没有与外包多边形的联系；
（1．4）不易检查拓扑错误。这种方法可用于简单的粗精度制图系统中。
2）树状索引编码法
该法采用树状索引以减少数据冗余并间接增加邻域信息，方法是对所有边界点进行数字化，将坐标对以顺序方式存储，由点索引与边界线号相联系，以线索引与各多边形相联系，形成树状索引结构。
图7-10和图7-11分别为图7-9的多边形文件和线文件树状索引示意图。其文件结构如下：
图7-10：线与多边形之间的树状索引
图7-11：点与边界线之间的树状索引
采用上述的树状结构，图7-9的多边形数据记录如下：
1）点文件：
点号
坐标
1
x1,y1
2
x2,y2
…
…
40
x40,y40
2）线文件
线号
起点
终点
点号
I
1
6
1,2,3,4,5,6
II
6
8
6,7,8
…
…
…
…
X
33
33
33,34,35,36,37,38,39,40,33
3）多边形文件
多边形编号
多边形边界
10
I,II,IX
20
III,VII,VIII,IX,X
30
X
40
IV,VI,VII
50
II,III,IV,V
树状索引编码消除了相邻多边形边界的数据冗余和不一致的问题，在简化过于复杂的边界线或合并相邻多边形时可不必改造索引表，邻域信息和岛状信息可以通过对多边形文件的线索引处理得到，但是比较繁琐，因而给相邻函数运算，消除无用边，处理岛状信息以及检查拓扑关系带来一定的困难，而且两个编码表都需要以人工方式建立，工作量大且容易出错。
3）拓扑结构编码法
要彻底解决邻域和岛状信息处理问题必须建立一个完整的拓扑关系结构，这种结构应包括以下内容：唯一标识，多边形标识，外包多边形指针，邻接多边形指针，边界链接，范围（最大和最小x、y坐标值）。采用拓扑结构编码可以较好地解决空间关系查询等问题，但增加了算法的复杂性和数据库的大小。
矢量编码最重要的是信息的完整性和运算的灵活性，这是由矢量结构自身的特点所决定的，目前并无统一的最佳的矢量结构编码方法，在具体工作中应根据数据的特点和任务的要求而灵活设计。
DIME(双重独立坐标地图编码，Dual Independent Map Encoding)编码系统
DIME是美国人口调查局在人口调查的基础上发展起来的，它通过有向编码建立了多边形、边界、节点之间的拓扑关系，DIME编码成为其它拓扑编码结构的基础。
4．矢栅结构的比较及转换算法
4．1栅格结构与矢量结构的比较
栅格结构与矢量结构似乎是两种截然不同的空间数据结构，栅格结构“属性明显、位置隐含”，而矢量结构“位置明显、属性隐含”，栅格数据操作总的来说比较容易实现，尤其是作为斑块图件的表示更易于为人们接受；而矢量数据操作则比较复杂，许多分析操作（如两张地图的覆盖操作，点或线状地物的邻域搜索等）用矢量结构实现十分困难，矢量结构表达线状地物是比较直观的，而面状地物则是通过对边界的描述而表达。无论哪种结构，数据精度和数据量都是一对矛盾，要提高精度，栅格结构需要更多的栅格单元，而矢量结构则需记录更多的线段结点。一般来说，栅格结构只是矢量结构在某种程度上的一种近似，如果要使栅格结构描述的图件取得与矢量结构同样的精度，甚至仅仅在量值上接近，则数据也要比后者大得多。
栅格结构在某些操作上比矢量结构更有效更易于实现，如按空间坐标位置的搜索，对于栅格结构是极为方便的，而对矢量结构则搜索时间要长得多；在给定区域内的统计指标运算，包括计算多边形形状、面积、线密度、点密度，栅格结构可以很快算得结果，而采用矢量结构则由于所在区域边界限制条件难以提取而降低效率，对于给定范围的开窗、缩放栅格结构也比矢量结构优越；另一方面，矢量结构用于拓扑关系的搜索则更为高效，即诸如计算多边形形状搜索邻域、层次信息等；对于网络信息只有矢量结构才能完全描述；矢量结构在计算精度与数据量方面的优势也是矢量结构比栅格结构受到欢迎的原因之一，对图7-10而言，假设坐标精度要求为万分之一，即5位数字，采用矢量结构需记录40个结点，每个结点用两个双字节整数记录x、y坐标，加上对其他说明信息的描述，200个字节足够了，而若用基本栅格记录，则需10000*10000=108个字节，即使采用单字节记录栅格代码（不超过255），也需约五百万个字节，当然实际图形的矢量结构记录采点一般要比图7-10密得多，但数据量仍大大少于栅格结构的数据量。
栅格结构除了可使大量的空间分析模型得以容易实现之外，还具有以下两个特点：（1）易于与遥感相结合。遥感影像是以象元为单位的栅格结构，可以直接将原始数据或经过处理的影像数据纳入栅格结构的地理信息系统。（2）易于信息共享。目前还没有一种公认的矢量结构地图数据记录格式，而不经压缩编码的栅格格式即整数型数据库阵列则易于为大多数程序设计人员和用户理解和使用，因此以栅格数据为基础进行信息共享的数据交流较为实用。
许多实践证明，栅格结构和矢量结构在表示空间数据上可以是同样有效的，对于一个GIS软件，较为理想的方案是采用两种数据结构，即栅格结构与矢量结构并存，对于提高地理信息系统的空间分辨率、数据压缩率和增强系统分析、输入输出的灵活性十分重要。两种格式的比较见表7-2。
表7-2：矢量格式与栅格格式的比较
优点
缺点
矢量数据
1．数据结构紧凑、冗余度低
2．有利于网络和检索分析
3．图形显示质量好、精度高
1．数据结构复杂
2．多边形叠加分析比较困难
栅格数据
1．数据结构简单
2．便于空间分析和地表模拟
3．现势性较强
1．数据量大
2．投影转换比较复杂
4．2相互转换算法
矢量结构与网格结构的相互转换，是地理信息系统的基本功能之一，目前已经发展了许多高效的转换算法；但是，从栅格数据到矢量数据的转换，特别是扫描图像的自动识别，仍然是目前研究的重点。
对于点状实体，每个实体仅由一个坐标对表示，其矢量结构和栅格结构的相互转换基本上只是坐标精度变换问题，不存在太大的技术问题。线实体的矢量结构由一系列坐标对表示，在变为栅格结构时，除把序列中坐标对变为栅格行列坐标外，还需根据栅格精度要求，在坐标点之间插满一系列栅格点，这也容易由两点式直线方程得到。线实体由栅格结构变为矢量结构与将多边形边界表示为矢量结构相似，因此以下重点讨论多边形（面实体）的矢量结构与栅格结构相互转换。
4．2．1矢量格式向栅格格式的转换
矢量格式向栅格格式转换又称为多边形填充，就是在矢量表示的多边形边界内部的所有栅格点上赋以相应的多边形编码，从而形成类似图7-4的栅格数据阵列。几种主要的算法描述如下：
1）内部点扩散算法
该算法由每个多边形一个内部点（种子点）开始，向其八个方向的邻点扩散，判断各个新加入点是否在多边形边界上，如果是边界上，则该新加入点不作为种子点，否则把非边界点的邻点作为新的种子点与原有种子点一起进行新的扩散运算，并将该种子点赋以该多边形的编号。重复上述过程直到所有种子点填满该多边形并遇到边界停止为止。扩散算法程序设计比较复杂，并且在一定的栅格精度上，如果复杂图形的同一多边形的两条边界落在同一个或相邻的两个栅格内，会造成多边形不连通，这样一个种子点不能完成整个多边形的填充。
2）复数积分算法
对全部栅格阵列逐个栅格单元地判断该栅格归属的多边形编码，判别方法是由待判点对每个多边形的封闭边界计算复数积分，对某个多边形，如果积分值为2(r，则该待判点属于此多边形，赋以多边形编号，否则在此多边形外部，不属于该多边形。
3）射线算法和扫描算法
射线算法可逐点判断数据栅格点在某多边形之外或在多边形内，由待判点向图外某点引射线，判断该射线与某多边形所有边界相交的总次数，如相交偶数次，则待判点在该多边形外部，如为奇数次，则待判点在该多边形内部（图7-12）。采用射线算法，要注意的是：射线与多边形边界相交时，有一些特殊情况会影响交点的个数，必须予以排除（图7-13）。
扫描算法是射线算法的改进，将射线改为沿栅格阵列列或行方向扫描线，判断与射线算法相似。扫描算法省去了计算射线与多边形边界交点的大量运算，大大提高了效率。
图7-12：射线算法
图7-13：射线算法的特殊情况
4）边界代数算法（BAF-Boundary Algebra Filling）[任伏虎]
边界代数多边形填充算法是一种基于积分思想的矢量格式向栅格格式转换算法，它适合于记录拓扑关系的多边形矢量数据转换为栅格结构。图7-15表示转换单个多边形的情况，多边形编号为a，模仿积分求多边形区域面积的过程，初始化的栅格阵列各栅格值为零，以栅格行列为参考坐标轴，由多边形边界上某点开始顺时针搜索边界线，当边界上行时（图7-15-a），位于该边界左侧的具有相同行坐标的所有栅格被减去a；当边界下行时（图7-15-b），该边界左边（前进方向看为右侧）所有栅格点加一个值a，边界搜索完毕则完成了多边形的转换。
图7-15：单个多边形的转换
图7-16：多个多边形的转换
事实上，每幅数字地图都是由多个多边形区域组成的，如果把不属于任何多边形的区域（包含无穷远点的区域）看成编号为零的特殊的多边形区域，则图上每一条边界弧段都与两个不同编号的多边形相邻，按弧段的前进方向分别称为左、右多边形，可以证明，对于这种多个多边形的矢量向栅格转换问题，只需对所有多边形边界弧段作如下运算而不考虑排列次序：当边界弧段上行时，该弧段与左图框之间栅格增加一个值（左多边形编号减去右多边形编号）；当边界弧段下行时，该弧段与左图框之间栅格增加一个值（右多边形编号减去左多边形编号）。两个多边形转换过程如图7-16所示。
边界代数法与前述其他算法的不同之处，在于它不是逐点判断与边界的关系完成转换，而是根据边界的拓扑信息，通过简单的加减代数运算将边界位置信息动态地赋给各栅格点，实现了矢量格式到栅格格式的高速转换，而不需要考虑边界与搜索轨迹之间的关系，因此算法简单、可靠性好，各边界弧段只被搜索一次，避免了重复计算。
但是这并不意味着边界代数法可以完全替代其它算法，在某些场合下，还是要采用种子填充算法和射线算法，前者应用于在栅格图像上提取特定的区域；后者则可以进行点和多边形关系的判断。
4．2．2栅格格式向矢量格式的转换
多边形栅格格式向矢量格式转换就是提取以相同的编号的栅格集合表示的多边形区域的边界和边界的拓扑关系，并表示由多个小直线段组成的矢量格式边界线的过程。
1）步骤
栅格格式向矢量格式转换通常包括以下四个基本步骤：
（1．1）多边形边界提取：采用高通滤波将栅格图像二值化或以特殊值标识边界点；
（1．2）边界线追踪：对每个边界弧段由一个结点向另一个结点搜索，通常对每个已知边界点需沿除了进入方向的其他7个方向搜索下一个边界点，直到连成边界弧段；
（1．3）拓扑关系生成：对于矢量表示的边界弧段数据，判断其与原图上各多边形的空间关系，以形成完整的拓扑结构并建立与属性数据的联系；
（1．4）去除多余点及曲线圆滑：由于搜索是逐个栅格进行的，必须去除由此造成的多余点记录，以减少数据冗余；搜索结果，曲线由于栅格精度的限制可能不够圆滑，需采用一定的插补算法进行光滑处理，常用的算法有：线形迭代法；分段三次多项式插值法；正轴抛物线平均加权法；斜轴抛物线平均加权法；样条函数插值法。
2）多边形栅格转矢量的双边界搜索算法（DBDF-Double Boundary Direct Finding）
算法的基本思想是通过边界提取，将左右多边形信息保存在边界点上，每条边界弧段由两个并行的边界链组成，分别记录该边界弧段的左右多边形编号。边界线搜索采用2*2栅格窗口，在每个窗口内的四个栅格数据的模式，可以唯一地确定下一个窗口的搜索方向和该弧段的拓扑关系，极大地加快了搜索速度，拓扑关系也很容易建立。具体步骤如下：
（2．1）边界点和结点提取：采用2*2栅格阵列作为窗口顺序沿行、列方向对栅格图像全图扫描，如果窗口内四个栅格有且仅有两个不同的编号，则该四个栅格表示为边界点；如果窗口内四个栅格有三个以上不同编号，则标识为结点（即不同边界弧段的交汇点），保持各栅格原多边形编号信息。对于对角线上栅格两两相同的情况，由于造成了多边形的不连通，也当作结点处理。图7-17和图7-18给出了节点和边界点的各种情形。
图7-17：节点的8种情形
图7-18：边界点的6种情形
（2．2）边界线搜索与左右多边形信息记录：边界线搜索是逐个弧段进行的，对每个弧段由一组已标识的四个结点开始，选定与之相邻的任意一组四个边界点和结点都必定属于某一窗口的四个标识点之一。首先记录开始边界点的两个多边形编号，作为该弧段的左右多边形，下一点组的搜索方向则由进入当前点的搜索方向和该点组的可能走向决定，每个边界点组只能有两个走向，一个是前点组进入的方向，另一个则可确定为将要搜索后续点组的方向。例如图7-18（c）所示边界点组只可能有两个方向，即下方和右方，如果该边界点组由其下方的一点组被搜索到，则其后续点组一定在其右方；反之，如果该点在其右方的点组之后被搜索到（即该弧段的左右多边形编号分别为b和a），对其后续点组的搜索应确定为下方，其他情况依此类推。可见双边界结构可以唯一地确定搜索方向，从而大大地减少搜索时间，同时形成的矢量结构带有左右多边形编号信息，容易建立拓扑结构和与属性数据的联系，提高转换的效率。
（2．3）多余点去除：多余点的去除基于如下思想：在一个边界弧段上的连续的三个点，如果在一定程度上可以认为在一条直线上（满足直线方程），则三个点中间一点可以被认为上多余的，予以去除。多余点是由于栅格向矢量转换时逐点搜索边界造成的（当边界为直线时），多余点去除算法可大量去除多余点，减少数据冗余。
5．空间索引机制
5．1索引概念
栅矢一体化空间数据结构一个重要的研究领域是如何建立有效的空间索引结构。目前对线要素索引结构研究较多，主要有PMR四叉树、带树和桶方法等，而面要素的索引结构主要有四叉树和R树等。这些结构各有自己的应用领域和相对优势，同时也都存在着不足。
空间索引就是指依据空间对象的位置和形状或空间对象之间的某种空间关系按一定的顺序排列的一种数据结构，其中包含空间对象的概要信息，如对象的标识、外接矩形及指向空间对象实体的指针。作为一种辅助性的空间数据结构，空间索引介于空间操作算法和空间对象之间，它通过筛选作用，大量与特定空间操作无关的空间对象被排除，从而提高空间操作的速度和效率。空间索引的性能的优劣直接影响空间数据库和地理信息系统的整体性能，它是空间数据库和地理信息系统的一项关键技术。常见大空间索引一般是自顶向下、逐级划分空间的各种数据结构空间索引，比较有代表性的包括BSP树、K-D-B树、R树、R+树和CELL树等。此外，结构较为简单的格网型空间索引有着广泛的应用。
5．2索引类型
5．2．1格网型空间索引
格网型空间索引思路比较简单了，容易理解和实现。其基本思想是将研究区域用横竖线条划分大小相等和不等的格网，记录每一个格网所包含的空间实体。当用户进行空间查询时，首先计算出用户查询对象所在格网，然后再在该网格中快速查询所选空间实体，这样一来就大大地加速了空间索引的查询速度。
5．2．2 BSP树空间索引
BSP树是一种二叉树，它将空间逐级进行一分为二的划分（图7-19）。BSP树能很好地与空间数据库中空间对象的分布情况相适应，但对一般情况而言，BSP树深度较大，对各种操作均有不利影响。
图7-19：BSP树
5．2．3 KDB树空间索引
KDB树是B树向多维空间的一种发展。它对于多维空间中的点进行索引具有较好的动态特性，删除和增加空间点对象也可以很方便地实现；其缺点是不直接支持占据一定空间范围的地物要素，如二维空间中的线和面。该缺点可以通过空间映射或变换的方法部分地得到解决。空间映射或变换就是将2n维空间中的区域变换到2n维空间中的点，这样便可利用点索引结构来对区域进行索引，原始空间的区域查询便转化为高维空间的点查询。但空间映射或变换方法仍然存在着缺点：高维空间的点查询要比原始空间的点查询困难得多；经过变换，原始空间中相邻的区域有可能在点空间中距离变得相当遥远，这些都将影响空间索引的性能。
5．2．4 R树和R+树
R树根据地物的最小外包矩形建立（图7-20），可以直接对空间中占据一定范围的空间对象进行索引。R树的每一个结点N都对应着磁盘页D（N）和区域I（N），如果结点不是叶结点，则该结点的所有子结点的区域都在区域I（N）的范围之内，而且存储在磁盘页D（N）中；如果结点是叶结点，那么磁盘页D（N）中存储的将是区域I（N）范围内的一系列子区域，子区域紧紧围绕空间对象，一般为空间对象的外接矩形。
R树中每个结点所能拥有的子结点数目是有上下限的。下限保证索引对磁盘空间的有效利用，子结点的数目小于下限的结点将被删除，该结点的子结点将被分配到其它的结点中；设立上限的原因是因为每一个结点只对应一个磁盘页，如果某个结点要求的空间大于一个磁盘页，那么该结点就要被划分为两个新的结点，原来结点的所有子结点将被分配到这两个新的结点中。
由于R树兄弟结点对应的空间区域可以重叠，因此，R树可以较容易地进行插入和删除操作；但正因为区域之间有重叠，空间索引可能要对多条路径进行搜索后才能得到最后的结果，因此，其空间搜索的效率较低。正是这个原因促使了R+树（图7-21）的产生。在R+树中，兄弟结点对应的空间区域没有重叠，而没有重叠的区域划分可以使空间索引搜索的速度大大提高；但由于在插入和删除空间对象时要保证兄弟结点对应的空间区域不重叠，而使插入和删除操作的效率降低。
图7-20：R树
图7-21：R+树
5．2．5 CELL树
考虑到R树和R+在插入、删除和空间搜索效率两方面难于兼顾，CELL树应运而生。它在空间划分时不再采用矩形作为划分的基本单位，而是采用凸多边形来作为划分的基本单位，具体划分方法与BSP树有类似之处，子空间不再相互覆盖。CELL树的磁盘访问次数比R树和R+树少，由于磁盘访问次数是影响空间索引性能的关键指标，故CELL树是比较优秀的空间索引方法（图7-22）。
图7-22：CELL树
6．空间信息查询
目前大多数成熟的商品化地理信息系统软件的查询功能都可完美地实现对空间实体的简单查找，如根据鼠标所指的空间位置，系统可查找出该位置的空间实体和空间范围（由若干个空间实体组成）以及它们的属性，并显示出该空间对象的属性列表，并可以进行有关统计分析。该查询工作可分为两步：首先借助于空间索引，在空间数据库中快速检索出被选空间实体；然后，根据空间数据和属性数据的连接即可得到该空间实体的属性列表。
6．1基于属性特征查询
一般来说，基于属性信息的查询操作主要是在属性数据库中完成的。目前大多数的地理信息系统软件都将属性信息存储在关系数据库中，而发展成熟的关系数据库又为我们提供了完备的数据索引方法及信息查询手段。几乎所有的关系数据库管理系统都支持标准的结构化查询语言。利用SQL，我们可以在属性数据库中很方便地实现属性信息的复合条件查询，筛选出满足条件的空间实体的标识值，再到空间数据库中根据标识值检索到该空间实体。
6．2基于空间关系和属性特征的查询（SQL）
空间实体间有着许多空间关系（包括拓扑、顺序、度量等关系）。在实际应用过程中，用户往往希望地理信息系统提供一些更能直接计算空间实体关系的功能，如用户希望查询出满足如下条件的城市：
A在某条铁路的东部；B距离该铁路不超过30公里；C城市人口大于70万；D城市选择区域是特定的多边形。整个查询计算涉及了空间顺序关系（铁路东部）、空间距离关系（距离该铁路不超过30公里）、空间拓扑关系（被选城市在特定的选择区域之内）、属性信息查询（城市人口大于70万）。
就目前成熟的地理信息系统而言，比较系统地完成上述查询任务还较为困难。为此，众多的地理信息系统专家提出了“空间查询语言”（Spatial Query Language）以作为解决问题的方案，但仍处于理论发展和技术探索阶段。
6．3一种空间扩展SQL查询语言——GeoSQL
查询、检索是地理信息系统中使用最频繁的功能之一，GIS用户提出的大部分问题都可以表达为查询形式，即空间查询语言不仅可以使GIS用户方便地访问、查询和处理空间数据，也可以实现空间数据的安全性和完整性控制。相对于一般SQL，空间扩展SQL 主要增加了空间数据类型和空间操作算子，以满足空间特征的查询。空间特征包含空间属性和非空间属性，空间属性由特定的“Location”字段来表示。空间数据类型除具有一般的整型、实型、字符串外，还具有下列空间数据类型：点类型、弧段类型、不封闭的线类型、（Polygon）多边形类型、图像类型、复杂空间特征类型。以上类型是针对“位置”字段而言的。GeoSQL中的空间操作算子是指带有参数的函数。通常它以空间特征为参数，返回空间特征或数值。空间操作算子主要分为两类：一元空间操作算子和二元空间操作算子。通常，标准SQL的一般形式为：SELECT…FROM…WHERE，分别对应关系操作投影、笛卡尔积和选择，其中，FROM语句代表所给关系的笛卡尔积，也就是定义了一个单独的关系。WHERE语句中的选择和SELECT语句中的投影均作用于该关系上。尽管GeoSQL属于非过程化文本语言，但为使操作简单方便，它仍可以借鉴可视化查询语言的特点，即使用图符、列表框等组件来尽量减少用户的文本输入，同时也可防止输入时由于误记、语义误解等产生的语法错误。GeoSQL的实现过程如图7-23所示。
图7-23：GeoSQL的实现过程
