第二章 空间数据结构.ppt

地理信息系统原理与方法 第二章空间数据结构 学习目标 理解地理空间信息的概念 掌握地理空间信息的描述方法 理解地理数据分类描述的方法 理解和掌握地理空间数据的拓扑关系 掌握栅格和矢量数据结构及其编码方法 了解栅格与矢量数据之间的转化方法重点 地理空间数据的拓扑关系 两种空间数据结构的特点及其编码方法 难点 拓扑结构 栅格数据编码 栅格数据结构 基本概念栅格数据结构指将空间分割成各个规则的网格单元 然后在各个格网单元内赋以空间对象相应的属性值的一种数据组织方式 在栅格结构中 点用一个栅格单元表示 线状地物则用沿线走向的一组相邻栅格单元表示 每个栅格单元最多只有两个相邻单元在线上 面或区域用记有区域属性的相邻栅格单元的集合表示 每个栅格单元可有多于两个的相邻单元同属一个区域 任何以面状分布的对象 都可以用栅格数据逼近 例子 用栅格结构表示地图 首先要给定每个物体的编码 如给定高程点的编码为8 烟囱的编码为7 铁路的编码为1 居民点的编码为5 林地的编码为3 菜地的编码为4 则地图用栅格结构表示为下图 栅格结构的特点 属性明显 定位隐含 即数据直接记录属性本身或属性的编码 而所在位置则根据行列号转换为相应的坐标给出 由于栅格结构是按一定的规则排列的 所表示的实体的位置很容易隐含在网格文件的存贮结构中 在网格文件中每个代码本身明确地代表了实体的属性或属性的编码栅格结构表示的地表是不连续的 是量化和近似离散的数据栅格数据的比例尺就是栅格大小与地表相应单元大小之比 图量化示意图 a 量化 b 量化为8bit 栅格数据层 在栅格数据结构中 物体的空间位置是用其在笛卡尔平面网格中的行号和列号坐标表示 物体的属性用像元的取值表示 每个像元在一个网格中只能取一次 同一像元要表示多重属性的事物就要用多个笛卡尔平面网格 每个笛卡尔网格表示一种属性或同一属性的不同特征 这种平面即层 栅格数据的取值方法 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 1 直接栅格编码 直接编码就是将栅格数据看作一个数据矩阵 逐行 或逐列 逐个记录代码 可以每行从左到右逐像元记录 也可奇数行从左到右而偶数行由右向左记录 为了特定的目的还可采用其他特殊的顺序 0 2 2 5 5 5 5 5 5 5 5 2 2 2 2 2 2 2 2 2 3 3 5 5 5 5 3 3 3 2 0 0 0 0 3 3 3 3 5 3 3 3 3 3 3 0 0 0 0 0 0 0 3 3 3 3 3 3 3 0 0 0 0 0 1 直接栅格编码 直接编码就是将栅格数据看作一个数据矩阵 逐行 或逐列 逐个记录代码 可以每行从左到右逐像元记录 也可奇数行从左到右而偶数行由右向左记录 为了特定的目的还可采用其他特殊的顺序 3 3 3 3 3 2 2 2 3 3 3 3 3 3 3 0 0 0 0 2 2 2 2 2 5 5 5 5 5 3 3 3 3 0 0 0 0 0 0 0 2 2 0 2 2 5 5 5 5 5 5 5 5 3 3 3 3 3 3 0 0 0 0 0 1 直接栅格编码 直接编码就是将栅格数据看作一个数据矩阵 逐行 或逐列 逐个记录代码 可以每行从左到右逐像元记录 也可奇数行从左到右而偶数行由右向左记录 为了特定的目的还可采用其他特殊的顺序 0 1 02 3 02 1 0 30 1 03 32 2 33 02 105 32 22 3 24 3 24 12 22 1 22 1 22 13 2 链式栅格编码 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 逐个记录各行 或列 代码发生变化的位置和相应代码 即按 位置 属性值 编码 沿列方向进行编码 1 0 2 2 4 0 1 2 4 0 1 2 5 3 6 0 1 5 2 2 4 3 7 0 1 5 2 2 3 3 8 0 1 5 3 3 1 5 6 3 1 5 5 3 3 行程编码 游程长度编码 3 游程长度编码 逐个记录各行 或列 代码发生变化的位置和相应代码 即 起位 止位 属性值 1 1 0 2 3 2 4 8 5 1 5 2 6 8 5 1 4 2 5 6 3 7 8 5 1 2 0 3 3 2 4 6 3 7 8 5 1 2 0 3 6 3 7 7 5 8 8 3 1 3 0 4 8 3 1 4 0 5 8 3 1 5 0 6 8 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 5 四叉树编码 是根据栅格数据二维空间分布的特点 将空间区域按照4个象限进行递归分割 2n 2n 且n 1 直到子象限的数值单调为止 最后得到一棵四分叉的倒向树 四叉树分解 各子象限大小不完全一样 但都是同代码栅格单元组成的子块 其中最上面的一个结点叫做根结点 它对应于整个图形 不能再分的结点称为叶子结点 可能落在不同的层上 该结点代表子象限单一的代码 所有叶子结点所代表的方形区域覆盖了整个图形 从上到下 从左到右为叶子结点编号 最下面的一排数字表示各子区的代码 为了保证四叉树分解能不断的进行下去 要求图形必须为2n 2n的栅格阵列 n为极限分割次数 n 1是四叉树最大层数或最大高度 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 36 37 38 39 34 35 40 000 03330333 33530022 23222202 22252555 33 355 西南 东南 西北 东北 根节点对应整个图形 总共有四层结点 每个结点对应一个象限 如2层4个结点分别对应于整个图形的四个象限 排列次序依次为西南 东南 西北 东北 叶子结点可能落在不同的层上 该结点代表的子象限具有单一的代码 所有叶子结点所代表的方形区域覆盖了整个图形 从上到下 从左到右为叶子结点的编号如图所示 共有40个叶子结点 也就是原图被划分为40个大小不等的方形子区 图中最下面的一排数字表示各子区的代码 分割的原则 将图像区域划分成四个大小相同的象限 而每个象限又可根据一定的规则判断是否继续等分为次一层的四个象限 其终止判据是 不管是哪一层上的象限 只要划分到仅代表一种地物或符合既定要求的少数几种地物时 则不能继续划分 否则一直划分到单个栅格像元为止 5 四叉树编码 直接栅格编码 简单直观 是压缩编码方法的逻辑原型 栅格文件 链码 压缩效率较高 以接近矢量结构 对边界的运算比较方便 但不具有区域性质 区域运算较难 游程长度编码 在很大程度上压缩数据 又最大限度的保留了原始栅格结构 编码解码十分容易 十分适合于微机地理信息系统采用 块码和四叉树编码 具有区域性质 又具有可变的分辨率 有较高的压缩效率 四叉树编码可以直接进行大量图形图象运算 效率较高 是很有前途的编码方法 矢量模型的概述 矢量结构通过记录坐标的方式尽可能精确地表示点 线 多边形等地理实体 点 线 面实体坐标编码 一个点的位置可以二维或者三维中的坐标的单一集合来描述 一条线通常由有序的两个或者多个坐标对集合来表示 特定坐标之间线的路径可以是一个线性函数或者一个较高次的数学函数 而线本身可以由中间点的集合来确定 一个面通常由一个边界来定义 而边界是由形成一个封闭的环状的一条或多条线所组成 如果区域有个洞在其中 那么可以采用多个环以描述它 拓扑邻接 元素之间的拓扑关系 拓扑关联 元素之间的拓扑关系 拓扑包含 元素之间的拓扑关系 1 地理空间数据的拓扑关系 不同类 同类 同类不同级 拓扑邻接 N1 N2 N1 N3 N1 N4 P1 P3 P2 P3拓扑关联 N1 1 3 6 P1 1 5 6拓扑包含 P3与P4 2 地理空间数据拓扑关系应用价值 1 确定地理实体间的相对空间位置 无需坐标和距离 2 利于空间要素查询 3 重建地理实体 点实体编码 线实体编码 多边形矢量编码 由多边形边界的x y坐标队集合及说明信息组成 对所有边界点数字化 将坐标对以顺序方式存储 由点索引与边界线号相联系 以线索引与各多边形相联系 形成完整的拓扑结构 多边形矢量编码 P1x1 y1 x2 y2 x3 y3 x4 y4 x5 y5 x6 y6 x1 y1 P2x7 y7 x8 y8 x9 y9 x10 y10 x11 y11 x5 y5 x6 y6 x7 y7 P3x12 y12 x13 y13 x14 y14 x15 y15 x12 y12 树状索引法 树状索引法 线号起点终点点号 656 1 2 3 4 5 565 6 656 7 8 9 10 11 5 121312 15 14 13 树状索引法 多边形文件多边形号边界线号1 2 3 树状索