空间数据结构及编码课件.ppt

1、空间数据结构及编码空间数据结构及编码 1.定义：定义：是指以地球表面空间位置为参照的是指以地球表面空间位置为参照的自然、社会和人文经济景观数据，可以是图形、自然、社会和人文经济景观数据，可以是图形、图像、文字、表格和数字等。图像、文字、表格和数字等。它是由系统的建立者通过数字化仪、扫描仪、键盘、它是由系统的建立者通过数字化仪、扫描仪、键盘、磁带机或其他系统通讯输入磁带机或其他系统通讯输入GISGIS，是系统程序作用的对，是系统程序作用的对象，是象，是GISGIS所表达的现实世界经过模型抽象的实质性内所表达的现实世界经过模型抽象的实质性内容容一、空间数据基本概念一、空间数据基本概念2.空间数据特

2、点：空间数据特点：数据的空间性数据的空间性 数据的属性数据的属性 数据的时间性数据的时间性3.在在GIS中，空间数据主要包括中，空间数据主要包括：1）某个已知坐标系中的位置）某个已知坐标系中的位置 2）实体间的空间关系）实体间的空间关系 3）与几何位置无关的属性）与几何位置无关的属性4.空间数据的拓扑关系空间数据的拓扑关系地理要素之间的空间区位关系可抽象为点、线（或弧）、多地理要素之间的空间区位关系可抽象为点、线（或弧）、多边形（区域）之间的空间几何关系，其关系边形（区域）之间的空间几何关系，其关系如下如下 欧氏平面上实体对象所具有的拓扑和非拓扑属性 拓扑属性拓扑属性一个点在一个弧段的端点一个

3、点在一个弧段的端点一个弧段是一个简单弧段（弧段自身不相交）一个弧段是一个简单弧段（弧段自身不相交）一个点在一个区域的边界上一个点在一个区域的边界上一个点在一个区域的内部一个点在一个区域的内部一个点在一个区域的外部一个点在一个区域的外部一个点在一个环的内部一个点在一个环的内部一个面是一个简单面（面上没有一个面是一个简单面（面上没有“岛岛”）一个面的连续性（给定面上任意两点，从一点可以完全在面一个面的连续性（给定面上任意两点，从一点可以完全在面的内部沿任意路径走向另一点）的内部沿任意路径走向另一点）非拓扑属非拓扑属性性两点之间的距离两点之间的距离一个点指向另一个点的方向一个点指向另一个点的方向弧段

4、的长度弧段的长度一个区域的周长一个区域的周长一个区域的面积一个区域的面积 基本的拓扑关系包括：连接性、包含和邻接性 定义：又称为网格结构，它是将地表划分定义：又称为网格结构，它是将地表划分成为紧密相邻的网格阵列。每个网格的位成为紧密相邻的网格阵列。每个网格的位置由行列号定义。它包含一个代码，以表置由行列号定义。它包含一个代码，以表示该网格的属性或指向属性记录的指针。示该网格的属性或指向属性记录的指针。注意：栅格数据模型是将连续空间离散化。注意：栅格数据模型是将连续空间离散化。1.概念概念二、栅格数据结构二、栅格数据结构二 维 空 间 坐二 维 空 间 坐标 网 或 其 局标 网 或 其 局部部

5、特别方便计算机特别方便计算机运作的数据组织运作的数据组织形式形式矩阵数矩阵数组组规整栅格：规整栅格：研究区域划分为规整研究区域划分为规整格网，空间位置数据格网，空间位置数据隐含其中隐含其中每一网格上放置空每一网格上放置空间对象在该位置上间对象在该位置上的属性数据的属性数据栅格空间数据模型栅格空间数据模型 三角形、方格和六角形划分三角形、方格和六角形划分 2.图形栅格数据结构表示图形栅格数据结构表示0 0 0 0 2 0 000 0 0 2 0 0 000 1 0 2 0 3 300 0 0 2 3 3 330 0 2 0 3 3 330 0 2 0 0 3 300 2 0 0 0 0 00 0

6、 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 6 0 0 0 0 0 0 0 0 0 0 0 0 6 6 6 0 0 0 0 0 0 0 0 0 0 6 0 0 0 0 0 0 0 0 0 0 0 6 0 0 0 6 0 0 0 0 0 0 6 0 0 0 0 0 0 0 0 0 0 7 4 4 4 4 4 4 7 7 7 7 4 7 7 7 4 4 4 4 8 7 7

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

8、码发生变化时依次记录该代码以及相同的代码重复的个依次记录该代码以及相同的代码重复的个数，从而实现数据的压缩。数，从而实现数据的压缩。两种方案两种方案（属性值，长度）（属性值，长度）例如例如 （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）。）。07444444777747774444877808408778088008008878888800008888

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

10、0）；）；（1，7），（），（2，4），（），（3，8），（），（8，0）；）；（1，7），（），（3，8）；）；（1，7），（），（6，8）；）；（1，7），（），（5，8）。）。（属性发生变化的位置（属性发生变化的位置，属性值），属性值）0744444477774777444487780840877808800800887888880000888800000888 特点：属性的变化愈少，行程愈长，则压特点：属性的变化愈少，行程愈长，则压缩的比例越大，压缩比与图的复杂程度成缩的比例越大，压缩比与图的复杂程度成反比。反比。块码是游程长度编码扩展到二维的情况，采用方块码是游程长度编码扩展到二维的

11、情况，采用方形区域作为记录单元，每个记录单元包括相邻的若形区域作为记录单元，每个记录单元包括相邻的若干栅格，数据结构由初始位置（行、列号）和半径，干栅格，数据结构由初始位置（行、列号）和半径，再加上记录单位的代码组成。再加上记录单位的代码组成。块块 码码0744444477774777444487780840877808800800887888880000888800000888对图所示图像的块码编码如下：对图所示图像的块码编码如下：(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),(

12、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),(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个整数，比直接编码还多，这是因为例中为描述方便，个整数，比直接编码还多，这是因为例中为描述方便，栅格划分很粗糙，在实际应用中，栅

13、格划分细，数据冗余多的多，才能显栅格划分很粗糙，在实际应用中，栅格划分细，数据冗余多的多，才能显出压缩编码的效果，而且还可以作一些技术处理，如行号可以通过行间标出压缩编码的效果，而且还可以作一些技术处理，如行号可以通过行间标记而省去记录，行号和半径等也不必用双字节整数来记录，可进一步减少记而省去记录，行号和半径等也不必用双字节整数来记录，可进一步减少数据冗余。数据冗余。链码（链码（Chain Codes）链码又称为弗里曼链码链码又称为弗里曼链码Freeman或边界或边界链码，链码可以有效地压缩栅格数据，而链码，链码可以有效地压缩栅格数据，而且对于估算面积、长度、转折方向的凹凸且对于估算面积、长

14、度、转折方向的凹凸度等运算十分方便，比较适合于存储图形度等运算十分方便，比较适合于存储图形数据数据。缺点缺点是对边界进行合并和插入等修改编辑是对边界进行合并和插入等修改编辑工作比较困难，对局部的修改将改变整体工作比较困难，对局部的修改将改变整体结构，效率较低，而且由于链码以每个区结构，效率较低，而且由于链码以每个区域为单位存储边界，相邻区域的边界将被域为单位存储边界，相邻区域的边界将被重复存储而产生冗余重复存储而产生冗余。基本思想基本思想：将一幅栅格地图或图像等分为四部分，：将一幅栅格地图或图像等分为四部分，逐块检查其格网属性值（或灰度），如果某个子逐块检查其格网属性值（或灰度），如果某个子区

15、的所有格网值都相同，则这个子区就不再继续区的所有格网值都相同，则这个子区就不再继续分割，否则还要把这个子区再分割，直到每个子分割，否则还要把这个子区再分割，直到每个子块都只含有相同的属性值或灰度为止。块都只含有相同的属性值或灰度为止。四叉树结构四叉树结构四叉树编码具有可变的分辨率，并且有区域性质，四叉树编码具有可变的分辨率，并且有区域性质，压缩数据灵活，许多运算可以在编码数据上直接实压缩数据灵活，许多运算可以在编码数据上直接实现，大大地提高了运算效率，是优秀的栅格压缩编现，大大地提高了运算效率，是优秀的栅格压缩编码之一码之一11110000111100001110000011100000334

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

17、据储存量，而且增加了操作的复杂性。量，而且增加了操作的复杂性。常规四叉树与线性四叉树常规四叉树与线性四叉树 线性四叉树只存储最后叶结点的信息。线性四叉树只存储最后叶结点的信息。包括叶结点的位置、深度和本结点的属性包括叶结点的位置、深度和本结点的属性或灰度值或灰度值 线性四叉树叶结点的编号需要遵循一定的线性四叉树叶结点的编号需要遵循一定的规则，这种编号成为地址码，它隐含了叶规则，这种编号成为地址码，它隐含了叶结点的位置和深度信息。结点的位置和深度信息。规则：首先将二维栅格数据的行列号转换为二进制，然后交叉放入Morton码中，即为线性四叉树的地址码：行号5（1 0 1）；列号7（1 1 1）Mo

18、rton 1 1 0 1 1 155 基于十进制的线性四叉树编码基于十进制的线性四叉树编码0145236789131410121516 图形文件如：TIFF、GIF、JPEG文件可用各种图像压缩算法作均称压缩，TIFF和GIF文件用无损压缩，使原图被精确重构无损压缩，使原图被精确重构，而JPEG采用有损压缩，它可达到很大的压缩有损压缩，它可达到很大的压缩比，但不能完整重构原图像比，但不能完整重构原图像。4.栅格数据类型栅格数据类型 卫星影像卫星影像 数字高程模型数字高程模型 数字正射影像数字正射影像 二进制扫描文件二进制扫描文件 数字栅格图形数字栅格图形 图形文件图形文件 特定地理信息系统软件

19、的栅格数据特定地理信息系统软件的栅格数据三、矢量数据结构三、矢量数据结构1.矢量空间数据模型空间对象 计算机中的表达点状 点坐标（x,y）线状 一串点坐标面状 一串首尾相连的点坐标描述对象本身的性质；描述某些空间关系其他说明数据几何数据：表达空间对象形状、位置及其位置关系每一点、线、面的唯一标识符属性数据（常用关系表组织）二维空间坐标2.有代表性的矢量空间数据结构1）Spaghetti结构结构 坐标序列法非拓扑数据结构非拓扑数据结构 由多边形边界的由多边形边界的x、y坐标对集合及说明信息组成，是坐标对集合及说明信息组成，是最简单的一种多边形矢量编码，如上图记为以下坐标文件：最简单的一种多边形矢

20、量编码，如上图记为以下坐标文件：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；30：x33,y33；x34,y34；x35,y35；x36,y36；x37,y37；x38,y38；x39,y39；x40,y40

21、；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多边形之间的公共边界被数字化和存储两次，由此多边形之间的公共边界被数字化和存储两次，由此产生冗余和碎屑多边形；产生

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

23、构）树状索引结构 以下分别为右以下分别为右图的多边形文图的多边形文件和线文件树件和线文件树状索引示意图。状索引示意图。其文件结构如其文件结构如下：下：线与多边形之间的树状索引点与边界线之间的树状索引 采用上述的树状结构，前图的多边形数据记录如下：1）点文件）点文件点号点号坐标坐标1x1,y12x2,y240 x40,y40 2）线文件）线文件线号线号起点起点终点终点点号点号I161,2,3,4,5,6II686,7,8X333333,34,35,36,37,38,39,40,333）多边形文件）多边形文件多边形编号多边形编号多边形边界多边形边界10I,II,IX20III,VII,VIII,I

24、X,X30X40IV,VI,VII50II,III,IV,V 树状索引结构树状索引结构消除了消除了相邻多边形边界的数相邻多边形边界的数据冗余和不一致的问题据冗余和不一致的问题，在简化过于复杂，在简化过于复杂的边界线或合并相邻多边形时可不必改造的边界线或合并相邻多边形时可不必改造索引表，邻域信息和岛状信息可以通过对索引表，邻域信息和岛状信息可以通过对多边形文件的线索引处理得到。多边形文件的线索引处理得到。但是比较繁琐，因而给相邻函数运算，消但是比较繁琐，因而给相邻函数运算，消除无用边，处理岛状信息以及检查拓扑关除无用边，处理岛状信息以及检查拓扑关系带来一定的困难，而且两个编码表都需系带来一定的困

25、难，而且两个编码表都需要以人工方式建立，工作量大且容易出错要以人工方式建立，工作量大且容易出错 拓扑结构拓扑结构 拓扑型数据结构由拓扑型数据结构由弧段坐标文件、结点文弧段坐标文件、结点文件和多边形文件等一系列含拓扑关系的数件和多边形文件等一系列含拓扑关系的数据文件组成据文件组成。结点文件由结点记录组成，存贮每个结点的结点号、结点坐标及与该结点连接的弧段等弧段坐标文件存贮组成弧段的点的坐标弧段文件由弧记录组成，存贮弧段的起止结点号和左右多边形号；多边形文件由多边形记录组成，存贮多边形号、组成多边形的弧段号以及多边形的周长、面积、中心点坐标。弧段号坐标串L1(X1,y1),(X2,y2),(X3,

26、y3).L2X1,y1),(X2,y2),(X3,y3).节点号节点坐标弧段V1X1,y1L1,L4,L5V2X2,y2L2,L3,L6弧段坐标文件节点文件弧段文件弧段文件多边形文件多边形文件#id多边形标识码多边形标识码周长周长面积面积1P08.418-4.5062P18.5962.078弧段号弧段号起点起点终点终点左多边形左多边形右多边形右多边形L1V1V4P0P1L2V4V6P0P2 Esri规定用于arcinfo的标准拓扑矢量数据格式为图层（coverage），在arcview中采用的标准非拓扑数据格式叫做shapefile四、栅格结构与矢量结构的比较四、栅格结构与矢量结构的比较 优点优点缺点缺点矢量数据矢量数据1数据结构紧凑、冗余数据结构紧凑、冗余度低度低2有利于网络和检索分有利于网络和检索分析析3图形显示质量好、精图形显示质量好、精度高度高1数据结构复杂数据结构复杂2多边形叠加分析比较多边形叠加分析比较困难困难栅格数据栅格数据1数据结构简单数据结构简单2便于空间分析和地表便于空间分析和地表模拟模拟3现势性较强现势性较强1数据量大数据量大2投影转换比较复杂投影转换比较复杂五、两种结构的相互转换 栅格数据的矢量化 矢量数据的栅格化