空间数据模型及数据结构

1、盐城师范学院盐城师范学院城市城市地理信息系统选讲教程地理信息系统选讲教程 1/107第三部分第三部分 空间数据模型与数据结构空间数据模型与数据结构 l目标要求：了解、掌握目标要求：了解、掌握GISGIS空间数据模型的空间数据模型的概念；了解、掌握常用的矢量数据结构和栅概念；了解、掌握常用的矢量数据结构和栅格数据结构。格数据结构。 空间数据模型空间数据模型 栅格数据结构栅格数据结构 矢量数据结构矢量数据结构 两种数据结构的比较与转换两种数据结构的比较与转换盐城师范学院盐城师范学院城市城市地理信息系统选讲教程地理信息系统选讲教程 2/107 1 1 空间数据模型空间数据模型l模型模型是对现实世界的

2、简化表达。是对现实世界的简化表达。l空间数据模型空间数据模型是关于现实世界中空间实体及是关于现实世界中空间实体及其相互间联系的概念，它为描述空间数据的其相互间联系的概念，它为描述空间数据的组织和设计空间数据库模式提供基本方法。组织和设计空间数据库模式提供基本方法。盐城师范学院盐城师范学院城市城市地理信息系统选讲教程地理信息系统选讲教程 3/1071.1 1.1 概述概述 lGISGIS空间数据模型由空间数据模型由概念数据模型、逻辑数概念数据模型、逻辑数据模型据模型和和物理数据模型物理数据模型三个有机联系的层次三个有机联系的层次组成。组成。概念数据模型概念数据模型是关于实体及实体间联系的抽象是关

3、于实体及实体间联系的抽象概念集概念集逻辑数据模型逻辑数据模型是表达概念数据模型中数据实体是表达概念数据模型中数据实体（或记录）及其间关系（或记录）及其间关系物理数据模型物理数据模型是描述数据在计算机中的物理组是描述数据在计算机中的物理组织、存储路径和数据库结构织、存储路径和数据库结构 盐城师范学院盐城师范学院城市城市地理信息系统选讲教程地理信息系统选讲教程 4/107 外模式 1 物理数据模型 逻辑数据模型 空间概念数据模型 外模式 2 外模式 3 现实空间世界 图3-1-1 空间数据模型的三个层次盐城师范学院盐城师范学院城市城市地理信息系统选讲教程地理信息系统选讲教程 5/107概念数据模型

4、概念数据模型l由于职业、专业等的不同，人们所关心的问题、研究对象、由于职业、专业等的不同，人们所关心的问题、研究对象、期望的结果等方面存在着差异，因而对现实世界的描述和期望的结果等方面存在着差异，因而对现实世界的描述和抽象也是不同的，形成了不同的用户视图，称之为外模式。抽象也是不同的，形成了不同的用户视图，称之为外模式。GISGIS空间数据模型的概念模型是考虑用户需求的共性，用空间数据模型的概念模型是考虑用户需求的共性，用统一的语言描述和综合、集成各用户视图。统一的语言描述和综合、集成各用户视图。l概念数据模型是关于实体及实体间联系的抽象概念集。概念数据模型是关于实体及实体间联系的抽象概念集。

5、 场模型场模型-栅格数据模型栅格数据模型 要素模型要素模型-矢量数据模型矢量数据模型 网络模型网络模型 盐城师范学院盐城师范学院城市城市地理信息系统选讲教程地理信息系统选讲教程 6/107空间逻辑数据模型空间逻辑数据模型l逻辑数据模型逻辑数据模型是根据概念数据模型确定的空间数据库信息是根据概念数据模型确定的空间数据库信息内容（空间实体及相互关系），具体地表达数据项、记录内容（空间实体及相互关系），具体地表达数据项、记录等之间的关系，可以有若干不同的实现方法。等之间的关系，可以有若干不同的实现方法。l结构化逻辑数据模型结构化逻辑数据模型 层次数据模型：层次数据模型：按树型结构组织数据记录，以反映

6、数据之间的隶按树型结构组织数据记录，以反映数据之间的隶属或层次关系。属或层次关系。 网络数据模型网络数据模型 l面向操作的逻辑数据模型面向操作的逻辑数据模型 关系数据模型关系数据模型 ：用二维表格表达数据实体之间的关系，用关系操用二维表格表达数据实体之间的关系，用关系操作提取或查询数据实体之间的关系作提取或查询数据实体之间的关系 l对象数据模型对象数据模型盐城师范学院盐城师范学院城市城市地理信息系统选讲教程地理信息系统选讲教程 7/107物理数据模型物理数据模型l逻辑数据模型逻辑数据模型并不涉及最底层的物理实现细节，但计算机并不涉及最底层的物理实现细节，但计算机处理的是二进制数据，必须将逻辑数

7、据模型转换为处理的是二进制数据，必须将逻辑数据模型转换为物理数物理数据模型据模型，即要设计，即要设计空间数据的物理组织、空间存取方法、空间数据的物理组织、空间存取方法、数据库总体存储结构数据库总体存储结构等。等。 l物理表示与组织：物理表示与组织：物理组织主要是考虑如何在外存储器上物理组织主要是考虑如何在外存储器上以最优的形式存放数据，通常要考虑操作效率、响应时间、以最优的形式存放数据，通常要考虑操作效率、响应时间、空间利用和总的开销。空间利用和总的开销。 层次逻辑数据模型的物理表示方法主要有物理邻接法、表结构法、层次逻辑数据模型的物理表示方法主要有物理邻接法、表结构法、目录法。目录法。 网络

8、数据模型的物理表示方法主要有变长指针表、位图法、目录网络数据模型的物理表示方法主要有变长指针表、位图法、目录法等。法等。 关系数据模型的物理表示是用关系表进行的。关系数据模型的物理表示是用关系表进行的。盐城师范学院盐城师范学院城市城市地理信息系统选讲教程地理信息系统选讲教程 8/107数据建模过程数据建模过程l数据建模过程分为三步：数据建模过程分为三步： 选择一种数据模型来对现实世界的数据进行组织；选择一种数据模型来对现实世界的数据进行组织； 选择一种数据结构来表达该数据模型；选择一种数据结构来表达该数据模型； 选择一种适合于记录该数据结构的文件格式。选择一种适合于记录该数据结构的文件格式。l

9、例如，表示地表高程的空间数据可以选用例如，表示地表高程的空间数据可以选用 栅格模型栅格模型进行组织，栅格模型选用游程编码这一数据结构进行表进行组织，栅格模型选用游程编码这一数据结构进行表达，处理后的数据则以文件形式进行存储。达，处理后的数据则以文件形式进行存储。 地表也可用地表也可用矢量模型矢量模型来组织，即以等高线来表示地表，数据以拓来组织，即以等高线来表示地表，数据以拓扑结构进行安排并且以扑结构进行安排并且以 DLGDLG文件格式存储。文件格式存储。 不规则三角网不规则三角网（TINTIN）模型，是另一种能很好地表达高程数据的数）模型，是另一种能很好地表达高程数据的数据模型。据模型。l因此

10、，一种空间数据建模可能有几种可选的数据结构，而因此，一种空间数据建模可能有几种可选的数据结构，而每一种数据结构又可能有多种文件格式进行存储。每一种数据结构又可能有多种文件格式进行存储。盐城师范学院盐城师范学院城市城市地理信息系统选讲教程地理信息系统选讲教程 9/107l地理信息系统中最常用的数据组织方式为矢地理信息系统中最常用的数据组织方式为矢量模型和栅格模型。在矢量模型中，用点、量模型和栅格模型。在矢量模型中，用点、线、面表达世界，在栅格模型中用空间单元线、面表达世界，在栅格模型中用空间单元（CellCell）或像元（）或像元（PixelPixel）来表达。）来表达。盐城师范学院盐城师范学院

11、城市城市地理信息系统选讲教程地理信息系统选讲教程 10/1071.2 1.2 基于场的栅格模型基于场的栅格模型l场模型用于模拟一定空间内连续变化的地场模型用于模拟一定空间内连续变化的地理现象。理现象。l例如，空气中污染物的集中程度、地表的例如，空气中污染物的集中程度、地表的温度、土壤的湿度水平以及空气与水的流温度、土壤的湿度水平以及空气与水的流动速度和方向。动速度和方向。盐城师范学院盐城师范学院城市城市地理信息系统选讲教程地理信息系统选讲教程 11/107l栅格数据模型是场模型的典型代表，它是将连续空间离散栅格数据模型是场模型的典型代表，它是将连续空间离散化，即用栅格单元划分整个连续空间；栅格

12、单元可以分为化，即用栅格单元划分整个连续空间；栅格单元可以分为规则的和不规则的；规则的和不规则的；l栅格单元的特征参数栅格单元的特征参数有尺寸、形状、方位和间距。有尺寸、形状、方位和间距。l在边数从在边数从3 3到到N N的规则栅格单元中，方格、三角形和六角形的规则栅格单元中，方格、三角形和六角形是空间数据处理中最常用的。是空间数据处理中最常用的。 盐城师范学院盐城师范学院城市城市地理信息系统选讲教程地理信息系统选讲教程 12/107栅格模型的分层表达栅格模型的分层表达盐城师范学院盐城师范学院城市城市地理信息系统选讲教程地理信息系统选讲教程 13/1071.3 1.3 基于要素的矢量模型基于要

13、素的矢量模型 l基于要素的矢量模型将现实世界抽象为各类基于要素的矢量模型将现实世界抽象为各类要素的集合，要素的空间位置用一系列特征要素的集合，要素的空间位置用一系列特征点的点的X X、Y Y（、（、Z Z）坐标来表达，要素之间的）坐标来表达，要素之间的空间关系主要通过拓扑关系来表达。空间关系主要通过拓扑关系来表达。l矢量数据模型已经历了矢量数据模型已经历了CADCAD模型、地理相关模型、地理相关数据模型（数据模型（CoverageCoverage模型）和面向对象的数模型）和面向对象的数据模型（据模型（GeodatabaseGeodatabase模型）模型）三个发展阶段。三个发展阶段。盐城师范学

14、院盐城师范学院城市城市地理信息系统选讲教程地理信息系统选讲教程 14/107矢量模型盐城师范学院盐城师范学院城市城市地理信息系统选讲教程地理信息系统选讲教程 15/1071.4 1.4 网络模型网络模型 l网络模型用于描述现实世界中的线性系统，如道路网络模型用于描述现实世界中的线性系统，如道路交通网络、给排水系统、电力网络等。交通网络、给排水系统、电力网络等。l网络模型将线性系统抽象为边线（网络模型将线性系统抽象为边线（EdgesEdges）和交汇）和交汇点（点（JunctionsJunctions）的集合；边线和边线之间通过交汇）的集合；边线和边线之间通过交汇点相连，流（点相连，流（flow

15、flow）（如汽车流、电流和水流）可）（如汽车流、电流和水流）可以从一条边线传输到另一条边线。以从一条边线传输到另一条边线。 l边线边线如街道、传输线路、管道以及河段等；如街道、传输线路、管道以及河段等；l交汇点交汇点如街道交叉点、保险丝、开关、服务中心以如街道交叉点、保险丝、开关、服务中心以及河流的汇合点等。及河流的汇合点等。盐城师范学院盐城师范学院城市城市地理信息系统选讲教程地理信息系统选讲教程 16/107lGeodatabase Geodatabase 对线性网络系统有两种描述模型：对线性网络系统有两种描述模型：几何几何网络模型网络模型（ geometric networkgeomet

16、ric network）和）和逻辑网络模型逻辑网络模型（logical networklogical network）。几何网络模型几何网络模型是组成线性网络系统的要素的集合，是由是组成线性网络系统的要素的集合，是由边线和交汇点相连组成的系统边线和交汇点相连组成的系统 。一条边线有两个交汇点，。一条边线有两个交汇点，而一个交汇点可以与任何数量的边线相连。几何网络模而一个交汇点可以与任何数量的边线相连。几何网络模型是从要素集合的视角来看网络模型。型是从要素集合的视角来看网络模型。网络要素类（网络要素类（network feature classnetwork feature class）：）：

17、简单交汇点要素（简单交汇点要素（simple junction featuresimple junction feature） 复杂交汇点要素（复杂交汇点要素（complex junction featurecomplex junction feature） 简单边线要素（简单边线要素（simple edge featuresimple edge feature） 复杂边线要素（复杂边线要素（complex edge featurecomplex edge feature）盐城师范学院盐城师范学院城市城市地理信息系统选讲教程地理信息系统选讲教程 17/107逻辑网络模型逻辑网络模型是一个由边线

18、元素和交汇点元素组成的网是一个由边线元素和交汇点元素组成的网络图表。络图表。 逻辑网络与几何网络相似，也是相连的边线和交汇点的逻辑网络与几何网络相似，也是相连的边线和交汇点的集合。主要的区别在于逻辑网络没有坐标值。它的主要集合。主要的区别在于逻辑网络没有坐标值。它的主要目标是用特定的属性表存储网络的连通性信息。既然逻目标是用特定的属性表存储网络的连通性信息。既然逻辑网络中的边线和交汇点没有几何属性，因此它们不是辑网络中的边线和交汇点没有几何属性，因此它们不是要素，而是元素（要素，而是元素（elementselements）。）。一个几何网络总是与一个逻辑网络相联系，在编辑几何一个几何网络总是与

19、一个逻辑网络相联系，在编辑几何网络要素的时候，相应的逻辑网络元素会自动更新。网络要素的时候，相应的逻辑网络元素会自动更新。逻辑网络不直接出现在逻辑网络不直接出现在GISGIS软件软件 的应用中，与你直接接的应用中，与你直接接触的是几何网络。逻辑网络是网络要素进行复杂行为的触的是几何网络。逻辑网络是网络要素进行复杂行为的基础。基础。盐城师范学院盐城师范学院城市城市地理信息系统选讲教程地理信息系统选讲教程 18/107盐城师范学院盐城师范学院城市城市地理信息系统选讲教程地理信息系统选讲教程 19/107 2 2 栅栅格格数数据据结结构构 5 5 5 5 5 5 9 9 9 9 9 9 9 9 9

20、95 5 5 5 5 5 5 9 9 9 9 9 9 9 9 95 5 5 5 5 5 5 5 9 9 9 9 9 9 9 95 5 5 5 5 5 5 5 9 9 9 9 9 9 9 95 5 5 5 5 5 5 5 9 9 9 9 9 9 9 95 5 5 5 5 5 5 5 9 9 9 9 9 9 9 9 5 5 5 5 5 5 5 5 9 9 9 9 9 9 9 95 5 5 5 5 5 5 5 9 9 9 9 9 9 9 95 5 5 5 5 5 5 5 9 9 9 9 9 9 9 96 5 5 5 5 5 5 5 9 9 9 9 9 9 9 96 5 5 5 5 5 5 5 5 9

21、 9 9 9 9 9 96 6 5 5 5 5 5 5 5 5 9 9 9 9 9 96 6 5 5 5 5 5 5 5 5 9 9 9 9 9 96 6 5 5 5 5 5 5 5 5 5 9 9 9 9 96 6 6 5 5 5 5 5 5 5 5 5 5 9 9 96 6 6 5 5 5 5 5 5 5 5 5 5 9 9 90 00 00 00 10 00 00 00 00 00 00 00 10 00 03 04 00 00 00 00 10 20 03 04 00 00 00 00 10 20 30 04 00 00 00 00 01 20 30 04 00 00 00 00 01

22、3 30 04 00 00 00 00 01 23 00 04 00 00 00 00 01 300 00 40 00 00 00 03 12 00 00 40 00 00 00 03 12 00 00 40 00 00 00 00 02 00 00 40 00 00 00 00 02 00 04 00 00 00 00 00 02 00 04 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 0断裂线 盐城师范学院盐城师范学院城市城市地理信息系统选讲教程地理信息系统选讲教程 20/1072.1 2.

23、1 简单栅格数据结构简单栅格数据结构 l栅格结构栅格结构是指将研究区域划分为大小均匀紧是指将研究区域划分为大小均匀紧密相邻的网格阵列，每个网格作为一个象元密相邻的网格阵列，每个网格作为一个象元或象素，由行、列号定义，并包含一个代码或象素，由行、列号定义，并包含一个代码, ,表示该象素的属性类型或量值。表示该象素的属性类型或量值。l栅格结构是以规则的阵列来表示空间地物或栅格结构是以规则的阵列来表示空间地物或现象分布的数据组织，组织中的每个数据表现象分布的数据组织，组织中的每个数据表示地物或现象的非几何属性特征。示地物或现象的非几何属性特征。盐城师范学院盐城师范学院城市城市地理信息系统选讲教程地理

24、信息系统选讲教程 21/107l点点用一个栅格单元表示用一个栅格单元表示l线状地物线状地物用沿线走向的一组相邻栅格单元表示用沿线走向的一组相邻栅格单元表示l面或区域面或区域用记有区域属性的相邻栅格单元的集合表示，每用记有区域属性的相邻栅格单元的集合表示，每个栅格单元可有多于两个的相邻单元同属一个区域。任何个栅格单元可有多于两个的相邻单元同属一个区域。任何以面状分布的对象以面状分布的对象( (土地利用、土壤类型、地势起伏、环境土地利用、土壤类型、地势起伏、环境污染等污染等) )，都可以用栅格数据逼近。遥感影像就属于典型的，都可以用栅格数据逼近。遥感影像就属于典型的栅格结构，每个象元的数字表示影像

25、的灰度等级。栅格结构，每个象元的数字表示影像的灰度等级。 图图3-6 3-6 点线面的栅格表达点线面的栅格表达盐城师范学院盐城师范学院城市城市地理信息系统选讲教程地理信息系统选讲教程 22/107栅格结构特点栅格结构特点l属性明显，定位隐含属性明显，定位隐含：即数据直接记录属性的指：即数据直接记录属性的指针或属性本身，而所在位置则根据行列号转换为针或属性本身，而所在位置则根据行列号转换为相应的坐标给出。相应的坐标给出。l结构容易实现，算法简单，且易于扩充、修改，结构容易实现，算法简单，且易于扩充、修改，也很直观，特别是易于同遥感影像结合处理也很直观，特别是易于同遥感影像结合处理。l误差较大：误

26、差较大：由于栅格结构对区域的量化，在计算由于栅格结构对区域的量化，在计算面积、长度、距离、形状等空间指标时，若栅格面积、长度、距离、形状等空间指标时，若栅格尺寸较大，则会造成较大的误差，同时由于在一尺寸较大，则会造成较大的误差，同时由于在一个栅格的范围内，可能存在多于一种的地物，而个栅格的范围内，可能存在多于一种的地物，而表示在相应的栅格结构中常常只能是一个代码。表示在相应的栅格结构中常常只能是一个代码。 盐城师范学院盐城师范学院城市城市地理信息系统选讲教程地理信息系统选讲教程 23/107确定栅格单元代码的方式确定栅格单元代码的方式 l当一个栅格单元中有多个地物要素时，可根当一个栅格单元中有

27、多个地物要素时，可根据需要用下列方法来确定栅格单元的代码：据需要用下列方法来确定栅格单元的代码：中心点法：中心点法： 面积占优法面积占优法重要性法重要性法盐城师范学院盐城师范学院城市城市地理信息系统选讲教程地理信息系统选讲教程 24/1072.2 2.2 栅格数据的压缩编码方式栅格数据的压缩编码方式 链式编码链式编码(Chain Codes)(Chain Codes)游程长度编码（游程长度编码（run-length coderun-length code） 块状编码块状编码(block code) (block code) 四叉树编码四叉树编码(quad-tree code) (quad-tr

28、ee code) 八叉树编码（八叉树编码（octree codeoctree code）盐城师范学院盐城师范学院城市城市地理信息系统选讲教程地理信息系统选讲教程 25/1072.2.1 2.2.1 链式编码链式编码(Chain Codes)(Chain Codes)l链式编码主要是记录线状地物和面状地物的链式编码主要是记录线状地物和面状地物的边界。它把线状地物和面状地物的边界表示边界。它把线状地物和面状地物的边界表示为：由某一起始点开始并按某些基本方向确为：由某一起始点开始并按某些基本方向确定的单位矢量链。基本方向可定义为：定的单位矢量链。基本方向可定义为：67012345盐城师范学院盐城师范

29、学院城市城市地理信息系统选讲教程地理信息系统选讲教程 26/10732233233246676021起始点起始点线状地物确定其起始点线状地物确定其起始点为像元为像元(1(1，5)5)，则其链式编，则其链式编码为：码为：32233233223323面状地物其起始点为像面状地物其起始点为像元元（5 5，8 8），），则该多边形则该多边形边界按顺时针方向的链式边界按顺时针方向的链式编码为：编码为：3244667602132446676021盐城师范学院盐城师范学院城市城市地理信息系统选讲教程地理信息系统选讲教程 27/107链式编码的优缺点链式编码的优缺点l优点优点对线状和多边形的表示具有很强的数据

30、压缩能力对线状和多边形的表示具有很强的数据压缩能力具有一定的运算功能，如面积和周长计算等，探测边界具有一定的运算功能，如面积和周长计算等，探测边界急弯和凹进部分等都比较容易急弯和凹进部分等都比较容易比较适于存储图形数据。比较适于存储图形数据。l缺点缺点对叠置运算如组合、相交等则很难实施对叠置运算如组合、相交等则很难实施对局部修改将改变整体结构，效率较低，而且由于链码对局部修改将改变整体结构，效率较低，而且由于链码以每个区域为单位存储边界，相邻区域的边界则被重复以每个区域为单位存储边界，相邻区域的边界则被重复存储而产生冗余。存储而产生冗余。 盐城师范学院盐城师范学院城市城市地理信息系统选讲教程地

31、理信息系统选讲教程 28/1072.2.2 2.2.2 游程长度编码（游程长度编码（run-length coderun-length code） l对于一幅栅格图像，常常有行对于一幅栅格图像，常常有行( (或列或列) )方向上方向上相邻的若干点具有相同的属性代码，因而可相邻的若干点具有相同的属性代码，因而可采取某种方法压缩那些重复的记录内容。采取某种方法压缩那些重复的记录内容。l只在各行只在各行( (或列或列) )数据的代码发生变化时依次数据的代码发生变化时依次记录该代码以及相同代码重复的个数，从而记录该代码以及相同代码重复的个数，从而实现数据的压缩。实现数据的压缩。 盐城师范学院盐城师范学

32、院城市城市地理信息系统选讲教程地理信息系统选讲教程 29/107l其游程长度编码为：其游程长度编码为：l(9,4)(9,4)，(0,4)(0,4)l(9,3)(9,3)，(0,5)(0,5)l(0,1)(0,1)，(9,2)(9,2)，(0,1)(0,1)，(7,2)(7,2)，(0,2)(0,2)l(0,4)(0,4)，(7,2)(7,2)，(0,2)(0,2)l(0,4)(0,4)，(7,4)(7,4)l(0,4)(0,4)，(7,4)(7,4)l(0,4)(0,4)，(7,4)(7,4)l(0,4)(0,4)，(7,4)(7,4)99990000990900009009770000007

33、7000000777700007777000077770000777 79 9990 000 00099999007070000007 77 7770 0000 007 7777 7770 000770070700000盐城师范学院盐城师范学院城市城市地理信息系统选讲教程地理信息系统选讲教程 30/107游程长度编码的特点游程长度编码的特点l压缩比的大小是与图的复杂程度成反比的，在变压缩比的大小是与图的复杂程度成反比的，在变化多的部分，游程数就多，变化少的部分游程数化多的部分，游程数就多，变化少的部分游程数就少，图件越简单，压缩效率就越高。就少，图件越简单，压缩效率就越高。l游程长度编码在栅格

34、加密时，数据量没有明显增游程长度编码在栅格加密时，数据量没有明显增加，压缩效率较高，且易于检索，叠加合并等操加，压缩效率较高，且易于检索，叠加合并等操作，运算简单，适用于机器存贮容量小，数据需作，运算简单，适用于机器存贮容量小，数据需大量压缩，而又要避免复杂的编码解码运算增加大量压缩，而又要避免复杂的编码解码运算增加处理和操作时间的情况。处理和操作时间的情况。 盐城师范学院盐城师范学院城市城市地理信息系统选讲教程地理信息系统选讲教程 31/1072.2.3 2.2.3 块状编码块状编码(block code) (block code) l采用方形区域作为记录单元，每个记录单元采用方形区域作为记

35、录单元，每个记录单元包括相邻的若干栅格，数据结构由初始位置包括相邻的若干栅格，数据结构由初始位置( (行、列号行、列号) )和半径，再加上记录单元的代码和半径，再加上记录单元的代码组成。组成。盐城师范学院盐城师范学院城市城市地理信息系统选讲教程地理信息系统选讲教程 32/107l用用1212个单位正方形，个单位正方形，5 5个个4 4单位的正方形和单位的正方形和2 2 个个16 16 单位的正方形就能完整单位的正方形就能完整表示，编码规则（左上表示，编码规则（左上角栅格单元行列号、边角栅格单元行列号、边长、属性代码）具体编长、属性代码）具体编码如下：码如下：l(1,1,2,9)(1,1,2,9

36、)，(1,3,1,9)(1,3,1,9)，(1,4,1,9)(1,4,1,9)，(1,5,2,0)(1,5,2,0)，(1,7,2,0)(1,7,2,0)，(2,3,1,9)(2,3,1,9)，(2,4,1,0)(2,4,1,0)，(3,1,1,0)(3,1,1,0)，(3,2,1,9)(3,2,1,9)，(3,3,1,9)(3,3,1,9)，(3,4,1,0)(3,4,1,0)， (3,5,2,7)(3,5,2,7)， (3,7,2,0)(3,7,2,0)， (4,1,1,0)(4,1,1,0)，(4,2,1,0)(4,2,1,0)， (4,3,1,0)(4,3,1,0)， (4,4,1,0

37、)(4,4,1,0)， (5,1,4,0)(5,1,4,0)，(5,5,4,7)(5,5,4,7)999900009909000090097700000077000000777700007777000077770000777 79 9990 000 00099999007070000007 77 7770 0000 007 7777 7770 000770070700000盐城师范学院盐城师范学院城市城市地理信息系统选讲教程地理信息系统选讲教程 33/107块状编码的特点块状编码的特点l一个多边形所包含的正方形越大，多边形的一个多边形所包含的正方形越大，多边形的边界越简单，块状编码的效率就越好

38、。块状边界越简单，块状编码的效率就越好。块状编码对大而简单的多边形更为有效，而对那编码对大而简单的多边形更为有效，而对那些碎部较多的复杂多边形效果并不好。些碎部较多的复杂多边形效果并不好。l块状编码在合并、插入、检查延伸性、计算块状编码在合并、插入、检查延伸性、计算面积等操作时有明显的优越性。然而对某些面积等操作时有明显的优越性。然而对某些运算不适应，必须在转换成简单数据形式才运算不适应，必须在转换成简单数据形式才能顺利进行。能顺利进行。 盐城师范学院盐城师范学院城市城市地理信息系统选讲教程地理信息系统选讲教程 34/1072.2.4 2.2.4 四叉树编码四叉树编码(quad-tree co

39、de) (quad-tree code) l四叉树结构的基本思想是四叉树结构的基本思想是将一幅栅格地图或将一幅栅格地图或图像等分为四部分，逐块检查其格网属性值图像等分为四部分，逐块检查其格网属性值( (或灰度或灰度) )，如果某个子区的所有格网值都具，如果某个子区的所有格网值都具有相同的值，则这个子区就不再继续分割，有相同的值，则这个子区就不再继续分割，否则还要把这个子区再分割成四个子区。这否则还要把这个子区再分割成四个子区。这样依次地分割，直到每个子块都只含有相同样依次地分割，直到每个子块都只含有相同的属性值或灰度为止。的属性值或灰度为止。 盐城师范学院盐城师范学院城市城市地理信息系统选讲教

40、程地理信息系统选讲教程 35/107四叉树结构的基本思想四叉树结构的基本思想9999000099090000900977000000770000007777000077770000777700007777999900000009999900707000000777777000000077777777000077007070000007007099 9 9 00 9 0 0 9000NWNESWSE盐城师范学院盐城师范学院城市城市地理信息系统选讲教程地理信息系统选讲教程 36/107四叉树的生成算法四叉树的生成算法l从上而下的分割算法：从上而下的分割算法：需要大量的运算，因为大量数据需需要大量的

41、运算，因为大量数据需要重复检查才能确定划分。当矩阵比较大，且区域内容要要重复检查才能确定划分。当矩阵比较大，且区域内容要素又比较复杂时，建立这种四叉树的速度比较慢。素又比较复杂时，建立这种四叉树的速度比较慢。l从下而上的合并算法：从下而上的合并算法：如果每相邻四个网格值相同则进行如果每相邻四个网格值相同则进行合并，逐次往上递归合并，直到符合四叉树的原则为止。合并，逐次往上递归合并，直到符合四叉树的原则为止。这种方法重复计算较少，运算速度较快。这种方法重复计算较少，运算速度较快。l为了保证四叉树能不断的分解下去，要求图像必须为为了保证四叉树能不断的分解下去，要求图像必须为2 2n n* *2 2

42、n n的栅格阵列，的栅格阵列，n n为极限分割次数，为极限分割次数，n+1n+1是四叉树的最大高度是四叉树的最大高度或最大层数。或最大层数。盐城师范学院盐城师范学院城市城市地理信息系统选讲教程地理信息系统选讲教程 37/107四叉树编码的特点四叉树编码的特点容易而有效地计算多边形的数量特征；容易而有效地计算多边形的数量特征；阵列各部分的分辨率是可变的，边界复杂部阵列各部分的分辨率是可变的，边界复杂部分四叉树较高即分级多，分辨率也高，而不需分四叉树较高即分级多，分辨率也高，而不需表示许多细节的部分则分级少，分辨率低，因表示许多细节的部分则分级少，分辨率低，因而既可精确表示图形结构又可减少存贮量；

43、而既可精确表示图形结构又可减少存贮量；栅格到四叉树及四叉树到简单栅格结构的转栅格到四叉树及四叉树到简单栅格结构的转换比其它压缩方法容易；换比其它压缩方法容易；多边形中嵌套异类小多边形的表示较方便。多边形中嵌套异类小多边形的表示较方便。盐城师范学院盐城师范学院城市城市地理信息系统选讲教程地理信息系统选讲教程 38/107四叉树结构分类四叉树结构分类l1. 1.常规四叉树常规四叉树l基于自然序数基于自然序数1 1，2 2，。，。99990000990900009009770000007700000077770000777700007777000077779 9990 000 00099999007

44、070000007 77 7770 0000 007 7777 7770 000770070700000盐城师范学院盐城师范学院城市城市地理信息系统选讲教程地理信息系统选讲教程 39/107常规四叉树地址常规四叉树地址999900009909000090097700000077000000777700007777000077770000777 79 9990 000 00099999007070000007 77 7770 0000 007 7777 7770 000770070700000盐城师范学院盐城师范学院城市城市地理信息系统选讲教程地理信息系统选讲教程 40/107常规四叉树特点：常

45、规四叉树特点：常规四叉树除了记录叶结点之外，还要记录中常规四叉树除了记录叶结点之外，还要记录中间结点。间结点。结点之间借助指针联系，每个结点需要用六个结点之间借助指针联系，每个结点需要用六个量表达：四个叶结点指针，一个父结点指针和量表达：四个叶结点指针，一个父结点指针和一个结点的属性或灰度值。一个结点的属性或灰度值。这些指针不仅增加了数据贮存量，而且增加了这些指针不仅增加了数据贮存量，而且增加了操作的复杂性。常规四叉树主要在数据索引和操作的复杂性。常规四叉树主要在数据索引和图幅索引等方面应用。图幅索引等方面应用。盐城师范学院盐城师范学院城市城市地理信息系统选讲教程地理信息系统选讲教程 41/1

46、07l2. 2.线性四叉树线性四叉树线性四叉树则只存贮最后叶结点的信息。包括线性四叉树则只存贮最后叶结点的信息。包括叶结点的位置、深度和本结点的属性或灰度值。叶结点的位置、深度和本结点的属性或灰度值。线性四叉树叶结点的编号需要遵循一定的规则，线性四叉树叶结点的编号需要遵循一定的规则，这种编号称为地址码，它隐含了叶结点的位置这种编号称为地址码，它隐含了叶结点的位置和深度信息。最常用的地址码是和深度信息。最常用的地址码是四进制或十进四进制或十进制制的的MortonMorton码。码。盐城师范学院盐城师范学院城市城市地理信息系统选讲教程地理信息系统选讲教程 42/107A.A.基于四进制的线性四叉树

47、编码基于四进制的线性四叉树编码l基本思路：以基本思路：以0 0，1 1，2 2，3 3代表四等分子区的代表四等分子区的左上，右上，左下，右下区，逐级分割时，左上，右上，左下，右下区，逐级分割时，地址编码随之延长。地址编码随之延长。盐城师范学院盐城师范学院城市城市地理信息系统选讲教程地理信息系统选讲教程 43/107基于四进制编码基于四进制编码999900009909000090097700000077000000777700007777000077770000777 79 9990 000 00099999007070000007 77 7770 0000 007 7777 7770 0007

48、70070700000盐城师范学院盐城师范学院城市城市地理信息系统选讲教程地理信息系统选讲教程 44/107B.B.基于按位操作的运算计算基于按位操作的运算计算MortonMorton码码l设十进制表示的行、列号在计算机内部的二进制设十进制表示的行、列号在计算机内部的二进制数字分别为：数字分别为：l十进制的十进制的MortonMorton码实际上是码实际上是II II、JJJJ中的二进制数字中的二进制数字交叉结合的结果，即交叉结合的结果，即2123121231).().(jjjjjJJiiiiiIInnnn211223311D).(MjijijijijinnnnEg:(3,5)(011,101

49、)(011011)(27) (7,3)(111,011)(101111)(47)盐城师范学院盐城师范学院城市城市地理信息系统选讲教程地理信息系统选讲教程 45/107基于十进制的基于十进制的MortonMorton码及四叉树的建立码及四叉树的建立 0 01 14 45 51616 1717 2020 21212 23 36 67 71818 1919 2222 23238 89 91212 1313 2424 2525 2828 29291010 1111 1414 1515 2626 2727 3030 31313232 3333 3636 3737 4848 4949 5252 53533

50、434 3535 3838 3939 5050 5151 5454 55554040 4141 4444 4545 5656 5757 6060 61614242 4343 4646 4747 5858 5959 6262 6363（a a）四叉树分割示意图）四叉树分割示意图(b) (b) 基于十进制的线性四叉树基于十进制的线性四叉树MortonMorton码码盐城师范学院盐城师范学院城市城市地理信息系统选讲教程地理信息系统选讲教程 46/107MortonMorton码码属性属性值值0 09 94 49 95 59 96 69 97 70 08 80 09 99 910100 011110

51、0MortonMorton码码 属性值属性值12129 913130 014140 015150 016160 020200 024247 728280 032320 048487 70 01 14 45 516161717202021212 23 36 67 718181919222223238 89 912121313242425252828292910101111141415152626272730303131323233333636373748484949525253533434353538383939505051515454555540404141444445455656575760

52、60616142424343464647475858595962626363线性四叉树存储结构线性四叉树存储结构盐城师范学院盐城师范学院城市城市地理信息系统选讲教程地理信息系统选讲教程 47/107二维行程编码二维行程编码l在生成的线性四叉树表中，仍存在前后叶在生成的线性四叉树表中，仍存在前后叶结点的值相同的情况，因而可以采取进一结点的值相同的情况，因而可以采取进一步的压缩表达，即将格网值相同的前后结步的压缩表达，即将格网值相同的前后结点合并成一个值，形成二维行程编码点合并成一个值，形成二维行程编码（Two Dimensional Run EncodingTwo Dimensional Run

53、 Encoding，简称，简称 2DRE2DRE）表。在这种二维行程编码中，前后）表。在这种二维行程编码中，前后两个地址码之差表达了该行程段的格网数，两个地址码之差表达了该行程段的格网数，它可以表示该子块的大小。它可以表示该子块的大小。盐城师范学院盐城师范学院城市城市地理信息系统选讲教程地理信息系统选讲教程 48/107MortonMorton码码 属性值属性值0 09 97 70 09 99 910100 012129 913130 024247 728280 048487 7MortonMorton码码 属性值属性值0 09 94 49 95 59 96 69 97 70 08 80 09

54、 99 910100 011110 0MortonMorton码码属性值属性值12129 913130 014140 015150 016160 020200 024247 728280 032320 048487 7线性四叉树存储结构线性四叉树存储结构二维行程编码存储结构二维行程编码存储结构盐城师范学院盐城师范学院城市城市地理信息系统选讲教程地理信息系统选讲教程 49/107Eg:Eg:3 35 57 73 32 22 26 66 62 22 26 67 73 34 44 44 44 44 44 44 43 34 44 44 47 77 78 88 84 44 44 44 48 88 88

55、88 84 44 44 44 48 88 84 44 44 44 44 44 48 88 84 44 43 33 34 44 44 44 44 44 43 33 34 44 44 44 44 44 43 33 33 34 44 44 44 44 43 33 33 34 44 44 44 44 4盐城师范学院盐城师范学院城市城市地理信息系统选讲教程地理信息系统选讲教程 50/1073 35 57 73 30 03 31 15 52 27 73 33 30 03 31 15 52 27 73 33 3图象线性四叉树存槠表二维行程编码存槠表盐城师范学院盐城师范学院城市城市地理信息系统选讲教程地理信息

56、系统选讲教程 51/1072 22 26 66 62 22 26 67 73 34 44 44 44 44 44 44 40 02 24 46 65 56 66 66 67 77 78 83 39 94 41010 4 41111 4 41212 4 40 02 24 46 67 77 78 83 39 94 4盐城师范学院盐城师范学院城市城市地理信息系统选讲教程地理信息系统选讲教程 52/1073 34 44 44 47 77 78 88 84 44 44 44 48 88 88 88 84 44 44 44 48 88 84 44 44 44 44 44 48 88 84 44 43 33

57、 34 44 44 44 44 44 43 33 34 44 44 44 44 44 43 33 33 34 44 44 44 44 43 33 33 34 44 44 44 44 40314243444841241671771881982082482843233644034434544634744840314167188284323364403454463474盐城师范学院盐城师范学院城市城市地理信息系统选讲教程地理信息系统选讲教程 53/1072.2.5 2.2.5 八叉树结构八叉树结构l八叉树结构是四叉树结构在三维空间的扩展。八叉树结构是四叉树结构在三维空间的扩展。l八叉树结构就是将空间

58、区域不断地分解为八个同样大小八叉树结构就是将空间区域不断地分解为八个同样大小的子区域的子区域( (即将一个六面的立方体再分解为八个相同大小即将一个六面的立方体再分解为八个相同大小的小立方体的小立方体) )，分解的次数越多，子区域就越小，一直到，分解的次数越多，子区域就越小，一直到同同区域的属性单一为止。按从下而上合并的方式来说，区域的属性单一为止。按从下而上合并的方式来说，就是将研究区空间先按就是将研究区空间先按定的分辨率将三维空间划分为定的分辨率将三维空间划分为三维栅格网，然后按规定的顺序每次比较三维栅格网，然后按规定的顺序每次比较3 3个相邻的栅格个相邻的栅格单元，如果其属性值相同则合并，

59、否则就记盘。依次递单元，如果其属性值相同则合并，否则就记盘。依次递归运算，直到每个子区域均为单值为止。归运算，直到每个子区域均为单值为止。 盐城师范学院盐城师范学院城市城市地理信息系统选讲教程地理信息系统选讲教程 54/107盐城师范学院盐城师范学院城市城市地理信息系统选讲教程地理信息系统选讲教程 55/107 3 3 矢量数据结构矢量数据结构 l矢量数据结构矢量数据结构实体式实体式索引式索引式双重独立式双重独立式链状双重独立式链状双重独立式盐城师范学院盐城师范学院城市城市地理信息系统选讲教程地理信息系统选讲教程 56/1073.1 3.1 实体式矢量数据结构实体式矢量数据结构l实体式数据结构

60、是指实体式数据结构是指构成多边形边界的各构成多边形边界的各个线段，以多边形为单元进行组织个线段，以多边形为单元进行组织。l按照这种数据结构，边界坐标数据和多边按照这种数据结构，边界坐标数据和多边形单元实体一一对应，各个多边形边界都形单元实体一一对应，各个多边形边界都单独编码和数字化。单独编码和数字化。l俗称面条型数据模型。俗称面条型数据模型。 盐城师范学院盐城师范学院城市城市地理信息系统选讲教程地理信息系统选讲教程 57/10712345678910111213141516171819202122232425262728293031多边形多边形数据项数据项A(x1,y1),(x2,y2),(x