第六章 空间数据管理

1、.空间数据管理空间数据管理 本章首先介绍空间数据库、与一般数据库的比本章首先介绍空间数据库、与一般数据库的比较，以及空间数据库的存储方式。较，以及空间数据库的存储方式。然后介绍了然后介绍了GIS中两种重要的数据结构：栅格结中两种重要的数据结构：栅格结构和矢量结构，以及其具体的存储方式，然后构和矢量结构，以及其具体的存储方式，然后比较了两种结构的特点，并给出了其相互转换比较了两种结构的特点，并给出了其相互转换算法。算法。最后介绍了空间检索中常用的技术最后介绍了空间检索中常用的技术空间索空间索引，介绍了一些常用的空间索引方式，如引，介绍了一些常用的空间索引方式，如BSP树、树、R树、树、CELL树

2、等；以及空间数据的查询功能。树等；以及空间数据的查询功能。.1.空间数据库空间数据库1.1地理信息系统与一般管理信息系统的比较地理信息系统与一般管理信息系统的比较(一一)两者区别两者区别 1）在硬件上）在硬件上，为了处理图形和图像数据，系统，为了处理图形和图像数据，系统需要配置专门的输入和输出设备，如数字化仪、需要配置专门的输入和输出设备，如数字化仪、绘图机、图形图像的显示设备等；许多野外实地绘图机、图形图像的显示设备等；许多野外实地采集和台站的观测所得到的资源信息是模拟量形采集和台站的观测所得到的资源信息是模拟量形式，系统还需要配置模式，系统还需要配置模数转换设备，这些设数转换设备，这些设备

3、往往超过中央处理机的价格，体积也比较大。备往往超过中央处理机的价格，体积也比较大。2）在软件上）在软件上，则要求研制专门的图形和图像数，则要求研制专门的图形和图像数据的分析算法和处理软件，这些算法和软件又直据的分析算法和处理软件，这些算法和软件又直接和数据的结构及数据库的管理方法有关。接和数据的结构及数据库的管理方法有关。.1.空间数据库空间数据库1.1地理信息系统与一般管理信息系统的比较地理信息系统与一般管理信息系统的比较3）在信息处理的内容和采用目的方面）在信息处理的内容和采用目的方面，一般的，一般的管理信息系统，主要是查询检索和统计分析，处管理信息系统，主要是查询检索和统计分析，处理的结

4、果，大多是制成某种规定格式的表格数据，理的结果，大多是制成某种规定格式的表格数据，而地理信息系统，除了基本的信息检索和统计分而地理信息系统，除了基本的信息检索和统计分析外，主要用于分析研究资源的合理开发利用，析外，主要用于分析研究资源的合理开发利用，制定区域发展规划，地区的综合治理方案，对环制定区域发展规划，地区的综合治理方案，对环境进行动态的监视和预测预报，为国民经济建设境进行动态的监视和预测预报，为国民经济建设中的决策提供科学依据，为生产实践提供信息和中的决策提供科学依据，为生产实践提供信息和指导。指导。.1.空间数据库空间数据库1.1地理信息系统与一般管理信息系统的比较地理信息系统与一般

5、管理信息系统的比较(二二)两者共同处两者共同处两者都是以计算机为核心的信息处理系统，都具两者都是以计算机为核心的信息处理系统，都具有数据量大和数据之间关系复杂的特点，也都随有数据量大和数据之间关系复杂的特点，也都随着数据库技术的发展在不断的改进和完善。比较着数据库技术的发展在不断的改进和完善。比较起来，商用的管理信息系统发展快，用户数量大，起来，商用的管理信息系统发展快，用户数量大，而且已有定型的软件产品可供选用，这也促进了而且已有定型的软件产品可供选用，这也促进了软件系统的标准化。地理信息系统，由于上述一软件系统的标准化。地理信息系统，由于上述一些特点，多是根据具体的应用要求专门设计，数些特

6、点，多是根据具体的应用要求专门设计，数据格式和组织管理方法各不相同。据格式和组织管理方法各不相同。 .1.空间数据库空间数据库1.2空间数据库空间数据库(一一) 数据库概念数据库概念数据库就是为一定目的服务，以特定的数据存储的相关数据库就是为一定目的服务，以特定的数据存储的相关联的数据集合，它是数据管理的高级阶段，是从文件管联的数据集合，它是数据管理的高级阶段，是从文件管理系统发展而来的。理系统发展而来的。地理信息系统的数据库（简称空间地理信息系统的数据库（简称空间数据库或地理数据库）是某一区域内关于一定地理要素数据库或地理数据库）是某一区域内关于一定地理要素特征的数据集合。特征的数据集合。

7、数据库数据库图书馆图书馆数据数据图书图书数据模型数据模型书卡编目书卡编目数据的物理组织数据的物理组织图书存放规则、书架图书存放规则、书架数据库管理系统数据库管理系统图书管理员图书管理员外存外存书库书库用户用户读者读者数据存取数据存取图书借阅图书借阅.1.空间数据库空间数据库1.2空间数据库空间数据库(一一) 空间数据库特点空间数据库特点数据量特别大；数据量特别大；不仅有地理要素的属性数据（与一般数据库不仅有地理要素的属性数据（与一般数据库中的数据性质相似），还有大量的空间数据；中的数据性质相似），还有大量的空间数据；数据应用广泛；数据应用广泛；.1.空间数据库空间数据库1.2空间数据库空间数据

8、库(三三)数据库管理系统数据库管理系统数据库管理系统（数据库管理系统（Database Management System，DBMS）是在文件处理系统的基础上）是在文件处理系统的基础上进一步发展的系统。进一步发展的系统。DBMS在用户应用程序和在用户应用程序和数据文件之间起到了桥梁作用数据文件之间起到了桥梁作用。DBMS的最大的最大优点是提供了两者之间的数据独立性，即应用优点是提供了两者之间的数据独立性，即应用程序访问数据文件时，不必知道数据文件的物程序访问数据文件时，不必知道数据文件的物理存储结构。当数据文件的存储结构改变时，理存储结构。当数据文件的存储结构改变时，不必改变应用程序。不必改变

9、应用程序。 .1.空间数据库空间数据库1.2空间数据库空间数据库1)采用标准采用标准DBMS存储空间数据的主要问题存储空间数据的主要问题 GIS中空间数据记录是变长的，且要存储和维护空间中空间数据记录是变长的，且要存储和维护空间数据拓扑关系；数据拓扑关系；DBMS一般都难以实现对空间数据的关联、连通、包一般都难以实现对空间数据的关联、连通、包含、叠加等基本操作。含、叠加等基本操作。GIS需要一些复杂的图形功能，一般的需要一些复杂的图形功能，一般的DBMS不能支不能支持；持；地理信息是复杂的，单个地理实体的表达需要多个文地理信息是复杂的，单个地理实体的表达需要多个文件、多条记录、或许包括大地网、

10、特征坐标、拓扑关系、件、多条记录、或许包括大地网、特征坐标、拓扑关系、空间特征量测值、属性数据的关键字以及非空间专题属空间特征量测值、属性数据的关键字以及非空间专题属性等；性等； 具有高度内部联系的具有高度内部联系的GIS数据记录需要更复杂的安全数据记录需要更复杂的安全性维护系统性维护系统。.1.空间数据库空间数据库1.2空间数据库空间数据库2)GIS数据管理方法主要数据管理方法主要4种类型种类型 对不同的应用模型开发独立的数据管理服务，这是对不同的应用模型开发独立的数据管理服务，这是一种基于文件管理的处理方法。一种基于文件管理的处理方法。 在商业化的在商业化的DBMS基础上开发附加系统。开发

11、一个基础上开发附加系统。开发一个附加软件用于存储和管理空间数据和空间分析，使附加软件用于存储和管理空间数据和空间分析，使用用DBMS管理属性数据。管理属性数据。 使用现有的使用现有的DBMS，通常是以，通常是以DBMS为核心，对系统为核心，对系统的功能进行必要扩充，空间数据和属性数据在同一的功能进行必要扩充，空间数据和属性数据在同一个个DBMS管理之下。需要增加足够数量的软件和功管理之下。需要增加足够数量的软件和功能来提供空间功能和图形显示功能。能来提供空间功能和图形显示功能。 重新设计一个具有空间数据和属性数据管理和分析重新设计一个具有空间数据和属性数据管理和分析功能的数据库系统。功能的数据

12、库系统。.1.空间数据库空间数据库1.3数据与文件组织数据与文件组织 (一一)数据组织分级数据组织分级p数据项数据项数据项是可以定义数据的最小单位，也叫元素、基本项、数据项是可以定义数据的最小单位，也叫元素、基本项、字段等，数据项与现实世界实体的属性相对应，数据项字段等，数据项与现实世界实体的属性相对应，数据项有一定的取值范围，称为域，域以外的任何值对该数据有一定的取值范围，称为域，域以外的任何值对该数据项都是无意义的。项都是无意义的。p记录记录记录是由若干相关联的数据项组成，是处理和存储信息记录是由若干相关联的数据项组成，是处理和存储信息的基本单位，是关于一个实体的数据总和，构成该记录的基本

13、单位，是关于一个实体的数据总和，构成该记录的数据项表示实体的若干属性。为了唯一标识每个记录，的数据项表示实体的若干属性。为了唯一标识每个记录，就必须有记录标识符，也叫关键字。记录标识符一般由就必须有记录标识符，也叫关键字。记录标识符一般由记录中的第一个数据项担任，唯一标识记录的关键字称记录中的第一个数据项担任，唯一标识记录的关键字称主关键字，其它标识记录的关键字称为辅关键字。主关键字，其它标识记录的关键字称为辅关键字。.1.空间数据库空间数据库1.3数据与文件组织数据与文件组织p文件文件文件是一给定类型的（逻辑）记录的全部具体值的文件是一给定类型的（逻辑）记录的全部具体值的集合，文件用文件名称

14、标识，文件根据记录的组织集合，文件用文件名称标识，文件根据记录的组织方式和存取方法可以分为：顺序文件、索引文件、方式和存取方法可以分为：顺序文件、索引文件、直接文件和倒排文件等。直接文件和倒排文件等。p数据库数据库数据库是比文件更大的数据组织，数据库是具有特数据库是比文件更大的数据组织，数据库是具有特定联系的数据的集合，也可以看成是具有特定联系定联系的数据的集合，也可以看成是具有特定联系的多种类型的记录的集合。数据库的内部构造是文的多种类型的记录的集合。数据库的内部构造是文件的集合，这些文件之间存在某种联系，不能孤立件的集合，这些文件之间存在某种联系，不能孤立存在。存在。 .1.空间数据库空间

15、数据库1.3数据与文件组织数据与文件组织(二二)数据间的逻辑联系数据间的逻辑联系 数据间的逻辑联系主要是指记录与记录之间的数据间的逻辑联系主要是指记录与记录之间的联系联系。记录是表示现实世界中的实体的。实体。记录是表示现实世界中的实体的。实体之间存在着一种或多种联系，这样的联系必然之间存在着一种或多种联系，这样的联系必然要反映到记录之间的联系上来。数据之间的逻要反映到记录之间的联系上来。数据之间的逻辑联系主要有三种：辑联系主要有三种：一对一的联系；一对多的一对一的联系；一对多的联系；多对多的联系联系；多对多的联系。.1.空间数据库空间数据库1.3数据与文件组织数据与文件组织(三三)常用数据文件

16、常用数据文件文件组织主要指数据记录在外存设备上的组织，文件组织主要指数据记录在外存设备上的组织，它由操作系统它由操作系统OS进行管理，具体讲在外存设备进行管理，具体讲在外存设备上如何安排数据和组织数据，以及实施对数据上如何安排数据和组织数据，以及实施对数据的访问方式等问题。操作系统实现的文件组织的访问方式等问题。操作系统实现的文件组织方式，可以分为方式，可以分为顺序文件、索引文件、直接文顺序文件、索引文件、直接文件和倒排文件件和倒排文件。.1.空间数据库空间数据库1.3数据与文件组织数据与文件组织p顺序文件顺序文件是最简单的文件组织形式，对记录按照主关键是最简单的文件组织形式，对记录按照主关键

17、字的顺序进行组织。字的顺序进行组织。 p索引文件索引文件索引文件除了存储记录本身（主文件）以外，索引文件除了存储记录本身（主文件）以外，还建立了若干索引表，这种带有索引表的文件还建立了若干索引表，这种带有索引表的文件叫索引文件。索引表中列出记录关键字和记录叫索引文件。索引表中列出记录关键字和记录在文件中的位置（地址）。在文件中的位置（地址）。 .1.空间数据库空间数据库1.3数据与文件组织数据与文件组织p直接文件直接文件 直接文件又称随机文件，其存储是根据记录关键字直接文件又称随机文件，其存储是根据记录关键字的值，通过某种转换方法得到一个物理存储位置，的值，通过某种转换方法得到一个物理存储位置

18、，然后把记录存储在该位置上。查找时，通过同样的然后把记录存储在该位置上。查找时，通过同样的转换方法，可以直接得到所需要的记录。转换方法，可以直接得到所需要的记录。 p倒排文件倒排文件倒排文件是带有辅索引的文件，其中辅索引是按照倒排文件是带有辅索引的文件，其中辅索引是按照一些辅关键字来组织索引的。倒排文件的主要优点一些辅关键字来组织索引的。倒排文件的主要优点是在处理多索引检索时，可以在辅检索中先完成查是在处理多索引检索时，可以在辅检索中先完成查询的询的交交、并并等逻辑运算，得到结果后再对等逻辑运算，得到结果后再对记录进行存取，从而提高查找速度。记录进行存取，从而提高查找速度。 .1.空间数据库空

19、间数据库1.4矢量和栅格数据结构矢量和栅格数据结构p矢量数据模型矢量数据模型在矢量模型中，现实世界的要素位置和范围可以采在矢量模型中，现实世界的要素位置和范围可以采用点、线或面表达，与它们在地图上表示相似，每用点、线或面表达，与它们在地图上表示相似，每一个实体的位置是用它们在坐标参考系统中的空间一个实体的位置是用它们在坐标参考系统中的空间位置（坐标）定义。位置（坐标）定义。 p栅格数据模型栅格数据模型在栅格模型中，空间被规则地划分为栅格（通常为在栅格模型中，空间被规则地划分为栅格（通常为正方形）。地理实体的位置和状态是用它们占据的正方形）。地理实体的位置和状态是用它们占据的栅格的行、列来定义的

20、。每个栅格的大小代表了定栅格的行、列来定义的。每个栅格的大小代表了定义的空间分辨率。义的空间分辨率。 .1.空间数据库空间数据库1.4矢量和栅格数据结构矢量和栅格数据结构栅格结构矢量结构.1.空间数据库空间数据库1.4矢量和栅格数据结构矢量和栅格数据结构.2.栅格数据结构及其编码栅格数据结构及其编码 2.1栅格数据结构栅格数据结构(一一)定义定义栅格结构是最简单最直接的空间数据结构，是指将地栅格结构是最简单最直接的空间数据结构，是指将地球表面划分为大小均匀紧密相邻的网格阵列，每个网球表面划分为大小均匀紧密相邻的网格阵列，每个网格作为一个象元或象素由行、列定义，并包含一个代格作为一个象元或象素由

21、行、列定义，并包含一个代码表示该象素的属性类型或量值，或仅仅包括指向其码表示该象素的属性类型或量值，或仅仅包括指向其属性记录的指针。属性记录的指针。p点用一个栅格单元表示；点用一个栅格单元表示；p线状地物沿线走向的一组相邻栅格单元表示，每线状地物沿线走向的一组相邻栅格单元表示，每个栅格单元最多只有两个相邻单元在线上；个栅格单元最多只有两个相邻单元在线上；p面或区域用记有区域属性的相邻栅格单元的集合面或区域用记有区域属性的相邻栅格单元的集合表示，每个栅格单元可有多于两个的相邻单元同属表示，每个栅格单元可有多于两个的相邻单元同属一个区域。一个区域。 .2.栅格数据结构及其编码栅格数据结构及其编码

22、2.1栅格数据结构栅格数据结构 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 6 0 0 0 0 0 0 0 0 0 0 0 0 6 6 6 0 0 0 0 0 0 0 0 0 0 6 0 0 0 0 0 0 0 0 0 0 0 6 0 0 0 6 0 0 0 0 0 0 6 0 0 0 0 0 0 0 0 0 0 7 4 4 4 4 4 4 7 7 7 7 4 7

23、7 7 4 4 4 4 8 7 7 8 0 8 4 0 8 7 7 8 0 8 8 0 0 8 0 0 8 8 7 8 8 8 8 8 0 0 0 0 8 8 8 8 0 0 0 0 0 8 8 8 （a）点 （b）线 （c）面 .2.栅格数据结构及其编码栅格数据结构及其编码 2.1栅格数据结构栅格数据结构(二二)特点特点栅格结构的显著特点是：栅格结构的显著特点是：p属性明显；属性明显；p定位隐含；定位隐含；p易于存储；易于存储；p算法简单；算法简单；p地表是不连续，是量化和近似离散的数据。地表是不连续，是量化和近似离散的数据。 .2.栅格数据结构及其编码栅格数据结构及其编码 2.2决定栅格单

24、元代码的方法决定栅格单元代码的方法在决定栅格代码时尽量保持地表的真实性，保证最大的信在决定栅格代码时尽量保持地表的真实性，保证最大的信息容量。图息容量。图7-5所示的一块矩形地表区域，内部含有所示的一块矩形地表区域，内部含有A、B、C三种地物类型，三种地物类型，O点为中心点，将这个矩形区域近似地表点为中心点，将这个矩形区域近似地表示为栅格结构中的一个栅格单元时，可根据需要，采取如示为栅格结构中的一个栅格单元时，可根据需要，采取如下的方式之一来决定栅格单元的代码。下的方式之一来决定栅格单元的代码。 .2.栅格数据结构及其编码栅格数据结构及其编码 2.2决定栅格单元代码的方法决定栅格单元代码的方法

25、p中心点法中心点法用处于栅格中心处的地物类型或现象特性决定栅格代码，用处于栅格中心处的地物类型或现象特性决定栅格代码，在图在图7-5所示的矩形区域中，中心点所示的矩形区域中，中心点O落在代码为落在代码为C的地物的地物范围内，按中心点法的规则，该矩形区域相应的栅格单范围内，按中心点法的规则，该矩形区域相应的栅格单元代码为元代码为C，中心点法常用于具有连续分布特性的地理要，中心点法常用于具有连续分布特性的地理要素，如降雨量分布、人口密度图等。素，如降雨量分布、人口密度图等。p面积占优法面积占优法以占矩形区域面积最大的地物类型或现象特性决定栅格以占矩形区域面积最大的地物类型或现象特性决定栅格单元的代

26、码，在图单元的代码，在图7-5所示的例子中，显见所示的例子中，显见B类地物所占类地物所占面积最大，故相应栅格代码定为面积最大，故相应栅格代码定为B。面积占优法常用于分。面积占优法常用于分类较细，地物类别斑块较小的情况。类较细，地物类别斑块较小的情况。 .2.栅格数据结构及其编码栅格数据结构及其编码 2.2决定栅格单元代码的方法决定栅格单元代码的方法p重要性法重要性法根据栅格内不同地物的重要性，选取最重要的地物根据栅格内不同地物的重要性，选取最重要的地物类型决定相应的栅格单元代码，假设图类型决定相应的栅格单元代码，假设图7-5中中A类最类最重要的地物类型，即重要的地物类型，即A比比B和和C类更为

27、重要，则栅类更为重要，则栅格单元的代码应为格单元的代码应为A。重要性法常用于具有特殊意。重要性法常用于具有特殊意义而面积较小的地理要素，特别是点、线状地理要义而面积较小的地理要素，特别是点、线状地理要素，如城镇、交通枢纽、交通线、河流水系等，在素，如城镇、交通枢纽、交通线、河流水系等，在栅格中代码应尽量表示这些重要地物。栅格中代码应尽量表示这些重要地物。p百分比法百分比法(长度占优法长度占优法)根据矩形区域内各地理要素所占面积的百分比数确根据矩形区域内各地理要素所占面积的百分比数确定栅格单元的代码，如可记面积最大的两类定栅格单元的代码，如可记面积最大的两类BA，也可以根据也可以根据B类和类和A

28、类所占面积百分比数在代码中类所占面积百分比数在代码中加入数字加入数字 .2.栅格数据结构及其编码栅格数据结构及其编码 2.3编码方法编码方法(一一)直接栅格编码直接栅格编码这是最简单直观而又非常重要的一种栅格结构编码方法，通常称这种这是最简单直观而又非常重要的一种栅格结构编码方法，通常称这种编码的图像文件为网格文件或栅格文件，栅格结构不论采用何种压缩编码的图像文件为网格文件或栅格文件，栅格结构不论采用何种压缩编码方法，其逻辑原型都是直接编码网格文件。直接编码就是将栅格编码方法，其逻辑原型都是直接编码网格文件。直接编码就是将栅格数据看作一个数据矩阵，逐行（或逐列）逐个记录代码，可以每行都数据看作

29、一个数据矩阵，逐行（或逐列）逐个记录代码，可以每行都从左到右逐个象元记录，也可以奇数行地从左到右而偶数行地从右向从左到右逐个象元记录，也可以奇数行地从左到右而偶数行地从右向左记录，为了特定目的还可采用其他特殊的顺序。左记录，为了特定目的还可采用其他特殊的顺序。 AAAAABBBAABBAABB.2.栅格数据结构及其编码栅格数据结构及其编码 2.3编码方法编码方法.2.栅格数据结构及其编码栅格数据结构及其编码 2.3编码方法编码方法(二二)压缩编码方法压缩编码方法 目前有一系列栅格数据压缩编码方法，如目前有一系列栅格数据压缩编码方法，如链码、游程长度链码、游程长度编码、块码和四叉树编码编码、块码

30、和四叉树编码等。其目的，就是用尽可能少的等。其目的，就是用尽可能少的数据量记录尽可能多的信息，其类型又有信息无损编码和数据量记录尽可能多的信息，其类型又有信息无损编码和信息有损编码之分。信息无损编码是指编码过程中没有任信息有损编码之分。信息无损编码是指编码过程中没有任何信息损失，通过解码操作可以完全恢复原来的信息，信何信息损失，通过解码操作可以完全恢复原来的信息，信息有损编码是指为了提高编码效率，最大限度地压缩数据，息有损编码是指为了提高编码效率，最大限度地压缩数据，在压缩过程中损失一部分相对不太重要的信息，解码时这在压缩过程中损失一部分相对不太重要的信息，解码时这部分难以恢复。在地理信息系统

31、中多采用信息无损编码，部分难以恢复。在地理信息系统中多采用信息无损编码，而对原始遥感影像进行压缩编码时，有时也采取有损压缩而对原始遥感影像进行压缩编码时，有时也采取有损压缩编码方法。编码方法。 .2.栅格数据结构及其编码栅格数据结构及其编码 2.3编码方法编码方法p链码链码链码又称为弗里曼链码链码又称为弗里曼链码Freeman或边界链码，链码可以有或边界链码，链码可以有效地压缩栅格数据，而且对于估算面积、长度、转折方向效地压缩栅格数据，而且对于估算面积、长度、转折方向的凹凸度等运算十分方便，比较适合于存储图形数据。缺的凹凸度等运算十分方便，比较适合于存储图形数据。缺点是对边界进行合并和插入等修

32、改编辑工作比较困难，对点是对边界进行合并和插入等修改编辑工作比较困难，对局部的修改将改变整体结构，效率较低局部的修改将改变整体结构，效率较低 37650p412(a)(b)012345(3,0)21100066567.2.栅格数据结构及其编码栅格数据结构及其编码 2.3编码方法编码方法p游程长度编码游程长度编码地理数据往往有较强的相关性，也就是说相邻像元的值地理数据往往有较强的相关性，也就是说相邻像元的值往往是相同的。游程长度编码的基本思想是：按行或列往往是相同的。游程长度编码的基本思想是：按行或列扫描，将相邻等值的像元合并，并记录代码的重复个数。扫描，将相邻等值的像元合并，并记录代码的重复个

33、数。其方法有两种方案：其方法有两种方案：一种编码方案是，只在各行（或列）数据的代码发一种编码方案是，只在各行（或列）数据的代码发生变化时依次记录该代码以及相同的代码重复的个生变化时依次记录该代码以及相同的代码重复的个数。数。.2.栅格数据结构及其编码栅格数据结构及其编码 2.3编码方法编码方法对下图沿行方向：（对下图沿行方向：（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），（），（

34、8，1）；）；(0，3)，(8，5)；(0，4)，(8，4)；(0，5)，(8，3)。 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 6 0 0 0 0 0 0 0 0 0 0 0 0 6 6 6 0 0 0 0 0 0 0 0 0 0 6 0 0 0 0 0 0 0 0 0 0 0 6 0 0 0 6 0 0 0 0 0 0 6 0 0 0 0 0 0 0 0 0

35、0 7 4 4 4 4 4 4 7 7 7 7 4 7 7 7 4 4 4 4 8 7 7 8 0 8 4 0 8 7 7 8 0 8 8 0 0 8 0 0 8 8 7 8 8 8 8 8 0 0 0 0 8 8 8 8 0 0 0 0 0 8 8 8 .2.栅格数据结构及其编码栅格数据结构及其编码 2.3编码方法编码方法另一种游程长度编码方案就是逐个记录各行（或列）另一种游程长度编码方案就是逐个记录各行（或列）代码发生变化的位置和相应代码。代码发生变化的位置和相应代码。沿列方向：（沿列方向：（1，0），（），（2，4），（），（4，0），（），（1，4），（），（4，0）；（）；（1，4）

36、，（），（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） 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 6 0 0 0 0 0 0 0 0 0

37、 0 0 0 6 6 6 0 0 0 0 0 0 0 0 0 0 6 0 0 0 0 0 0 0 0 0 0 0 6 0 0 0 6 0 0 0 0 0 0 6 0 0 0 0 0 0 0 0 0 0 7 4 4 4 4 4 4 7 7 7 7 4 7 7 7 4 4 4 4 8 7 7 8 0 8 4 0 8 7 7 8 0 8 8 0 0 8 0 0 8 8 7 8 8 8 8 8 0 0 0 0 8 8 8 8 0 0 0 0 0 8 8 8 .2.栅格数据结构及其编码栅格数据结构及其编码 2.3编码方法编码方法游程长度编码在栅格压缩时，数据量没有明显游程长度编码在栅格压缩时，数据量没有

38、明显增加，压缩效率较高，且易于检索，叠加合并增加，压缩效率较高，且易于检索，叠加合并等操作，运算简单，适用于机器存储容量小，等操作，运算简单，适用于机器存储容量小，数据需大量压缩，而又要避免复杂的编码解码数据需大量压缩，而又要避免复杂的编码解码运算增加处理和操作时间的情况。运算增加处理和操作时间的情况。.2.栅格数据结构及其编码栅格数据结构及其编码 2.3编码方法编码方法p块状编码块状编码块码是游程长度编码扩展到块码是游程长度编码扩展到二维的情况，采用方形区域二维的情况，采用方形区域作为记录单元，每个记录单作为记录单元，每个记录单元包括相邻的若干栅格，数元包括相邻的若干栅格，数据结构由初始位置

39、据结构由初始位置(行、列号行、列号)和半径，再加上记录单元的和半径，再加上记录单元的代码组成。代码组成。(1,1,2,9),(1,3,1,9),(1,4,1,9),(1,5,2,0),(1,7,2,0),(2,3,1,9),(2,4,1,0),(3,1,1,0),(3,2,1,9),(3,3,1,9),(3,4,1,0), (3,5,2,7), (3,7,2,0), (4,1,4,0),(5,5,4,7), (8,1,1,0), (8,2,1,0), (8,3,1,0), (8,4,1,0).2.栅格数据结构及其编码栅格数据结构及其编码 2.3编码方法编码方法 0 4 4 4 4 4 4 4

40、0 0 0 0 0 0 0 0 0 0 0 0 0 8 4 4 4 8 8 8 8 8 7 7 4 4 7 7 7 7 7 7 7 7 7 7 8 8 8 8 0 8 0 0 8 7 8 8 8 8 8 8 8 8 8 8 0 4 4 7 7 7 7 7 4 4 4 4 4 7 7 7 4 4 4 4 8 8 7 7 0 0 4 8 8 8 7 7 0 0 8 8 8 8 7 8 0 0 0 8 8 8 8 8 0 0 0 0 8 8 8 8 0 0 0 0 0 8 8 8 （a）块码分割）块码分割 （b）四叉树分割）四叉树分割.2.栅格数据结构及其编码栅格数据结构及其编码 2.3编码方法编码

41、方法p四叉树四叉树基本思想：四叉树将整个图像区逐步分解为一系列被基本思想：四叉树将整个图像区逐步分解为一系列被单一类型区域内含的方形区域，最小的方形区域为一个单一类型区域内含的方形区域，最小的方形区域为一个栅格象元，分割的原则是，将图像区域划分为四个大小栅格象元，分割的原则是，将图像区域划分为四个大小相同的象限，而每个象限又可根据一定规则判断是否继相同的象限，而每个象限又可根据一定规则判断是否继续等分为次一层的四个象限，其终止判据是，不管是哪续等分为次一层的四个象限，其终止判据是，不管是哪一层上的象限，只要划分到仅代表一种地物或符合既定一层上的象限，只要划分到仅代表一种地物或符合既定要求的少数

42、几种地物时，则不再继续划分，否则一直划要求的少数几种地物时，则不再继续划分，否则一直划分到单个栅格象元为止。分到单个栅格象元为止。.2.栅格数据结构及其编码栅格数据结构及其编码 2.3编码方法编码方法定义：定义：将将2n 2n像元阵列连续地进行像元阵列连续地进行4象限等分，一象限等分，一直分到子象限中像素值单调为止，这查即形成一颗直分到子象限中像素值单调为止，这查即形成一颗四分叉的倒向树。四分叉的倒向树。根：根：整个区域；整个区域；高：高：深度、分几深度、分几级，几次分割；级，几次分割；叶：叶：不能再分割的块；不能再分割的块；树叉：树叉：还需还需分割的块；分割的块； 每个树叉均有每个树叉均有4

43、个分叉，叫四叉树。个分叉，叫四叉树。.2.栅格数据结构及其编码栅格数据结构及其编码 2.3编码方法编码方法编码方法编码方法1)常规四叉树常规四叉树记录这棵树的叶结点外，中间结点，结点之间的联系记录这棵树的叶结点外，中间结点，结点之间的联系用指针联系，每个结点需要用指针联系，每个结点需要6个变量：个变量：父结点指针、四个子结点的指针和本结点的属性值父结点指针、四个子结点的指针和本结点的属性值。指针不仅指针不仅增加了数据的存储量增加了数据的存储量，还增加了操作的还增加了操作的复杂复杂性性：如层次数（分割次数）由从父结点移到根结点的如层次数（分割次数）由从父结点移到根结点的次数来确定，结点所代表的图

44、像块的位置需要从根节次数来确定，结点所代表的图像块的位置需要从根节点开始逐步推算下来。所以，点开始逐步推算下来。所以，常规四叉树并不广泛用常规四叉树并不广泛用于存储数据于存储数据，其价值在于建立索引文件，进行数据检其价值在于建立索引文件，进行数据检索。索。.2.栅格数据结构及其编码栅格数据结构及其编码 2.3编码方法编码方法2)线性四叉树线性四叉树记录叶结点的位置，深度（几次分割）和属性。记录叶结点的位置，深度（几次分割）和属性。地址码：定位码、地址码：定位码、Morton码（加拿大学者码（加拿大学者Morton于于1966年提出）年提出） 四进制、十进制。其具有以下优点：四进制、十进制。其具

45、有以下优点：p存贮量小，只对叶结点编码，节省了大量中间结存贮量小，只对叶结点编码，节省了大量中间结点的存储，地址码隐含着结点的分割路径和分割次点的存储，地址码隐含着结点的分割路径和分割次数。数。p线性四叉树可直接寻址，通过其坐标值直接计算线性四叉树可直接寻址，通过其坐标值直接计算其其Morton码，而不用建立四叉树。码，而不用建立四叉树。p定位码容易存储和执行实现集合相加等组合操作。定位码容易存储和执行实现集合相加等组合操作。.2.栅格数据结构及其编码栅格数据结构及其编码 2.3编码方法编码方法四进制的四进制的Morton码码1、 方法方法1：四叉树从上而下（形成）四叉树从上而下（形成）（从整

46、体开始）由叶结点（从整体开始）由叶结点找找Morton码。码。 A、分割一次，增加一、分割一次，增加一位数字，大分割在前，小位数字，大分割在前，小分割在后。所以，分割在后。所以，码的位码的位数表示分割的次数数表示分割的次数。 B、每一个位均是不大于每一个位均是不大于3的四进制数，表达位置。的四进制数，表达位置。由由Morton找出四叉树叶结找出四叉树叶结点的具体位置。点的具体位置。 02AAA BAAA A AA0303B BA A.2.栅格数据结构及其编码栅格数据结构及其编码 2.3编码方法编码方法 1）计算每个栅格对应的）计算每个栅格对应的MQ MQ=2*Ib+Jb I,J化为二进制化为二

47、进制Ib,Jb 看最大的看最大的I,J,不足在前补零。不足在前补零。 其其始行列号从始行列号从0计。计。2) 按码的升序排成线性表，放按码的升序排成线性表，放在连续的内存块中。在连续的内存块中。3）依次检查每四个相邻的）依次检查每四个相邻的MQ对应的属性值，相同合并（不同对应的属性值，相同合并（不同码位去掉），不同则存盘码位去掉），不同则存盘,直到直到没有能够合并的子块为止。没有能够合并的子块为止。A000A001A010A011A002 B003B012B013A020A021B030B031A022A023B032B03300011011.2.栅格数据结构及其编码栅格数据结构及其编码 2.

48、3编码方法编码方法A000A001A010A011A002 B003B012B013A020A021B030B031A022A023B032B033000001002003010011012013020021022023030031032033AAABAABBAAAABBBB000001002003010011012013020030AAABAABBAB.2.栅格数据结构及其编码栅格数据结构及其编码 2.3编码方法编码方法十进制的十进制的MortonMorton码码-MD-MD四进制四进制MortonMorton码直观上切合四叉树分割，但许多语言码直观上切合四叉树分割，但许多语言不支持四进制变

49、量，需用十进制表示不支持四进制变量，需用十进制表示MortonMorton码码. .1 1、一种按位操作的方法：、一种按位操作的方法：如行为如行为2 2、列为、列为3 3的栅格的的栅格的MDMD步骤：步骤： (1)(1)行、列号为二进制行、列号为二进制 Ib= 1 0 Jb= 1 1Ib= 1 0 Jb= 1 1(2)I(2)I行行J J列交叉列交叉 1 1 0 1 = 131 1 0 1 = 13(3)(3)再化为十进制再化为十进制. . 实质上是按左上、右上、左下、右下的顺序，从零开始对实质上是按左上、右上、左下、右下的顺序，从零开始对每个栅格进行自然编码。每个栅格进行自然编码。 A 0A

50、 1A 4A 5A 2 B 3B 6B 7A 8A 9B 12B 13A 10A 11B 14B 15.2.栅格数据结构及其编码栅格数据结构及其编码 2.3编码方法编码方法4.把一幅把一幅2n2n的图像压缩成线的图像压缩成线性四叉树的过程性四叉树的过程 1、按、按Morton码把图象读入一码把图象读入一维数组。维数组。 2、相邻的四个象元比较，一、相邻的四个象元比较，一致的合并，只记录第一个象元的致的合并，只记录第一个象元的Morton码。循环比较所形成的大码。循环比较所形成的大块，相同的再合并，直到不能合块，相同的再合并，直到不能合并为止。并为止。 3、进一步用游程长度编码压、进一步用游程长

51、度编码压缩。压缩时只记录第一个象元的缩。压缩时只记录第一个象元的Morton码。码。A 0A 1A 4A 5A 2 B 3B 6B 7A 8A 9B 12B 13A 10A 11B 14B 15.2.栅格数据结构及其编码栅格数据结构及其编码 2.3编码方法编码方法右图的压缩处理过程为：右图的压缩处理过程为：1、按、按Morton码读入一维数组。码读入一维数组。Morton码：码：0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15象象 元元 值：值： A A A B A B B B A A A A B B B B2、四相邻象元合并，只记录第一个象元的、四相邻象元合并，只记

52、录第一个象元的Morton码。码。 0 1 2 3 4 5 6 7 8 12 A A A B A A B B A B3、由于不能进一步合并，则用游程长度编码压缩。、由于不能进一步合并，则用游程长度编码压缩。 0 3 4 6 8 12 A B A B A B B 15B 14A 11A 10B 13B 12A 9A 8B 7B 6 B 3A 2A 5A 4A 1A 0.2.栅格数据结构及其编码栅格数据结构及其编码 2.3编码方法编码方法采用四叉树编码时，为了保证四叉树分解能不断地进行下采用四叉树编码时，为了保证四叉树分解能不断地进行下去，要求图像必须为去，要求图像必须为2n2n的栅格阵列，的栅格

53、阵列，n为极限分割数，为极限分割数，n+1为四叉树的最大高度或最大层数，图为四叉树的最大高度或最大层数，图7-4（c）为）为2323的栅格，因此最多划分三次，最大层数为的栅格，因此最多划分三次，最大层数为4，对于非标准尺，对于非标准尺寸的图像需首先通过增加背景的方法将图像扩充为寸的图像需首先通过增加背景的方法将图像扩充为2n2n的图像。的图像。 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

54、0 0 0 0 0 0 6 0 0 0 0 0 0 0 0 0 0 0 0 6 6 6 0 0 0 0 0 0 0 0 0 0 6 0 0 0 0 0 0 0 0 0 0 0 6 0 0 0 6 0 0 0 0 0 0 6 0 0 0 0 0 0 0 0 0 0 7 4 4 4 4 4 4 7 7 7 7 4 7 7 7 4 4 4 4 8 7 7 8 0 8 4 0 8 7 7 8 0 8 8 0 0 8 0 0 8 8 7 8 8 8 8 8 0 0 0 0 8 8 8 8 0 0 0 0 0 8 8 8 （a）点）点 （b）线）线 （c）面）面图图7-4：点、线、区域的格网：点、线、区域

55、的格网.2.栅格数据结构及其编码栅格数据结构及其编码 2.3编码方法编码方法四叉树编码具有可变的分辨率，并且有区域性质，压缩数四叉树编码具有可变的分辨率，并且有区域性质，压缩数据灵活，许多运算可以在编码数据上直接实现，大大地提据灵活，许多运算可以在编码数据上直接实现，大大地提高了运算效率，是优秀的栅格压缩编码之一。高了运算效率，是优秀的栅格压缩编码之一。好的压缩编码方法就是要在尽可能减少运算时间的基础上好的压缩编码方法就是要在尽可能减少运算时间的基础上达到最大的数据压缩效率，并且是算法适应性强，易于实达到最大的数据压缩效率，并且是算法适应性强，易于实现。现。p链码的压缩效率较高，已经近矢量结构

56、，对边界的运算链码的压缩效率较高，已经近矢量结构，对边界的运算比较方便，但不具有区域的性质，区域运算困难；比较方便，但不具有区域的性质，区域运算困难；p游程长度编码既可以在很大程度上压缩数据，又最大限游程长度编码既可以在很大程度上压缩数据，又最大限度地保留了原始栅格结构，编码解码十分容易；度地保留了原始栅格结构，编码解码十分容易；p块码和四叉树码具有区域性质，又具有可变的分辨率，块码和四叉树码具有区域性质，又具有可变的分辨率，有较高的压缩效率，四叉树编码可以直接进行大量图形图有较高的压缩效率，四叉树编码可以直接进行大量图形图像运算，效率较高，是很有前途的方法。像运算，效率较高，是很有前途的方法

57、。.3.矢量数据结构及其编码矢量数据结构及其编码 3.1矢量数据结构矢量数据结构矢量数据结构是最常见的图形数据结构，是一种面向目标矢量数据结构是最常见的图形数据结构，是一种面向目标的数据组织方式。矢量方法强调离散现象的存在，将线离的数据组织方式。矢量方法强调离散现象的存在，将线离散为一串采样点的坐标串，面状区域由边界线确定。由于散为一串采样点的坐标串，面状区域由边界线确定。由于矢量数据结构具有结构紧凑，冗余度低，利于网络、检索矢量数据结构具有结构紧凑，冗余度低，利于网络、检索分析等优点，是分析等优点，是GIS主要的数据存储结构之一。主要的数据存储结构之一。(一一)定义定义p点实体：记录点坐标和

58、属性代码；点实体：记录点坐标和属性代码；p线实体：记录两个或一系列采样点的坐标，并加属性代线实体：记录两个或一系列采样点的坐标，并加属性代码；码；p面实体：记录边界上一系列采样点的坐标，由于多边形面实体：记录边界上一系列采样点的坐标，由于多边形封闭，边界为闭合环，加面域属性代码。封闭，边界为闭合环，加面域属性代码。.3.矢量数据结构及其编码矢量数据结构及其编码 3.1矢量数据结构矢量数据结构(二二)特点特点矢量结构的特点是：矢量结构的特点是：定位明显、属性隐含定位明显、属性隐含，其定，其定位是根据坐标直接存储的，而属性则一般存于文位是根据坐标直接存储的，而属性则一般存于文件头或数据结构中某些特

59、定的位置上，这种特点件头或数据结构中某些特定的位置上，这种特点使得其图形运算的算法总体上比栅格数据结构复使得其图形运算的算法总体上比栅格数据结构复杂的多，有些甚至难以实现，当然有些地方也有杂的多，有些甚至难以实现，当然有些地方也有所便利和独到之处，在计算长度、面积、形状和所便利和独到之处，在计算长度、面积、形状和图形编辑、几何变换操作中，矢量结构有很高的图形编辑、几何变换操作中，矢量结构有很高的效率和精度，而在叠加运算、邻域搜索等操作时效率和精度，而在叠加运算、邻域搜索等操作时则比较困难。则比较困难。.3.矢量数据结构及其编码矢量数据结构及其编码 3.2编码方法编码方法(一一) 点实体点实体对

60、于点实体和线实体的矢量编码比较直接，只要能将空间信息对于点实体和线实体的矢量编码比较直接，只要能将空间信息和属性信息记录完全就可以了。点是空间上不能再分的地理实和属性信息记录完全就可以了。点是空间上不能再分的地理实体，可以是具体的或抽象的，如地物点、文本位置点或线段网体，可以是具体的或抽象的，如地物点、文本位置点或线段网络的结点等，络的结点等，由一对由一对x、y坐标表示坐标表示。(二二)线实体线实体线实体主要用来表示线状地物（如公路、水系、山脊线等）符线实体主要用来表示线状地物（如公路、水系、山脊线等）符号线和多边形边界，有时也称为号线和多边形边界，有时也称为“弧弧”、“链链”、“串串”等，等