空间数据结构与管理.ppt

3.2.1 空间数据结构 3.2.2 空间数据管理,第二节 空间数据结构与空间数据管理,3.2.1 空间数据结构,地理信息系统空间数据结构是指空间数据的编排方式和组织关系。空间数据编码是空间数据结构的实现，目的是将图形数据、影像数据、统计数据等资料，按一定的数据结构转换为适用于计算机存储和处理的形式。一种高效率的数据结构应具:（1）能够正确表示要素之间的层次关系，便于不同数据联接和覆盖。（2）正确反映地理实体的空间排列方式和各实体间相互关系。（3）便于存取和检索。（4）节省存贮空间，减少数据冗余。（5）存取速度快，在运算速度较慢的微机上要达到快速响应。（6）足够灵活性，数据组织具有插入新数据、删除或修改部分数据的基本功能。,GIS支持的空间数据结构：矢量数据结构 栅格数据结构 矢量栅格混合数据结构,栅格数据单元格经常是矩形（主要是正方形）的，但可以随应用的需要进行具体设定，比如设置为三角形。栅格数据的比例尺就是栅格大小与地表相应单元大小之比。栅格尺寸越小，其分辨率越高，数据量也越大。栅格单元中存在多种地物，导致属性误差，“混合像元”问题。,一、栅格数据结构,栅格数据结构是指将地球表面划分为大小均匀紧密相邻的网格阵列，每个网格作为一个像元或像素由行、列定义，并包含一个代码表示该像素的属性类型或量值，或仅仅包括指向其属性记录的指针，表示地物或现象的非几何属性特征。,属性明显：数据直接记录了属性或指向属性的指针，可以直接得到地物的属性代码。定位隐含：栅格结构是按一定的规则排列的，实体位置隐含在格网文件的存储结构中。栅格数据结构容易实现，算法简单，且易于扩充、修改，也很直观，特别是易于同遥感影像的结合处理，给地理空间数据处理带来了极大的方便。,1、栅格数据结构特点,2、栅格数据取值方法,中心归属法：每个栅格单元的值以网格中心点对应的面域属性值来确定。长度占优法：每个栅格单元的值以网格中线（水平或垂直）的大部分长度所对应的面域的属性值来确定。面积占优法：每个栅格单元的值以在该网格单元中占据最大面积的属性值来确定。重要性法：根据栅格内不同地物的重要性程度，选取特别重要的空间实体决定对应的栅格单元值，如稀有金属矿产区，其所在区域尽管面积很小或不位于中心，也应采取保留的原则。,3、栅格数据获取途径,手工获取，专题图上划分均匀网格，逐个决定其网格代码。扫描仪扫描专题图的图像数据行、列、颜色（灰度），定义颜色与属性对应表，用相应属性代替相应颜色，得到（行、列、属性）再进行栅格编码、存贮，即得该专题图的栅格数据。由矢量数据转换而来。遥感影像数据，对地面景像的辐射和反射能量的扫描抽样，并按不同的光谱段量化后，以数字形式记录下来的像素值序列。格网DEM数据，当属性值为地面高程，则为格网DEM，通过DEM内插得到。,常用栅格排列顺序,4、简单栅格数据排列方式,遥感图像数据排列方式,（1）BSQ方式：各波段的二维图像数据按波段顺序排列。（2）BIL方式：对每一行中代表一个波段的光谱值进行排列，然后按波段顺序排列该行。（3）BIP方式：在一行中，每个像元按光谱波段次序进行排列。,每个像元可能是占一个字节的整型数。如果图像比较大，这种逐点存储的方式，所占的空间是十分巨大的。所以在实际存储时，多采用压缩存储的方式。,压缩编码的目的是用尽可能少的数据量记录尽可能多的信息，类型分为：信息无损编码：编码过程中没有任何信息损失，通过解码操作可以完全恢复原来的信息。信息有损编码：为了提高编码效率，最大限度地压缩数据，在压缩过程中损失一部分相对不太重要的信息，解码时这部分难以恢复。在地理信息系统中的压缩编码多采用信息无损编码，而对原始遥感影像进行压缩时也可以采取有损压缩编码方法。但数据压缩所获得的空间节省与数据处理的时间花费往往是成正比例，即所节省的空间越多，数据压缩与解压所需的时间往往也多，因此所采取的方法要根据实际情况而定。,5、栅格数据存储的压缩编码,、行程编码,行程编码1只在各行（或列）数据的代码发生变化时依次记录该代码以及相同代码重复的个数。,行程编码2逐个记录各行（或列）代码发生变化的位置和相应的代码，下图可沿列方向进行行程编码：1列：（1，3），（3，1）；2列：（1，3），（4，1）；3列：（1，3），（5，1）；4列：（1，4），（2，3），（5，1）；5列：（1，4），（4，3），（6，2），（7，1）；6列：（1，4），（4，2）；7列：（1，4），（4，2）；8列：（1，4），（3，2）。,行程编码优缺点,优点：压缩效率较高，且易于进行检索，叠加合并等操作，运算简单，适用于机器存储容量小，数据需大量压缩，而又要避免复杂的编码解码运算增加处理和操作时间的情况。缺点：对于图斑破碎，属性和边界多变的数据压缩效率较低，甚至压缩后的数据量比原始数据还大。,把多边形范围划分成由像元组成的正方形，然后对各个正方形进行编码。块式编码数据结构中包括3个数字：块的初始位置（行、列号）和块的大小（块包括的像元数），再加上记录单元的代码组成。,、块式编码,行程和块式编码都对大而简单的多边形更有效，块式编码对多边形之间求并和求交较方便。,、四叉树编码,根据栅格数据二维空间分布特点，将空间区域按照4个象限进行递归分割（2n2n，且n1），直到子象限的数值单调为止，最后得到一棵四分叉的倒向树。四叉树分解，各子象限大小不完全一样，但都是同代码栅格单元组成的子块，其中最上面的一个结点叫做根结点，对应于整个图形。不能再分的结点称为叶子结点，可能落在不同层上，该结点代表子象限单一的代码，所有叶子结点所代表的方形区域覆盖了整个图形。从上到下，从左到右为叶子结点编号，最下面的一排数字表示各子区的代码。为了保证四叉树分解能不断的进行下去，要求图形必须为2n2n的栅格阵列。n 为极限分割次数，n1是四叉树最大层数或最大高度。为了在计算机中既能以最小的冗余存储与图像对应的四叉树，又能方便地完成各种图形操作，专家们已提出多种编码方式。,美国马里兰大学采用的四叉树编码方法是：记录每个叶子结点的地址和值，值就是子区的代码，其中地址包括两个部分，共占有32位（二进制），最右边四位记录该叶子结点的深度，即处于四叉树的第几层上，有了深度可以推知子区的大小；地址由从根结点到该叶子结点的路径表示。0，1，2，3分别表示NW、NE、SW、SE，从右边第五位开始2n字节记录这些方向。,第5个结点深度为4，第一层为根结点，第二层处于SW象限记为2，第三层处于NE象限记为1，第四层处于SE象限记为3，表示为二进制为：0000000（22位）100111（6位）0100（4位）每层象限位置由二位二进制表示。这样，记录了各个叶子的地址，再记上相应的代码值，就记录了整个图像，并可在此编码的基础上进行多种图像操作。,四叉树编码的优缺点,优点容易而有效地计算多边形的数量特征；阵列各部分的分辨率是可变的，边界复杂部分四叉树较高，即分级多，分辨率也高，而不需要表示许多细节的部分则分级少，分辨率低，因而既可精确表示图形结构又可减少存储量；栅格到四叉树及四叉树到简单栅格结构的转换比其他压缩方法容易；多边形中嵌套异类多边形的表示较方便，是优秀的栅格压缩编码之一。缺点 其最大不足是其不稳定性，即同样的原始数据应用不同的算法进行编码可能会得到不同的编码结果。不利于形状分析和模式识别。,二、矢量数据结构,矢量是具有一定大小和方向的量,数学上和物理上也叫向量。线段长度表示大小，线段端点的顺序表示方向。有向线段用一系列有序特征点表示，有向线段集合就构成了图形。矢量数据就是代表地图图形的各离散点平面坐标（x，y）的有序集合。矢量数据结构是通过记录坐标的方式，尽可能地将点、线、面地理实体表现得精确无误。其坐标空间假定为连续空间，不必象栅格数据结构那样进行量化处理。因此矢量数据能更精确地定义位置、长度和大小。矢量结构允许最复杂的数据以最小的数据冗余进行存储，相对栅格结构来说，数据精度高，所占空间小，是高效的空间数据结构。其精度仅受数字化设备的精度和数值记录字长的限制。,定位明显：其定位是根据坐标直接存储的，无需任何推算。属性隐含：属性则一般存于文件头或数据结构中某些特定的位置上。矢量数据结构图形运算的算法总体上比栅格数据结构复杂的多，在叠加运算、邻域搜索等操作时比较困难，有些甚至难以实现，在计算长度、面积、形状和图形编辑、几何变换操作中，矢量结构有很高的效率和精度。,1矢量数据结构特点,2、空间实体类型,点：空间上不能再分的地理实体，可以是具体的或抽象的，如地物点、文本位置点或线段网络的结点等，由一对x、y坐标表示。地面上的矿点、水井、高程控制水准点等都是点实体。线：空间上具有一定延伸方向性的线状地物，由一组有序点组成，采用一组有序的(X，Y)坐标来表示。如河流和道路、断层、地质体分界线等为线状地物。面：指有封闭边界和面积的实体，由一组有序线段包围而成区域。采用一组首尾位置重合的有序线段表示。例如湖泊、矿区、土壤类型等。,从几何上来说，资源空间目标可划分为点、线、面、体四种基本类型。对表示在地图中的各种要素都可抽象为点、线、面几何图形的实体。,3、矢量数据获取途径,1)由外业测量获得 利用测量仪器自动记录测量成果(常称为电子手薄)，然后转到地理数据库。2)由栅格数据转换获得 利用栅格数据矢量化技术，把栅格数据转换为矢量数据。3)跟踪数字化 用跟踪数字化的方法，把地图变成离散的矢量数据。,对于点实体矢量结构中只记录其在特定坐标系下的坐标和属性代码。,点实体数据编码,4、矢量数据编码,唯一标识码是系统排列序号；线标识码可以标识线的类型；起始点和终止点号可直接用坐标表示；显示信息是显示时的文本或符号等；与线相联系的非几何属性可以直接存储于线文件中，也可单独存储，而由标识码联接查找。,线实体矢量数据编码,多边形实体矢量数据编码,多边形矢量编码不但要表示空间图形为多边形的面状实体的位置和属性，更为重要的是要能表达区域的拓扑性质，如形状、邻域和层次等，以便使这些基本的空间单元可以作为专题图资料进行显示和操作，其编码比点和线实体的矢量编码要复杂得多，也更为重要。它与机助制图系统仅为显示和制图目的而设计的编码有很大不同。编码方法：坐标序列法、树状索引编码法、拓扑结构编码法。,坐标序列法,由多形边界的x、y坐标对集合及说明信息组成，是最简单的一种多边形矢量编码。,一个区域或一幅地图可以划分成许多多边形，多边形4由、弧段组成，文件编码坐标为:x9,y9；x8,y8；x7,y7；x20,y20；x21,y21；x22,y22；x23,y23；x24,y24；x18,y18；x18,y18；x19,y19。每个多边形在数据库中是相互独立、分开存储的。,坐标序列法的优缺点,优点：文件结构简单，易于实现以多边形为单位的运算和显示。缺点：多边形之间的公共边界被数字化和存储两次，由此产生冗余和碎屑多边形；如重叠陕长多边形及裂缝的产生。每个多边形自成体系而缺少邻域信息，难以进行邻域处理，如消除某两个多边形之间的共同边界；不能解决“洞”和“岛”之类的多边形嵌套问题。没有方便方法来检查多边形边界的拓扑关系正确与否，如有无不完整的多边形（死点）或拓扑学上不能接受的环（奇异多边形）。这种方法可用于简单的粗精度制图系统中。,树状索引编码法,采用树状索引以减少数据冗余并间接增加邻域信息，方法是对所有边界点进行数字化，将坐标对以顺序方式存储，由点索引与边界线号相联系，以线索引与各多边形相联系，形成树状索引结构。,图形数据,线与多边形之间的树状索引,点与边界线之间的树状索引,树状索引编码法示例,形成的文件记录,树状索引编码法的优势和不足,树状索引编码消除了相邻多边形边界的数据冗余和不一致的问题，在简化过于复杂的边界线或合并相邻多边形时可不必改造索引表，邻域信息和岛状信息可以通过对多边形文件的线索引处理得到。但是比较繁琐，因而给相邻函数运算，消除无用边，处理岛状信息以及检查拓扑关系带来一定的困难，而且两个编码表都需要以人工方式建立，工作量大且容易出错。,双重独立地图编码,拓扑关系类型a 拓扑邻接：指存在于空间图形的同类元素之间的拓扑关系。结点邻接关系有N1/N4，N1/N2等；多边形邻接关系有P1/P3，P2/P3 等。b 拓扑关联：拓扑关联指存在于空间图形的不同类元素之间的拓扑关系。结点与弧段关联关系有N1/C1、C3、C6，N2/C1、C2、C5 等。多边形与线段的关联关系有P1/C1、C5、C6，P2/C2、C4、C5、C7等。c 拓扑包含：拓扑包含指存在于空间图形的同类但不同级的元素之间的拓扑关系，P2包含P4。,拓扑概念拓扑学是研究图形在保持连续状态下变形时的那些不变的性质，也称“橡皮板几何学”。在拓扑空间中对距离或方向参数不予考虑。拓扑关系是指网结构元素结点、弧段、面域之间的空间关系。,双重独立地图编码简称DIME结构（Dual Independent Map Encoding）。它是由美国人口调查局建立起来的为人口调查目的而设计的一种拓扑编码方法，是一种把几何量度信息（直角坐标）与拓扑逻辑信息结合起来的系统。DIME文件的基本元素：线段、线段始结点和终结点标识符、区域代码（左区号和右区号）。方法：对所有边界点进行数字化，将坐标对以顺序方式存储，由点索引与边界线号相联系，以线索引与各多边形相联系，形成树状索引结构。结点坐标文件包括结点标识符和结点坐标，拓扑结构文件包括结点、线段、多边形间的拓扑关系。DIME结构中，线段通常被认为是直线型的，复杂的曲线由一系列逼近曲线的直线段来表示。结点与结点或者面域与面域之间为邻接关系，而结点与线段或面域与线段之间为关联关系。,双重独立地图编码优点通过有向编码建立了多边形、边界、节点之间的拓扑关系，有效地进行数据存储正确性检查，同时便于对数据进行更新和检索。这种数据结构在自动区域单元时，空间点的坐标是自行闭合。否则数据存储或编码有错，区域不能自行闭合，或者出现多余的线段，达不到数据自动编辑的目的。DIME编码成为其它拓扑编码结构的基础。它采用树状索引以减少数据冗余并间接增加邻域信息。,矢量编码保证了信息的完整性和运算的灵活性，这是由矢量结构自身的特点所决定的。目前并没有统一的最佳的矢量结构编码方法，在具体工作中应根据数据的特点和任务的要求而灵活设计。,无拓扑关系的矢量结构,实体型矢量数据编码（无拓扑矢量数据编码）虽然会产生数据冗余和歧异，但易于编辑，如MapInfo。,带拓扑关系的矢量结构,拓扑型矢量数据编码消除了数据的冗余和歧异，但操作复杂，甚至会产生新的数据冗余，如ARC/INFO。,5、矢量数据结构与栅格数据结构的比较,将矢量面对目标的方法和栅格元子充填的方法结合起来，采用填满线状目标路径和充填面状目标空间的方法结合使用的数据结构。线状地物：除记录原始取样点外，还记录路径所通过的栅格。面状地物：除记录它的多边形周边以外，还包括中间的面域栅格。特点：它保留了矢量的全部性质，以目标为单元直接聚集所有的位置信息，并能建立拓扑关系；它建立了栅格与地物的关系，即路径上的任一点都直接与目标建立了联系。从原理上说，这是一种以矢量的方式来组织栅格数据的数据结构。,三、矢量栅格一体化数据结构,空间数据库（或称地图数据库）是地理信息系统的重要组成部分，因为地图是地理信息系统的主要载体。地理信息系统是一种以地图为基础，供资源、环境、区域调查以及规划的管理和决策用的空间信息系统。空间数据库模型是数据库中对数据的逻辑组织形式的描述。,3.2.2 空间数据管理,一、传统DBMS管理和空间数据管理,1、从数据管理的角度看GIS中数据的特点,数据量大，常要作查询，因此必需注意提高查询效率，如建立索引等；数据类型和关系复杂，常要记录拓扑关系；GIS数据常具有非结构化特征，如描述线面状地物的长度不等；数据要嵌套；一个对象可能包含多个对象。,2、关系模型描述空间数据存在的问题,缺乏构造复杂对象的能力，以记录为单位的数据模型不能很好的面向用户，不能描述嵌套和递归等复杂关系。数据类型少，不支持抽象数据类型，如不能定义几何数据类型（点，线，面）和空间操作算子（相交，包含等），无法完成地理意义上的分析查询。缺乏语义表达能力，即语义贫乏。它表达实体和实体间关系只能在表内，或通过公共值的跨表连接,实现效率低，不利于建立数据的概念模型。表形式不适用表示图形数据，图形数据涉及的坐标、属性、拓朴关系用表格表示使问题显得复杂化。,二、空间数据管理系统的模式类型,1、全文件管理系统,将属性数据和空间数据均放在文件系统中进行管理。程序依赖于数据文件的存储结构，数据文件修改时，应用程序也随之改变。,优点：（1）厂商可根据自己要求定义文件格式，管理数据；（2）有利于存储非结构化不定长数据。缺点：（1）不利于数据查找；（2）数据共享性等差。,2、文件和关系数据库混合系统,文件和关系数据库混合系统是传统GIS所用的方式。如arcinfo,mapinfo等。系统中,图形用数据文件存储，属性用关系数据库表存储。两者通过标识符相联结，这种方式实际上不能建立真正意义上的空间数据库。,优点:GIS 可通过DBMS提供的高级编程语言的接口，直接操纵属性数据，查询属性数据库，并在GIS的用户界面下，显示查询结果。在ODBC(Open DataBase Connectivity,开放式数据库互连)推出后，GIS软件商只需开发GIS与ODBC的接口软件，就可将属性数据与任何一个支持ODBC的RDBMS连接。这样用户可在一个界面下处理图形和属性数据。,缺点:属性数据和图形数据通过ID联系起来，使查询运算，模型操作运算速度慢；数据分布和共享困难；属性数据和图形数据分开存储，数据的安全性、一致性、完整性、并发控制以及数据损坏后的恢复方面缺少基本的功能；缺乏表示空间对象及其关系的能力。,目前，空间数据管理正在逐步走出文件管理模式,3、全关系型数据库系统管理,图形数据和属性数据都用现有的关系数据库管理系统管理，管理数据库管理系统不作任何扩展，由GIS软件商在此基础上进行开发。,优点:（1）在全关系型数据库中加入了二进制数据块形式省去大量关系连接操作,可提高查询速度；（2）便于数据的维护；缺点:（1）不定长记录造成存储效率的下降；（2）实现SQL查询要附加接口；因此它只适用于功能简单的GIS。,4、对象关系型数据库系统,采用通用关系数据库管理系统效率低，面向对象型空间数据库管理系统又不够成熟，随着空间信息系统的发展，许多数据库管理系统的软件商纷纷对关系数据库进行扩充，使之能直接存储非结构化的空间数据，形成对象关系型数据库GIS系统。对象关系型空间数据库是在标准的RDBMS上加了一层空间数据管理专用模块如Oracle在其数据库中加入了oralce Spatial 组件，以支持空间数据；Informix为用户定义数据类型，提供了Data Blade插件。定义了操作点、线、面等空间对象的函数，解决了空间数据的变长记录管理。,优点解决了空间数据的变长记录管理，使数据管理效率大大提高；空间和属性之间联结有空间数据管理模块解决，不仅具有操作关系数据的函数，还具有操作图形的API函数;对象关系型空间数据库是在标准的关系数据库上加一层空间数据管理模块；用该层功能将地理结构查询语言转化成标准的SQL查询，空间数据查询速度快。缺点 空间数据对象还不能有用户任意定义，用户使用受一定限制。如定义的空间函数支持的对象不带拓扑关系，用户不能定义带拓扑关系的数据模型。,5、面向对象型数据库系统,面向对象型空间数据库管理系统最适合空间数据的表达和管理。,优点支持变长记录，还支持对象的嵌套，信息的继承和聚集。面向对象数据库管理系统允许定义合适的数据结构和数据操作。,缺点 不支持SQL语言，在通用性上受局限。面向对象型空间数据库管理系统还不够成熟，价格又昂贵，目前在GIS领域还不通用。,三、空间数据的分层和空间数据索引机制,1、空间数据的分层,空间数据分层的方法按专题分层；按时间序列分层；按地面垂直高度。,2、空间索引机制,空间索引就是指依据空间对象的位置和形状或空间对象之间的某种空间关系按一定的顺序排列的一种数据结构，其中包含空间对象的概要信息，如对象的标识、外接矩形及指向空间对象实体的指针。作为一种辅助性的空间数据结构，空间索引介于空间操作算法和空间对象之间，它通过筛选作用，大量与特定空间操作无关的空间对象被排除，从而提高空间操作的速度和效率。空间索引的性能的优劣直接影响空间数据库和地理信息系统的整体性能，它是空间数据库和地理信息系统的一项关键技术。,常见空间索引一般是自顶向下、逐级划分空间的各种数据结构空间索引，比较有代表性的包括BSP树、R树、R+树和CELL树等。此外，结构较为简单的格网型空间索引有着广泛的应用。,格网型空间索引基本思想：将研究区域用横竖线条划分大小相等和不等的格网，记录每一个格网所包含的空间实体。当用户进行空间查询时，首先计算出用户查询对象所在格网，然后再在该网格中快速查询所选空间实体，这样一来就大大地加速了空间索引的查询速度。,空间属性表描述要素的一般信息，如湖泊的深度，空间索引表描述要素所在格网的信息，表描述要素的点数，范围等信息，三张表通过FID关联。,四、海量空间数据组织与管理,随着GIS应用领域的不断扩大，如城市规划系统、地下管网管理系统、土地管理系统、公安警用系统等，由于其管理的数据量很大，且比例尺也大。所以，靠对单幅图的管理已不能适应应用的需要。多数GIS采用图幅为单位的管理，即按图幅将大区域空间数据进行分割，现在世界各国的一般方法是采用经纬线分幅或采用规则矩形分幅。,在组织这个大区域空间时，首先为空间的组织形式进行定义。其中包括：坐标单位、经度和纬度跨度（用经纬线分幅时）、比例尺、图幅的宽和高（用矩形分幅时）、地图投影类型，椭球体参数等。数据库中所有图幅都按定义的形式进行录入。在大区域空间的组织形式确定后，就可逐一将图幅输入库中。输入时须指出该图幅的文件名（可能一个图幅含有多个文件）和用于确定图幅在库中的位置的横向纵向序号（矩形分幅）或左下角经纬度（经纬线分幅）。对系统而言，当用户要求按某局部范围进行检索时，系统可对所指定范围对应的图幅文件进行检索；当用户要求按分类要素进行检索时，系统可根据图幅之间的邻接关系将所有需要的要素检索出来。,数据库中图幅的组织方法,