5 GIS数据组织与结构fkt.pptx

《5 GIS数据组织与结构fkt.pptx》由会员分享，可在线阅读，更多相关《5 GIS数据组织与结构fkt.pptx（57页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、 本章内容：主要介绍GIS中两种重要的数据结构：栅格结构和矢量结构的特点，以及具体的存储方式，并简单介绍了相互转换的算法。第一节第一节 数据模型数据模型l通俗地讲，数据模型就是现实世界的模拟。通俗地讲，数据模型就是现实世界的模拟。l数据模型可分成两个不同的层次数据模型可分成两个不同的层次:（1）概念模型：）概念模型：也称信息模型，是按用户的观点来对数据也称信息模型，是按用户的观点来对数据和信息建模，是一种独立于任何计算机系统实现的，如实体联系模和信息建模，是一种独立于任何计算机系统实现的，如实体联系模型，这类模型完全不涉及信息在计算机系统中的表示，只是用来描型，这类模型完全不涉及信息在计算机系

2、统中的表示，只是用来描述某个特定组织所关心的信息结构，被称作述某个特定组织所关心的信息结构，被称作“概念数据模型概念数据模型”。（2）数据模型：）数据模型：主要包括网状模型、层次模型、关系模型主要包括网状模型、层次模型、关系模型等，是按计算机系统的观点对数据建模，是直接面向数据库中数据等，是按计算机系统的观点对数据建模，是直接面向数据库中数据逻辑结构的，涉及到计算机系统，一般又称为逻辑结构的，涉及到计算机系统，一般又称为“基本数据模型基本数据模型”或或“结构数据模型结构数据模型”。（1）概念模型）概念模型l基本内容：基本内容：（1）两类）两类实体实体：对象与：对象与属性属性；（2）实体的两级：

3、个体与总体；）实体的两级：个体与总体；（3）个体与总体之间的）个体与总体之间的联系联系。l用用ER图来描述现实世界的概念模型。图来描述现实世界的概念模型。l步骤：步骤：（1）标定局部应用中的实体；）标定局部应用中的实体；（2）实体的属性、标识实体的码；）实体的属性、标识实体的码；（3）确定实体之间的联系及其类型）确定实体之间的联系及其类型（1：1、1：n、m：n）lE-R图提供了表示图提供了表示实体、属性和联系实体、属性和联系的方法的方法（基（基本要素）。本要素）。l实体：实体：现实世界中一组具有某些共同特性和行为现实世界中一组具有某些共同特性和行为的对象可抽象为一个实体。如，在学校环境中，的

4、对象可抽象为一个实体。如，在学校环境中，可把张三、李四等对象抽象为学生实体。对象与可把张三、李四等对象抽象为学生实体。对象与实体是实体是“member of”的关系。的关系。注：注：对象类型的组成部分可抽象为实体的属性。对象类型的组成部分可抽象为实体的属性。l实体与属性是相对而言的。实体与属性是相对而言的。一般来说，属性不能一般来说，属性不能再具有需要描述的性质，即属性必须不可分的数再具有需要描述的性质，即属性必须不可分的数据项；属性不能和其他实体具有联系，即联系只据项；属性不能和其他实体具有联系，即联系只能发生在实体之间。能发生在实体之间。l根据需求分析，要考察实体之间是否存在联系，根据需求

5、分析，要考察实体之间是否存在联系，有无多余联系。有无多余联系。ER图基础知识图基础知识ER图举例：图举例：实体：班主任、学生、班级、宿舍。实体：班主任、学生、班级、宿舍。班主任班主任班级班级教室教室学生学生宿舍宿舍管理管理上课上课管理管理住宿住宿指导指导性别性别职工号职工号姓名姓名班级号班级号学生人数学生人数教室编号教室编号地址地址容量容量宿舍号宿舍号地址地址人数人数学号学号姓名姓名出生日期出生日期1n1n1n1n1n上课上课mn第二节第二节 数据与文件组织数据与文件组织数据数据是现实世界中信息的载体，是信息的具是现实世界中信息的载体，是信息的具体表达形式，为了表达有意义的信息内容，数据体表达

6、形式，为了表达有意义的信息内容，数据必须按照一定的方式进行组织和存储。必须按照一定的方式进行组织和存储。数据库数据库是为一定目的服务，以特定的数据存储是为一定目的服务，以特定的数据存储的相关联的数据集合，是数据按照一定的格式存的相关联的数据集合，是数据按照一定的格式存放的仓库。放的仓库。GIS的数据库的数据库是某一区域内关于一定地理要素是某一区域内关于一定地理要素特征的数据集合。特征的数据集合。l空间数据库与一般数据库相比，具有：空间数据库与一般数据库相比，具有：l数据量特别大；数据量特别大；l不仅有地理要素的属性数据，还有大量的空间数据；不仅有地理要素的属性数据，还有大量的空间数据；l数据应

7、用广泛。数据应用广泛。1.数据库中的数据组织一般可分为四级：数据库中的数据组织一般可分为四级：数据项、记数据项、记录、文件和数据库。录、文件和数据库。2.数据间的逻辑联系：数据间的逻辑联系：一对一的联系；一对多的一对一的联系；一对多的联系；多对多的联系。联系；多对多的联系。3.常用的数据文件：常用的数据文件：顺序文件、索引文件、直接顺序文件、索引文件、直接文件和倒排文件。文件和倒排文件。l数据项：数据项：是可以定义数据的最小单位，也叫元是可以定义数据的最小单位，也叫元素、基本项、字段等，数据项与现实世界实体的素、基本项、字段等，数据项与现实世界实体的属性相对应，数据项有一定的取值范围，称为域。

8、属性相对应，数据项有一定的取值范围，称为域。l记录：记录：是由若干相关联的数据项组成，是处理是由若干相关联的数据项组成，是处理和存储信息的基本单位，是关于一个实体的数据和存储信息的基本单位，是关于一个实体的数据总和，构成该记录的数据项表示实体的若干属性。总和，构成该记录的数据项表示实体的若干属性。为了标识每条记录，都必须有记录的标识符，也为了标识每条记录，都必须有记录的标识符，也叫叫“关键字关键字”。l文件：文件：是一给定类型记录的全部具体值的集合，是一给定类型记录的全部具体值的集合，文件用文件名称标识。文件用文件名称标识。l数据库数据库l顺序文件：顺序文件：是最简单的文件组织形式，对记录按照

9、主关键字的顺是最简单的文件组织形式，对记录按照主关键字的顺序进行组织。当主关键字是数字型时，以其数值的大小为序；若主序进行组织。当主关键字是数字型时，以其数值的大小为序；若主关键字是文字型的，则以字母的排列为序。关键字是文字型的，则以字母的排列为序。l索引文件：索引文件：除了存储记录本身（主文件）以外，还建立了若干索除了存储记录本身（主文件）以外，还建立了若干索引表，这种带有索引表的文件叫索引文件。索引表中列出记录关键引表，这种带有索引表的文件叫索引文件。索引表中列出记录关键字和记录在文件中的位置（地址）。读取记录时，只要提供记录的字和记录在文件中的位置（地址）。读取记录时，只要提供记录的关键

10、字值，系统通过查找索引表获得记录的位置，然后取出该记录。关键字值，系统通过查找索引表获得记录的位置，然后取出该记录。l直接文件：直接文件：又称随机文件，其存储是根据记录关键字的值，通过又称随机文件，其存储是根据记录关键字的值，通过某种转换方法得到一个物理存储位置，然后把记录存储在该位置上。某种转换方法得到一个物理存储位置，然后把记录存储在该位置上。查找时，通过同样的转换方法，可以直接得到所需要的记录。查找时，通过同样的转换方法，可以直接得到所需要的记录。l倒排文件：倒排文件：是带有辅索引的文件，其中辅索引是按照一些辅关键是带有辅索引的文件，其中辅索引是按照一些辅关键字来组织索引的。倒排文件是一

11、种多关键字的索引文件，其中的索字来组织索引的。倒排文件是一种多关键字的索引文件，其中的索引不能唯一标识记录，往往同一索引指向若干记录。因而，索引往引不能唯一标识记录，往往同一索引指向若干记录。因而，索引往往带有一个指针表，指向所有该索引标识的记录。通过辅索引不能往带有一个指针表，指向所有该索引标识的记录。通过辅索引不能直接读取记录，而要通过主关键字才能查到记录的位置。直接读取记录，而要通过主关键字才能查到记录的位置。数据库结构数据库结构l 关系模型（关系模型（relational modelrelational model）满足一定条件满足一定条件的二维表格。的二维表格。l 层次模型（层次模型

12、（hierarchical modelhierarchical model）以记录类型以记录类型为节点的有向树（为节点的有向树（treetree）。其主要特征是：（）。其主要特征是：（1 1）除根节）除根节点点外外，任任何何节节点点都都有有且且 只只有有一一个个“父父亲亲”；（2 2）“父父”节节点表示的实体与点表示的实体与“子子”节点表示的实体是一对多的联系。节点表示的实体是一对多的联系。l网状模型（网状模型（network modelnetwork model）（1 1）可以有一个以上的结点没有）可以有一个以上的结点没有“父父”结点；结点；（2 2）至少有一个结点有多于一个）至少有一个结点

13、有多于一个“父父”结点；结点；（3 3）结点之间可以有多种联系；）结点之间可以有多种联系；（4 4）可以存在回路。）可以存在回路。（a）关系结构表（b）层次模型示例-林地数据库（c）网状模型示例第三节第三节 空间数据组织与结构空间数据组织与结构 l 栅格数据结构l 矢量数据结构l 栅格与矢量数据结构的选择与转换l 两种数据结构的优缺点比较l数据结构：数据结构：指的是数据之间的相互关系，指的是数据之间的相互关系，即数据的组织形式。即数据的组织形式。l数据元素之间的逻辑关系，也称数据元素之间的逻辑关系，也称数据的逻辑结数据的逻辑结构构，是从逻辑关系上描述数据，与数据的存储无，是从逻辑关系上描述数据

14、，与数据的存储无关，关，是独立于计算机的。数据的逻辑结构可看是独立于计算机的。数据的逻辑结构可看作是从具体问题抽象出来的数学模型。作是从具体问题抽象出来的数学模型。l数据元素及其关系在计算机存储器上的表示，称数据元素及其关系在计算机存储器上的表示，称为为数据的存储结构（物理结构），数据的存储结构（物理结构），是逻辑结是逻辑结构用计算机语言的实现，它依赖于计算机语言。构用计算机语言的实现，它依赖于计算机语言。对机器语言而言，存储结构是具体的。对机器语言而言，存储结构是具体的。描述地理实体的数据本身的组织方法，称为内描述地理实体的数据本身的组织方法，称为内部数据结构部数据结构。数据结构数据结构即指

15、数据组织的形式，是即指数据组织的形式，是适合于计算机存储、管理和处理的数据逻辑结构。适合于计算机存储、管理和处理的数据逻辑结构。空间数据结构空间数据结构则是地理实体的空间排列方式和相则是地理实体的空间排列方式和相互关系的抽象描述。互关系的抽象描述。GISGIS的内部数据结构基本上可分为两大类：的内部数据结构基本上可分为两大类：矢矢量量结结构构和和栅栅格格结结构构。两两类类结结构构都都可可用用来来描描述述地理实体的点、线、面三种基本地理实体的点、线、面三种基本类型。类型。一、数据模型一、数据模型l矢量模型矢量模型 在矢量模型中，每一个实体的在矢量模型中，每一个实体的位置用它们位置用它们在坐标参考

16、系统中的空间位置定义在坐标参考系统中的空间位置定义。地图空间。地图空间中的每一位置都有唯一的坐标值。点、线和多中的每一位置都有唯一的坐标值。点、线和多边形用于表达不规则的地理实体在现实世界的边形用于表达不规则的地理实体在现实世界的状态。状态。矢量模型中的空间实体与所表达的现实矢量模型中的空间实体与所表达的现实世界中的空间实体具有一定的对应关系。世界中的空间实体具有一定的对应关系。一、数据模型一、数据模型l栅格模型栅格模型 在栅格模型中，空间被规则地划分为栅格。地理实体在栅格模型中，空间被规则地划分为栅格。地理实体的的位置和状态用其占据的栅格的行、列定义位置和状态用其占据的栅格的行、列定义。栅格

17、的。栅格的值表值表达这个位置上物体的类型或状态达这个位置上物体的类型或状态。每个栅格的大小代表了。每个栅格的大小代表了定义的空间分辨率。定义的空间分辨率。栅格模型最小单元与它表达的真实世界空间实体没有栅格模型最小单元与它表达的真实世界空间实体没有直接的对应关系。如，道路是被具有道路属性值的一组栅直接的对应关系。如，道路是被具有道路属性值的一组栅格表达的，而不是通过某一栅格单元识别的。格表达的，而不是通过某一栅格单元识别的。一、数据模型一、数据模型 在栅格和矢量数据模型中，空间信息都是用统在栅格和矢量数据模型中，空间信息都是用统一的单位表达。一的单位表达。在栅格模型中，在栅格模型中，统一的单位是

18、栅格统一的单位是栅格，表达一个区域所用，表达一个区域所用栅格的数量很大，但其栅格单元的大小一样，每个栅格的位栅格的数量很大，但其栅格单元的大小一样，每个栅格的位置都被严格定义。置都被严格定义。矢量方法中，矢量方法中，统一的单元是点、线和多边形统一的单元是点、线和多边形，与栅格方，与栅格方法相比，在数量上所用的表达单元较少，但大小可变。同一法相比，在数量上所用的表达单元较少，但大小可变。同一类型的矢量单元的位置是用连续坐标值定义。矢量数据提供类型的矢量单元的位置是用连续坐标值定义。矢量数据提供的坐标位置比栅格数据用行、列号所表达位置更精确。的坐标位置比栅格数据用行、列号所表达位置更精确。栅格结构

19、和矢量结构栅格结构和矢量结构1.定定 义义二、栅格数据结构及其编码二、栅格数据结构及其编码特点：特点：属性明显、定位隐含。属性明显、定位隐含。栅格结构是最简单、最直接的空间数据结构。栅格结构是最简单、最直接的空间数据结构。像元由像元由行列确定位置。数据表示地物或现象的非几何属性特征。行列确定位置。数据表示地物或现象的非几何属性特征。（a）点 （b）线 (c)面 栅格结构表示的地表是不连续的，是栅格结构表示的地表是不连续的，是量化和近似离散的数据。栅格数据的比量化和近似离散的数据。栅格数据的比例尺就是栅格大小与地表相应单元大小例尺就是栅格大小与地表相应单元大小之比。之比。对于栅格数据结构：对于栅

20、格数据结构：l点：点：为一个像元；为一个像元；l线：线：在一定方向上连接成串的相邻像在一定方向上连接成串的相邻像元集；元集；l面：面：聚集在一起的相邻像元集合；聚集在一起的相邻像元集合；点线面二、栅格数据结构及其编码二、栅格数据结构及其编码栅格数据的应用模型：栅格数据的应用模型：2.2.决定栅格单元代码的方式决定栅格单元代码的方式q 中心点法中心点法：用处于栅格中心处的地物类用处于栅格中心处的地物类型或现象特性决定栅格代码。常用于具有连续型或现象特性决定栅格代码。常用于具有连续分布特性的地理要素。分布特性的地理要素。q 面积占优法：面积占优法：以占矩形区域面积最大的以占矩形区域面积最大的地物类

21、型或现象特性决定栅格单元的代码。常地物类型或现象特性决定栅格单元的代码。常用于分类较细，地物类别斑块较小的情况。用于分类较细，地物类别斑块较小的情况。在决定栅格代码时尽量保持地表的真实性，保证在决定栅格代码时尽量保持地表的真实性，保证最大的信息容量。最大的信息容量。栅格单元代码的确定 q 重要性法：重要性法：根据栅格内不同地物的重要性，选取最重要的地物根据栅格内不同地物的重要性，选取最重要的地物类型决定相应的栅格单元代码。常用于具有特殊意义而面积较小的类型决定相应的栅格单元代码。常用于具有特殊意义而面积较小的地理要素。地理要素。q 百分比法：百分比法：根据矩形区域内各地理要素所占面积的百分比数

22、根据矩形区域内各地理要素所占面积的百分比数确定栅格单元的代码。确定栅格单元的代码。栅格数据的组织方法主要有以下三种：栅格数据的组织方法主要有以下三种：（1 1）以以栅栅格格单单元元为为记记录录的的序序列列，不不同同层层上上同同一一像像元位置上的各属性值表示为一个列数组元位置上的各属性值表示为一个列数组（图（图(a)(a)）；（2 2）以以层层为为基基础础，每每一一层层又又以以像像元元顺顺序序记记录录它它的的坐坐标标和和属属性性值值，一一层层记记录录完完后后再再记记录录第第二二层层（图图 (b)(b)）这种方法较为简单，但需要的存贮空间最大；这种方法较为简单，但需要的存贮空间最大；（3 3）以以

23、层层为为基基础础，但但每每一一层层内内则则以以多多边边形形为为序序记记录录多多边边形形的的属属性性值值和和充充满满多多边边形形的的各各栅栅格格单单元元的的坐坐标标（图（图（c c）。）。3.3.栅格数据的组织方法栅格数据的组织方法 方方法法(a)(a)比比(b)(b)占占用用的的存存储储空空间间少少，因因为为N N层层中中实实际际只只存存贮贮了了一一层层的的像像元元坐坐标标，而而方方法法(b)(b)则则要要存存储储多多次次（与与属属性性个个数数相相同同）。方方法法(c)(c)则则节节省省了了许许多多用用于于存存贮贮属属性性的的空空间间，因因为为同同一一属属性性的的制制图单元中几个栅格单元只记录

24、一次属性值。图单元中几个栅格单元只记录一次属性值。4.4.栅格结构编码方法栅格结构编码方法q 直接栅格编码：直接栅格编码：是一种简单而直观的栅格结构编码方法，是一种简单而直观的栅格结构编码方法，通常称这种编码的图像文件为网格文件或栅格文件。直接编码就是将栅通常称这种编码的图像文件为网格文件或栅格文件。直接编码就是将栅格数据看作一个数据矩阵，逐行（或逐列）逐个记录代码，可以每行都格数据看作一个数据矩阵，逐行（或逐列）逐个记录代码，可以每行都从左到右逐个像元记录，也可以奇数行从左到右而偶数行从右到左记录。从左到右逐个像元记录，也可以奇数行从左到右而偶数行从右到左记录。一些常用的栅格排列顺序 q 压

25、缩数据编码：压缩数据编码：分辨率与存储单元示意图(a)(b)栅格文件一般都很大，为了节省存储空间，就必须栅格文件一般都很大，为了节省存储空间，就必须对栅格数据进行压缩。对栅格数据进行压缩。（1 1）链码（链码（Chain CodesChain Codes）（2 2）游程长度编码游程长度编码 （3 3）常规四叉树编码常规四叉树编码 （4 4）线性四叉树编码线性四叉树编码压缩数据编码压缩数据编码（1 1）链码（）链码（Chain CodesChain Codes）链式编码又称为弗里曼链码链式编码又称为弗里曼链码(Freeman)(Freeman)或边界链码。或边界链码。任意一条线都可用链码串序列表

26、示为：任意一条线都可用链码串序列表示为：（i，j）a a1 1 a a2 2 a a3 3 a an n 0a 0ai i77链码的例子，链码表示为：链码的例子，链码表示为：A（i，j）07655700110765570011 压缩数据编码压缩数据编码（2）游程长度编码（）游程长度编码（Run-Length Codes)游程编码示意图 把把具具有有相相同同属属性性值值的的邻邻近近栅栅格格单单元元合合并并在在一一起起，合合并并一一次次称称为为一一个个游游程程。游游程程用用一一对对数数字字表表达达，第第一一个个值值表表示示游游程程长长度度，第第二二个个值值表表示示游游程程属属性性值值。每每一一个个

27、新新行行都都以以一一个个新新的的游游程程开开始始。表表达达游游程程长长度度的的位位数数取取决决于于栅栅格格区区域域的的列列数数，游游程程属属性性值值则则取取决决于于栅格区域属性的最大类别数（分类的级别数）。栅格区域属性的最大类别数（分类的级别数）。（3）常规四叉树编码）常规四叉树编码压缩数据编码压缩数据编码四叉树分割 基本思想：基本思想：四叉树将整个图像区逐步分解为一系列被单一四叉树将整个图像区逐步分解为一系列被单一类型区域内含的方形区域，最小的方形区域为一个栅格象元。类型区域内含的方形区域，最小的方形区域为一个栅格象元。四叉树编码 在常规四叉树中，为了保证四叉树能不断地进行下去，在常规四叉树

28、中，为了保证四叉树能不断地进行下去，要求图像必须为要求图像必须为2 2n n 2 2n n 的栅格阵列，的栅格阵列，n n为极限分割数，为极限分割数，n+1n+1为四叉树最大高度或最大层数。上图为为四叉树最大高度或最大层数。上图为为为2323的栅的栅格，因此最多划分三次，最大层数为格，因此最多划分三次，最大层数为4。常规四叉树的特点：常规四叉树的特点：（1 1）运算量较大。运算量较大。（2 2）占用的存储空间较大。占用的存储空间较大。链码链码的压缩效率较高，已经近矢量结构，对边界的运算比的压缩效率较高，已经近矢量结构，对边界的运算比较方便，但不具有区域的性质，区域运算困难；较方便，但不具有区域

29、的性质，区域运算困难；游程长度编码游程长度编码既可以在很大程度上压缩数据，又最大限度既可以在很大程度上压缩数据，又最大限度地保留了原始栅格结构，编码解码十分容易；地保留了原始栅格结构，编码解码十分容易；四叉树码四叉树码具有区域性质，又具有可变的分辨率，有较高的具有区域性质，又具有可变的分辨率，有较高的压缩效率。压缩效率。压缩数据编码压缩数据编码三、矢量数据结构及其编码三、矢量数据结构及其编码1.定义定义矢量数据结构矢量数据结构是通过记录坐标的方式，是通过记录坐标的方式，尽可能地将点、线、面地理实体表现得精确尽可能地将点、线、面地理实体表现得精确无误。其坐标空间假定为连续空间，不必像无误。其坐标

30、空间假定为连续空间，不必像栅格数据结构那样进行量化处理。因此矢量栅格数据结构那样进行量化处理。因此矢量数据能更精确地定义位置、长度和大小。数据能更精确地定义位置、长度和大小。矢量结构的特点：矢量结构的特点：定位明显、属性隐含。定位明显、属性隐含。点点实实体体，矢矢量量结结构构中中只只记记录录其其在在特特定定坐坐标标系系下下的的坐坐标标和和属属性性代码；代码；线实体线实体，就是用一系列足够短的直线首尾相接表示一条曲就是用一系列足够短的直线首尾相接表示一条曲线线，当当曲曲线线被被分分割割成成多多而而短短的的线线段段后后，这这些些小小线线段段可可以以近近似似地地看看成成直直线线段段，而而这这条条曲曲

31、线线也也可可以以足足够够精精确确地地由由这这些些小小直直线线段段序序列列表表示示，矢矢量量结结构构中中只只记记录录这这些些小小线线段段的的端端点点坐坐标标，将将曲曲线线表表示示为为一一个个坐坐标标序序列列，坐坐标标之之间间认认为为是是以以直直线线段段相相连连，在在一一定定精精度度范范围围内内可可以以逼逼真真地表示各种形状的线状地物；地表示各种形状的线状地物；“多多边边形形”在在地地理理信信息息系系统统中中是是指指一一个个任任意意形形状状、边边界界完完全全闭闭合合的的空空间间区区域域。其其边边界界将将整整个个空空间间划划分分为为两两个个部部分分：包包含含无无穷穷远远点点的的部部分分称称为为外外部

32、部，另另一一部部分分称称为为多多边边形形内内部部。区区域域的的边边界界线线，可可被被看看作作是是由由一一系系列列多多而而短短的的直直线线段段组组成成，每每个个小小线线段段作作为为这这个个区区域域的一条边，因此这种区域就可以看作是由这些边组成的多边形了。的一条边，因此这种区域就可以看作是由这些边组成的多边形了。2.2.矢量数据结构的编码方法矢量数据结构的编码方法点点实实体体 对于点实体和线实体的矢量编对于点实体和线实体的矢量编码比较直接，只要能将空间信息和码比较直接，只要能将空间信息和属性信息记录完全就可以了。属性信息记录完全就可以了。线实体 唯一标识码唯一标识码线标识码线标识码起始点起始点终止

33、点终止点坐标对序列坐标对序列显示信息显示信息非几何属性非几何属性线实体线实体 多边形矢量编码，不但要表示位置和属性，更多边形矢量编码，不但要表示位置和属性，更重要的是能表达区域的重要的是能表达区域的拓扑特征拓扑特征，如形状、邻域和，如形状、邻域和层次结构等，以便使这些基本的空间单元可以作为层次结构等，以便使这些基本的空间单元可以作为专题图的资料进行显示和操作。专题图的资料进行显示和操作。（1 1）坐标序列法）坐标序列法（2 2）树状索引编码法）树状索引编码法多多边边形形（1）坐标序列法：坐标序列法：由由多边形边界的多边形边界的x、y坐标对集合坐标对集合及说明信息组成，是最简单的及说明信息组成，

34、是最简单的一种多边形矢量编码一种多边形矢量编码。坐标序列法表示的多边形 1 10 0：x1,y1；x2,y2；x3,y3；x4,y4；x5,y5；x6,y6；x7,y7；x8,y8；x9,y9；x10,y10；x11,y11；2 20 0：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；3 30 0：x33,y33；x34,y34；x35,y35；x36,y36；x37,y37；x38

35、,y38；x39,y39；x40,y40；4 40 0：x19,y19；x20,y20；x21,y21；x28,y28；x29,y29；x30,y30；x31,y31；x32,y32；5 50 0：x21,y21；x22,y22；x23,y23；x8,y8；x7,y7；x6,y6；x24,y24；x25,y25；x26,y26；x27,y27；x28,y28；多多边边形形 坐标序列法文件结构简单，缺点：坐标序列法文件结构简单，缺点：（1 1）多边形之间的公共边界被数字化和存储两多边形之间的公共边界被数字化和存储两次，由此产生冗余和碎屑多边形；次，由此产生冗余和碎屑多边形；（2 2）每个多边形自

36、成体系而缺少邻域信息，难以）每个多边形自成体系而缺少邻域信息，难以进行邻域处理，如消除某两个多边形之间的共同边界；进行邻域处理，如消除某两个多边形之间的共同边界；（3 3）岛只作为一个单个的图形建造，没有与外包）岛只作为一个单个的图形建造，没有与外包多边形的联系；多边形的联系；（4 4）不易检查拓扑错误。这种方法可用于简单的）不易检查拓扑错误。这种方法可用于简单的粗精度制图系统中。粗精度制图系统中。（2）树状索引编码法树状索引编码法：减少数据冗余并间减少数据冗余并间接增加邻域信息，方法是对所有边界点进行数字接增加邻域信息，方法是对所有边界点进行数字化，将坐标对以顺序方式存储，由点索引与边界化，

37、将坐标对以顺序方式存储，由点索引与边界线号相联系，以线索引与各多边形相联系，形成线号相联系，以线索引与各多边形相联系，形成树状索引结构。树状索引结构。线与多边形之间的树状索引点与边界线之间的树状索引 多多边边形形 线线号号起起点点终终点点点点号号I161,2,3,4,5,6II686,7,8X333333,34,35,36,37,38,39,40,33多边形文件：多边形文件：点文件：点文件：点号坐标点号坐标x1，y1x2，y240 x40，y40线文件：线文件：多边形编号多边形编号多边形边界多边形边界10I,II,IX20III,VII,VIII,IX,X30X40IV,VI,VII50II,

38、III,IV,V 树状索引编码消树状索引编码消除了相邻多边形边界除了相邻多边形边界的数据冗余和不一致的数据冗余和不一致的问题的问题。图形目标范围示意图 首先对图形区域网格化，然后分别计算包围首先对图形区域网格化，然后分别计算包围图形实体的矩形区域左下角、右上角所在网格图形实体的矩形区域左下角、右上角所在网格的标识。对图形实体的标识。对图形实体A A而言，它的标识为（而言，它的标识为（6 6，3 3）、（）、（1111，7 7）。）。（3）拓扑结构编码法：）拓扑结构编码法：要彻底解决邻域和岛状信息要彻底解决邻域和岛状信息处理问题必须建立一个完整的拓扑关系结构处理问题必须建立一个完整的拓扑关系结构

39、。在下面将要介绍的数据结构中，用在下面将要介绍的数据结构中，用(LX,LY)(LX,LY)，(RX,RY)(RX,RY)分别表示矩形区域左下角、右上角的网格标识。分别表示矩形区域左下角、右上角的网格标识。(1)特殊点的数据结构特殊点的数据结构 在在GISGIS中，特殊点指钻孔、井下实测点、注记分隔线端点中，特殊点指钻孔、井下实测点、注记分隔线端点等点状图形目标，它们一般不与线状目标发生联系，但可能等点状图形目标，它们一般不与线状目标发生联系，但可能被某一多边形所包围。被某一多边形所包围。表1 特殊点的数据结构(2)结点的数据结构结点的数据结构 表2 特殊点的数据结构 由于与结点相关的弧由于与结

40、点相关的弧段数是不确定的，所以，在段数是不确定的，所以，在数据结构中加入了标识弧段数据结构中加入了标识弧段数的字段。数的字段。(3)一般线段的数据结构一般线段的数据结构表3 一般线段的数据结构 一般线段为一般线段为“特特殊点殊点”的简单连接，的简单连接，所以无需表达数据点所以无需表达数据点及线段间的相关关系，及线段间的相关关系，数据结构十分简单。数据结构十分简单。(4)弧段的数据结构弧段的数据结构 表4 弧段的数据结构(5)多边形的数据结构多边形的数据结构表5 多边形的数据结构(6)剖面线的数据结构剖面线的数据结构 表6 剖面线的数据结构 剖面线任意点都有剖面线任意点都有(x,y)(x,y)和

41、地和地层的厚度。另外，由于剖面线不层的厚度。另外，由于剖面线不可能无限地延长，所以，它的两可能无限地延长，所以，它的两端都将被其它图形实体所限制。端都将被其它图形实体所限制。这些图形实体可能有：断层，冲这些图形实体可能有：断层，冲刷带，火成岩，图形边界等。刷带，火成岩，图形边界等。剖面线示意图 第四节 两种数据结构的比较与转换1.比比较较优优点点缺缺点点矢矢量量数数据据1表示地理数据的精度较高表示地理数据的精度较高2.严密的数据结构，数据量小严密的数据结构，数据量小3有利于网有利于网络络和和检检索分析索分析4图图形形显显示示质质量好、精度高量好、精度高5.图形数据和属性数据的恢复、图形数据和属

42、性数据的恢复、更新、综合都能实现更新、综合都能实现6.面向目标，不仅能表达属性，而面向目标，不仅能表达属性，而且能方便的记录每个目标的具体属且能方便的记录每个目标的具体属性信息。性信息。1.数据数据结结构复构复杂杂2.多多边边形叠加分析比形叠加分析比较较困困3.数学模拟比较困难数学模拟比较困难4.技术复杂，特别是软硬件技术复杂，特别是软硬件 栅栅格格数据数据1数据数据结结构构简单简单2便于空便于空间间分析和地表模分析和地表模拟拟3现势现势性性较较强强4.数学模拟方便数学模拟方便1数据量大数据量大2投影投影转换转换比比较较复复杂杂3.用大像元减少数据量时，用大像元减少数据量时，精度和信息量受损精

43、度和信息量受损4.地图输出不美观地图输出不美观5.难以建立网络连接关系难以建立网络连接关系（1）矢量向栅格的转换矢量向栅格的转换 矢量向栅格的转换过程叫矢量向栅格的转换过程叫“栅格化栅格化”。从矢量。从矢量向栅格转换过程中，应尽量保持矢量图形的精度。向栅格转换过程中，应尽量保持矢量图形的精度。矢量向栅格格式转换的几种主要算法：矢量向栅格格式转换的几种主要算法：内部点扩散法内部点扩散法复数积分算法复数积分算法射线算法射线算法扫描算法扫描算法边界代数算法边界代数算法2.栅格与矢量数据结构的选择与转换栅格与矢量数据结构的选择与转换 内部点扩散法内部点扩散法 该算法由每个多边形一个内部点（种子该算法由

44、每个多边形一个内部点（种子点）开始，向其八个方向的邻点扩散，判断点）开始，向其八个方向的邻点扩散，判断各个新加入点是否在多边形边界上，如果是各个新加入点是否在多边形边界上，如果是边界上，则该新加入点不作为种子点，否则边界上，则该新加入点不作为种子点，否则把非边界点的邻点作为新的种子点与原有种把非边界点的邻点作为新的种子点与原有种子点一起进行新的扩散运算，并将该种子点子点一起进行新的扩散运算，并将该种子点赋以该多边形的编号。重复上述过程直到所赋以该多边形的编号。重复上述过程直到所有种子点填满该多边形并遇到边界停止为止。有种子点填满该多边形并遇到边界停止为止。（1）矢量向栅格的转换矢量向栅格的转换

45、 复数积分算法复数积分算法 对全部栅格阵列逐个栅格单元地对全部栅格阵列逐个栅格单元地判断该栅格归属的多边形编码，判别方判断该栅格归属的多边形编码，判别方法是由待判点对每个多边形的封闭边界法是由待判点对每个多边形的封闭边界计算复数积分，对某个多边形，如果积计算复数积分，对某个多边形，如果积分值为分值为2 r，则该待判点属于此多边形，则该待判点属于此多边形，赋以多边形编号，否则在此多边形外部，赋以多边形编号，否则在此多边形外部，不属于该多边形。不属于该多边形。（1）矢量向栅格的转换矢量向栅格的转换 射线算法射线算法 射线算法可逐点判断数据栅格点在某多边射线算法可逐点判断数据栅格点在某多边形之外或在

46、多边形内，由待判点向图外某点引形之外或在多边形内，由待判点向图外某点引射线，判断该射线与某多边形所有边界相交的射线，判断该射线与某多边形所有边界相交的总次数，如相交偶数次，则待判点在该多边形总次数，如相交偶数次，则待判点在该多边形外部，如为奇数次，则待判点在该多边形内部。外部，如为奇数次，则待判点在该多边形内部。射线算法射线算法 射线算法的特殊情况射线算法的特殊情况 扫描算法扫描算法 扫描算法是射线算法的改进，将射线扫描算法是射线算法的改进，将射线改为沿栅格阵列列或行方向扫描线，判断改为沿栅格阵列列或行方向扫描线，判断与射线算法相似。扫描算法省去了计算射与射线算法相似。扫描算法省去了计算射线与

47、多边形边界交点的大量运算，大大提线与多边形边界交点的大量运算，大大提高了效率。高了效率。边界代数算法边界代数算法 适合于记录拓扑关系的多边形矢量数适合于记录拓扑关系的多边形矢量数据转换为栅格结构。据转换为栅格结构。单个多边形的转换 多个多边形的转换栅格格式向矢量格式转换的基本步骤：栅格格式向矢量格式转换的基本步骤：（1）二值化：二值化：为了简化追踪算法，需把为了简化追踪算法，需把256256个灰阶压缩为个灰阶压缩为2 2个灰阶，即个灰阶，即0 0和和1 1两级。两级。（2）细化：细化：细化是消除线划横断面栅格数的差异，使得每一条线细化是消除线划横断面栅格数的差异，使得每一条线只保只保留代表其轴

48、线或周围轮廓线（对多边形而言）位置的单个栅格的宽度。留代表其轴线或周围轮廓线（对多边形而言）位置的单个栅格的宽度。（3）跟踪：跟踪：跟踪的目的是把细化后的栅格数据整理为从结点出发跟踪的目的是把细化后的栅格数据整理为从结点出发的线的线段或闭合的线条，并以矢量形式加以存储。段或闭合的线条，并以矢量形式加以存储。（4）去除多余点及曲线圆滑：）去除多余点及曲线圆滑：由于搜索是逐个栅格进行的，必须去除由由于搜索是逐个栅格进行的，必须去除由此造成的多余点记录，以减少数据冗余此造成的多余点记录，以减少数据冗余。（5）拓扑关系的生成：）拓扑关系的生成：判断弧段与多边形间的空间关系，以形成完整的判断弧段与多边形

49、间的空间关系，以形成完整的拓扑结构并建立与属性数据的关系。拓扑结构并建立与属性数据的关系。（2）栅格向矢量的转换）栅格向矢量的转换 从栅格单元转换到几何图形的过程，通常称为矢量化。从栅格单元转换到几何图形的过程，通常称为矢量化。矢量化过程要保证以下两点：矢量化过程要保证以下两点：（1 1）拓扑转换，即保持栅格表示）拓扑转换，即保持栅格表示出的连通性与邻接性；（出的连通性与邻接性；（2 2）转换物体正确的外形。）转换物体正确的外形。第五节第五节 空间索引机制空间索引机制l 概念概念 空间索引空间索引就是指依据空间对象的就是指依据空间对象的位置和形状或空间对象之间的某位置和形状或空间对象之间的某种

50、空间关系种空间关系按一定的顺序排列的一种数据结构。作为一种辅助性的空按一定的顺序排列的一种数据结构。作为一种辅助性的空间数据结构，空间索引介于空间操作算法和空间对象之间，通过筛选间数据结构，空间索引介于空间操作算法和空间对象之间，通过筛选作用，提高空间操作的速度和效率。作用，提高空间操作的速度和效率。空间索引性能的优劣直接影响空间数据库和地理信息系统的整体空间索引性能的优劣直接影响空间数据库和地理信息系统的整体性能，是一项关键技术。性能，是一项关键技术。l 索引类型索引类型 格网型空间索引格网型空间索引 BSP树空间索引树空间索引 KDB树空间索引树空间索引 R树和树和R+树树 CELL树树B