空间数据结构及编码.ppt

1、l 数据结构数据结构是数据的组织形式，即数据以什么形式在计算机中存储和处理。如顺序存储结构和链式存储结构。l 空间数据结构空间数据结构是表达空间数据的数据结构，即空间数据组织形式，包括矢量数据结构和栅格数据结构。1 地理空间及其表达地理空间及其表达2 地理空间数据及其特征地理空间数据及其特征3 空间数据结构类型与编码空间数据结构类型与编码4 空间数据结构的建立空间数据结构的建立1.1 地理空间的概念地理空间的概念 地理空间地理空间指上至大气电离层，下至地壳与地幔交界的莫霍面之间的空间区域。地壳(33km)、生物圈、水圈和大气圈(100km)1.2 地理空间定位框架地理空间定位框架地理空间中准确

2、测定位置地理空间中准确测定位置地理空间定位框架地理空间定位框架大地测量控制系统大地测量控制系统平面控制网平面控制网高程控制网高程控制网平面位置平面位置高程高程大地坐标直角坐标56年黄海高程系1985国家高程基准P(B,L,H)P( x, y, z)北京54国家80WGS841.3 空间实体表达空间实体表达 (1) 空间实体的概念空间实体的概念 地理空间特征实体地理空间特征实体指具有形状、属性和时指具有形状、属性和时序特征的空间对象或地理实体，包括：序特征的空间对象或地理实体，包括： 点、线、面、曲面和体点、线、面、曲面和体 地理空间特征实体构成地球圈层间复杂的地理空间特征实体构成地球圈层间复杂

3、的地理综合体，是地理综合体，是GIS表示和建立空间数据库的表示和建立空间数据库的主要对象。主要对象。（2） 空间实体的数据表达方法空间实体的数据表达方法 点点是地理空间实体的基本元素。如何表是地理空间实体的基本元素。如何表达空间的一个点是关键。达空间的一个点是关键。点的表达方法点的表达方法：l矢量表示法矢量表示法：一个没有大小的点（坐标）：一个没有大小的点（坐标）l栅格表示法栅格表示法：一个有固定大小的点：一个有固定大小的点 (面元面元) 相应地，有对现实世界相应地，有对现实世界空间实体空间实体的两种的两种数据表达方法：数据表达方法：l矢量数据模型矢量数据模型l栅格数据模型栅格数据模型矢量数据

4、模型矢量数据模型栅格数据模型栅格数据模型空间实体的两种数据表达方法空间实体的两种数据表达方法21 GIS空间数据分类空间数据分类l空间数据是GIS的核心核心，是GIS的操作对象操作对象l设计和使用GIS的第一步工作： 获取所需的空间数据获取所需的空间数据，并创建空间数据库获取空间数据获取空间数据空间数据库空间数据库空间分析空间分析l空间数据分类空间数据分类：可按多种方式进行分类数据来源数据来源 数据结构数据结构 数据特征数据特征 几何特征几何特征数据发布形式数据发布形式地图数据地图数据影像数据影像数据文本数据文本数据矢量数据矢量数据栅格数据栅格数据空间数据空间数据非空间属非空间属性数据性数据点

5、点线线面、曲面面、曲面体体数字线画图数字线画图数字栅格图数字栅格图数字高程模型数字高程模型数字正射影像数字正射影像图图空间数据的分类空间数据的分类(一一)按数据来源分类按数据来源分类（1）地图数据地图数据：普通地图和专题地图（2）影像数据影像数据：卫星遥感和航空遥感（3）文本数据文本数据：实测数据、调查报告、文献资料。(二二)按数据结构分类按数据结构分类（1）矢量数据矢量数据：用欧氏空间中的点、线、面等几何元素来表达空间实体的几何特征数据。（2）栅格数据栅格数据：将空间分割成规则网格，在各网格上用相应的属性值表示空间实体。(三三)按数据特征分类按数据特征分类（1）空间定位数据空间定位数据：空间

6、实体在地球上的位置数据。（2）非空间属性数据非空间属性数据：空间实体自身的名称、种类、数量、质量等特征数据。(四）按数据几何特征分类四）按数据几何特征分类（1）点点：对0维空间实体的抽象数据，如三角点等。（2）线线：对1维线性空间实体的抽象数据，如河流。（3）面面：对2维平面空间实体的抽象数据， 如湖泊。（4）曲面曲面：对在面上连续分布的空间实体的抽象数据， 2.5维，如地形、气温。（5）体体：对3维空间实体的抽象数据，如地质构造。(五五)按数据发布形式分类按数据发布形式分类（1）数字线画图数据数字线画图数据：现有地形图要素的矢量数据。（2）数字栅格图数据数字栅格图数据：现有纸质地图在扫描数字

7、化后，经几何纠正等处理，得到的数字栅格图。（3）数字高程模型（数字高程模型（DEM）数据）数据：以数字形式表达地形起伏的数据。（4）数字正射影像数据数字正射影像数据：对遥感数据数字影像，经逐像元投影差改正、镶嵌，按国家基本比例尺地图图幅范围剪裁生成的数字正射投影影像数据。l补充补充：根据表示对象的不同分7种类型（Jack Dangermond, 1984）点状符号线状符号面状符号地点名称线状要素名称区域名称高程点等值线概略等值区气象站航线样方分布区点状要素线状要素面状要素区域中心境界线行政单元道路交点街道街区606159ABCD208区209区2082098940573雷德兰科顿方塔内237商

8、业区20520620620620720720720620520520620722 空间数据的基本特征空间数据的基本特征（一）基本特征（一）基本特征 （1）空间特征）空间特征 指地理现象和过程的位置、形状和大小，及空间关系，包括：l定位特征定位特征 x，y坐标数据描述；l拓扑特征拓扑特征与相邻地理现象和过程的空间关系，方位关系、拓扑关系、相似关系。 （2）属性特征）属性特征 地理现象和过程所具有的专属性质专属性质，名称、数量、质量、性质等。 （3）时间特征）时间特征 一定区域内的地理现象和过程随时间的变化变化情况情况。 （二）基本信息（二）基本信息 空间数据的基本特征数据传递基本信息基本信息。（

9、1）定位信息）定位信息 地理现象和过程的在地球表面的分布状态分布状态。直线、S形曲线、环线。（2）属性信息）属性信息 地理现象和过程具有的非空间属性非空间属性，等级：主干道、次干道、支路。（3）拓扑信息）拓扑信息 地理现象和过程间的空间关系。相邻、关联基本信息：基本信息：（1）定位信息）定位信息直线、曲线和环直线、曲线和环（2）属性信息）属性信息主、次干道、主、次干道、支路支路（3）拓扑信息）拓扑信息连接、邻接、连接、邻接、关联关联23 空间数据的拓扑关系空间数据的拓扑关系231 概念概念l凡具有网状结构网状结构特征的地理要素，如自然和行政分区、各种资源的空间分布、交通网等，都存在节点、弧段和

10、多边形之间的拓扑关系。l拓扑关系拓扑关系是明确定义空间结构关系的一种数学方法。l它描述空间点、线、面之间的空间关系，用于空间数据的编辑、组织，在GIS空间空间分析中分析中有重要意义。232 拓扑关系的类型拓扑关系的类型 3种：l 拓扑邻接拓扑邻接l 拓扑关联拓扑关联l 拓扑包含拓扑包含 （1）拓扑邻接）拓扑邻接 指存在于空间图形的相同类型元素相同类型元素之间的拓扑关系。 l节点邻接节点邻接关系（连通性），N1/ N2l弧段邻接弧段邻接关系，C1 /C3l多边形邻接多边形邻接关系关系，P1 / P2 节点邻接节点邻接方法方法：查找有公共节点弧段，得出节点邻接矩阵节点的邻接矩阵节点的邻接矩阵节点节

11、点 N1 N2 N3 N4 N5 N1 - 1 1 1 0 N2 1 - 1 1 0 N3 1 1 - 1 0 N4 1 1 1 - 0 N5 0 0 0 0 - 弧段邻接弧段邻接方法方法：查找有公共节点弧段，推出弧段邻接矩阵。弧段弧段 C1 C2 C3 C4 C5 C6 C7 C1 - 1 1 0 1 1 0 C2 1 - 1 1 1 0 0 C3 1 1 - 1 0 1 0 C4 0 1 1 - 1 1 0 C5 1 1 0 1 - 1 0 C6 1 0 1 1 1 - 0 C7 0 0 0 0 0 0 -弧段的邻接矩阵弧段的邻接矩阵多边形邻接多边形邻接：用弧段左右多边形左右多边形表示。l

12、方法方法：查找有公共边的左右相邻多边形，推出多边形邻接矩阵和邻接表。 P1 P2 P3 P4P1 - 1 1 0P2 1 - 1 0P3 1 1 - 1P4 0 0 1 -（a）多边形邻接矩阵）多边形邻接矩阵 邻接多边形邻接多边形P1 P2 P3 P2 P1 P3P3 P1 P2 P4P4 P3 （b）多边形邻接表）多边形邻接表整整理理（2）拓扑关联）拓扑关联 指存在于空间图形中不同类型元素不同类型元素（节点、弧段、多边形）之间的拓扑关系。l节点节点弧段的关联关系弧段的关联关系, C1/N2,N1节点和弧段之间的关联节点和弧段之间的关联弧段弧段 起点起点 终点终点 C1 N2 N1 C2 N3

13、 N2 C3 N1 N3 C4 N4 N3 C5 N2 N4 C6 N4 N1 C7 N5 N5 多边形多边形 弧段弧段 P1 C1 C5 C6 P2 C3 C4 C6 P3 C2 C4 C5 C7 P4 C7 多边形和弧段之间的关多边形和弧段之间的关联联l多边形多边形弧段弧段的关联关系，P1/C1,C5,C6； P2/C3,C4,C6 (3)拓扑包含拓扑包含指存在于空间图形的相同类型但不同等级元素之间的拓扑关系。P1P2P1P3P2P1P3P2（a）简单包含）简单包含(b)多层包含多层包含(c)等价包含等价包含拓扑包含关系的几种形式拓扑包含关系的几种形式233 拓扑关系的关联表达拓扑关系的关

14、联表达 要将节点、弧段和多边形之间的拓扑关系表达出来，可以采用：全显式、半隐式全显式、半隐式（1）全显式表达）全显式表达 明确表达两组关系：l节点节点弧段弧段多边形多边形之间拓扑关系之间拓扑关系l多边形多边形弧段弧段节点节点之间拓扑关系之间拓扑关系节点和弧段的关联关系节点和弧段的关联关系节点节点 弧段弧段N1 C1 C3 C6N2 C1 C2 C5N3 C2 C3 C4N4 C4 C5 C6 N5 C7弧段与多边形的关联弧段与多边形的关联弧段弧段 左多边形左多边形 右多边形右多边形 C1 P1 C2 P3 C3 P2 C4 P2 P3 C5 P1 P3 C6 P1 P2 C7 P4 P3多边形

15、多边形 弧段弧段 P1 C1 C5 C6 P2 C3 C4 C6 P3 C2 C4 C5 C7 P4 C7 多边形和弧段的关联关系多边形和弧段的关联关系弧段和节点的关联关系弧段和节点的关联关系弧段弧段 起点起点 终点终点 C1 N2 N1 C2 N3 N2 C3 N1 N3 C4 N4 N3 C5 N2 N4 C6 N4 N1 C7 N5 N5 （2）半隐式表示）半隐式表示 简化为一个表简化为一个表即半隐式表示。 ARC/ INFO中的弧段数据结构中的弧段数据结构ARCID 起节点起节点 终节点终节点 左多边形左多边形 右多边形右多边形 弧坐标弧坐标 C1 N2 N1 P1 xn2,yn2xn

16、1,yn1 C2 N3 N2 P3 xn3,yn3xn2,yn2 C3 N1 N3 P2 xn1,yn1xn3,yn3 C4 N4 N3 P2 P3 xn4,yn4xn3,yn3 C5 N2 N4 P1 P3 xn2,yn2xn4,yn4 C6 N4 N1 P1 P2 xn4,yn4xn1,yn1 C7 N5 N5 P4 P3 xn5,yn5xn5,yn5 拓扑关系对GIS数据处理和空间分析有三点重意义：（1）拓扑关系不需要坐标或计算距离，就可以确定地理实体之间的空间位置关系。拓扑数据比几何数据具有更大的稳定性。不受比例尺限制，也不随投影关系变化。几何形状不同，拓扑关系可能相同。 234 空间

17、拓扑关系的意义空间拓扑关系的意义l节点间拓扑邻接关系相同节点间拓扑邻接关系相同几何形状不同，拓扑关系相同举例：几何形状不同，拓扑关系相同举例： l多边形之间拓扑邻接关系相同多边形之间拓扑邻接关系相同拓扑学拓扑学：研究图形在拓扑变化下的不变性：研究图形在拓扑变化下的不变性的学科。的学科。GIS理论基础之一。理论基础之一。 拓扑关系对GIS数据处理和空间分析有三点重意义：（2）利用拓扑数据有利于空间要素的查有利于空间要素的查询询。如：区域邻接；（3）可以利用拓扑数据作为工具，重建地理实体。建立封闭多边形。 2.4 空间数据的计算机表示空间数据的计算机表示 复杂的空间数据，如何组织和建立它们的联系，

18、以便计算机存储和操作，称空间数据结构。 空间数据计算表示的基本方法： 空间分幅、属性分层、时间分段空间分幅、属性分层、时间分段（1）空间分幅）空间分幅 将整个地理空间划分为许多子空间，再选择要表达的子空间。（2）属性分层）属性分层 将要表达的空间数据抽象为不同类型属性的数据层来表示；（3）时间分段）时间分段 将有时间特征的地理数据按其变化规律划分为不同的时间段数据，再逐一表示。 以矢量数据结构为例。为了把地理数据存入计算机数据库：l 首先，将区域划分为若干个幅面幅面；l 其次，对每个幅面，从逻辑上将空间数据分为不同的专题层，如土地利用、地形、道路、居民点、森林分布等；l 最后，将一个专题层的地

19、理要素或实体按点、线或面状目标存储，每个目标的数据由空间数据和属性数据组成。杭州地区森林重点火险区杭州地区森林重点火险区3.1 矢量数据结构矢量数据结构3.2 栅格数据结构栅格数据结构3.3 栅格数据结构与矢量数据结构的比较栅格数据结构与矢量数据结构的比较3.4 矢量与栅格一体化数据结构矢量与栅格一体化数据结构3.5 曲面数据结构曲面数据结构311 定义与特点定义与特点l定义定义：基于矢量模型的数据结构称矢量数据结：基于矢量模型的数据结构称矢量数据结构。构。GIS中中弧段弧段可视为矢量可视为矢量 矢量大小矢量大小：相邻两节点间的弧段长度；：相邻两节点间的弧段长度； 矢量方向矢量方向：弧段两端点

20、的顺序表示方向。：弧段两端点的顺序表示方向。 矢量数据结构是利用欧几里得几何学中的点、矢量数据结构是利用欧几里得几何学中的点、线、面及其组合体表示地理实体空间分布。线、面及其组合体表示地理实体空间分布。（1）点）点：（：（x, y） 点目标有空间位置，没有形状和面积。点目点目标有空间位置，没有形状和面积。点目标如居民点、旅游景点、城市。标如居民点、旅游景点、城市。 （2）线）线：多个点组成的矢量弧段（：多个点组成的矢量弧段（x1,y1）（x2,y2）（xn,yn）。）。 线目标有形状，没面积。线状目标：河流、线目标有形状，没面积。线状目标：河流、道路、行政区界、等高线等线状地物。道路、行政区界

21、、等高线等线状地物。（3）面）面：由线段组成的多边形。：由线段组成的多边形。 面目标有形状，有面积。面状目标：区域、面目标有形状，有面积。面状目标：区域、国家、省、县，湖泊、林地。国家、省、县，湖泊、林地。l矢量数据结构的特点矢量数据结构的特点（1）点、线、面及其组合表示地理实体的数据组织方式，能很好地表达地理实体的空间分布特征，数据精度高精度高；（2）数据存储冗余度低冗余度低；（3）便于网络分析网络分析；（4）可计算多边形面积及周长面积及周长；（5）便于图形放大、缩小放大、缩小（6）数据结构复杂，结构复杂，多层数据叠合分析困难多层数据叠合分析困难。 312 矢量数据结构的主要类型矢量数据结构

22、的主要类型l实体数据结构实体数据结构l拓扑数据结构拓扑数据结构3121 实体数据结构实体数据结构 空间数据以基本的空间对象点、线或点、线或多边形为单元多边形为单元进行单独组织。不含拓扑关系的信息。 最典型的是面条结构（Spaghetti）。/wiki/SpaghettiSpaghetti结构结构l以基本的空以基本的空间对象间对象点、线点、线或多边形为单或多边形为单元元进行单独组进行单独组织。织。l如如ArcView 的的Shape文件文件和和MapInfo的的Tab文件。文件。主要特点：主要特点：(1)数据以点、线、多边形为单元进行组织，数据以点、线

23、、多边形为单元进行组织，数据结构数据结构直观简单直观简单。(2)每个多边形以闭合线段存储，每个多边形以闭合线段存储，多边形公共多边形公共边界被数字化和存储两次边界被数字化和存储两次，造成数据冗余和不一，造成数据冗余和不一致性。致性。(3)点、线和多边形有各自的坐标数据，没有点、线和多边形有各自的坐标数据，没有拓扑数据，彼此不关联，拓扑数据，彼此不关联，拓朴分析困难拓朴分析困难(4)岛或洞岛或洞只作为一个单个图形，没有与外界只作为一个单个图形，没有与外界多边形的联系。多边形的联系。 3122 拓扑数据结构拓扑数据结构（一）拓扑数据结构的种类（一）拓扑数据结构的种类lDIME (Dual Inde

24、pendent Map Encoding,对偶独立地图编码对偶独立地图编码) 1970年，美国人口普查分析和制图。以城市街道为编码主体。年，美国人口普查分析和制图。以城市街道为编码主体。以以线段为基本单元线段为基本单元。线段是直线，有两个端点。线段是直线，有两个端点。lTIGER（地理编码和参照系统的拓扑集成，（地理编码和参照系统的拓扑集成，Topologically Integrated Geographic Encoding and Referencing） 1990年，人口普查中，年，人口普查中，TIGER取代了取代了DIME文件。文件。扩展扩展到记录到记录道路、铁路、河流、湖泊、街道、

25、人口普查边界。道路、铁路、河流、湖泊、街道、人口普查边界。lPOLYVRT（多边形转换器（多边形转换器, Polygon converter model,多边形、线、多边形、线、点转换点转换;美国美国Harvard Laboratory for Computer Graphics and Spatial Analysis, 1974） 以链为基本单元以链为基本单元，处理更复杂的拓朴结构。，处理更复杂的拓朴结构。共同特点共同特点：点是相互独立的，点连成线，线构成面。基本对象弧段：点是相互独立的，点连成线，线构成面。基本对象弧段DIME编码编码POLYVRT编码编码（二）拓扑数据结构的文件构成（二

26、）拓扑数据结构的文件构成l节点节点文件构成文件构成l弧段弧段坐标文件构成坐标文件构成l多边形多边形文件构成文件构成l拓扑数据结构的拓扑数据结构的弧段文件构成弧段文件构成拓扑数据结构的文件构成举例：拓扑数据结构的文件构成举例：7个节点，个节点，10个弧段，个弧段，5个多边形个多边形线线号号起起点点终终点点左多左多边形边形右多右多边形边形C1N1N2P2P1C2N3N2P1P4C3N1N3P1C4N1N4P2C5N2N5P2P4C6N4N5P3P2C7N5N6P3P4C8N4N6P3C9N7N7P4P5C10N3N6P4拓扑数据结构的弧段文件构成拓扑数据结构的弧段文件构成4个文件构成：个文件构成：

27、（三）拓扑编辑功能（三）拓扑编辑功能 拓扑数据结构最重要的技术特征和贡献最重要的技术特征和贡献就是拓扑编辑功能。即可以利用拓朴关系，检查数字化原始数据组织和存储的错误，并自动生自动生成多边形成多边形。 原理原理：多边形起始节点和终止节点相同多边形起始节点和终止节点相同。 因此，自动编辑和建立一个指定多边形时，其坐标点应当自行闭合自行闭合。否则，表示数据存储或编码有错误。拓扑编辑功能：拓扑编辑功能：l多边形连接编辑多边形连接编辑：搜索顺序连接组成封闭多边形的弧段。l节点连接编辑节点连接编辑：搜索顺序连接围绕某节点的所有多边形。 线线号号起起点点终终点点左多左多边形边形右多右多边形边形C1N1N2

28、P2P1C2N3N2P1P4C3N1N3P1C4N1N4P2C5N2N5P2P4C6N4N5P3P2C7N5N6P3P4C8N4N6P3C9N7N7P4P5C10N3N6P4拓扑数据结构的弧段文件构成拓扑数据结构的弧段文件构成1多边形连接编辑多边形连接编辑方法方法：以多边形为目标，整理弧段，使弧段围绕多边形顺序连接。 对多边形P1按右多边形按右多边形进行编辑。步骤步骤：1）在拓扑数据结构的弧段文件中找出与指定多边形P1有关的全部弧段全部弧段 弧段号弧段号起节点起节点终节点终节点左多边形左多边形右多边形右多边形C1N1N2P2 P1C3N1N3P1 C2N3N2P1 P42) 调整弧段方向调整弧

29、段方向检查上表中各弧段，调整弧段方向，使各弧段右多边形均为右多边形均为P1。改变C2、C3方向。弧段号弧段号起节点起节点 终节点终节点 左多边形左多边形 右多边形右多边形C1N1N2P2 P1C3N3N1P1C2N2N3P4 P1 3）调整弧段顺序）调整弧段顺序任取一个弧段起节点作为起点，调整弧段顺序号，使多边形各节点顺序相连多边形各节点顺序相连。C3、C2弧段交换位置：节点N1N2N3N1闭合多边形。连接的节点自行封闭。弧段号弧段号起节点起节点终节点终节点 左多边形左多边形 右多边形右多边形C1N1N2P2 P1C2N2N3P4 P1 C3N3N1P1如果编辑过程出现多边形不闭合、多余线段、

30、代码遗漏等问题，如果编辑过程出现多边形不闭合、多余线段、代码遗漏等问题，应检查原始线段记录文件的错误，修正后再进行编辑。应检查原始线段记录文件的错误，修正后再进行编辑。2节点连接编辑节点连接编辑方法方法：以节点为中心，整理多边形，使多边形围多边形围绕节点顺序连接绕节点顺序连接，首尾呼应。以节点N2为例，对其进行编辑（逆时针），算法过程：算法过程：1）找出含有指定节点）找出含有指定节点N2的所有弧段的所有弧段 弧段弧段号号起节起节点点终节终节点点左多左多边形边形右多右多边形边形C1N1N2P2P1C5N2N5P2P4C2N3N2P1P42)调整弧段方向调整弧段方向检查上表各弧段方向，使终节点均为

31、终节点均为N2。交换弧段C5的起始终止节点和左右多边形顺序，终止节点均为N2。得下表弧段号弧段号起节点起节点 终节点终节点 左多边形左多边形 右多边形右多边形C1N1N2P2 P1C5N5N2P4 P2C2N3N2P1 P43) 调整弧段顺序调整弧段顺序 任取一个左多边形作为起点，交换弧段顺序，以保证该节点周围的多边形顺序连接节点周围的多边形顺序连接。 以P2左多边形为起点，交换C5和C2弧段顺序，得到与节点N2相连的多边形顺序连接方向（逆时针）为P2P1P4P2，该节点第一区与最后一个区一致，编码无误。弧段号弧段号起节点起节点终节点终节点左多边形左多边形右多边形右多边形C1N1N2P2 P1

32、C2N3N2P1 P4C5N5N2P4 P2l如果上述顺序连接的多边形不能首尾呼应，如果上述顺序连接的多边形不能首尾呼应，或出现多余弧段，或记录缺失，节点无法连结，或出现多余弧段，或记录缺失，节点无法连结，则表示弧段文件则表示弧段文件有错有错，应检查错误原因，重新，应检查错误原因，重新编辑。直到所节点都经过正确编辑和改正，才编辑。直到所节点都经过正确编辑和改正，才能将该弧段文件用于节点文件和多边形文件的能将该弧段文件用于节点文件和多边形文件的自动生成，以及建立数据库。自动生成，以及建立数据库。l拓扑数据结构及其自动编辑功能在拓扑数据结构及其自动编辑功能在ARC/INFO中采用。中采用。 3.

33、2. 1 栅格数据结构定义栅格数据结构定义l定义定义：基于栅格模型的数据结构简称栅格数据结构。 栅格数据结构是将空间分割成规则的空间分割成规则的网格，称栅格单元。网格，称栅格单元。在各个栅格单元上给出相应的属性值属性值来表示地理实体的一种数据组织形式。 栅格数据结构栅格数据结构 (a)矢量数据(b)栅格单元(c)单元属性值3. 2. 3. 2. 2 2 栅格形状栅格形状l当栅格对应于实体的当栅格对应于实体的一种属性一种属性时，取值容易确定。时，取值容易确定。l当栅格对应于实体当栅格对应于实体多种属性多种属性时时( (跨边界跨边界) )，有多种取，有多种取值方法：值方法：面积占优法、中心点法、长

34、度占优法、重要性法面积占优法、中心点法、长度占优法、重要性法 3. 2. 3 栅格单元属性值栅格单元属性值1 1）面积占优法）面积占优法栅格取值栅格取值=栅格中面积最大的属性值栅格中面积最大的属性值 面积占优法面积占优法A CB D D D D D B D D C B C C C A A C C2 2）中心点法）中心点法栅格取值栅格取值=栅格中心点的值栅格中心点的值 中心点法中心点法 D D D D B D C C B A C C A A C CA CB D 3 3）长度占优法）长度占优法栅格取值栅格取值=栅格中心横线所占最长部分的属性值栅格中心横线所占最长部分的属性值 长度占优法长度占优法

35、D D D D B D C C B A C C A A C CA CB D 4 4）重要性法）重要性法 栅格取值栅格取值=重要属性值重要属性值 上述取值方法，不论哪一种都会有误差上述取值方法，不论哪一种都会有误差 D D D D D D D C B D D C A A C C 重要性法重要性法A CB D 3. 2. 3. 2. 4 4 栅格尺寸栅格尺寸 网格边长决定栅格数据的精度。无论网格边长网格边长多小，都有信息丢失信息丢失。 11min22iHAAA区域区域最小多边形的面积最小多边形的面积i=1,2,=1,2,n(,n(区域多边形数区域多边形数) ) 边长边长=H/2 =H/2 时，该多

36、边形得到表示时，该多边形得到表示 合理栅格尺寸合理栅格尺寸H H : :通常，用通常，用最小多边形最小多边形的精度标准来的精度标准来确定网格尺寸确定网格尺寸，既，既有效逼近地理实体，又最大限度减少数据量。有效逼近地理实体，又最大限度减少数据量。（1 1）优点）优点l用离散的栅格表达地理要素比较用离散的栅格表达地理要素比较直观；直观；l容易实现多层数据的容易实现多层数据的叠合操作；叠合操作；l便于与便于与遥感遥感及扫描输入数据相匹配使用。及扫描输入数据相匹配使用。3. 2. 5 栅格数据结构的特点栅格数据结构的特点 （2）缺点）缺点l数据精度取决于网格数据精度取决于网格边长边长，单元数据几何级数

37、，单元数据几何级数递增；递增；l相邻网格单元属性值的相关性，造成相邻网格单元属性值的相关性，造成数据冗余数据冗余度大；度大；l网络网络分析困难；分析困难；l图形图形质量差质量差，不能无极缩放，不能无极缩放 栅格数据数据量很大，需要对栅格数据数据量很大，需要对数据压缩和编码数据压缩和编码 3 32 26 6 栅格数据结构的类型与编码栅格数据结构的类型与编码l 栅格矩阵结构栅格矩阵结构l 费尔曼链码费尔曼链码l 游程编码结构游程编码结构l 四叉树数据结构四叉树数据结构 3 32 26 61 1 栅格矩阵结构栅格矩阵结构l栅格数据结构栅格数据结构是用矩阵来存储栅格数据单元的存储是用矩阵来存储栅格数据

38、单元的存储结构。最简单和直观编码法。逐行、列编码。结构。最简单和直观编码法。逐行、列编码。 矢量多边形矢量多边形空间分割空间分割栅格矩阵栅格矩阵面状栅格矩阵结构优点：优点：结构简单结构简单。缺点：数据量大，缺点：数据量大，占用大量存储空间占用大量存储空间。例如：例如：（1）8 x 8阶栅格数据存储空间：阶栅格数据存储空间：8 8 2字节字节=128字节；字节；（2）10 10 km2 区域，区域，1m栅格边长，栅格数据栅格边长，栅格数据存在空间：存在空间：10 000 10 000 2200 兆字节兆字节 随着空间分辨率的提高，存储数据量将呈几随着空间分辨率的提高，存储数据量将呈几何级数递增。

39、何级数递增。 为降低栅格数据量，出现为降低栅格数据量，出现多种压缩编码法多种压缩编码法。3 32 26 62 2 费尔曼链码费尔曼链码 （Freemans Chain CodeFreemans Chain Code）l19611961，FreemanFreeman提出（美）。提出（美）。l费尔曼链码也称边界链码，是费尔曼链码也称边界链码，是二二值图象值图象边缘编码方法边缘编码方法l适用于曲线和区域边界编码。适用于曲线和区域边界编码。l编码方法：编码方法： 扫描图像扫描图像黑白二值图像。黑白二值图像。 编码编码8 8邻域思想，用邻域思想，用8 8个方向码编码线划图。个方向码编码线划图。曲线曲线：

40、已知曲线上的一个点，搜索：已知曲线上的一个点，搜索8个方向可找到它的后续栅格点，个方向可找到它的后续栅格点， 并用方向代码表示。如此可得费尔曼链码表。并用方向代码表示。如此可得费尔曼链码表。 标号标号高程高程 起始起始行行 列列链码链码#1#1100m100m4 14 10,7,7,0,0,0,0,2,0,1,2,2,2,2,0,7,7,0,0,0,0,2,0,1,2,2,2,2,4,3,3,4,4,4,5,5,6,5,6,64,3,3,4,4,4,5,5,6,5,6,6#2#2200m200m5 35 37,7,0,0,1,2,2,2,3,3,5,5,5,67,7,0,0,1,2,2,2,3

41、,3,5,5,5,6654(i,j)03217曲线上某点曲线上某点(i,j)的的8个个邻域方向代码邻域方向代码：1012345678910123456789#1 7 7 00 0 0 2 0 1 2 2 2 2 4 3 3 4 4 4 5 5 6 5 60 7 70 0 1 2 2 2 3 3 5 5 5#2区域区域 ：边界方向链码：边界方向链码 起始起始行列行列链码链码10 110 17 7，0 0，l l，0 0，7 7，l l，7 7，0 0，0 0，2 2，3 3，2 2，2 2，1 1，0 0，7 7，0 0，0 0，0 0，0 0，2 2，4 4，3 3，4 4，4 4，3 3，4

42、 4，4 4，5 5，4 4，5 5，4 4，5 5，4 4，5 5，4 4，6 6，6 6优点优点： 对多边形有很强的数据压缩能力；对多边形有很强的数据压缩能力； 便于计算面积和周长；便于计算面积和周长； 探测边界急弯和凹进部分等都比较容易。探测边界急弯和凹进部分等都比较容易。缺点：缺点： 很难实现叠置运算如组合、相交等；很难实现叠置运算如组合、相交等； 对局部修改将改变整体结构，效率较低；对局部修改将改变整体结构，效率较低； 相邻区域的边界被重复存储，产生数据冗余。相邻区域的边界被重复存储，产生数据冗余。 3 32 26 63 3 游程编码结构游程编码结构 游程编码（游程编码（Run Le

43、ngth CodeRun Length Code）对有块状地物的）对有块状地物的栅格数据进行压缩编码。栅格数据进行压缩编码。l游程游程指栅格矩阵指栅格矩阵一行内相邻同值栅格的数量一行内相邻同值栅格的数量，也称行，也称行程程l游程编码结构游程编码结构是在栅格数据矩阵中，逐行将相邻同值是在栅格数据矩阵中，逐行将相邻同值栅格合并，记录合并后栅格的值及合并栅格的数量。栅格合并，记录合并后栅格的值及合并栅格的数量。l目的目的：压缩栅格数据量，消除数据间的冗余。：压缩栅格数据量，消除数据间的冗余。 l游程编码结构的建立游程编码结构的建立方法方法将栅格矩阵的将栅格矩阵的一行一行数据序列数据序列 X X1 1

44、, X, X2 2, , , X , Xn n映射为映射为二元组序列二元组序列 （A Ai i, P, Pi i） i=1,2,.,K (Ki=1,2,.,K (Kn n) )其中，其中，A Ai i 栅格属性值栅格属性值; ;P Pi i 游程长度游程长度; ;n n 栅格总数栅格总数; ;K K 游程总数游程总数; i; i游程序号。游程序号。例：将栅格矩阵结构转换为游程编码结构。例：将栅格矩阵结构转换为游程编码结构。p55栅格矩阵栅格矩阵l游程编码能否压缩数据量，需估计数据冗余度游程编码能否压缩数据量，需估计数据冗余度Re式中：式中：Q相邻栅格属性值变化次数的累加和；相邻栅格属性值变化次

45、数的累加和；m、n为行、列数。为行、列数。当当Re1 / 5时，可取得明显压缩效果。例：时，可取得明显压缩效果。例：0.71875881811mnQRel游程编码压缩效果，可用压缩比衡量：游程编码压缩效果，可用压缩比衡量： 式中，式中，S压缩比；压缩比；m、n栅格矩阵行列数；栅格矩阵行列数；K游程总数。游程总数。l 压缩比越大，压缩效果越显著。压缩比越大，压缩效果越显著。上例上例p55p55： m=n=8m=n=8 K=26 K=26 S=64 / 26 =2.4615 压缩比压缩比 5 5：2 2 KnmS优点：优点： 压缩了直接编码的存储量，压缩了直接编码的存储量，数据压缩率数据压缩率较高

46、，且信息不丢失较高，且信息不丢失，是一种无损压缩方法，是一种无损压缩方法，通过解码可以恢复为栅格矩阵。通过解码可以恢复为栅格矩阵。 缺点：缺点： 只考虑行，不考虑列间关系，只考虑行，不考虑列间关系， 是一维游程编码。是一维游程编码。 3 32 26 64 4 四叉树数据结构四叉树数据结构一、基本概念一、基本概念l 游程编码结构只在一个方向对栅格数据进行压缩，是一维数据压缩编码。四叉树四叉树（Quadtree）结构可以在两个方向对栅格数据进行压缩，是更有效更有效的数据压缩方法。l 四叉树数据结构概念四叉树数据结构概念 将空间区域（2n 2n , n1）分割为4 4个象限个象限，按4个象限检查其栅

47、格属性值。如果某个象限所有栅格具有相同的属性值，则这个象限就不再分割。否则，还要把这个象限分割成四个象限。如此分割，直到每个象限只含有相同的属性值为止。属性值相同，不再分割的单元称叶节点叶节点。最小的叶节点是一个栅格。整个栅格区域叫做根节点根节点。0 2 2 5 5 5 5 52 2 2 2 2 5 5 50 0 0 0 0 3 3 32 2 2 2 3 3 5 50 0 2 3 3 3 5 50 0 3 3 3 3 5 30 0 0 3 3 3 3 30 0 0 0 3 3 3 35 3 3 3 3 3 0 30 2 2 2 2 5 2 22 2 0 0 2 2 2 3 5 5 2 55 3

48、 50 0 03 33 3 0 3四叉树数据结构概念四叉树数据结构概念0 12 3二、四叉树的存储方法有两种二、四叉树的存储方法有两种 常规四叉树和线性四叉树常规四叉树和线性四叉树1 1） 常规四叉树常规四叉树l 分割子象限分割子象限检测全区域，属性值不同时，把栅格图象等分成4个子象限；l 检查子象限检查子象限属性值相同属性值相同不再分割；不再分割；属性值不同属性值不同子象限再分割成子象限再分割成4 4个子象限。个子象限。l 如此递归分割如此递归分割，直到每个子象限属性值相同为止。这种生成四叉树的方法称为自上而下自上而下（top-down）方式。 常规四叉树及其生成过程常规四叉树及其生成过程第

49、第0次分割：第次分割：第0层层第第1次分割：第次分割：第1层层第第2次分割：第次分割：第2层层第第3次分割：第次分割：第3层层012311121310121122123120 10 11 12 13120 121122 123 0 1 2 3l最大深度数最大深度数 2n2n栅格图，最大深度数为n（分割次数）l最大层数最大层数 n+1，层次为0，1，2，nl每层栅格宽度每层栅格宽度 第 i 层叶节点正方形边长2 n - i 层序号i=0，1，2，n；n最大深度数。例如：一幅例如：一幅2 23 3 2 23 3的栅格图象的栅格图象 最大深度最大深度 n=3n=3 最大层数最大层数 = =4 4 层

50、序号分别为层序号分别为0 0、1 1、2 2、3 3各层正方形边长：各层正方形边长： 第第 0 0 层：层： 23-0=8 第第 1 1 层：层： 23-1=4 第第 2 2 层：层： 23-2=2 第第 3 层：层： 23-3=1 l缺点缺点（1）占用内外存空间比较大。）占用内外存空间比较大。 （2）对栅格数据进行运算时，要作）对栅格数据进行运算时，要作遍历遍历树节点的运树节点的运算。算。 增加操作的复杂性。增加操作的复杂性。 在在GIS或图象分割中不采用常规四叉树，而用或图象分割中不采用常规四叉树，而用线线性四叉树性四叉树（Linear Quadtree）。）。 l l 常规四叉树每个节点

51、通常常规四叉树每个节点通常存储存储6 6个量个量： 4 4个子节点指针个子节点指针。叶节点的子指针为空。叶节点的子指针为空。 1 1个父节点指针个父节点指针。根节点的父指针为空。根节点的父指针为空。 1 1个节点值个节点值。 2）线性四叉树）线性四叉树 l线性四叉树编码是用常规四叉树的方式组织数据，并线性四叉树编码是用常规四叉树的方式组织数据，并不以常规四叉树方式存储数据。不以常规四叉树方式存储数据。 l只需存储每个叶节点的只需存储每个叶节点的3个量个量： 位置位置：层内位置：层内位置 （即（即Morton码）码） 深度深度：第几层：第几层 （或节点大小）（或节点大小） 节点值节点值 位置码位

52、置码=位置位置+深度深度 叶节点叶节点 （层内位置和层数）（层内位置和层数） （大小不等的正方形）（大小不等的正方形） l线性四叉树是线性四叉树是线性排列节点位置码线性排列节点位置码。 各种编码方法的差异在于位置码的编码方法不同。各种编码方法的差异在于位置码的编码方法不同。线性四叉树示意图线性四叉树示意图 位置码位置码1 位置码位置码2 位置码位置码 位置码位置码11 位置码位置码12（1）基于位置和深度的线性四叉树编码）基于位置和深度的线性四叉树编码 分割分割子区子区栅格值栅格值叶节点叶节点位置码位置码否否是是原图原图相同否相同否自上而下的分割方法自上而下的分割方法 l用位置和深度构造叶节点

53、的位置码用位置和深度构造叶节点的位置码(二合一码二合一码)。l用二进制表示。用二进制表示。 (1)0(4) (5) (6) (7)13 1415 16(2)0(8)0(3)1(9)1(10)1(11)0(12)0(18)0(19)0(17)00000000000000000110000001111000011111000111100000000000000000000 0 1 2 3 0 1 2 3 0 1 2 3 0 1 2 3 0 1 2 3 0 1 2 3(1)(2)(3)(4)(5)(6)(7)(8)(9)(10) (11) (12)(14) (15) (16)(13)(17) (18

54、) (19)0层层1层层2层层3层层线性四叉树线性四叉树l线性四叉树中，叶节点（线性四叉树中，叶节点（7 7）的位置编码：）的位置编码：位置（层内码）位置（层内码） 深度深度 ( (几几层层) )3第一层第一层0第二层第二层3第三层第三层3000011111111 0000 1111l 位置码的十进制值：位置码的十进制值：0 02 29 9+ +0 02 28 8+ +1 12 27 7+ +1 12 26 6+ +1 12 25 5+ +1 12 24 4+ +0 02 23 3+ +0 02 22 2+ +1 12 21 1+ +1 12 20 0=243=2431919个叶节点叶节点位置

55、码表个叶节点叶节点位置码表 1 10 0 0 0 0 00 0 0 0 0 00 0 1 00 0 1 02 22 20 0 0 1 0 00 0 0 1 0 00 0 1 00 0 1 066663 30 0 1 0 0 00 0 1 0 0 00 0 1 00 0 1 01301304 40 0 1 1 0 00 0 1 1 0 00 0 1 10 0 1 11951955 50 0 1 1 0 10 0 1 1 0 10 0 1 10 0 1 12112116 60 0 1 1 1 00 0 1 1 1 00 0 1 10 0 1 12272277 70 0 0 0 1 1 1 1 1

56、1 1 10 0 0 0 1 1 1 12432438 80 1 0 0 0 00 1 0 0 0 00 0 0 10 0 0 12572579 91 0 0 0 0 01 0 0 0 0 00 0 1 00 0 1 051451410101 0 0 1 0 01 0 0 1 0 00 0 1 00 0 1 057857811111 0 1 0 0 01 0 1 0 0 00 0 1 00 0 1 064264212121 0 1 1 0 01 0 1 1 0 00 0 1 00 0 1 070670613131 1 0 0 0 01 1 0 0 0 00 0 1 10 0 1 1771771

57、14141 1 0 0 0 11 1 0 0 0 10 0 1 10 0 1 178778715151 1 0 0 1 01 1 0 0 1 00 0 1 10 0 1 180380316161 1 0 0 1 11 1 0 0 1 10 0 1 10 0 1 181981917171 1 0 1 0 01 1 0 1 0 00 0 1 00 0 1 083483418181 1 1 0 0 01 1 1 0 0 00 0 1 00 0 1 0898898叶结叶结点号点号二进制码二进制码十进十进制码制码19191 1 1 1 0 01 1 1 1 0 00 0 1 00 0 1 0962962

58、（2 2） 基于四进制的线性四叉树编码基于四进制的线性四叉树编码 M MQ Q 四进制 M MQ Q 码是加拿大学者Morton于1966年提出。栅格栅格位置码位置码相邻相邻4单元单元属性值属性值叶节点叶节点是是否否原图原图相同否相同否合并合并去位置码去位置码最低位最低位线性线性排列排列位置码位置码自下而上（自下而上（bottom-upbottom-up）合并方法）合并方法 四进制四进制?l 四叉树四叉树四等分四等分四进制四进制 都用都用4 4个数字个数字0 0、1 1、2 2、3 3l 位置编码位置编码 I Iyb yb I IxbxbMQ= 2 Iyb（行号）（行号）+Ixb（列号）（列号

59、） MQ=2Iyb+Ixbl叶节点（7）在各层的编码组合，即四进制位置码四进制位置码：第一层第一层第二层第二层第三层第三层0 03 33 3深度隐含深度隐含 l实际上，实际上，033可以通过行列号直接推算出来，这就是四可以通过行列号直接推算出来，这就是四进制编码。进制编码。 l对2n 2n图象，可用用 n 个个四进制数位表示所有栅格位四进制数位表示所有栅格位置码。置码。 如叶节点（7）： 033四进制编码过程四进制编码过程: :l 栅格行列号转换成二进制行号栅格行列号转换成二进制行号I Iybyb、列号、列号I Ixbxbl 四进制四叉树位置码四进制四叉树位置码 位置码：位置码：M MQ Q=

60、2 =2 I Iybyb+I+Ixbxb第第011行，行，011列：列：MQ=2 x 011+011=022+011=033 000 001 010 011 100 101 110 111MQ000 001 010 011 100 101 110 111000002 003 012 013 102 103 112 113001020 021 030 031 120 121 130 131010022 023 032 033 122 123 132 133011200 201 210 211 300 301 310 311100202 203 212 213 302 303 312 313101