第三章 空间数据结构.ppt

第三章 空间数据结构与编码,栅格数据结构及编码 矢量数据结构及编码 矢栅数据结构转换 矢栅一体化数据结构,空间数据结构与数据编码,1.概念 空间数据结构：指适合于计算机系统存储、管理和处理的地学图形的逻辑结构，是地理实体的空间排列方式和相互关系的抽象描述 空间数据编码：为实现空间数据的计算机存储、处理和管理，将空间实体的一定的数据结构转换为适合计算机操作的过程栅格数据结构：应用与图像处理系统和GIS中 矢量数据结构：主导了CAD系统和有着强大制图功能的GIS一、基于规则格网空间数据模型的数据 结构 (栅格数据结构),（一）概念 栅格数据结构是最简单最直观的空间数据结构，又称网格结构或像元结构 将地球表面划分为大小均匀紧密相邻的网格阵列，每个网格作为一个像元或者像素，有行、列号定义，并包含一个代码，表示该网格的属性值或者量值，或者仅仅包含指向其它属性记录的指针一）概念,栅格数据结构实际就是像元阵列，每个像元由行列确定它的位置 由于栅格结构是按照一定的规则排列的，所表示的实体的位置很容易隐含在文件的存储结构中，且行列坐标可以很容易的转为其他坐标系下的坐标在文件中每个代码本身明确代表实体的属性或属性编码。

点用一个栅格单元表示； 线状地物沿线走向的一组相邻栅格单元表示，每个栅格单元最多只有两个相邻单元上； 面或区域用记有区域属性的相邻栅格单元的集合表示，每个栅格单元可有多于两个的相邻单元同属一个区域一）概念,（二）基本特征,点有大小、地理空间离散 大小由行列号决定，划分程度决定点大小、点数多少、 表达内容的复杂程度及精度高低 属性特征显性表示 可以直接看到属性，并多以颜色、代码或灰度表示 面向位置、感觉微观 位置由行列号决定，每个位置都有相应的数据三）栅格数据的组织,不同类型的地理实体分层编排， 每层只有单一的类型 一个栅格单元只有一个属性代码组织方法,,,（三）栅格数据的组织,（四）栅格结构的建立,1、 手工获取，专题图上划分均匀网格，逐个决定其网格代码 2、扫描仪扫描专题图的图像数据{行、列、颜色（灰度）}，定义颜色与属性对应表，用相应属性代替相应颜色，得到（行、列、属性）再进行栅格编码、存贮，即得该专题图的栅格数据 3、 由矢量数据转换而来 4、 遥感影像数据，对地面景象的辐射和反射能量的扫描抽样，并按不同的光谱段量化后，以数字形式记录下来的象素值序列 5、 格网DEM数据，当属性值为地面高程，则为格网DEM，通过DEM内插得到。

一）建立途径,（四）栅格结构的建立,二）栅格系统的建立,1、 栅格坐标系的确定 表示具有空间分布特征的地理要素，不论采用什么编码系统，什么数据结构都应在统一的坐标系统下，而坐标系的确定实质是坐标系原点和坐标轴的确定 由于栅格编码一般用于区域性GIS，原点的选择常具有局部性质，但为了便于区域的拼接，栅格系统的起始坐标应与国家基本比例尺地形图公里网的交点相一致，并分别采用公里网的纵横坐标轴作为栅格系统的坐标轴四）栅格结构的建立,二）栅格系统的建立,2、 栅格单元的尺寸,1）原则：应能有效地逼近空间对象的分布特征，又减少数据的冗余度格网太大，忽略较小图斑，信息丢失 2）方法：用保证最小多边形的精度标准来确定尺寸经验公式： h为栅格单元边长 Ai为区域所有多边形的面积每个栅格元素只能取一个值，实际上一个栅格可能对应于实体中几种不同属性值，存在栅格数据取值问题,（四）栅格结构的建立,三）栅格属性值的确定,1、中心点法 用处于栅格中心处的地物类型或现象特性决定栅格代码 中心点法常用于具有连续分布特性的地理要素，如降雨量分布、人口密度图等 三）栅格属性值的确定,2、面积占优法 以占矩形区域面积最大的地物类型或现象特性决定栅格单元的代码 。

用于分类较细，地物类别斑块较小的情况三）栅格属性值的确定,3、长度占优法 将网格中心画一横线，用横线所占最长部分属性值作为栅格属性,三）栅格属性值的确定,4、重要性法 突出某些主要属性，只要在栅格中出现就把该属性作为栅格属性,三）栅格属性值的确定,5、百分比法 根据矩形区域内各地理要素所占面积的百分比数确定单元的取值三）栅格属性值的确定,（五）栅格数据编码方式,直接栅格编码 压缩编码方法 链码（Chain Encoding） 游程编码（Run-length Encoding） 块状编码（Block Encoding） 四叉树编码（Quandtree Encoding）,（五）栅格数据结构类型,（1）直接栅格编码 最简单最直观而又非常重要的一种栅格结构编码方法 把规则格网平面作为一个二维矩阵进行数学表达，每个栅格是具有行、列位置的矩阵元素，该空间实体属性编码值赋予矩阵元素 逐行或逐列记录代码1）直接栅格编码,(1,1,2),(1,2,2),(1,3,2), (1,4,1),(1,5,1),(1,6,7), (1,7,7),(1,8,7), (2,1,2),(2,2,2),(2,3,2), ……,如果行列号记录在专门文件中，则只记录属性值： （2,2,2,1,1,7,7,7,2,2,2,2,1,7,7,7……）,优点： 1易于实现用循环语句编程，实现快速运算 2易于实现空间属性的分解与分类，易于实现空间分析中叠加等操作,缺点： 数据存储量大,基本要素包括：行，列，属性值（N，M，Xij） 其中行、列值隐性，属性值显性。

1）直接栅格编码,（2）费尔曼链码 （边界编码）,将线状地物或区域边界表示为：由某一起始点和某些基本方向上的单位矢量链组成 前两个字母表示起点的行列号，从第三个数字开始每个数字表示单位矢量的方向单位矢量的长度为一个栅格单元，后续点可能位于前继点8个基本方向上2）费尔曼链码 （边界编码）,具体编码过程： 起始点的寻找一般遵守从上到下、从左到右的原则 当发现没有记录过的点且数值也不为零时，就是这一条线或边界的起点，记下该地物的特征码和行列号；然后按顺时针方向寻找，找到相邻的等值点，并按八个方向编码 如遇到不能闭合的线段，结束后可返回到起始点再开始寻找下一个线段 已记录过的栅格单元，可将属性代码置零，以免重复编码2）费尔曼链码 （边界编码）,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,4,5,4,5,4,5,4,2,4,4,6,5,6,7,0,2,2,1,（2）费尔曼链码 （边界编码）,优缺点： 数据压缩率强，便于计算长度，面积，转折方向的凸凹度，易于储存 但难于实现叠置运算，不便于合并插入操作对局部改动涉及到整体结构适于对曲线和边界进行编码2）费尔曼链码 （边界编码）,（3）游程（行程）编码,基本思路：对一个栅格图形，常常有行（列）方向上相邻的若干栅格单元具有相同的属性代码，因而可采用某种方法压缩那些重复代码内容。

编码方案：只是在各行（列）栅格单元的代码发生变化时依次记录该代码以及相同代码重复的个数或者记录代码发生变化的位置3）游程（行程）编码,游程：栅格数据矩阵中相邻并属性相同的栅格视为一游程，以游程为单位记录数据第一行：4个游程 第二行：3个游程,适于对块状地物的栅格数据进行压缩编码,编码方式：(gk，lk) gk—栅格属性值 lk —游程终止列号或长度 K=1,2,3,4…m(mn),分为游程终止编码和游程长度编码,（3）游程（行程）编码,(0,1) (4,3) (7,8) (4,5) (7,8) (4,4) (8,6) (7,8) (0,2) (4,3) (8,6) (7,8) (0,2) (8,6) (7,7)(8,8) (0,3) (8,8) (0,4) (8,8) (0,5) (8,8),游程终止编码,（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),游程长度编码：,（3）游程（行程）编码,特点：属性的变化愈少，游程愈长，即压缩比的大小与图的复杂程度成反比。

优点：数据压缩率高，易于实现叠加，检索和合并运算 缺点：适合类型区面积较大的专题图、遥感影像分类集中的分类图，不适合类型连续变化或类型区分散的分类图3）游程（行程）编码,（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，3，1，2），（3，4，1，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）块状编码,特点： 1、面状地物所能包含的正方形越大，多边形边界越简单，块码编码效率超高； 2、图形比较碎，多边形边界复杂的图形，数据压缩率低； 3、利于计算面积、合并插入等操作4）块状编码,（5）四叉树编码（Quadtree Code）,四叉树概述： 四叉树又称为四元树或四分树，是最有效的栅格数据压缩编码方法之一，绝大部分图形操作和运算都可以直接在四叉树结构上实现，四叉树编码即压缩了数据量，又可大大提高图形操作的效率1、基本思想：将2n×2n象元组成的图像(不足的用背景补上) 按四个象限进行递归分割，并判断属性是否单一， 单一：不分 不单一：递归分割 最后得到一颗四分叉的倒向树5）四叉树编码（Quadtree Code）,2、四叉树的树形表示： 用一倒立树表示分割和分割结果 根：整个区域 高：深度、分几级，几次分割 叶：不能再分割的块 树叉：还需分割的块1）常规四叉树及编码,原始栅格,四叉树图,,,,,,,,,,,,1）常规四叉树及编码,记录这棵树的叶结点外，中间结点，结点之间的联系用指针联系， 每个结点需要6个变量：父结点指针、四个子结点的指针和本结点的属性值对一幅2N ×2N的栅格阵列，最大深度为N，可能有的层次为0，1，2，…，N，最大层数为N+1.那么，每层的栅格宽度为： 2（最大深度-当前层次） 反映了所在叶结点表示的正方形集合的大小。

1）常规四叉树 及编码,缺点： 所占空间比较大，不仅要记录每个结点，还要记录一个前趋结点和四个后继点，以及反映结点之间联系，对栅格数据进行运算时，还要作遍历树结点的运算，增加操作复杂性1）常规四叉树及编码,指针不仅增加了数据的存储量，还增加了操作的复杂性：如层次数（分割次数）由从父结点移到根结点的次数来确定，结点所代表的图像块的位置需要从根节点开始逐步推算下来所以，常规四叉树并不广泛用于存储数据，其价值在于建立索引文件，进行数据检索2)线性四叉树及编码,以四叉树的方式组织数据，但不以四叉树方式存储数据 通过编码四叉树的叶结点表示数据的层次和空间关系叶结点具有一个反映位置的关键字，亦称位置码实质是把原来大小相等的栅格集合转换成大小不等的正方形集合，对不同尺寸和位置的正方形集合赋予一个位置码2)线性四叉树及编码,只存贮最后叶结点信息 包括：结点号、结点位置、深度、本节点的 属性或灰度值。