空间数据结构及编码.ppt

空间数据结构及编码,1.定义：是指以地球表面空间位置为参照的自然、社会和人文经济景观数据，可以是图形、图像、文字、表格和数字等。,它是由系统的建立者通过数字化仪、扫描仪、键盘、磁带机或其他系统通讯输入GIS，是系统程序作用的对象，是GIS所表达的现实世界经过模型抽象的实质性内容,一、空间数据基本概念,2.空间数据特点：数据的空间性 数据的属性 数据的时间性,3.在GIS中，空间数据主要包括：1）某个已知坐标系中的位置2）实体间的空间关系3）与几何位置无关的属性,4.空间数据的拓扑关系,地理要素之间的空间区位关系可抽象为点、线（或弧）、多边形（区域）之间的空间几何关系，其关系如下,欧氏平面上实体对象所具有的拓扑和非拓扑属性,基本的拓扑关系包括：连接性、包含和邻接性,定义：又称为网格结构，它是将地表划分成为紧密相邻的网格阵列。每个网格的位置由行列号定义。它包含一个代码，以表示该网格的属性或指向属性记录的指针。注意：栅格数据模型是将连续空间离散化。,1.概念,二、栅格数据结构,栅格空间数据模型,三角形、方格和六角形划分,2.图形栅格数据结构表示,线,面,点,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）,（8，4）,（7，1）,（8，1）；（0，3）,（8，5）；（0，4）,（8，4）；（0，5）,（8，3）。,压缩比的大小是与图的复杂程度成反比的，在变化多的部分，游程数就多，变化少的部分游程数就少，图件越简单，压缩效率就越高,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，0）；（1，7），（2，4），（3，8），（8，0）；（1，7），（3，8）；（1，7），（6，8）；（1，7），（5，8）。,（属性发生变化的位置，属性值）,特点：属性的变化愈少，行程愈长，则压缩的比例越大，压缩比与图的复杂程度成反比。,块码是游程长度编码扩展到二维的情况，采用方形区域作为记录单元，每个记录单元包括相邻的若干栅格，数据结构由初始位置（行、列号）和半径，再加上记录单位的代码组成。,块 码,对图所示图像的块码编码如下：(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)。,该例中块码用了120个整数，比直接编码还多，这是因为例中为描述方便，栅格划分很粗糙，在实际应用中，栅格划分细，数据冗余多的多，才能显出压缩编码的效果，而且还可以作一些技术处理，如行号可以通过行间标记而省去记录，行号和半径等也不必用双字节整数来记录，可进一步减少数据冗余。,链码（Chain Codes）,基本思想：将一幅栅格地图或图像等分为四部分，逐块检查其格网属性值（或灰度），如果某个子区的所有格网值都相同，则这个子区就不再继续分割，否则还要把这个子区再分割，直到每个子块都只含有相同的属性值或灰度为止。,四叉树结构,四叉树编码具有可变的分辨率，并且有区域性质，压缩数据灵活，许多运算可以在编码数据上直接实现，大大地提高了运算效率，是优秀的栅格压缩编码之一,0层,1层,2层,3层,（1）,（2）,（3）,（4）,（5）,（6）,（7）,（8）,（9）,（10）,（11）,（12）,（13）,（14）,（15）,（16）,（17）,（18）,（19）,常规四叉树除了记录叶结点之外，还要记录中间结点。结点之间借助指针联系，每个结点需要用六个量表达，即四个叶结点指针、一个父结点指针和一个结点的属性或灰度值。这些指针不仅增加了数据储存量，而且增加了操作的复杂性。,常规四叉树与线性四叉树,线性四叉树只存储最后叶结点的信息。包括叶结点的位置、深度和本结点的属性或灰度值线性四叉树叶结点的编号需要遵循一定的规则，这种编号成为地址码，它隐含了叶结点的位置和深度信息。,规则：首先将二维栅格数据的行列号转换为二进制，然后交叉放入Morton码中，即为线性四叉树的地址码：行号5（1 0 1）；列号7（1 1 1）Morton 1 1 0 1 1 155,基于十进制的线性四叉树编码,图形文件如：TIFF、GIF、JPEG文件可用各种图像压缩算法作均称压缩，TIFF和GIF文件用无损压缩，使原图被精确重构，而JPEG采用有损压缩，它可达到很大的压缩比，但不能完整重构原图像。,4.栅格数据类型,卫星影像数字高程模型数字正射影像二进制扫描文件数字栅格图形图形文件特定地理信息系统软件的栅格数据,三、矢量数据结构,1.矢量空间数据模型,2.有代表性的矢量空间数据结构,1）Spaghetti结构 坐标序列法,非拓扑数据结构,由多边形边界的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；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多边形之间的公共边界被数字化和存储两次，由此产生冗余和碎屑多边形；2每个多边形自成体系而缺少邻域信息，难以进行邻域处理，如消除某两个多边形之间的共同边界；3.岛只作为一个单个的图形建造，没有与外包多边形的联系；4不易检查拓扑错误。这种方法可用于简单的粗精度制图系统中,该法采用树状索引以减少数据冗余并间接增加邻域信息，方法是对所有边界点进行数字化，将坐标对以顺序方式存储，由点索引与边界线号相联系，以线索引与各多边形相联系，形成树状索引结构,2）树状索引结构,以下分别为右图的多边形文件和线文件树状索引示意图。其文件结构如下：,线与多边形之间的树状索引,点与边界线之间的树状索引,采用上述的树状结构，前图的多边形数据记录如下：1）点文件,2）线文件,3）多边形文件,树状索引结构消除了相邻多边形边界的数据冗余和不一致的问题，在简化过于复杂的边界线或合并相邻多边形时可不必改造索引表，邻域信息和岛状信息可以通过对多边形文件的线索引处理得到。但是比较繁琐，因而给相邻函数运算，消除无用边，处理岛状信息以及检查拓扑关系带来一定的困难，而且两个编码表都需要以人工方式建立，工作量大且容易出错,拓扑结构,拓扑型数据结构由弧段坐标文件、结点文件和多边形文件等一系列含拓扑关系的数据文件组成。,结点文件由结点记录组成，存贮每个结点的结点号、结点坐标及与该结点连接的弧段等弧段坐标文件存贮组成弧段的点的坐标弧段文件由弧记录组成，存贮弧段的起止结点号和左右多边形号；多边形文件由多边形记录组成，存贮多边形号、组成多边形的弧段号以及多边形的周长、面积、中心点坐标。,弧段坐标文件,节点文件,弧段文件,多边形文件,Esri规定用于arcinfo的标准拓扑矢量数据格式为图层（coverage），在arcview中采用的标准非拓扑数据格式叫做shapefile,四、栅格结构与矢量结构的比较,五、两种结构的相互转换,栅格数据的矢量化矢量数据的栅格化,