地信空间数据结构.ppt

1、空间数据结构,3.1 数据模型和数据结构 3.2 矢量数据结构（重点） 3.3 栅格数据结构（重点） 3.4 矢栅结构的比较及转换算法（难点） 3.5 其它的数据结构介绍,问题思考,在计算机中该如何对其进行存储和表达？,现实空间世界,空间数据模型,空间数据结构,组织与管理,计算机存储,认知与抽象,空间数据库,数据文件,现实世界是以各种符号形式来表达和记录的，计算机在对数字和字符这些符号进行操作时，又将它们表示为二进制形式。因此，基于计算机的GIS不能直接作用于现实世界，必须对现实世界进行数据描述。 模型是对现实世界的简化表达。数据建模是指把现实世界的数据组织为有用且能反映真实信息的数据集的过程

2、。数据模型就是根据一定的方案(数据逻辑)对数据进行组织的一种方式。 数据建模过程分为三步： 首先，选择一种数据模型来对现实世界的数据进行组织； 然后，选择一种数据结构来表达该数据模型； 最后，选择一种适合于记录该数据结构的文件格式。,3.1 数据模型和数据结构,空间数据结构指数据组织的形式，是适合于计算机存储、管理和处理的数据逻辑结构。 数据结构是数据模型和文件格式之间的中间媒介。,在GIS中主要有栅格和矢量两种数据结构。在矢量模型中， 用点、线、面表达空间实体，在栅格模型中用空间单元（Cell）或 像元（Pixel）来表达。,3.1 数据模型和数据结构,3.2 矢量数据结构,3.2.1 基本

3、概念,1.矢量数据结构定义 矢量数据结构是通过记录坐标的方式尽可能精确地表示点、线、多边形等地理实体。或者说矢量数据结构通过记录空间对象的坐标及空间关系来表达空间对象的位置。,2.矢量结构的特点 定位明显、属性隐含，其定位是根据坐标直接存储的，而属性则一般存于文件头或数据结构中某些特定的位置上，这种特点使得其图形运算的算法总体上比栅格数据结构复杂的多，在计算长度、面积、形状和图形编辑、几何变换操作中，矢量结构有很高的效率和精度，而在叠加运算、邻域搜索等操作时则比较困难。用拓扑关系描述空间对象之间的关系，与遥感等图象数据难以结合，输出图形质量好，精度高。,3.2 矢量数据结构,3.2.2 图形表

4、示,点：空间的一个坐标点； 线：多个点组成的弧段； 面：多个弧段组成的封 闭多边形。,3.2 矢量数据结构,3.2.3 矢量数据的获取,（1）由外业测量获得 可利用测量仪器自动记录测量成果，然后转到地理数据库中。 （2）由栅格数据转换获得 利用栅格数据矢量化技术，把栅格数据转换为矢量数据。 （3）跟踪数字化 用跟踪数字化的方法，把地图变成离散的矢量数据。,3.2 矢量数据结构,3.2.4 矢量数据的组织,矢量数据表示时应考虑以下问题： （1）矢量数据自身的存贮和处理。 （2）与属性数据的联系。 （3）矢量数据之间的空间关系(拓扑关系)。,矢量数据结构按其是否明确表示地理实体间的空间关系分为实体

5、数据结构和拓扑数据结构两大类。,多边形 数据项 A (x1,y1),(x2,y2),(x3,y3),(x4,y4), (x5,y5),(x6,y6),(x7,y7),(x8,y8), (x9,y9),(x1,y1) B (x1,y1),(x9,y9),(x8,y8),(x17,y17), (x16,y16),(x15,y15),(x14,y14) , (x13,y13),(x12,y12),(x11,y11), (x10,y10),(x1,y1) C (x24,y24),(x25,y25),(x26,y26), (x27,y27),(x28,y28),(x29,y29), (x30,y30),

6、(x31,y31),(x24,y24) D (x19,y19),(x20,y20),(x21,y21), (x22,y22),(x23,y23),(x15,y15), (x16,y16),(x19,y19) E (x5,y5),(x18,y18),(x19,y19), (x16,y16),(x17,y17),(x8,y8), (x7,y7),(x6,y6),(x5,y5),3.2.4 矢量数据的组织,1.实体数据结构,实体式（Spaghetti):又称面条结构（坐标序列法），以实体为单位,记录多边形边界的坐标对（x、y）集合及说明信息组成，只记录空间对象的位置坐标和属性信息，不记录拓扑关系。,

7、1.实体数据结构,缺点： （1）相邻多边形的公共边界被数字化并存储两次，造成数据冗余和碎屑多边形数据不一致，浪费空间，导致双重边界不能精确匹配。 （2）自成体系，缺少多边形的邻接信息，无拓扑关系，难以进行邻域处理，如消除多边形公共边界，合并多边形。 （3）岛作为一个单个图形，没有与外界多边形联系。不易检查拓扑错误。 所以，这种结构只用于简单的制图系统中，显示图形。,优点：结构简单、直观、易实现以实体为单位的运算和显示。,3.2 矢量数据结构,2.拓扑数据结构,（一）树状索引式结构,对所有点的坐标按顺序建坐标文件，再建点与边（线）、线与多边形的索引文件,形成树状索引结构。,Map,1、点文件：,

8、索引文件：,3、面文件：,2、弧段文件:,与实体式相比： 优点：用建索引的方法消除多边形数据的冗余和不一致，邻接信息、岛信息可在多边形文件中通过是否公共弧段号的方式查询。 缺点：表达拓扑关系较繁琐，给相邻运算、消除无用边、处理岛信息、检索拓扑关系等带来困难，以人工方式建立编码表，工作量大，易出错。,线与多边形之间的树状索引,点与边界线之间的树状索引,（二）双重独立式编码结构,1、点文件,2、线文件:线文件是以线段为记录单位,3、面文件,关联,邻接,关联,连通,拓扑关系明确,又称双重独立地图编码DIME(Dual lndependent Map Encoding) 是美国人口调查系统所采用的编码

9、方法。它通过有向编码建立了多边形、边界、节点之间的拓扑关系，DIME是一种拓扑编码结构，是其它拓扑编码结构的基础。对于一条线段，用顺序的两点以及相邻多边形予以定义。,这种数据结构除了通过线文件生成面文件外，还需要点文件,在DIME中做如下改进：将以线段为记录单位改为以弧段为单位链状双重独立式编码,（三）链状双重独立式编码结构,链状双重独立式编码是DIME编码的一种改进。在DIME中，一条边只能用直线两端点的序号及相邻的面域来表示，而在链状数据结构中，将若干直线段合为一个弧段（或链段），每个弧段可以有许多中间点。 在链状双重独立式编码中，主要有四个文件：多边形文件、弧段文件、弧段点文件、点坐标文

10、件。,3.2 矢量数据结构,（三）链状双重独立式编码结构,弧段文件 弧段号起始点终结点左多边形右多边形 a51OA b85EA c168EB d195OE e1519OD f1516DB g115OB h81AB i1619DE j3131BC 弧段坐标文件 弧段号点 号 a5,4,3,2,1 b8,7,6,5 c16,17,8 d19,18,5 e15,23,22,21,20,19 f15,16, g1,10,11,12,13,14,15 h8,9,1 i16,19 j31,30,29,28,27,26,25,24,31,多边形文件 多边形号 弧段号 周长 面积 中心点坐标 Ah,b,a B

11、g,f,c,h,-j Cj De,i,f Ee,i,d,b,（三）链状双重独立式编码结构的特点,拓扑关系明确，也能表达岛信息，而且以弧段为记录单位，满足实际应用需要。因为一般数字化一条街道时，必然有许多中间点，但我们在做空间分析是却没有必要以这些中间点所组成的折线为研究对象，而应以整条弧段（某条街道）为研究对象.,当图形数据修改、删除、增加点、线、面要素后，其拓扑关系也发生改变，所以，需重新建拓扑。,3.3 栅格数据结构,3.3.1 基本概念,1、定义 栅格数据结构实际就是像元阵列，每个像元由行列确定它的位置，用像元值表示空间对象的类型、等级等特征。 由于栅格结构是按一定的规则排列的，所表示的

12、实体位置隐含在文件的存储结构中，且行列坐标可以很容易地转为其它坐标系下的坐标。在数据文件中每个代码明确地表示了实体的属性或属性的编码。,3.3 栅格数据结构,3.3.1 基本概念,2、栅格数据结构的特点,离散的量化栅格值表示空间对象 位置隐含,属性明显 几何和属性偏差 难以建立空间对象之间的关系,3.3.2 图形表示,栅格结构用密集正方形（或三角形，多边形）将地理区域划分为网格阵列。位置由行，列号定义，属性为栅格单元的值。,点：由单个栅格表达。 线：由沿线走向有相同属性取值的一组相邻栅格表达。 面：由沿线走向有相同属性取值的一片栅格表达。 栅格数据表示的是二维表面上的地理数据的离散化数值。在栅

13、格数据中，地表被分割为相互邻接、规则排列的地块，每个地块与一个像元相对应。因此，栅格数据的比例尺就是栅格(像元)的大小与地表相应单元的大小之比，当像元所表示的面积较大时，对长度、面积等的量测有较大影响。每个像元的属性是地表相应区域内地理数据的近似值，因而有可能产生属性方面的偏差。,3.3 栅格数据结构,3.3.3 栅格数据的建立,1、建立途径,（1）手工获取，专题图上划分均匀网格，逐个决定其网格代码。 （2）扫描仪扫描专题图的图像数据行、列、颜色（灰度），定义颜色与属性对应表，用相应属性代替相应颜色，得到（行、列、属性）再进行栅格编码、存贮，即得该专题图的栅格数据。 （3）由矢量数据转换而来。

14、 （4）遥感影像数据，对地面景象的辐射和反射能量的扫描抽样，并按不同的光谱段量化后，以数字形式记录下来的象素值序列。,（5）格网DEM数据，当属性值为地面高程，则为格网DEM，通过DEM内插得到。,3.3.3 栅格数据的建立,2、栅格单元的确定,（1）原则：应能有效地逼近空间对象的分布特征，又减少数据的冗余度。 一般讲实体特征愈复杂，栅格尺寸越小，分辨率愈高，然而栅格数据量愈大（按分辨率的平方指数增加）计算机成本就越高，处理速度越慢。 （2）方法：用保证最小多边形的精度标准来确定尺寸经验公式： h为栅格单元边长 Ai为区域所有多边形的面积。,3.3.4 栅格数据的建立,3、栅格属性值的确定,当

15、一个栅格单元内有多个可选属性值时，按一定方法来确定栅格属性值。 1、中心点法：取位于栅格中心的属性值为该栅格的属性值。 2、面积占优法：栅格单元属性值为面积最大者，常用于分类较细，地理类别图斑较小时。 3、 重要性法：定义属性类型的重要级别，取重要的属性值为栅格属性值，常用于有重要意义而面积较小的要素，特别是点、线地理要素。 4、长度占优法每个栅格单元的值由该栅格中线段最长的实体的属性来确定。,3.3 栅格数据结构,3.3.4 栅格数据的编码,什么是地理数据编码？,地理数据编码，是根据GIS的目的和任务，把地图、图像等资料按一定数据结构转换为适于计算机存贮和分析处理的数据过程。地理编码要反映出

16、地理实体的空间特征，以及地理实体的属性特征。,3.3 栅格数据结构,3.3.4 栅格数据的编码,地理信息种类繁多、内容丰富、只有将它们按一定的规律进行分类和编码，使其有序地存储、检索，才能满足各种应用分析需求。因此，地理数据编码是空间数据库建立和 GIS设计的重要基础，是表现由现实世界到数据世界之间的界面，是连接从现实世界到数据世界的纽带。,为什么要进行地理数据编码？,3.3.4 栅格数据的编码方法,链码(Chain_Encoding),直接栅格编码,游程长编码(Run_length Encoding),块码(Block_Encoding),四叉树编码(Quarter_tree Encodin

17、g),3.3.4 栅格数据的编码方法,1、直接栅格编码,直接编码就是将栅格数据看作一个数据矩阵，逐行（或逐列）逐个记录代码，可以每行从左到右逐像元记录，也可奇数行从左到右而偶数行由右向左记录，为了特定的目的还可采用其他特殊的顺序。,0，2，2，5，5，5，5，5；,2，2，2，2，2，5，5，5；,2，2，2，2，3，3，5，5；0，0，2，3，3，3，5，5；0，0，3，3，3，3，5，3；0，0，0，3，3，3，3，3；0，0，0，0，3，3，3，3；0，0，0，0，0，3，3，3。,3.3.4 栅格数据的编码方法,1、直接栅格编码,特点：最直观、最基本的网格存贮结构，没有进行任何压缩数据

18、处理，栅格数据量大，格网数多。,特点？,由于地理数据往往有较强的相关性，即相邻象元的值往往是相同的。为了能以尽可能少的数据量记录尽可能多的信息，该如何在计算机中合理地组织这些栅格层数据以达到最优存储，存储空间最小呢？,问题？,3.3.4 栅格数据的编码方法,2、链码,它是从某一起点开始用沿八个基本方向前进的单位矢量链来表示线状地物或多边形的边界。 8个基本方向自0开始按逆时针方向代码分别为0，1，2，3，4，5，6，7。单位矢量的长度默认为一个栅格单元。,1,2,3,4,5,0,7,6,3.3.4 栅格数据的编码方法,2、链码,线状地物的链码编码： 2，2 6 7 6 0 6 5,链码编码示例

19、,多边形边界链码编码： 8，4 5 6 3 3 2 1 2 0 6 6 7,起始点,3.3.4 栅格数据的编码方法,2、链码,优点： 对线状地物和多边形的表示具有很强的数据压缩能力 具有一定的运算功能，如面积和周长的计算 探测编辑急弯和凹进部分比较容易 类似矢量数据结构，比较适于存储图形数据 缺点： 对于叠置运算（如：组合、相交等）很难实施 对局部修改将改变整体结构，效率较低 相邻区域的边界被重复存储，产生数据冗余,小结,3.3 栅格数据结构,3、游程长度编码,基本思路： 对于一幅栅格图像，常常有行（或列）方向上相邻的若干点具有相同的属性代码，因而可以采取某种方法压缩那些重复记录的内容。,编码

20、方案：,只在各行（或列）数据的代码发生变化时依次记录该代码值以及相同代码重复的个数。 或者：只在各行（或列）数据的代码发生变化时依次记录该代码位置以及相应的代码。,3.3.4 栅格数据的编码方法,3、游程长度编码,游程长度编码示例（行方向）,沿行方向进行编码：( 0，1），（2，2），（5，5）；（2，5），（5，3）；（2，4），（3，2），（5，2）；（0，2），（2，1），（3，3），（5，2）；（0，2），（3，4），（5，1），（3，1）；（0，3），（3，5）；（0，4），（3，4）；（0，5），（3，3）。,3.3.4 栅格数据的编码方法,3、游程长度编码,游程长度编码示例（列方

21、向）,沿列方向进行编码：( 1，0），（2，2），（5，0）；（3，2），（5，0）；（4，2），（1，3），（3，0）；（1，5），（2，2），（3，3），（2，0）；(1，5)，（1，2），（5，3），（1，0）；（2，5），（6，3）；（5，5），（3，3）；（4，5），（4，3)。,3.3.4 栅格数据的编码方法,3、游程长度编码,特点： 数据压缩效率较高，特别是对图形要素比较单一的栅格文件 栅格加密时，数据量不会明显增加，压缩效率高 最大限度的保留了原始栅格结构，编码解码运算简单，且易于检索，叠加，合并等操作 适宜性： 区域越大，数据的相关性越强，则压缩越大，适用于类型区域面积较大的

22、专题图，而不适合于类型连续变化或类别区域分散的分类图（压缩比与图的复杂程度成反比）。,小结,3.3.4 栅格数据的编码方法,4、块码,块码是游程编码扩展到二维的情况，采用方形区域作为记录单元，每个单元包括相邻的若干珊格，数据编码由初始位置（行列号）加上半径，再加上记录单元的代码组成。即数据对组成：（初始行、列，半径，属性值）,（1，1，1，0），（1，2，2，2），（1，4，1，5），（1，5，1，5），（1，6，2，5），（1，8，1，5）；（2，1，1，2），（2，4，1，2），（2，5，1，2），（2，8，1，5）；（3，1，1，2），（3，2，1，2），（3，3，1，2），（3，4，1

23、，2）， （3，5，2，3），（3，7，2，5）；（4，1，2，0），（4，3，1，2），（4，4，1，3）；（5，3，1，3），（5，4，2，3），（5，6，1，3），（5，7，1，5），（5，8，1，3）；（6，1，3，0），（6，6，3，3）；（7，4，1，0），（7，5，1，3）；（8，4，1，0），（8，5，1，0）。,4、块码,特点： 一个多边形包含的正方形越大，多边形的边界越简单，块状编码的效率越好，即块状编码对大而简单的多边形更为有效，对碎部较多的复杂多边形效果不好。 具有可变分辨率，即当属性变化小时图块大，对于大块图斑记录单元大，分辨率低，压缩比高。,小结,3.3 栅格数据结

24、构,3.3.4 栅格数据的编码方法,5、四叉树编码,是根据栅格数据二维空间分布的特点，将空间区域按照4个象限进行递归分割（2n2 n，且n1），直到子象限的数值单调为止，最后得到一棵四分叉的倒向树。四叉树分解，各子象限大小不完全一样，但都是同代码栅格单元组成的子块，其中最上面的一个结点叫做根结点，它对应于整个图形。不能再分的结点称为叶子结点，可能落在不同的层上，该结点代表子象限单一的代码，所有叶子结点所代表的方形区域覆盖了整个图形。从上到下，从左到右为叶子结点编号，最下面的一排数字表示各子区的代码。 为了保证四叉树分解能不断的进行下去，要求图形必须为2n2 n的栅格阵列。n 为极限分割次数，n

25、1是四叉树最大层数或最大高度,5、四叉树编码,基本思想： 将2n2n象元组成的图像(不足的用背景补上) 按四个象限进行递归分割，并判断属性是否单一。 单一：不分。 不单一：递归分割。 最后得到一颗四分叉的倒向树。,1 2 3 4 5 6 7 8,1 2 3 4 5 6 7 8,3.3 栅格数据结构,5、四叉树编码,树杈结点,叶子结点,1 2 3 4 5 6 7 8,1 2 3 4 5 6 7 8,四叉树的树形表示： 用一倒立树表示这种分割和分割结果。 树根：整个区域； 树高：深度、分几级，几次分割 树叶：不能再分割的块；,3.3.4 栅格数据的编码方法,5、四叉树编码,四叉树编码方法,NW （

26、0）,NE （1）,SW （2）,SE （3）,1层,2层,3层,记录每个叶子结点的地址和属性,0,1,2,3,20,21,22,23,200,201,202,203,230,231,232,233,1 2 3 4 5 6 7 8,1 2 3 4 5 6 7 8,3.3.4 栅格数据的编码方法,5、四叉树编码,优点： 容易而有效地计算多边形的数量特征； 阵列个部分的分辨率是可变的，因而既可以精确表示图形结构又可以减少存储量； 多边形中嵌套异类小多边形的表示比较方便 缺点： 转换的不定性，用同一形状和大小的多变形可能得到多种不同的四叉树结构，因此，不利于形状分析和模式识别。,总结,3.3.4 栅

27、格数据的编码方法,直接栅格编码：简单直观，是压缩编码方法的逻辑原型（栅格文件）； 链码：压缩效率较高，接近矢量结构，对边界的运算比较方便，但不具有区域性质，区域运算较难； 游程编码：在很大程度上压缩数据，又最大限度的保留了原始栅格结构，编码解码十分容易； 块码和四叉树编码：具有区域性质，又具有可变的分辨率，有较高的压缩效率，四叉树编码可以直接进行大量图形图象运算，效率较高，是当前使用较多的压缩编码方法。,总结,3.3.4 栅格数据的编码方法,3.4 矢栅结构的比较及转换算法,在GIS建立过程中，应根据应用目的和应用特点、可能获得的数据精度以及地理信息系统软件和硬件配置情况，选择合适的数据结构。

28、,栅格结构: 大范围小比例尺的自然资源、环境、农林业等区域问题的研究。,矢量结构： 城市分区或详细规划、土地管理、公用事业管理等方面的应用。,3.4 矢栅结构的比较及转换算法,3.4.1 矢栅结构的比较,3.4 矢栅结构的比较及转换算法,3.4.2 矢栅结构相互转换,矢量结构与栅格结构的相互转换，是地理信息系统的基本功能之一，目前已经发展了许多高效的转换算法；但是，从栅格数据到矢量数据的转换，特别是扫描图像的自动识别，仍然是目前研究的重点。,对于点状实体，每个实体仅由一个坐标对表示，其矢量结构和栅格结构的相互转换基本上只是坐标精度变换问题，不存在太大的技术问题。线实体的矢量结构由一系列坐标对表

29、示，在变为栅格结构时，除把序列中坐标对变为栅格行列坐标外，还需根据栅格精度要求，在坐标点之间插满一系列栅格点，这也容易由两点式直线方程得到。线实体由栅格结构变为矢量结构与将多边形边界表示为矢量结构相似，因此以下重点讨论多边形（面实体）的矢量结构与栅格结构相互转换。,3.4 矢栅结构的比较及转换算法,3.4.2 矢栅结构相互转换,1、矢量格式向栅格格式的转换 矢量格式向栅格格式转换又称为多边形填充，就是在矢量表示的多边形边界内部的所有栅格点上赋以相应的多边形编码，从而形成栅格数据阵列。几种主要的算法描述如下： （1）内部点扩散算法 该算法由每个多边形一个内部点（种子点）开始，向其八个方向的邻点扩

30、散，判断各个新加入点是否在多边形边界上，如果是边界上，则该新加入点不作为种子点，否则把非边界点的邻点作为新的种子点与原有种子点一起进行新的扩散运算，并将该种子点赋以该多边形的编号。,重复上述过程直到所有种子点填满该多边形并遇到边界停止为止。扩散算法程序设计比较复杂，并且在一定的栅格精度上，如果复杂图形的同一多边形的两条边界落在同一个或相邻的两个栅格内，会造成多边形不连通，这样一个种子点不能完成整个多边形的填充。,3.4 矢栅结构的比较及转换算法,3.4.2 矢栅结构相互转换,（2）复数积分算法 对全部栅格阵列逐个栅格单元地判断该栅格归属的多边形编码，判别方法是由待判点对每个多边形的封闭边界计算复数积分，对某个多边形，如果