第二章空间数据结构及编码

第二章空间数据结构及编码1、从现实世界到计算机世界概念模型数据模型数据结构文件格式四个层次现实世界用户认识局部抽象概念模型----面向用户数据模型---面向机器按照著名数据库专家E.F.Codd的理论认为数据模型实质上是一组为用户服务的规则,这些规则规定其数据结构如何组织以及应当允许进行何种操作。一基本概念2.Gis中地理空间数据组织的主要对象•从地理空间现象或事物到计算机世界,一般也要有概念模型,数据模型,数据结构和文件格式几个层次.这个过程有时统称为地理空间数据建模Gis怎样组织数据以模拟地理事物和现象的呢?举例•我们将gis所抽象,表达的地理事物和现象,称为空间对象;空间对象的位置相互关系,称为空间关系a空间对象•点状空间对象(0维对象)•线状空间对象•面状空间对象•体状空间对象除空间维数特性外,空间对象还可以从其复杂性,规则性,人为性等角度认识和区分b空间关系通常分为3类•度量空间关系•顺序空间关系•拓扑空间关系-------连接性-------包含-------邻接性3.空间数据结构和空间数据模型两个概念之间的关系•空间数据结构和空间数据模型研究地理空间数据组织和管理.两者之间的关系,与一般的数据结构和数据模型的关系有两点相似之处.其一,空间数据结构所作的数据组织工作,比空间数据模型更基层些,它偏重数据表达的物理实现,而空间数据模型涉及到空间数据管理的层次.其二，同普通数据的数据模型一样,空间数据模型的命名通常与相应的空间数据结构相同.4.空间分析与非空间分析5.空间数据定义特点：数据的空间性数据的属性数据的时间性6.空间数据的编码7.空间数据的拓扑关系地理要素之间的空间区位关系可抽象为点、线（或弧）、多边形（区域）之间的空间几何关系，其关系如下欧氏平面上实体对象所具有的拓扑和非拓扑属性拓扑属性一个点在一个弧段的端点一个弧段是一个简单弧段（弧段自身不相交）一个点在一个区域的边界上一个点在一个区域的内部一个点在一个区域的外部一个点在一个环的内部一个面是一个简单面（面上没有“岛”）一个面的连续性（给定面上任意两点，从一点可以完全在面的内部沿任意路径走向另一点）非拓扑属性两点之间的距离一个点指向另一个点的方向弧段的长度一个区域的周长一个区域的面积弧属性表（AAT）多边形属性表（PAT）#－id多边形标识码周长面积108.418-4.50621048.5962.07831024.2961.14441012.2330.30151034.3250.983＃－id弧标识码起始结点终到结点弧左多边形弧右多变形弧长13831321.51523343351.04033541132.10643722242.23353615124.12063953521.09373445512.1931.本图有多少个多边形和弧？2.哪个多边形是包含于另一个中？3.哪个多边形和多边形102相邻？4.手工建立一个简单示意图表明本图的空间格局二、栅格数据结构定义：又称为网格结构，它是将地表划分成为紧密相邻的网格阵列。每个网格的位置由行列号定义。它包含一个代码，以表示该网格的属性或指向属性记录的指针。注意：栅格数据模型是将连续空间离散化，即用二维铺盖或划分覆盖整个连续空间，这种铺盖可以分为规则的和不规则的1.概念三角形、方格和六角形划分栅格数据模型2.图形栅格数据结构表示00002000000200000102033000023333002033330020033002000000000000000000000000002000000000000000000000000000000000000000000000000600000000000066600000000006000000000006000600000060000000000744444477774777444487780840877808800800887888880000888800000888线面点3.决定栅格单元代码的方式面积占优法中心点法重要性法4.栅格结构编码方式•直接栅格编码•行程编码•块码•链式编码•四叉树结构•二维行程编码基本思路：对于一幅栅格图像，常常有行（或列）方向上相邻的若干点具有相同的属性代码，因而可采取某种方法压缩那些重复的记录内容。游程长度编码（Run-LengthCodes）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）,（8，4）,（7，1）,（8，1）；（0，3）,（8，5）；（0，4）,（8，4）；（0，5）,（8，3）。0744444477774777444487780840877808800800887888880000888800000888压缩比的大小是与图的复杂程度成反比的，在变化多的部分，游程数就多，变化少的部分游程数就少，图件越简单，压缩效率就越高44：642）逐个记录各行（或列）代码发生变化的位置和相应代码编码如下（沿列方向）（1，0），（2，4），（4，0）；（1，4），（4，0）；（1，4），（5，8），（6，0）；（1，7），（2，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）。（属性值，属性发生变化的位置）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),(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)。0744444477774777444487780840877808800800887888880000888800000888该例中块码用了120个整数，比直接编码还多，这是因为例中为描述方便，栅格划分很粗糙，在实际应用中，栅格划分细，数据冗余多的多，才能显出压缩编码的效果，而且还可以作一些技术处理，如行号可以通过行间标记而省去记录，行号和半径等也不必用双字节整数来记录，可进一步减少数据冗余。•块码具有可变的分辨率，即当代码变化小时图块大，就是说在区域图斑内部分辨率低；反之，分辨率高。•块码与游程长度编码相似，随着图形复杂程度的提高而降低效率，就是说图斑越大，压缩比越高；图斑越碎，压缩比越低。•块码在合并、插入、检查延伸性、计算面积等操作时有明显的优越性。•然而在某些操作时，则必须把游程长度编码和块码解码，转换为基本栅格结构进行。•链码（ChainCodes）链码又称为弗里曼链码[Freeman]或边界链码，链码可以有效地压缩栅格数据，而且对于估算面积、长度、转折方向的凹凸度等运算十分方便，比较适合于存储图形数据。缺点是对边界进行合并和插入等修改编辑工作比较困难，对局部的修改将改变整体结构，效率较低，而且由于链码以每个区域为单位存储边界，相邻区域的边界将被重复存储而产生冗余。基本思想：将一幅栅格地图或图像等分为四部分，逐块检查其格网属性值（或灰度），如果某个子区的所有格网值都相同，则这个子区就不再继续分割，否则还要把这个子区再分割，直到每个子块都只含有相同的属性值或灰度为止。四叉树结构四叉树编码具有可变的分辨率，并且有区域性质，压缩数据灵活，许多运算可以在编码数据上直接实现，大大地提高了运算效率，是优秀的栅格压缩编码之一1）从四叉树的特点可知，一幅2n*2n栅格阵列图，具有的最大深度数为n，可能具有的层次为0，1，2，……..n注意2）每一层的栅格宽度，即每层边上包含的最大栅格数，反映了所在叶结点表示的正方形集合的大小，其值为：2（最大深度-当前层次）例如：一幅23×23的栅格阵列，它具有的最大深度为3，可能层次分别为0，1，2，3。其中：第0层边长上的最大栅格数为2（3-0）＝8第1层边长上的最大栅格数为2（3-1）＝4第2层边长上的最大栅格数为2（3-2）＝2第3层边长上的最大栅格数为2（3-3）＝1111100001111000011100000111000003344400033444000334400003344000011011010344004034000层1层2层3层（1）（2）（3）（4）（5）（6）（7）（8）（9）（10）（11）（12）（13）（14）（15）（16）（17）（18）（19）•常规四叉树除了记录叶结点之外，还要记录中间结点。结点之间借助指针联系，每个结点需要用六个量表达，即四个叶结点指针、一个父结点指针和一个结点的属性或灰度值。这些指针不仅增加了数据储存量，而且增加了操作的复杂性。常规四叉树与线性四叉树•线性四叉树只存储最后叶结点的信息。包括叶结点的位置、深度和本结点的属性或灰度值•线性四叉树叶结点的编号需要遵循一定的规则，这种编号成为地址码，它隐含了叶结点的位置和深度信息。a.基于深度和层次码的线性四叉树的编码它是通过记录叶结点的深度码和层次码来描述叶结点的位置码几种线性四叉树的编码111100001111000011100000111000003344400033444000334400003344000011011010344004034000层1层2层3层（1）（2）（3）（4）（5）（6）（7）（8）（9）（10）（11）（12）（13）（14）（15）（16）（17）（18）（19）该地址码的十进制为：？层次码深度码第一层第二层第三层00111100110层1层2层3层（1）（2）（3）（4）（5）（6）（7）（8）（9）（10）（11）（12）（13）（14）（15）（16）（17）（18）（19）b.基于四进制的线性四叉树编码0层1层2层3层（1）（2）（3）（4）（5）（6）（7）（8）（9）（10）（11）（12）（13）（14）（15）（16）（17）（18）（19）第一层第二层第三层033思考•请为23×23栅格阵列中的每个栅格建立基于四进制的四叉树编码方式的地址码？•你能找出何种规律？000001010011100101110111000000001010011100101110111001002003012013102103112113010020021030031120121130131011022023032033122123132133100200201210211300301310311101202203212213302303312313110220221230231320321330331111222223232233322323332333先将栅格的行列号转换为二进制，得二进制行号Iyb，列号Ixb，则M=2×Iyb＋Ixb如结点7：M=2*011+011＝033•如果知道基于四进制四叉树编码方式的地址码，你能知道它的行列号码吗？思考•若该位的编码值为0，1，则行号Iyb值为0；•若该位的编码值为2，3，则行号Iyb值为1；•若该位