空间数据结构及编码.

《空间数据结构及编码.》由会员分享，可在线阅读，更多相关《空间数据结构及编码.（50页珍藏版）》请在金锄头文库上搜索。

1、空间数据结构及编码 1.定义： 是指以地球表面空间位置为参照的 自然、社会和人文经济景观数据，可以是图形 、图像、文字、表格和数字等。 它是由系统的建立者通过数字化仪、扫描仪、键盘、 磁带机或其他系统通讯输入GIS，是系统程序作用的对 象，是GIS所表达的现实世界经过模型抽象的实质性内 容 一、空间数据基本概念 2.空间数据特点： 数据的空间性 数据的属性 数据的时间性 3.在GIS中，空间数据主要包括 ： 1）某个已知坐标系中的位置 2）实体间的空间关系 3）与几何位置无关的属性 4.空间数据的拓扑关系 地理要素之间的空间区位关系可抽象为点、线（或弧）、多 边形（区域）之间的空间几何关系，其

2、关系如下 欧氏平面上实体对象所具有的拓扑 和非拓扑属性 拓扑属性一个点在一个弧段的端点 一个弧段是一个简单简单 弧段（弧段自身不相交） 一个点在一个区域的边边界上 一个点在一个区域的内部 一个点在一个区域的外部 一个点在一个环环的内部 一个面是一个简单简单 面（面上没有“岛岛”） 一个面的连续连续 性（给给定面上任意两点，从一点可以完全在 面的内部沿任意路径走向另一点） 非拓扑属 性 两点之间间的距离 一个点指向另一个点的方向 弧段的长长度 一个区域的周长长 一个区域的面积积 基本的拓扑关系包括：连接性、包含和邻 接性 定义：又称为网格结构，它是将地表划分 成为紧密相邻的网格阵列。每个网格的位

3、 置由行列号定义。它包含一个代码，以表 示该网格的属性或指向属性记录的指针。 注意：栅格数据模型是将连续空间离散化 。 1.概念 二、栅格数据结构 二维空间坐 标网或其局 部 特别方便计算机 运作的数据组织 形式矩阵数 组 规整栅格： 研究区域划分为规整 格网，空间位置数据 隐含其中 每一网格上放置空 间对象在该位置上 的属性数据 栅格空间数据模型 三角形、方格和六角形划分 2.图形栅格数据结构表示 0 0 0 0 2 0 00 0 0 0 2 0 0 00 0 1 0 2 0 3 30 0 0 0 2 3 3 33 0 0 2 0 3 3 33 0 0 2 0 0 3 30 0 2 0 0

4、0 0 00 线面点 3.栅格结构编码方式 直接栅格编码 行程编码 块码 链式编码 四叉树结构 二维行程编码 下一页 基本思路：对于一幅栅格图像，常常有行（ 或列）方向上相邻的若干点具有相同的属 性代码，因而可采取某种方法压缩那些重 复的记录内容。 游程长度编码（Run-Length Codes） 1）只在各行（或列）数据的代码发生变化时 依次记录该代码以及相同的代码重复的个 数，从而实现数据的压缩。 两种方案 （属性值，长度） 例如 （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）

5、,（8，4）,（7，1）,（8，1）； （0，3）, （8，5）；（0，4）,（8，4）；（0，5）,（8，3）。 0744 4444 7777 4777 44448778 08408778 0880 0800 8878 8888 00008888 00000888 压缩比的大小是与图的复杂程度成反比 的，在变化多的部分，游程数就多，变 化少的部分游程数就少，图件越简单， 压缩效率就越高 44：64 2）逐个记录各行（或列）代码发 生变化的位置和相应代码 编码如下（沿列方向） （1，0），（2，4），（4，0）； （1，4），（4，0）； （1，4），（5，8），（6，0）； （1，7），（2

6、，4），（4，8），（7，0）； （1，7），（2，4），（3，8），（8，0）； （1，7），（3，8）； （1，7），（6，8）； （1，7），（5，8）。 （属性发生变化的位置 ，属性值） 0744 4444 7777 4777 44448778 08408778 0880 0800 8878 8888 00008888 00000888 特点：属性的变化愈少，行程愈长，则压 缩的比例越大，压缩比与图的复杂程度成 反比。 块码是游程长度编码扩展到二维的情况，采用方 形区域作为记录单元，每个记录单元包括相邻的若 干栅格，数据结构由初始位置（行、列号）和半径 ，再加上记录单位的代码组成。 块

7、 码 0744 4444 7777 4777 44448778 08408778 0880 0800 8878 8888 00008888 00000888 对图所示图像的块码编码如下： (1,1,1,0),(1,2,2,4),(1,4,1,7),(1,5,1,7), (1,6,2,7),(1,8,1,7),(2,1,1,4),(2,4,1,4), (2,5,1,4),(2,8,1,7),(3,1,1,4),(3,2,1,4), (3,3,1,4),(3,4,1,4),(3,5,2,8),(3,7,2,7), (4,1,2,0),(4,3,1,4),(4,4,1,8),(5,3,1,8), (

8、5,4,2,8),(5,6,1,8),(5,7,1,7),(5,8,1,8), (6,1,3,0),(6,6,3,8),(7,4,1,0),(7,5,1,8), (8,4,1,0),(8,5,1,0)。 该例中块码用了120个整数，比直接编码还多，这是因为例中为描述方便 ，栅格划分很粗糙，在实际应用中，栅格划分细，数据冗余多的多，才能 显出压缩编码的效果，而且还可以作一些技术处理，如行号可以通过行间 标记而省去记录，行号和半径等也不必用双字节整数来记录，可进一步减 少数据冗余。 链码（Chain Codes） 链码又称为弗里曼链码Freeman或边界 链码，链码可以有效地压缩栅格数据，而 且对

9、于估算面积、长度、转折方向的凹凸 度等运算十分方便，比较适合于存储图形 数据。 缺点是对边界进行合并和插入等修改编辑 工作比较困难，对局部的修改将改变整体 结构，效率较低，而且由于链码以每个区 域为单位存储边界，相邻区域的边界将被 重复存储而产生冗余。 基本思想：将一幅栅格地图或图像等分为四部分 ，逐块检查其格网属性值（或灰度），如果某个 子区的所有格网值都相同，则这个子区就不再继 续分割，否则还要把这个子区再分割，直到每个 子块都只含有相同的属性值或灰度为止。 四叉树结构 四叉树编码具有可变的分辨率，并且有区域性质， 压缩数据灵活，许多运算可以在编码数据上直接实 现，大大地提高了运算效率，是

10、优秀的栅格压缩编 码之一 11110000 11110000 11100000 11100000 33444000 33444000 33440000 33440000 110 110 10 34400 40 3400 0层 1层 2层 3层 （1） （2）（3） （4）（5）（6） （7） （8） （9） （10） （11） （12） （13）（14） （15） （16） （17） （18） （19） 常规四叉树除了记录叶结点之外，还要记 录中间结点。结点之间借助指针联系，每 个结点需要用六个量表达，即四个叶结点 指针、一个父结点指针和一个结点的属性 或灰度值。这些指针不仅增加了数据储存 量

11、，而且增加了操作的复杂性。 常规四叉树与线性四叉树 线性四叉树只存储最后叶结点的信息。 包括叶结点的位置、深度和本结点的属性 或灰度值 线性四叉树叶结点的编号需要遵循一定的 规则，这种编号成为地址码，它隐含了叶 结点的位置和深度信息。 规则：首先将二维栅格数据的行列号转换为 二进制，然后交叉放入Morton码中，即为 线性四叉树的地址码： 行号5（1 0 1）；列号7（1 1 1） Morton 1 1 0 1 1 155 基于十进制的线性四叉树编码 0145 2367 891314 10121516 图形文件如：TIFF、GIF、JPEG文件可用 各种图像压缩算法作均称压缩，TIFF和GIF

12、 文件用无损压缩，使原图被精确重构，而 JPEG采用有损压缩，它可达到很大的压缩 比，但不能完整重构原图像。 4.栅格数据类型 卫星影像 数字高程模型 数字正射影像 二进制扫描文件 数字栅格图形 图形文件 特定地理信息系统软件的栅格数据 三、矢量数据结构 1.矢量空间数据模型 空间对象 计算机中的表达 点状 点坐标（x,y） 线状 一串点坐标 面状 一串首尾相连的点坐标 描述对象本身的性质； 描述某些空间关系 其他说明数据 几何数据： 表达空间对象形状 、位置及其位置关 系 每一点、线、 面的唯一标识 符 属性数据 （常用关 系表组织 ） 二维空间 坐标 2.有代表性的矢量空间数据结构 1）S

13、paghetti结构 坐标序列法 非拓扑数据结构 由多边形边界的x、y坐标对集合及说明信息组成，是最 简单的一种多边形矢量编码，如上图记为以下坐标文件： 10：x1,y1；x2,y2；x3,y3；x4,y4；x5,y5；x6,y6；x7,y7；x8,y8； x9,y9；x10,y10；x11,y11； x1,y1； 20：x1,y1；x12,y12；x13,y13；x14,y14；x15,y15；x16,y16； x17,y17；x18,y18；x19,y19；x20,y20；x21,y21；x22,y22； x23,y23；x8,y8；x9,y9；x10,y10；x11,y11； x1,y1

14、； 30：x33,y33；x34,y34；x35,y35；x36,y36；x37,y37；x38,y38； x39,y39；x40,y40； x33,y33； 40：x19,y19；x20,y20；x21,y21；x28,y28；x29,y29；x30,y30； x31,y31；x32,y32； x19,y19； 50：x21,y21；x22,y22；x23,y23；x8,y8；x7,y7；x6,y6；x24,y24 ；x25,y25；x26,y26；x27,y27；x28,y28； x21,y21； 坐标序列法文件结构简单，易于实现以多边形为单位 的运算和显示。 缺点： 1多边形之间的公共边

15、界被数字化和存储两次，由此 产生冗余和碎屑多边形； 2每个多边形自成体系而缺少邻域信息，难以进行邻 域处理，如消除某两个多边形之间的共同边界； 3. 岛只作为一个单个的图形建造，没有与外包多边形 的联系； 4不易检查拓扑错误。这种方法可用于简单的粗精度 制图系统中 该法采用树状索引以减少数据冗余并间接 增加邻域信息，方法是对所有边界点进行 数字化，将坐标对以顺序方式存储，由点 索引与边界线号相联系，以线索引与各多 边形相联系，形成树状索引结构 2）树状索引结构 以下分别为右 图的多边形文 件和线文件树 状索引示意图 。其文件结构 如下： 线与多边形之间的树状索引 点与边界线之间的树状索引 采用

16、上述的树状结构，前图的多边形数据记录 如下： 1）点文件 点号 坐标标 1x1,y1 2x2,y2 40x40,y40 2）线线文件 线线号 起点终终点点号 I161,2,3,4,5,6 II686,7,8 X333333,34,35,36,37,38,39,40,33 3）多边边形文件 多边边形编编号 多边边形边边界 10I,II,IX 20III,VII,VIII,IX,X 30X 40IV,VI,VII 50II,III,IV,V 树状索引结构消除了相邻多边形边界的数 据冗余和不一致的问题，在简化过于复杂 的边界线或合并相邻多边形时可不必改造 索引表，邻域信息和岛状信息可以通过对 多边形文件的线索引处理得到。 但是比较繁琐，因而给相邻函数运算，消 除无用边，处理岛状信息以及检查拓扑关 系带来一定的困难，而且两个编码表都需 要以人工方式建立，工作量大且容易出错 拓扑结构 拓扑型数据结构由弧段坐