《空间数据管理》PPT课件.ppt

《《空间数据管理》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《空间数据管理》PPT课件.ppt（102页珍藏版）》请在三一办公上搜索。

1、空间数据管理,本章首先介绍空间数据库、与一般数据库的比较，以及空间数据库的存储方式。然后介绍了GIS中两种重要的数据结构：栅格结构和矢量结构，以及其具体的存储方式，然后比较了两种结构的特点，并给出了其相互转换算法。最后介绍了空间检索中常用的技术空间索引，介绍了一些常用的空间索引方式，如BSP树、R树、CELL树等；以及空间数据的查询功能。,1.空间数据库1.1地理信息系统与一般管理信息系统的比较,(一)两者区别 1）在硬件上，为了处理图形和图像数据，系统需要配置专门的输入和输出设备，如数字化仪、绘图机、图形图像的显示设备等；许多野外实地采集和台站的观测所得到的资源信息是模拟量形式，系统还需要配

2、置模数转换设备，这些设备往往超过中央处理机的价格，体积也比较大。2）在软件上，则要求研制专门的图形和图像数据的分析算法和处理软件，这些算法和软件又直接和数据的结构及数据库的管理方法有关。,1.空间数据库1.1地理信息系统与一般管理信息系统的比较,3）在信息处理的内容和采用目的方面，一般的管理信息系统，主要是查询检索和统计分析，处理的结果，大多是制成某种规定格式的表格数据，而地理信息系统，除了基本的信息检索和统计分析外，主要用于分析研究资源的合理开发利用，制定区域发展规划，地区的综合治理方案，对环境进行动态的监视和预测预报，为国民经济建设中的决策提供科学依据，为生产实践提供信息和指导。,1.空间

3、数据库1.1地理信息系统与一般管理信息系统的比较,(二)两者共同处两者都是以计算机为核心的信息处理系统，都具有数据量大和数据之间关系复杂的特点，也都随着数据库技术的发展在不断的改进和完善。比较起来，商用的管理信息系统发展快，用户数量大，而且已有定型的软件产品可供选用，这也促进了软件系统的标准化。地理信息系统，由于上述一些特点，多是根据具体的应用要求专门设计，数据格式和组织管理方法各不相同。,1.空间数据库1.2空间数据库,(一)数据库概念数据库就是为一定目的服务，以特定的数据存储的相关联的数据集合，它是数据管理的高级阶段，是从文件管理系统发展而来的。地理信息系统的数据库（简称空间数据库或地理数

4、据库）是某一区域内关于一定地理要素特征的数据集合。,1.空间数据库1.2空间数据库,(一)空间数据库特点数据量特别大；不仅有地理要素的属性数据（与一般数据库中的数据性质相似），还有大量的空间数据；数据应用广泛；,1.空间数据库1.2空间数据库,(三)数据库管理系统数据库管理系统（Database Management System，DBMS）是在文件处理系统的基础上进一步发展的系统。DBMS在用户应用程序和数据文件之间起到了桥梁作用。DBMS的最大优点是提供了两者之间的数据独立性，即应用程序访问数据文件时，不必知道数据文件的物理存储结构。当数据文件的存储结构改变时，不必改变应用程序。,1.空间

5、数据库1.2空间数据库,1)采用标准DBMS存储空间数据的主要问题 GIS中空间数据记录是变长的，且要存储和维护空间数据拓扑关系；DBMS一般都难以实现对空间数据的关联、连通、包含、叠加等基本操作。GIS需要一些复杂的图形功能，一般的DBMS不能支持；地理信息是复杂的，单个地理实体的表达需要多个文件、多条记录、或许包括大地网、特征坐标、拓扑关系、空间特征量测值、属性数据的关键字以及非空间专题属性等；具有高度内部联系的GIS数据记录需要更复杂的安全性维护系统。,1.空间数据库1.2空间数据库,2)GIS数据管理方法主要4种类型对不同的应用模型开发独立的数据管理服务，这是一种基于文件管理的处理方法

6、。在商业化的DBMS基础上开发附加系统。开发一个附加软件用于存储和管理空间数据和空间分析，使用DBMS管理属性数据。使用现有的DBMS，通常是以DBMS为核心，对系统的功能进行必要扩充，空间数据和属性数据在同一个DBMS管理之下。需要增加足够数量的软件和功能来提供空间功能和图形显示功能。重新设计一个具有空间数据和属性数据管理和分析功能的数据库系统。,1.空间数据库1.3数据与文件组织,(一)数据组织分级数据项数据项是可以定义数据的最小单位，也叫元素、基本项、字段等，数据项与现实世界实体的属性相对应，数据项有一定的取值范围，称为域，域以外的任何值对该数据项都是无意义的。记录记录是由若干相关联的数

7、据项组成，是处理和存储信息的基本单位，是关于一个实体的数据总和，构成该记录的数据项表示实体的若干属性。为了唯一标识每个记录，就必须有记录标识符，也叫关键字。记录标识符一般由记录中的第一个数据项担任，唯一标识记录的关键字称主关键字，其它标识记录的关键字称为辅关键字。,1.空间数据库1.3数据与文件组织,文件文件是一给定类型的（逻辑）记录的全部具体值的集合，文件用文件名称标识，文件根据记录的组织方式和存取方法可以分为：顺序文件、索引文件、直接文件和倒排文件等。数据库数据库是比文件更大的数据组织，数据库是具有特定联系的数据的集合，也可以看成是具有特定联系的多种类型的记录的集合。数据库的内部构造是文件

8、的集合，这些文件之间存在某种联系，不能孤立存在。,1.空间数据库1.3数据与文件组织,(二)数据间的逻辑联系 数据间的逻辑联系主要是指记录与记录之间的联系。记录是表示现实世界中的实体的。实体之间存在着一种或多种联系，这样的联系必然要反映到记录之间的联系上来。数据之间的逻辑联系主要有三种：一对一的联系；一对多的联系；多对多的联系。,1.空间数据库1.3数据与文件组织,(三)常用数据文件文件组织主要指数据记录在外存设备上的组织，它由操作系统OS进行管理，具体讲在外存设备上如何安排数据和组织数据，以及实施对数据的访问方式等问题。操作系统实现的文件组织方式，可以分为顺序文件、索引文件、直接文件和倒排文

9、件。,1.空间数据库1.3数据与文件组织,顺序文件是最简单的文件组织形式，对记录按照主关键字的顺序进行组织。索引文件索引文件除了存储记录本身（主文件）以外，还建立了若干索引表，这种带有索引表的文件叫索引文件。索引表中列出记录关键字和记录在文件中的位置（地址）。,1.空间数据库1.3数据与文件组织,直接文件 直接文件又称随机文件，其存储是根据记录关键字的值，通过某种转换方法得到一个物理存储位置，然后把记录存储在该位置上。查找时，通过同样的转换方法，可以直接得到所需要的记录。倒排文件倒排文件是带有辅索引的文件，其中辅索引是按照一些辅关键字来组织索引的。倒排文件的主要优点是在处理多索引检索时，可以在

10、辅检索中先完成查询的交、并等逻辑运算，得到结果后再对记录进行存取，从而提高查找速度。,1.空间数据库1.4矢量和栅格数据结构,矢量数据模型在矢量模型中，现实世界的要素位置和范围可以采用点、线或面表达，与它们在地图上表示相似，每一个实体的位置是用它们在坐标参考系统中的空间位置（坐标）定义。栅格数据模型在栅格模型中，空间被规则地划分为栅格（通常为正方形）。地理实体的位置和状态是用它们占据的栅格的行、列来定义的。每个栅格的大小代表了定义的空间分辨率。,1.空间数据库1.4矢量和栅格数据结构,1.空间数据库1.4矢量和栅格数据结构,2.栅格数据结构及其编码 2.1栅格数据结构,(一)定义栅格结构是最简

11、单最直接的空间数据结构，是指将地球表面划分为大小均匀紧密相邻的网格阵列，每个网格作为一个象元或象素由行、列定义，并包含一个代码表示该象素的属性类型或量值，或仅仅包括指向其属性记录的指针。点用一个栅格单元表示；线状地物沿线走向的一组相邻栅格单元表示，每个栅格单元最多只有两个相邻单元在线上；面或区域用记有区域属性的相邻栅格单元的集合表示，每个栅格单元可有多于两个的相邻单元同属一个区域。,2.栅格数据结构及其编码 2.1栅格数据结构,（a）点（b）线（c）面,2.栅格数据结构及其编码 2.1栅格数据结构,(二)特点栅格结构的显著特点是：属性明显；定位隐含；易于存储；算法简单；地表是不连续，是量化和近

12、似离散的数据。,2.栅格数据结构及其编码 2.2决定栅格单元代码的方法,在决定栅格代码时尽量保持地表的真实性，保证最大的信息容量。图7-5所示的一块矩形地表区域，内部含有A、B、C三种地物类型，O点为中心点，将这个矩形区域近似地表示为栅格结构中的一个栅格单元时，可根据需要，采取如下的方式之一来决定栅格单元的代码。,2.栅格数据结构及其编码 2.2决定栅格单元代码的方法,中心点法用处于栅格中心处的地物类型或现象特性决定栅格代码，在图7-5所示的矩形区域中，中心点O落在代码为C的地物范围内，按中心点法的规则，该矩形区域相应的栅格单元代码为C，中心点法常用于具有连续分布特性的地理要素，如降雨量分布、

13、人口密度图等。面积占优法以占矩形区域面积最大的地物类型或现象特性决定栅格单元的代码，在图7-5所示的例子中，显见B类地物所占面积最大，故相应栅格代码定为B。面积占优法常用于分类较细，地物类别斑块较小的情况。,2.栅格数据结构及其编码 2.2决定栅格单元代码的方法,重要性法根据栅格内不同地物的重要性，选取最重要的地物类型决定相应的栅格单元代码，假设图7-5中A类最重要的地物类型，即A比B和C类更为重要，则栅格单元的代码应为A。重要性法常用于具有特殊意义而面积较小的地理要素，特别是点、线状地理要素，如城镇、交通枢纽、交通线、河流水系等，在栅格中代码应尽量表示这些重要地物。百分比法(长度占优法)根据

14、矩形区域内各地理要素所占面积的百分比数确定栅格单元的代码，如可记面积最大的两类BA，也可以根据B类和A类所占面积百分比数在代码中加入数字,2.栅格数据结构及其编码 2.3编码方法,(一)直接栅格编码这是最简单直观而又非常重要的一种栅格结构编码方法，通常称这种编码的图像文件为网格文件或栅格文件，栅格结构不论采用何种压缩编码方法，其逻辑原型都是直接编码网格文件。直接编码就是将栅格数据看作一个数据矩阵，逐行（或逐列）逐个记录代码，可以每行都从左到右逐个象元记录，也可以奇数行地从左到右而偶数行地从右向左记录，为了特定目的还可采用其他特殊的顺序。,AAAAABBBAABBAABB,2.栅格数据结构及其编

15、码 2.3编码方法,2.栅格数据结构及其编码 2.3编码方法,(二)压缩编码方法 目前有一系列栅格数据压缩编码方法，如链码、游程长度编码、块码和四叉树编码等。其目的，就是用尽可能少的数据量记录尽可能多的信息，其类型又有信息无损编码和信息有损编码之分。信息无损编码是指编码过程中没有任何信息损失，通过解码操作可以完全恢复原来的信息，信息有损编码是指为了提高编码效率，最大限度地压缩数据，在压缩过程中损失一部分相对不太重要的信息，解码时这部分难以恢复。在地理信息系统中多采用信息无损编码，而对原始遥感影像进行压缩编码时，有时也采取有损压缩编码方法。,2.栅格数据结构及其编码 2.3编码方法,链码链码又称

16、为弗里曼链码Freeman或边界链码，链码可以有效地压缩栅格数据，而且对于估算面积、长度、转折方向的凹凸度等运算十分方便，比较适合于存储图形数据。缺点是对边界进行合并和插入等修改编辑工作比较困难，对局部的修改将改变整体结构，效率较低,(3,0)21100066567,2.栅格数据结构及其编码 2.3编码方法,游程长度编码地理数据往往有较强的相关性，也就是说相邻像元的值往往是相同的。游程长度编码的基本思想是：按行或列扫描，将相邻等值的像元合并，并记录代码的重复个数。其方法有两种方案：一种编码方案是，只在各行（或列）数据的代码发生变化时依次记录该代码以及相同的代码重复的个数。,2.栅格数据结构及其

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

18、（3，8），（8，0）；（1，7），（3，8）；（1，7），（6，8）；（1，7），（5，8）,2.栅格数据结构及其编码 2.3编码方法,游程长度编码在栅格压缩时，数据量没有明显增加，压缩效率较高，且易于检索，叠加合并等操作，运算简单，适用于机器存储容量小，数据需大量压缩，而又要避免复杂的编码解码运算增加处理和操作时间的情况。,2.栅格数据结构及其编码 2.3编码方法,块状编码块码是游程长度编码扩展到二维的情况，采用方形区域作为记录单元，每个记录单元包括相邻的若干栅格，数据结构由初始位置(行、列号)和半径，再加上记录单元的代码组成。,(1,1,2,9),(1,3,1,9),(1,4,1,9),

19、(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编码方法,（a）块码分割（b）四叉树分割,2.栅格数据结构及其编码 2.3编码方法,四叉树基本思想：四叉树将整个图像区逐步分解为一系列被单一类型区域内含的方形区域，最小的方形区域为一个栅格象元，分割的原则是，将图像区域划分为四个大小相同的象限，而每

20、个象限又可根据一定规则判断是否继续等分为次一层的四个象限，其终止判据是，不管是哪一层上的象限，只要划分到仅代表一种地物或符合既定要求的少数几种地物时，则不再继续划分，否则一直划分到单个栅格象元为止。,2.栅格数据结构及其编码 2.3编码方法,定义：将2n2n像元阵列连续地进行4象限等分，一直分到子象限中像素值单调为止，这查即形成一颗四分叉的倒向树。根：整个区域；高：深度、分几级，几次分割；叶：不能再分割的块；树叉：还需分割的块；每个树叉均有4个分叉，叫四叉树。,2.栅格数据结构及其编码 2.3编码方法,编码方法1)常规四叉树记录这棵树的叶结点外，中间结点，结点之间的联系用指针联系，每个结点需要

21、6个变量：父结点指针、四个子结点的指针和本结点的属性值。指针不仅增加了数据的存储量，还增加了操作的复杂性：如层次数（分割次数）由从父结点移到根结点的次数来确定，结点所代表的图像块的位置需要从根节点开始逐步推算下来。所以，常规四叉树并不广泛用于存储数据，其价值在于建立索引文件，进行数据检索。,2.栅格数据结构及其编码 2.3编码方法,2)线性四叉树记录叶结点的位置，深度（几次分割）和属性。地址码：定位码、Morton码（加拿大学者Morton于1966年提出）四进制、十进制。其具有以下优点：存贮量小，只对叶结点编码，节省了大量中间结点的存储，地址码隐含着结点的分割路径和分割次数。线性四叉树可直接

22、寻址，通过其坐标值直接计算其Morton码，而不用建立四叉树。定位码容易存储和执行实现集合相加等组合操作。,2.栅格数据结构及其编码 2.3编码方法,四进制的Morton码1、方法1：四叉树从上而下（形成）（从整体开始）由叶结点找Morton码。A、分割一次，增加一位数字，大分割在前，小分割在后。所以，码的位数表示分割的次数。B、每一个位均是不大于3的四进制数，表达位置。由Morton找出四叉树叶结点的具体位置。,03,B,A,2.栅格数据结构及其编码 2.3编码方法,1）计算每个栅格对应的MQ MQ=2*Ib+Jb I,J化为二进制Ib,Jb 看最大的I,J,不足在前补零。其始行列号从0计。

23、2)按码的升序排成线性表，放在连续的内存块中。3）依次检查每四个相邻的MQ对应的属性值，相同合并（不同码位去掉），不同则存盘,直到没有能够合并的子块为止。,2.栅格数据结构及其编码 2.3编码方法,2.栅格数据结构及其编码 2.3编码方法,十进制的Morton码-MD,四进制Morton码直观上切合四叉树分割，但许多语言不支持四进制变量，需用十进制表示Morton码.,1、一种按位操作的方法：如行为2、列为3的栅格的MD步骤：(1)行、列号为二进制 Ib=1 0 Jb=1 1(2)I行J列交叉 1 1 0 1=13(3)再化为十进制.实质上是按左上、右上、左下、右下的顺序，从零开始对每个栅格进

24、行自然编码。,2.栅格数据结构及其编码 2.3编码方法,4.把一幅2n2n的图像压缩成线性四叉树的过程 1、按Morton码把图象读入一维数组。2、相邻的四个象元比较，一致的合并，只记录第一个象元的Morton码。循环比较所形成的大块，相同的再合并，直到不能合并为止。3、进一步用游程长度编码压缩。压缩时只记录第一个象元的Morton码。,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

25、B2、四相邻象元合并，只记录第一个象元的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,2.栅格数据结构及其编码 2.3编码方法,采用四叉树编码时，为了保证四叉树分解能不断地进行下去，要求图像必须为2n2n的栅格阵列，n为极限分割数，n+1为四叉树的最大高度或最大层数，图7-4（c）为2323的栅格，因此最多划分三次，最大层数为4，对于非标准尺寸的图像需首先通过增加背景的方法将图像扩充为2n2n的图像。,（a）点（b）线（c）面图7-4：点、线、区域的

26、格网,2.栅格数据结构及其编码 2.3编码方法,四叉树编码具有可变的分辨率，并且有区域性质，压缩数据灵活，许多运算可以在编码数据上直接实现，大大地提高了运算效率，是优秀的栅格压缩编码之一。好的压缩编码方法就是要在尽可能减少运算时间的基础上达到最大的数据压缩效率，并且是算法适应性强，易于实现。链码的压缩效率较高，已经近矢量结构，对边界的运算比较方便，但不具有区域的性质，区域运算困难；游程长度编码既可以在很大程度上压缩数据，又最大限度地保留了原始栅格结构，编码解码十分容易；块码和四叉树码具有区域性质，又具有可变的分辨率，有较高的压缩效率，四叉树编码可以直接进行大量图形图像运算，效率较高，是很有前途

27、的方法。,3.矢量数据结构及其编码 3.1矢量数据结构,矢量数据结构是最常见的图形数据结构，是一种面向目标的数据组织方式。矢量方法强调离散现象的存在，将线离散为一串采样点的坐标串，面状区域由边界线确定。由于矢量数据结构具有结构紧凑，冗余度低，利于网络、检索分析等优点，是GIS主要的数据存储结构之一。(一)定义点实体：记录点坐标和属性代码；线实体：记录两个或一系列采样点的坐标，并加属性代码；面实体：记录边界上一系列采样点的坐标，由于多边形封闭，边界为闭合环，加面域属性代码。,3.矢量数据结构及其编码 3.1矢量数据结构,(二)特点矢量结构的特点是：定位明显、属性隐含，其定位是根据坐标直接存储的，

28、而属性则一般存于文件头或数据结构中某些特定的位置上，这种特点使得其图形运算的算法总体上比栅格数据结构复杂的多，有些甚至难以实现，当然有些地方也有所便利和独到之处，在计算长度、面积、形状和图形编辑、几何变换操作中，矢量结构有很高的效率和精度，而在叠加运算、邻域搜索等操作时则比较困难。,3.矢量数据结构及其编码 3.2编码方法,(一)点实体对于点实体和线实体的矢量编码比较直接，只要能将空间信息和属性信息记录完全就可以了。点是空间上不能再分的地理实体，可以是具体的或抽象的，如地物点、文本位置点或线段网络的结点等，由一对x、y坐标表示。(二)线实体线实体主要用来表示线状地物（如公路、水系、山脊线等）符

29、号线和多边形边界，有时也称为“弧”、“链”、“串”等，其矢量编码一般:唯一标识码是系统排列序号；线标识码可以标识线的类型；起始点和终止点号可直接用坐标表示；显示信息是显示时的文本或符号等；与线相联系的非几何属性可以直接存储于线文件中，也可单独存储，而由标识码联接查找。由一串x、y坐标表示,3.矢量数据结构及其编码 3.1矢量数据结构,3.矢量数据结构及其编码 3.2编码方法,(三)多边形实体多边形矢量编码不但要表示位置和属性，更为重要的是要能表达区域的拓扑性质，如形状、邻域和层次等，以便使这些基本的空间单元可以作为专题图资料进行显示和操作，由于要表达的信息十分丰富，基于多边形的运算多而复杂，因

30、此多边形矢量编码比点和线实体的矢量编码要复杂得多，也更为重要。,3.矢量数据结构及其编码 3.2编码方法,1)多边形实体表示坐标序列法（Spaghetti方式）,3.矢量数据结构及其编码 3.2编码方法,由多边形边界的x、y坐标对集合及说明信息组成，是最简单的一种多边形矢量编码，上图可记为以下坐标文件：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；x2

31、0,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；,3.矢量数据结构及其编码 3.2编码方法,坐

32、标序列法只记录空间对象的位置坐标和属性信息，不记录拓扑关系。无拓扑关系，主要用于显示、输出及一般查询多边形之间的公共边界被数字化和存储两次，由此产生冗余和碎屑多边形；每个多边形自成体系而缺少邻域信息，难以进行邻域处理，如消除某两个多边形之间的共同边界；岛只作为一个单个的图形建造，没有与外包多边形的联系；不易检查拓扑错误。这种方法可用于简单的粗精度制图系统中。,3.矢量数据结构及其编码 3.2编码方法,2)多边形实体表示树状索引编码法该法采用树状索引以减少数据冗余并间接增加邻域信息，方法是对所有边界点进行数字化，将坐标对以顺序方式存储，由点索引与边界线号相联系，以线索引与各多边形相联系，形成树状

33、索引结构。,3.矢量数据结构及其编码 3.2编码方法,3.矢量数据结构及其编码 3.2编码方法,点文件：,线文件：,3.矢量数据结构及其编码 3.2编码方法,多边形文件：,3.矢量数据结构及其编码 3.2编码方法,树状索引编码：消除了相邻多边形边界的数据冗余和不一致的问题；简化复杂边界线或合并相邻多边形时可不必改造索引表；邻域信息和岛状信息可以通过对多边形文件的线索引处理得到，但是比较繁琐；相邻函数运算，消除无用边，处理岛状信息以及检查拓扑关系比较困难两个编码表都需要以人工方式建立，工作量大且容易出错。,3.矢量数据结构及其编码 3.2编码方法,3)多边形实体表示拓朴结构编码法要彻底解决邻域和

34、岛状信息处理问题必须建立一个完整的拓扑关系结构，这种结构应包括以下内容：唯一标识，多边形标识，外包多边形指针，邻接多边形指针，边界链接，范围（最大和最小x、y坐标值）。采用拓扑结构编码可以较好地解决空间关系查询等问题，但增加了算法的复杂性和数据库的大小。,3.矢量数据结构及其编码 3.2编码方法,双重独立式编码法(DIMEDual lndependent Map Encoding),这种数据结构除了通过线文件生成面文件外，还需要点文件,3.矢量数据结构及其编码 3.2编码方法,链式双重独立式编码法链状双重独立式数据结构是DIME数据结构的一种改进。在DIME中，一条边只能用直线两端点的序号及相

35、邻的面域来表示，而在链状数据结构中，将若干直线段合为一个弧段（或链段），每个弧段可以有许多中间点。在链状双重独立数据结构中，主要有四个文件：多边形文件、弧段文件、弧段坐标文件、结点文件。,弧段文件弧段号起始点终结点左多边形右多边形a51OAb85EAc168EBd195OEe1519ODf1516DBg115OBh81ABi1619DEj3131BC弧段坐标文件弧段号点 号a5,4,3,2,1b8,7,6,5c16,17,8d19,18,5e15,23,22,21,20,19f15,16,g1,10,11,12,13,14,15h8,9,1i16,19j31,30,29,28,27,26,25

36、,24,31,多边形文件多边形号弧段号周长 面积 中心点坐标Ah,b,aBg,f,c,h,-jCjDe,i,fEe,i,d,b,4.矢栅结构的比较及转换算法 4.1栅格结构和矢量结构的比较,栅格结构与矢量结构似乎是两种截然不同的空间数据结构，栅格结构“属性明显、位置隐含”，而矢量结构“位置明显、属性隐含”，栅格数据操作总的来说比较容易实现，尤其是作为斑块图件的表示更易于为人们接受；而矢量数据操作则比较复杂，许多分析操作（如两张地图的覆盖操作，点或线状地物的邻域搜索等）用矢量结构实现十分困难，矢量结构表达线状地物是比较直观的，而面状地物则是通过对边界的描述而表达。,4.矢栅结构的比较及转换算法

37、4.1栅格结构和矢量结构的比较,矢量格式与栅格格式的比较,4.矢栅结构的比较及转换算法 4.2相互转换算法,(一)矢量格式向栅格格式的转换 内部点扩散算法(种子填充法)该算法由每个多边形一个内部点（种子点）开始，向其八个方向的邻点扩散，判断各个新加入点是否在多边形边界上，如果是边界上，则该新加入点不作为种子点，否则把非边界点的邻点作为新的种子点与原有种子点一起进行新的扩散运算，并将该种子点赋以该多边形的编号。复数积分算法(内角和法)对全部栅格阵列逐个栅格单元地判断该栅格归属的多边形编码，判别方法是由待判点对每个多边形的封闭边界计算复数积分，对某个多边形，如果积分值为2r，则该待判点属于此多边形

38、，赋以多边形编号，否则在此多边形外部，不属于该多边形。,4.矢栅结构的比较及转换算法 4.2相互转换算法,射线算法和扫描算法射线算法可逐点判断数据栅格点在某多边形之外或在多边形内，由待判点向图外某点引射线，判断该射线与某多边形所有边界相交的总次数，如相交偶数次，则待判点在该多边形外部，如为奇数次，则待判点在该多边形内部（图7-12）。采用射线算法，要注意的是：射线与多边形边界相交时，有一些特殊情况会影响交点的个数，必须予以排除（图7-13）。扫描算法是射线算法的改进，将射线改为沿栅格阵列列或行方向扫描线，判断与射线算法相似。扫描算法省去了计算射线与多边形边界交点的大量运算，大大提高了效率。,4

39、.矢栅结构的比较及转换算法 4.2相互转换算法,4.矢栅结构的比较及转换算法 4.2相互转换算法,边界代数算法（BAF-Boundary Algebra Filling）(1)单多边形转换。多边形编号为a，初始化的栅格阵列各栅格值为零，以栅格行列为参考坐标轴，由多边形边界上某点开始顺时针搜索边界线，当边界上行时（图7-15-a），位于该边界左侧的具有相同行坐标的所有栅格被减去a；当边界下行时（图7-15-b），该边界左边（前进方向看为右侧）所有栅格点加一个值a，边界搜索完毕则完成了多边形的转换。,4.矢栅结构的比较及转换算法 4.2相互转换算法,单多边形的转换,4.矢栅结构的比较及转换算法 4

40、.2相互转换算法,(2)多个多边形的转换。如果把不属于任何多边形的区域（包含无穷远点的区域）看成编号为零的特殊的多边形区域，则图上每一条边界弧段都与两个不同编号的多边形相邻，按弧段的前进方向分别称为左、右多边形，可以证明，对于这种多个多边形的矢量向栅格转换问题，只需对所有多边形边界弧段作如下运算而不考虑排列次序：当边界弧段上行时，该弧段与左图框之间栅格增加一个值（左多边形编号减去右多边形编号）；当边界弧段下行时，该弧段与左图框之间栅格增加一个值（右多边形编号减去左多边形编号）。两个多边形转换过程如下图所示。,4.矢栅结构的比较及转换算法 4.2相互转换算法,4.矢栅结构的比较及转换算法 4.2

41、相互转换算法,(二)栅格向矢量转换1)栅格格式向矢量格式转换通常包括以下四个基本步骤：多边形边界提取：采用高通滤波将栅格图像二值化或以特殊值标识边界点；边界线追踪：对每个边界弧段由一个结点向另一个结点搜索，通常对每个已知边界点需沿除了进入方向的其他7个方向搜索下一个边界点，直到连成边界弧段；,4.矢栅结构的比较及转换算法 4.2相互转换算法,拓扑关系生成：对于矢量表示的边界弧段数据，判断其与原图上各多边形的空间关系，以形成完整的拓扑结构并建立与属性数据的联系；去除多余点及曲线圆滑：由于搜索是逐个栅格进行的，必须去除由此造成的多余点记录，以减少数据冗余；搜索结果，曲线由于栅格精度的限制可能不够圆

42、滑，需采用一定的插补算法进行光滑处理，常用的算法有：线形迭代法；分段三次多项式插值法；正轴抛物线平均加权法；斜轴抛物线平均加权法；样条函数插值法,4.矢栅结构的比较及转换算法 4.2相互转换算法,2）多边形栅格转矢量的双边界搜索算法（DBDF-Double Boundary Direct Finding）算法的基本思想是通过边界提取，将左右多边形信息保存在边界点上，每条边界弧段由两个并行的边界链组成，分别记录该边界弧段的左右多边形编号。边界线搜索采用2*2栅格窗口，在每个窗口内的四个栅格数据的模式，可以唯一地确定下一个窗口的搜索方向和该弧段的拓扑关系，极大地加快了搜索速度，拓扑关系也很容易建立

43、。,4.矢栅结构的比较及转换算法 4.2相互转换算法,具体步骤如下：（1）边界点和结点提取：采用2*2栅格阵列作为窗口顺序沿行、列方向对栅格图像全图扫描，如果窗口内四个栅格有且仅有两个不同的编号，则该四个栅格表示为边界点；如果窗口内四个栅格有三个以上不同编号，则标识为结点（即不同边界弧段的交汇点），保持各栅格原多边形编号信息。对于对角线上栅格两两相同的情况，由于造成了多边形的不连通，也当作结点处理。图7-17和图7-18给出了节点和边界点的各种情形。,4.矢栅结构的比较及转换算法 4.2相互转换算法,图7-17：节点的8种情形,4.矢栅结构的比较及转换算法 4.2相互转换算法,图7-18：边界

44、点的6种情形,4.矢栅结构的比较及转换算法 4.2相互转换算法,（2）边界线搜索与左右多边形信息记录：对每个弧段由一组已标识的四个结点开始，首先记录开始边界点的两个多边形编号，作为该弧段的左右多边形，下一点组的搜索方向则由进入当前点的搜索方向和该点组的可能走向决定，每个边界点组只能有两个走向，一个是前点组进入的方向，另一个则可确定为将要搜索后续点组的方向。,4.矢栅结构的比较及转换算法 4.2相互转换算法,例如图7-18（c）所示边界点组只可能有两个方向，即下方和右方，如果该边界点组由其下方的一点组被搜索到，则其后续点组一定在其右方；反之，如果该点在其右方的点组之后被搜索到（即该弧段的左右多边

45、形编号分别为b和a），对其后续点组的搜索应确定为下方，其他情况依此类推。,4.矢栅结构的比较及转换算法 4.2相互转换算法,（3）多余点去除：多余点的去除基于如下思想：在一个边界弧段上的连续的三个点，如果在一定程度上可以认为在一条直线上（满足直线方程），则三个点中间一点可以被认为上多余的，予以去除。多余点是由于栅格向矢量转换时逐点搜索边界造成的（当边界为直线时），多余点去除算法可大量去除多余点，减少数据冗余。,5.空间索引机制5.1索引概念,空间索引就是指依据空间对象的位置和形状或空间对象之间的某种空间关系按一定的顺序排列的一种数据结构，其中包含空间对象的概要信息，如对象的标识、外接矩形及指向

46、空间对象实体的指针。作为一种辅助性的空间数据结构，空间索引介于空间操作算法和空间对象之间，它通过筛选作用，大量与特定空间操作无关的空间对象被排除，从而提高空间操作的速度和效率。常见大空间索引一般是自顶向下、逐级划分空间的各种数据结构空间索引，主要包括：,5.空间索引机制5.1索引概念,格网型空间索引BSP树K-D-B树R树R+树CELL树,5.空间索引机制5.2索引类型,(一)格网型空间索引格网型空间索引思路比较简单了，容易理解和实现。其基本思想是将研究区域用横竖线条划分大小相等和不等的格网，记录每一个格网所包含的空间实体。当用户进行空间查询时，首先计算出用户查询对象所在格网，然后再在该网格中

47、快速查询所选空间实体，这样一来就大大地加速了空间索引的查询速度。,5.空间索引机制5.2索引类型,在下图中有三个制图物体：一条河流、一个湖泊和一条省界，它们的关键字分别为5，11和23。河流穿过的栅格为2，34，35，67，68；湖泊覆盖的栅格为68，69，100，101；省界所通过的栅格为5，37，36，35，67，99，98，97。这种物体与栅格的关系可用位图法来表示。由图看出，一个栅格中包含的物体个数就是该栅格在栅格索引的对应记录中存贮的比特“1”的个数。这是定位(开窗)检索的基本工具。此外，物体与栅格的关系亦可用变长指针法表示，如图所示,5.空间索引机制5.2索引类型,5.空间索引机制

48、5.2索引类型,5.空间索引机制5.2索引类型,(二)BSP树空间索引(Binary Space Partitioning Tree)BSP树是一种二叉树，它将空间逐级进行一分为二的划分（图7-19）。BSP树能很好地与空间数据库中空间对象的分布情况相适应，但对一般情况而言，BSP树深度较大，对各种操作均有不利影响。,5.空间索引机制5.2索引类型,(三)KDB树空间索引KDB树就是BSP树向多维空间的一种发展。它对于多维空间中的点进行索引具有较好的动态特性，删除和增加空间点对象也可以很方便地实现；其缺点是不直接支持占据一定空间范围的地物要素，如二维空间中的线和面。该缺点可以通过空间映射或变换

49、的方法部分地得到解决。空间映射或变换就是将2n维空间中的区域变换到2n维空间中的点，这样便可利用点索引结构来对区域进行索引，原始空间的区域查询便转化为高维空间的点查询。但空间映射或变换方法仍然存在着缺点：高维空间的点查询要比原始空间的点查询困难得多；经过变换，原始空间中相邻的区域有可能在点空间中距离变得相当遥远，这些都将影响空间索引的性能。,5.空间索引机制5.2索引类型,(四)R树和R+树R树根据地物的最小外包矩形建立（图7-20），可以直接对空间中占据一定范围的空间对象进行索引。R树的每一个结点N都对应着磁盘页D（N）和区域I（N），如果结点不是叶结点，则该结点的所有子结点的区域都在区域I

50、（N）的范围之内，而且存储在磁盘页D（N）中；如果结点是叶结点，那么磁盘页D（N）中存储的将是区域I（N）范围内的一系列子区域，子区域紧紧围绕空间对象，一般为空间对象的外接矩形。,5.空间索引机制5.2索引类型,R树,5.空间索引机制5.2索引类型,R+树,5.空间索引机制5.2索引类型,(五)CELL树考虑到R树和R+在插入、删除和空间搜索效率两方面难于兼顾，CELL树应运而生。它在空间划分时不再采用矩形作为划分的基本单位，而是采用凸多边形来作为划分的基本单位，具体划分方法与BSP树有类似之处，子空间不再相互覆盖。CELL树的磁盘访问次数比R树和R+树少，由于磁盘访问次数是影响空间索引性能的