空间数据结构.pptx

《空间数据结构.pptx》由会员分享，可在线阅读，更多相关《空间数据结构.pptx（82页珍藏版）》请在三一办公上搜索。

1、第五章 空间数据结构,空间数据结构是指对空间数据逻辑模型描述的数据组织关系和编排方式。同一空间数据逻辑模型往往采用多种空间数据结构，例如游程长度编码结构、四叉树结构都是栅格数据模型的具体实现。空间数据结构对地理信息系统中数据存储、查询检索和应用分析等操作处理的效率有着至关重要的影响，是地理信息系统沟通信息的桥梁，只有充分理解不同地理信息系统所采用的特定数据结构，才能正确有效地使用系统。,空间数据结构是数据逻辑模型与数据文件格式间的桥梁,桥梁,数据结构即指数据组织的形式，是适合于计算机存储、管理和处理的数据逻辑结构。是地理实体的空间排列方式和相互关系的抽象描述。,在地理信息系统中描述地理要素和地

2、理现象的空间数据，主要包括空间位置、拓扑关系和属性三个方面的内容。,栅格结构,矢量结构,定位拓扑关系属性,一、空间数据结构要描述的内容,1、描述的内容,空间实体是指地理空间中客观存在的具体事物,GIS中需要描述：空间位置：主要指位置信息，也包括位置信息的扩展，如形态及实体的组成（复合对象）等；位置用笛卡尔坐标系中X,Y坐标表示；空间关系：主要指空间对象的拓扑关系；非几何属性：表示空间特征的非几何属性，实体的行为及功能特征；实体的衍生信息：如一个实体有多个名称。实体的时态：实体的行为，功能特征以及实体属性随时间的变化。如岛屿的侵蚀、水体污染的扩散、建筑的变形等；,二、空间实体在地理信息系统中的表

3、示,1、单一实体2、多种特征的实体3、带有属性的空间实体的表示4、多层属性信息的表示,（3，3）可用于表示一个点的位置。（1，7），（3，5），（5，5），（5，3），（6，1），可用于表示一条线。（3，10），（6，9），（7，10），（10，7），（9，5），（4，6），（3，8），（3，10）可用于表示 一个多边形。注意第一个坐标和最后一个坐标相同，因为多边形总是封闭的。,1、单一实体,点实体用一组x、y坐标表示线实体用一组有序的x、y坐标表示面实体用一组首尾相同的坐标表示（简单数据结构）。,2、多种实体的表示,如果具有多种实体，就需要对每一实体给定一个识别码。对每一实体用其识别码和相应

4、的坐标列表有关的序号来描述。,表示道路的一组线特征的属性包括：道路类型：1=分隔行驶的公路 2=干线公路 3=主要公路 4=住宅区街道 5=未铺完的公路路面材料：混凝土、柏油、砾石路面宽度：以米计量道路名称：在GIS系统中可有如下的描述，并通过属性表的方式来表示：道路类型 长度 路面材料 宽度 道路名称 2 2715.5 混凝土 52 八一路,3、带有属性的空间实体的表示,用属性表表示属性信息,坐标表和属性表之间共享同一识别码,通过坐标表和属性表之间共享同一识别码来使属性信息和位置信息相结合,4、多层信息的表示,空间数据的分类，是指根据系统功能及国家规范和标准，将具有不同属性或特征的要素区别开

5、来的过程，以便从逻辑上将空间数据组织为不同的信息层(见下图)；,Spatial data model,空间数据模型：矢量模型、栅格模型和三角网数据模型。,用于表示地理实体的数据模型,GIS的数据模型分为两大类：矢量数据模型和栅格数据模型。,5.1 矢量空间数据结构,矢量数据结构对矢量数据模型进行数据的组织。它直接以几何空间坐标为基础，记录实体坐标及其关系，尽可能精确地表示点、线、多边形等地理实体，允许任意位置、长度和面积的精确定义。,标识码,属性,空间对象编码唯一连接几何和属性数据,数据库,独立编码,点:(x,y)线:(x1,y1),(x2,y2),(xn,yn)面:(x1,y1),(x2,y

6、2),(x1,y1),点位字典,点:点号文件,线:点号串,面:点号串,几何 位置,多边形数据文件,点数据文件,多边形文件,1、实体数据结构/spaghetti数据结构,相邻多边形的公共边界要被数字化和存储两遍，节点在数据库中被多次记录，不仅造成数据冗余，还容易造成数据的不一致，引起严重的匹配误差，可能导致输出的公共边界出现间隙或重叠；岛只作为一个单图形，没有建立与外界多边形的联系。每个多边形自成体系，缺少多边形的邻域信息和图形的拓扑关系；难以检查多边形边界的拓扑关系正确与否，如是否存在间隙、重叠、不完整的多边形（死点）或拓扑学上不能接受的环（奇异多边形）等问题。,实体数据结构的缺点：,多边形异

7、常,拓扑空间数据结构没有固定的格式，还没有形成标准，但基本原理相同；拓扑空间数据结构的共同的特点是：点是相互独立的，点连成线，线构成面；每条线始于起始结点，止于终止结点，并与左右多边形相邻接。拓扑空间数据结构主要有：索引式双重独立编码结构链状双重独立编码结构等。,2、拓扑空间数据结构,1）索引式拓扑空间数据结构,点文件,边文件,多边形文件,索引式拓扑空间数据结构,索引式拓扑空间数据结构的优缺点,优点：用建索引的方法消除多边形数据的冗余和不一致，邻接信息、岛信息可在多边形文件中通过是否公共弧段号的方式查询。缺点：表达拓扑关系较繁琐，给相邻运算、消除无用边、处理岛信息、检索拓扑关系等带来困难，以人

8、工方式建立编码表，工作量大，易出错。,20,线文件,2）双重独立编码结构/DIME（Dual Independent Map Encoding）码,3）链状双重独立编码结构（之一）,弧段坐标文件,弧段拓扑文件,多边形拓扑文件,3）链状双重独立编码结构（之二）,a、点拓扑：表示弧段的连通性,表示连通性（Connectivity），即弧段在节点相连要检查弧段的连通性，如果两条弧段共享一个节点，那么这两个弧段是直接相连的；,b、弧拓扑：Arc-Node 拓扑结构,表示弧段的方向,c、弧拓扑：Left-Right多边形拓扑结构,通过弧段的左右多边形，定义了相临性（Contiguity）要检查多边形的相

9、邻性，在Arc-Node数据模型中，只需检查两个多边形是否共享一条公共弧段。,d、面拓扑：Polygon-Arc拓扑结构,定义了区域，即多边形由弧段组成,e、面拓扑：检查多边形的包含关系,要检查多边形B是否包含多边形A，在Arc-Node数据模型中，选择所有定义多边形A的弧段，然后检查所选弧段两侧多边形的标识码。如果在所选弧段的一侧有多边形A，另一侧有多边形B，那么，多边形B必定包含多边形A。,5.2、栅格数据结构,栅格数据结构指将分析空间划分成多个规则的、互相相邻的网格单元（正方形,三角形、六边形），然后给各个格网单元赋以相应空间对象的属性值，用此多个格网单元组成的规则格网（GRID）来表示

10、地理现象的空间位置和属性特征。,5.2.1 栅格数据表示地理现象的方法,1、表示点2、表示线3、表示多边形4、表示连续面,栅格空间数据结构,点：为一个像元。线：在一定方向上连接成串的相邻像元集合。面：聚集在一起的相邻像元集合。,1、表示点,点使用离散分布的单个单元格来表示，单元格的值表示某个地理现象的属性，不同的值表示不同的地理对象或同一地理现象的不同属性。,2、表示线,单条线通过一系列有序相连的具有相同值单元格来表示，宽度为单个单元格，不同的值表示不同的地理对象或同一地理现象的不同属性。,3、表示多边形,单个面表示为一簇具有相同值的相邻单元格，不同的值表示不同的地理对象或同一地理现象的不同属

11、性,4、表示曲面 lattice,这时单元格的值并不代表整个单元格范围地理形象的取值，而代表单元格中心点的取值，其它点的值要靠插值得到。在ArcGIS中，Lattice 是用规则分布的样本点表示曲面类型地理现象的数据模型，每一样本点表示表示面上该位置的xyz。,5.2.2 栅格系统的组成要素,1、栅格单元2、栅格取值的数据类型3、栅格数据模型的坐标系统,一个完整的栅格模型需要以下几个参数：栅格形状；栅格单元尺寸大小/分辨率；栅格原点；栅格的倾角；,列,行,西南角格网坐标（XWS，YWS）,格网分辨率,X,栅格形状,Y,栅格单元的定义,1、栅格单元的尺寸,规则的网格单元叫做单元格(Cell)，每

12、个单元格都有一定的尺寸和取值，尺寸对应一定的地理空间范围单元格的大小表示栅格数据的分辨率，单元格尺寸越小，分辨率越高。,2、栅格单元的尺寸确定方法,1）原则：应能有效地逼近空间对象的分布特征，又减少数据的冗余度。格网太大，忽略较小图斑，信息丢失。一般讲实体特征愈复杂，栅格尺寸越小，分辨率愈高，然而栅格数据量愈大（按分辨率的平方指数增加）计算机成本就越高，处理速度越慢。2）方法：用保证最小多边形的精度标准来确定尺寸经验公式：h为栅格单元边长 Ai为区域所有多边形的面积。,3、栅格数据模型的坐标系统,栅格数据模型的坐标系统：坐标系统由单元格尺寸、行列序号和栅格的原点坐标所决定，坐标轴平行于栅格的行

13、和列；栅格系统的原点：栅格系统的原点选为栅格的左上角；栅格系统的原点坐标通常与国家基本比例尺公里网的交点相一致。栅格方位：大多采用公里网的纵横坐标轴作为栅格系统的纵横坐标；但也有以经纬网来作为栅格方位的参考轴，这样为栅格系统的隐含位置编码提供了方便。,5.2.3 栅格结构的建立,表示具有空间分布特征的地理要素，不论采用什么编码系统，什么数据结构(矢、栅)都应在统一的坐标系统下，而坐标系的确定实质是坐标系原点和坐标轴的确定。由于栅格编码一般用于区域性GIS，原点的选择常具有局部性质，但为了便于区域的拼接，栅格系统的起始坐标应与国家基本比例尺地形图公里网的交点相一致，并分别采用公里网的纵横坐标轴作

14、为栅格系统的坐标轴。,1、栅格坐标系的确定,2、栅格代码（属性值）的确定,当一个栅格单元内有多个可选属性值时，按一定方法来确定栅格属性值。1、中心点法：取位于栅格中心的属性值为该栅格的属性值。2、面积占优法：栅格单元属性值为面积最大者，常用于分类较细，地理类别图斑较小时。3、重要性法：定义属性类型的重要级别，取重要的属性值为栅格属性值，常用于有重要意义而面积较小的要素，特别是点、线地理要素。4、长度占优法每个栅格单元的值由该栅格中线段最长的实体的属性来确定。5、分层结构法（Hierarchical Method）：赋值之前需要建立决策树。,A,B,b,a,a,2,1,2、栅格单元的取值,取值可

15、能表示不同的地物类别或同一类地物的不同属性；栅格取值可能表示某一类地物，如房产图；某个属性值，如数字地面模型；颜色或灰度，如航空相片。,整型：多表示类型浮点型：表示连续变化的地理现象字符：表示类型逻辑型,1、完全栅格数据结构,层2属性值,层N属性值,数据文件,栅格1,x坐标,y坐标,层1属性值,栅格2,栅格N,栅格N,基于面域方式,基于层方式,基于栅格方式,单次完全栅格结构,BIP:bandinterleavedbypixelformat结构波段按像元交叉,BIL:bandinterleavedbylineformat）结构波段按行交叉格式,2、多通道/多波段影像完全数据结构,1）游程长度编码

16、结构（之一）,(0,5),(4,3)(0,3),(4,5)(0,2),(4,4),(8,2)(0,2),(4,3),(8,3)(2,2),(4,2),(8,4)(2,3),(4,1),(8,4)(2,4),(8,4)(2,4),(8,4),（si，li）,3、压缩栅格数据结构,(0,5),(4,8)(0,3),(4,8)(0,2),(4,6),(8,8)(0,2),(4,5),(8,8)(2,2),(4,4),(8,8)(2,3),(4,4),(8,8)(2,4),(8,8)(2,4),(8,8),（si，posi）,1）游程长度编码结构（之二）,特点,对于游程长度编码，区域越大，数据的相关性

17、越强，则压缩越大，适用于类型区域面积较大的专题图，而不适合于类型连续变化或类别区域分散的分类图（压缩比与图的复杂程度成反比）。这种编码在栅格加密时，数据量不会明显增加，压缩率高，并最大限度地保留原始栅格结构，编码解码运算简单，且易于检索，叠加，合并等操作，这种编码应用广泛。,栅格单元数满足2n2n，递归分割，直到每一区间相同或不可再分割。(1）常规四叉树（记录这棵树的叶结点外，中间结点，结点之间的联系用指针联系，每个结点需要6个变量：父结点指针、四个子结点的指针和本结点的属性值。）指针不仅增加了数据的存储量，还增加了操作的复杂性：如层次数（分割次数）由从父结点移到根结点的次数来确定，结点所代表

18、的图像块的位置需要从根节点开始逐步推算下来。所以，常规四叉树并不广泛用于存储数据，主要在数据索引和图幅索引等方面应用,2）四叉树结构,线性四叉树则只存贮最后叶结点的信息，包括叶结点的位置编码/地址码、属性或灰度值；线性四叉树地址码，通常采用十进制Morton码（MD码）：,MD码的“位”运算生成,(2)线性四叉树,列方向,行方向,MD码实例,MD码实例图示,栈,按MD码顺序依次提取4个栅格单元,栈顶指针,比较,入栈,压栈,栈顶指针,栈,判别,编码过程图示,流程图,编码结果,四叉树优缺点,优点：1）存贮量小，只对叶结点编码，节省了大量中间结点的存储，地址码隐含着结点的分割路径和分割次数。对于团块

19、图像，四叉树表示法占用空间上述其他方法要少得多，四叉树表示法基本上是一种非冗余表示法。2）线性四叉树可直接寻址，通过其坐标值直接计算其Morton码，而不用建立四叉树(自下而上）。3)容易执行实现集合相加等组合操作4）四叉树具有可变率或多重分辩率的特点使得它有很好的应用前景，适用于处理凝聚性或呈块状分布的空间数据，特别适用于处理分布不均匀的块状空间数据，但不适用于连续表面（如地形）或线状地物。,四叉树缺点,5)四叉树未能直接表示物体间的拓扑关系。6)与非树表示法比较，四叉树表示法的缺点在于转换的不稳定性或叫滑动变异例如，两个图像的差异仅由于平移，就会构成极为不同的四叉树，因而很难根据四叉树来判

20、断这两个图像是否全同，故不利于做形状分析和模式识别，,7)一个物体的图像在构成四叉树时会被分割到若干个象限中，使它失去了内在的相关性。,8)矢/栅正反变换还不理想。9)建立四叉树耗费机时很多。10)四叉树虽可修改，但很费事,对线性四叉树中仍存在前后叶结点相同值的情况，进一步压缩数据，将前后值相同的叶结点归并：,3）二维行程编码结构,链码数据结构首先采用弗里曼（Freeman）码对栅格中的线或多边形边界进行编码，然后再组织为链码结构。,起始点,4,5,5,6,7,0,1,2,2,2,起始点,链码结构文件,4、链码结构,影像金字塔结构用于图像编码和渐进式图像传输，是一种典型的分层数据结构形式，适合

21、于栅格数据和影像数据的多分辨率组织，也是一种栅格数据或影像数据的有损压缩方式，有M-金字塔，T-金字塔等。,5、影像金字塔数据结构,作业1,1、用关系模型表示下图中多边形、线和点之间的关系，并用Arc/Info的拓朴方式表示其邻接关系和连通关系，并进行拓朴编码，其中1、2、3、4、5、6为边，1、2、3、4为节点，1、2、3为多边形，（）内为各点坐标。,例1，已知栅格单元位于第二行、第二列，求栅格的线性四叉数的十进制编码（MD码）。解：第二行、第二列的二进制形式为（010）行、（010）列 MD=（0 0 1 1 0 0）=123+122=12二进制转化成十进制要从右到左用二进制的每个数去乘以

22、2的相应次方,不过次方要从0开始,例2，已知栅格的MD码为12，求其行列号。解：将12转为二进制数为：001100用2辗转相除至结果为1，将余数和最后的1从下向上倒序写 就是结果 隔行抽取，行号为（010），列号为（010）即行号为第二行，列号为第二列。,作业2,作业3,对以下栅格文件进行线性四叉树编码,5.3 矢栅一体化空间数据结构,1、栅格、矢量数据结构的对比,矢量、栅格数据结构的选择,栅格结构:大范围小比例尺的自然资源、环境、农林业等区域问题的研究。矢量结构：城市分区或详细规划、土地管理、公用事业管理等方面的应用。,在GIS建立过程中，应根据应用目的和应用特点、可能获得的数据精度以及地理

23、信息系统软件和硬件配置情况，选择合适的数据结构。,2、矢栅一体化概念,将矢量面对目标的方法和栅格元子充填的方法结合起来，具体采用填满线状目标路径和充填面状目标空间的方法作为一体化数据结构的基础。一方面，它保留了矢量的全部性质，以目标为单元直接聚集所有的位置信息，并能建立拓扑关系；另一方面，它建立了栅格与地物的关系，即路径上的任一点都直接与目标建立了联系。从原理上说，这是一种以矢量的方式来组织栅格数据的数据结构。,一体化数据结构细分格网,将地理区域划分成多级格网：粗格网基本格网细分格网三级格网都采用线性四叉树编码用（M0、M1、M2）表示，其中M0表示点或线所通过的粗格网的MD码，是研究区的整体

24、编码；M1表示点或线所通过的基本格网的Morton码，也是研究区的整体编码；M2表示点或线所通过的细分格网的Morton码，是基本栅格内的局部编码,矢栅一体化数据结构,x,y,M1 M2,3、三个约定,A、三个约定：地面上的点状地物仅有空间位置，没有形状和面积，在计算机内部仅有一个位置数据。线状地物有形状但没有面积，它在平面上的投影是一连续不间断的直线或曲线，在计算机内部需要用一组元子填满整个路径。面状地物具有形状和面积，它在平面上的投影是由边界包围的紧致空间和一组填满路径的元子表达的边界组成。,点状地物一体化数据结构,线状地物一体化数据结构,面状地物一体化数据结构,分类数据结构,4、一体化数

25、据结构设计,约定1，将点的坐标转化为地址码M1 和M2,结构简单灵活，便于点的插入和删除，还能处理一个栅格内包含多个点状目标的情况。,1)、点状地物和结点的数据结构,2)、线状地物的数据结构,用一串数据表达每个线状地物的路径即可（中间点和穿越点），将该线状地物经过的所有栅格的地址全部记录下来。仿照矢量数据组织的链状双重独立式编码，以弧段为记录单位。,弧段的数据结构:,3)、面状地物的数据结构,2）带指针的二维行程码-面域,1)弧段文件边界弧段-形状（边线中间点和穿越点的M码）,叶结点的属性值改为指向该地物的下一个子块的循环指针,循环指针指向该地物下一个子块的地址码，并在最后指向该地物本身,用循

26、环指针将同属于一个目标的叶结点链接起来,只要进入第一块就可以顺着指针直接提取该地物的所有子块，从而避免像栅格数据那样为查询某一个目标需遍历整个矩阵，大大提高了查询速度。,0,8,32,40,46,4)、复杂地物的数据结构,由几个或几种点、线、面状简单地物组成的地物称为复杂地物。例如将一条公路上的中心线、交通灯、立交桥等组合为一个复杂地物，用一个标识号表示。复杂地物的数据结构如表7所示。,5.4 镶嵌式空间数据结构,以正方形和矩形单元进行地理空间划分的规则镶嵌数据模型，采用栅格数据结构进行数据的组织；Voronoi多边形和TIN三角网采用专门的数据结构进行数据组织。,特征点数据,Voronoi单

27、元邻接关系表,Voronoi顶点信息表,Voronoi单元顶点组成表,1、Voronoi图空间数据结构,1,3,4,5,6,2,1,2,6,8,5,4,3,7,9,12,7,11,TIN网图,三角形拓扑文件,点文件,2、TIN数据结构（以三角形为基本对象）,1,3,4,5,6,2,1,2,6,8,5,4,3,7,9,12,7,11,TIN网图,连接点文件,点文件,2、TIN数据结构（以结点为基本对象）,5.4 三维空间数据结构,1、八叉树数据结构,64，0，0,2、不规则四面体数据结构,表面三维TIN数据结构,TIN数据组织方法,TIN数据组织方法,三维TIN数据组织方法,点的数据结构,三角形的数据结构,边的数据结构,