第四章 空间数据结构.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,第四章 空间数据结构,数据结构,即数据的组织形式，是适用于计算机存储、管理、处理的数据逻辑表达。换句话说，是指数据以什么形式在计算机中存储和处理。,空间数据结构,是空间逻辑数据模型在计算机中的组织关系和编排方式。包括基于矢量模型的矢量数据结构、基于栅格模型的栅格数据结构和基于不规则镶嵌模型的,TIN,的曲面数据结构等。,4.1,矢量数据结构,矢量数据结构,是对矢量数据模型进行数据的组织，通过记录坐标的方式尽可能精确地表示点、线、多边形等地理实体，坐标空间设为连续，允许任意位置、长度和面积的精确定义。,其,精度仅受数字化设备的精度和数值记录字长的限制。,矢量数据,矢量数据的类型,Buildings.Polygon,Streams,Line,Wells,Point,Roads,Line,Zoning,Polygon,MAP SHEETS,矢量结构允许最复杂的数据以最小的数据冗余进行存储，相对栅格结构来说，数据精度高，数据存储的冗余小，是高效的空间数据结构。,分为,实体数据结构,和,拓扑数据结构,。,4.1.1,实体数据结构,实体数据结构中，空间数据按照基本的空间对象（点、线或多边形）为单元进行单独的组织，其中不包含拓扑关系信息，最典型的是所谓的面条（,spaghetti,）结构，又称为坐标序列法。常采用这种数据结构的有,ArcGIS,中的,Shape,文件和,MapInfo,的,Tab,文件等。（,49,页）,点的,表示,线的表示,面的,表示,矢量数据模型中单一空间实体的表达,坐标序列法（,Spaghetti,方式）示例,图形数据,1,0,：,x1,y1,；,x2,y2,；,x3,y3,；,x4,y4,；,x5,y5,；,x6,y6,；,x7,y7,；,x8,y8,；,x9,y9,；,x10,y10,；,x11,y11,；,x1,y1,。,2,0,：,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,。,编码数据,坐标序列法的优缺点,优点：文件结构简单，易于实现以多边形为单位的运算和显示,缺点：,对于相连的线，交叉点要重复输入和存储；对于多边形其公共边也要重复输入和存储，从而产生数据冗余和分析处理不便的问题；,对于复杂多边形，不能解决多边形中,“,岛,”,、,“,洞,”,之类的镶套问题，,“,岛,”,或,“,洞,”,只能作为单个的多边形来构造，没有和周围的多边形建立关系；,很难检查多边形的边界正确与否，即多边形的完整性；,每个多边形自成体系，缺少有关邻域的信息，使拓扑关系，即相邻关系很难跟踪。,适用范围：制图及一般查询，不适合复杂的空间分析,4.1.2,拓扑结构编码法,具有拓扑关系的矢量数据结构就是拓扑数据结构。拓扑数据模型是一种基于矢量的比较有效的数据模型，,ArcGIS,的,Coverage,就是一种拓扑数据结构。,拓扑数据结构包括树状索引编码法、双重独立编码结构、链状双重独立编码结构等。,其,实质是通过地理实体之间的空间关系表示来线和多边形,。,基本概念,弧段：构成多边形的线称为弧段，每个弧段可以有许多中间点。,节点：两条以上弧段相交的点称为节点,岛：由一条弧段组成的多边形称为岛或洞。,简单多边形：多边形图中不含岛的多边形称为简单多边形。,复合多边形：含岛的多边形称为复合多边形，包括为边界和内边界，岛可以看做复合多边形的内边界。,1,树状索引编码法（层次索引法、索引式结构）,采用树状索引以减少数据冗余并间接增加邻域信息，方法是,对所有边界点进行数字化，将坐标对以顺序方式存储，由点索引与边界线号相联系，以线索引与各多边形相联系，形成树状索引结构,树状索引编码法示例,图形数据,树状索引编码法示例,线与多边形之间的树状索引,树状索引编码法示例,点与边界线之间的树状索引,树状索引编码法示例,形成的文件记录,索引式,线与多边形之间的树状索引,点与多边形之间的树状索引,树状索引编码消除了相邻多边形边界的数据冗余和不一致的问题，在简化过于复杂的边界线或合并相邻多边形时可不必改造索引表，邻域信息和岛状信息可以通过对多边形文件的线索引处理得到，,但是,比较繁琐，因而给相邻函数运算，消除无用边，处理岛状信息以及检查拓扑关系带来一定的困难，而且两个编码表都需要以人工方式建立，工作量大且容易出错。,2.,双重独立编码结构,美国人口调查局于,1980,年建立的双重独立地图编码系统。简称,DIME(Dual,Independent Map Encoding),，这种结构最适合于城市地理信息系统。,线文件是双重独立编码结构的基本对象。线文件由线标识码、起始节点、终止节点、左多边形和右多边形组成；节点文件由节点的标识码、节点坐标及与该节点连接的线的标识码等；多边形文件由多边形标识码、组成该多边形的线标识码组成。,C4,N4,C8,C6,P3,C7,N6,C10,N3,C3,N1,P1,C2,N2,C1,P2,C5,N5,P4,P5,C9,N7,线号,起结点,终结点,左多边形,右多边形,C,1,N,1,N,2,P,2,P,1,C,2,N,3,N,2,P,1,P,4,C,3,N,1,N,3,P,1,C,4,N,1,N,4,P,2,C,5,N,2,N,5,P,2,P,4,C,6,N,4,N,5,P,3,P,2,多边形：多边形由一系列的相互连结的线组成，并通过其内部的唯一标识点来标识。标识点的标识码和该多边形属性表中的标识码相一致，由此建立的多边形空间信息和属性信息的关系。,多边形,线,ID,P1,C1,C2,C3,P2,C1,C5,C4,P3,C6,C7,C8,P4,C5,C7,C10,C2,.,C4,N4,C8,C6,P3,C7,N6,C10,N3,C3,N1,P1,C2,N2,C1,P2,C5,N5,P4,P5,C9,N7,面拓扑,节点,坐标,线,N1,X1,y1,C1,C4,C3,N2,X2,y2,C1,C5,C2,N3,X3,y3,C2,C3,C10,N4,X4,y4,C4,C6,C8,.,C4,N4,C8,C6,P3,C7,N6,C10,N3,C3,N1,P1,C2,N2,C1,P2,C5,N5,P4,P5,C9,N7,点拓扑,补充：基于双重独立编码的拓扑检查,从线文件中，找出与当前编辑的多边形相关的所有记录。如对上例中的,P1,进行检查，先在线文件中找出与,p1,有关的所有记录：,线号,起结点,终结点,左多边形,右多边形,C,1,N,1,N,2,P,2,P,1,C,2,N,3,N,2,P,1,P,4,C,3,N,1,N,3,P,1,C4,N4,C8,C6,P3,C7,N6,C10,N3,C3,N1,P1,C2,N2,C1,P2,C5,N5,P4,P5,C9,N7,补充：基于双重独立编码的拓扑检查,2.,如果,P1,在左（右）多边形的位置，将之与处在右（左）多边形处位置的多边形号相交换，同时也将该记录的节点号位置相应的交换；反之，顺序不变。,线号,起结点,终结点,左多边形,右多边形,C,1,N,1,N,2,P,2,P,1,C,2,N,2,N,3,P,4,P,1,C,3,N,3,N,1,P,1,C4,N4,C8,C6,P3,C7,N6,C10,N3,C3,N1,P1,C2,N2,C1,P2,C5,N5,P4,P5,C9,N7,补充：基于双重独立编码的拓扑检查,从经过代码位置转换的记录中，任取一个起始节点作为起点，顺序连接各节点，使得节点能自行封闭，即,N1 N2 N3 N1,。如果不能自动封闭，则说明出现记录缺损或多余，线文件有错误。,线号,起结点,终结点,左多边形,右多边形,C,1,N,1,N,2,P,2,P,1,C,2,N,2,N,3,P,4,P,1,C,3,N,3,N,1,P,1,C4,N4,C8,C6,P3,C7,N6,C10,N3,C3,N1,P1,C2,N2,C1,P2,C5,N5,P4,P5,C9,N7,3.,链式双重独立编码结构,链式双重独立编码是,DIME,数据结构的一种改进。在,DIME,中，一条边只能用直线两端点的序号及相邻多边形表示，而在链状数据结构中，将若干条直线段合为一个弧段（或链段），每个弧段可以有许多中间点。,ARCGIS,中的,Coverage,数据模型就是采用链式双重独立编码结构。,拓扑结构的特点是,:,除结点外，每个空间对象都是由更基本的对象组成的。只有点的坐标是被实际存储的，其他复杂空间对象的坐标信息实际上是逻辑构成的。任一复杂对象能分解为一组结点及其拓扑关系的定义。,这样，一个图层中存储的全部坐标信息就是结点的坐标，建立其他对象只是建立对这些坐标的引用。,虽然建立拓扑结构需要额外的存储数据，但对坐标数据的存储却没有数据冗余的问题。,拓扑结构编码是某些空间分析的基础。,小结,矢量数据结构特点：定位明显，属性隐含,。,其定位是根据坐标直接存储的，无需任何推算；属性则一般存于文件头或数据结构中某些特定的位置上。,这种特点使得矢量数据结构在图形运算的算法总体上比栅格数据结构复杂的多，在叠加运算、邻域搜索等操作时比较困难，有些甚至难以实现，但其也有便利和独到之处，在计算长度、面积、形状和图形编辑、几何变换操作中，矢量结构有很高的效率和精度。,4.2,栅格数据结构,栅格结构是最简单最直接的空间数据结构，是指将地球表面划分为大小均匀紧密相邻的网格阵列，每个网格作为一个象元或象素由行、列定义，并包含一个代码表示该象素的属性类型或量值，或仅仅包括指向其属性记录的指针。,栅格数据编码方法分为两大类：,直接栅格编码（完全栅格数据结构）,压缩编码方法（压缩栅格数据结构）,链码,游程长度编码,块码,四叉树,二维行程编码,4.2.1,直接栅格编码,直接编码就是将栅格数据看作一个数据矩阵，逐行（或逐列）逐个记录代码，可以每行都从左到右逐个象元进行记录，也可以奇数行地从左到右而偶数行地从右向左记录，为了特定目的还可采用其他特殊的顺序,一些常用的栅格排列顺序,4.2.2,压缩编码方式,压缩编码的目的就是用尽可能少的数据量记录尽可能多的信息，其类型分为,信息无损编码,:,编码过程中没有任何信息损失，通过解码操作可以完全恢复原来的信息,信息有损编码,:,为了提高编码效率，最大限度地压缩数据，在压缩过程中损失一部分相对不太重要的信息，解码时这部分难以恢复,在地理信息系统中的压缩编码多采用信息无损编码，而对原始遥感影像进行压缩时也可以采取有损压缩编码方法。,链码（,Chain Codes,）,链式编码又称为弗里曼链码,(Freeman,，,1961,）或边界链码。该编码方法将数据表示为由某一,原点,开始并按,某些基本方向,确定的单位矢量链。,如：基本方向可定义为：东,0,，东南,1,，南,2,，西南,3,，西,4,，西北,5,，北,6,，东北,7,等八个基本方向。,例如，确定原点为像元（,10,，,1,），则某个多边形边界按顺时针方向的链式编码为：,10,，,1,，,7,，,0,，,1,，,0,，,7,，,1,，,7,，,0,，,0,，,2,，,3,，,2,，,2,，,1,，,0,，,7,，,0,，,0,，,0,，,0,，,2,，,4,，,3,，,4,，,4,，,3,，,4,，,4,，,5,，,4,，,5,，,4,，,5,，,4,，,5,，,4,，,6,，,6,。其中前两个数字,10,和,1,表示起点为第十行第一列，从第三个数字开始每个数字表示单位矢量的方向，八个方向以,0,7,的整数代表。,5,5,5,5,4,4,3,3,5,5,5,5,4,4,3,2,5,5,5,5,5,3,2,2,5,5,5,5,5,5,2,2,7,6,6,1,4,4,3,3,7,7,7,1,4,4,3,3,2,2,2,1,1,1,1,1,2,2,5,5,5,5,5,1,练习,链码（,Chain Codes,）优缺点,优点：,链式编码对多边形的表示具有很强的数据压缩能力，且具有一定的运算功能，如面积和周长计算等，探测边界急弯和凹进部分等都比较容易，比较适于存储图形数据。,缺点：,对叠置运算如组合、相交等则很难实施，对局部修改将改变整体结构，效率较低，而且由于链码以每个区域为单位存储边界，相邻区域的公共边界被重复存储会产生冗余。,游程长度编码,（Run-Length Codes）,它的基本思路是：对于一幅栅格图像，常常有行（或列）方向上相邻的若干点具有相同的属性代码，因而可采取某种方法压缩那些重复的记录内容。,所谓的,游程（行程）,是指栅格矩阵内相邻同值栅格的数量。,游程长度编码,（,Run-Length Codes,）,其实现方法有两种,一种编码方案是，只在各行（或列）数据的代码发生变化时依次记录该代码以及相同的代码重复的个数，从而实现数据的压缩。,另一种游程长度编码方案就是逐个记录各行（或列）代码发生变化的位置和相应代码,游程长度编码示例,按第一种编码方法,（,左上角坐标，沿行方向）,，此数据游程长度编码：,（,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,个栅格。,游程长度编码示例,（,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,）。,按第二种编码方法，,记录各行（或列）代码发生变化的位置和相应代码,此数据游程长度编码（左上角坐标，沿列方向）：,游程编码能否压缩数据量，主要取决于栅格数据的性质，通常可以通过事先测试，估计数据冗余度,R,e,：,R,e,=1-Q/mn,式中：,Q,表示相邻属性值变化次数的累加和,m,表示行数,n,表示列数,当,R,e,的值大于,1/5,时，表示栅格数据的压缩可取的明显的效果,其压缩效果可以由压缩比来表征：,S=,m,n,/K,式中：,K,为游程总数,m,表示行数,n,表示列数,压缩比越大，表示压缩效果越好,游程长度编码优缺点,优点,压缩效率较高，且易于进行检索，叠加合并等操作，运算简单，适用于机器存储容量小，数据需大量压缩，而又要避免复杂的编码解码运算增加处理和操作时间的情况,缺点,对于图斑破碎，属性和边界多变的数据压缩效率较低，甚至压缩后的数据量比原始数据还大。,块码（,Chain Codes,）,块码是游程长度编码扩展到二维的情况，采用方形区域作为记录单元，每个记录单元包括相邻的若干栅格，数据结构由初始位置（行、列号）和半径，再加上记录单位的代码组成。,块码编码示例,其块码编码为：,(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),。,四叉树,编码,四叉树编码将整个图像区逐步分解为一系列仅包含单一类型的方形区域，最小的方形区域为一个栅格象元。,四叉树编码,其,基本,分割方法,是将一幅栅格地图或图像,等分,为四部分。逐块检查其,栅格,属性值,(,或灰度,),。如果某个子区的所有栅格值都具有相同的值。则这个子区就不再继续分割，否则还要把这个子区再分割成四个子区。这样依次地分割，直到每个子块都只含有相同的属性值或灰度为止。,四叉树编码示例,四叉树编码要求,采用四叉树编码时，为了保证四叉树分解能不断地进行下去，要求图像必须为2,n,2,n,的栅格阵列,，,对于非标准尺寸的图像需首先通过增加背景的方法将图像扩充为2,n,2,n,的图像。,生成四叉树主要有两种方法，即自上而下（,top-down,）和自下而上（,bottton,-up,）。,由上而下的方法运算量大，耗时较长。因而实践中可以采用从下而上的方法建立四叉树编码。对栅格数据按,Morton,码的顺序进行检测：如果每相邻四个栅格值相同则进行合并，逐次往上递归合并，直到符合四叉树的原则为止。这种方法重复计算较少，运算速度较快。,四叉树的生成,四叉树结构的编码方式,四叉树结构按其编码的方法不同分为常规四叉树和线性四叉树：,常规四叉树,：除了记录叶结点之外，还要记录中间结点。结点之间借助指针联系，每个结点需要用六个量表达：,四个叶结点指针，一个父结点指针和一个结点的属性或灰度值,。这些指针不仅增加了数据贮存量，而且增加了操作的复杂性。常规四叉树主要在,数据索引和图幅索引,等方面应用。,四叉树结构的编码方式,线性四叉树,：,只存贮最后叶结点的信息。包括,叶结点的位置,（莫顿码值）,、深度和本结点的属性或灰度值,。所谓,深度,是指处于四叉树的第几层上。由深度可推知子区的大小。线性四叉树叶结点的编号需要遵循一定的规则，这种编号称为,地址码,，它隐含了叶结点的位置和深度信息。最常用的地址码是,二进制或十进制的,Morton,码,。,美国马里兰大学地理信息系统中采用的编码方式：,该方法记录了叶子结点的地址和值，值就是子区域的代码，而地址码包括两个部分，由,32,位来表示（二进制），最右边,4,位记录该叶子结点的深度，即处于四叉树的第几层上，有了深度即可推知子区域的大小；从右边第,5,位开始,2n,个字节记录叶子结点的路径，用以描述叶子结点的位置，,0,，,1,，,2,，,3,分别表示,SW,SE,NW,NE,；其余各位用,0,补齐。,上图空白处叶子结点,5,，深度为,3,；路径为,3,，,0,，,0,；,用马里兰大学的编码方式可以记为：,0.0,（,22,位）；,110000,（,6,位）；,0011,（四位）,栅格数据编码练习,二维行程编码,在生成线性四叉树之后，仍然存在前后叶节点的值相同的情况，因而可以进一步压缩数据，将前后值相同的叶节点合并，行程新的线性列表。（见,P101,图,4.14,）,栅格数据压缩存储的编码方法,A,A,A,A,A,R,A,A,A,R,A,A,A,R,A,A,R,A,A,A,A,A,A,A,A,A,G,G,A,A,G,G,G,G,G,G,G,A,G,G,G,A,G,G,A,A,A,A,A,A,R,A,A,A,A,R,A,A,A,R,R,A,A,A,1,4,3,2,5,8,7,6,1,2,3,4,5,6,7,8,0,1,2,3,4,5,6,7,起点行列号，单位矢量,R,:(1,5),3,2,2,3,3,2,3,链式编码,游程长度编码,逐行编码,数据结构,:,行号,属性,重复次数,1,A,4,R,1,A,4,块状编码,正方形区域为记录单元,数据结构,:,初始位置,半径,属性,(1,1,3,A),(1,4,1,A),(1,5,1,R),(1,6,2,A),NE,SW,NW,SE,G,G,G,G,A,G,G,A,A,G,A,A,A,四叉树编码,常见栅格压缩编码方法总结：,链码的压缩效率较高，已经近矢量结构，对边界的运算比较方便，但不具有区域的性质，区域空间分析运算困难。,游程长度编码既可以在很大程度上压缩数据，又最大限度地保留了原始栅格结构，编码解码十分容易。,但对破碎数据处理效果不好,。,块码和四叉树编码具有区域性质，又具有可变的分辨率，有较高的压缩效率，,但运算效率是其瓶颈。,其中四叉树编码可以直接进行大量图形图像运算，效率较高，是很有前途的方法。,其他压缩编码方式,还有很多编码方法，如傅立叶变换、小波变换、余弦变换等，常常用于遥感原始数据的压缩。由于它们多数是有损压缩，一般不用于需要进行分析的栅格数据。在四叉树基础上发展而来的八叉树目前也是研究热点之一。,小结,栅格数据结构属性明显，定位隐含：,属性明显,数据中直接记录了数据属性或指向数据属性的指针，因而我们可以直接得到地物的属性代码,定位隐含,所在位置则根据行列号转换为相应的坐标，也就是说定位是根据数据在数据集中的位置得到的。栅格结构是按一定的规则排列的，所表示的实体的位置很容易隐含在格网文件的存储结构中,栅格模型,矢量模型,优点：,（,1,）数据结构简单；,（,2,）空间数据的叠置和组合十分容易方便；,（,3,）各类空间分析都很易于进行；,（,4,）数学模拟方便；,（,5,）技术开发费用低。,优点：,（,1,）表示地理数据的精度较高；,（,2,）严密的数据结构，数据量小；,（,3,）用网络连接法能完整地描述拓扑关系；,（,4,）图形输出精确美观；,（,5,）图形数据和属性数据的恢复、更新、综合都能实现。,缺点：,（,1,）图形数据量大；,（,2,）用大像元减少数据量时，可识别的现象结构将损失大量信息；,（,3,）地图输出不精美；,（,4,）难以建立网络连接关系；,（,5,）投影变换花的时间多。,缺点：,（,1,）数据结构复杂；,（,2,）矢量多边形地图或多边形网很难用叠置方法与栅格图进行组合；,（,3,）显示和绘图费用高，特别是高质量绘图、彩色绘图和晕线图等；,（,4,）数学模拟比较困难；,（,5,）技术复杂，多边形内的空间分析不容易实现。,4.3,矢量数据结构与栅格数据结构比较,矢量数据模型与栅格数据模型比较,从应用领域来看,栅格结构和矢量结构都有一定的局限性。一般来说，大范围小比例尺的自然资源、环境、农业、林业、地质等区域问题的研究，城市总体规划阶段的战略性布局研究等使用栅格模型比较合适；城市分区或详细规划、土地管理、公共事业管理等方面应用矢量模型比较合适。,从数据来源来看,对于一个与遥感相结合的地理信息系统来说，栅格结构是必不可少的，因为遥感影像是以像元为单位的，可以直接将原始数据或经处理的影像数据纳入栅格结构的地理信息系统；而对地图数字化、拓扑检测、矢量绘图等，矢量数据结构又是必不可少的。,矢量数据结构与栅格数据结构的选择,在,GIS,建立过程中，应根据应用的目的和应用的特点、可能获取的数据精度以及地理信息系统软件和硬件的配置情况选择合适的数据结构。,矢量与栅格一体化（了解）,为了发挥矢量和栅格数据结构各自的特点，在两种数据的基础上发展了矢量,栅格一体化数据结构（,unified data structure),这种空间数据结构的思想是,通过同时记录多边形边界和边界中间包含的栅格地址,，实现既保持矢量数据的特征又具有栅格数据的性质。,基本思想,：为了提高点、线和边界的表示精度，一般将点所在格网或线、边界通过的格网细分，根据精度要求可分为按照,256256,或,1616,将基本格网细分。基本格网和细分格网都采用线性四叉数编码，采样点和线目标与基本格网的交点用两个十进制,Morton,码表示。,一、矢量与栅格一体化的概念,为了建立矢量与栅格一体化数据结构，要对点、线、面目标数据结构的存储要求作如下的统一约定,:,对点状目标,，因为没有形状和面积，在计算机内部只需要表示该点的一个位置数据及与结点关联的弧段信息。,对线状目标,，它有形状，但没有面积，在计算机内部需用一组元子来填满整个路径，并表示该弧段相关的拓扑信息。,对面状目标,，它既有形状，又有面积，在计算机内部需表示由元子填满路径的组边界和由边界组成的紧凑空间。,4.4,不规则镶嵌数据结构,4.4.1,Voronio,数据结构（见教材,106,页）,4.1.2 TIN,数据结构,TIN,模型的数据存储方式比栅格数据复杂，它不仅要存储每个点的高程，还要存储其平面坐标、节点连接的拓扑关系，三角形及邻接三角形等关系。,TIN,模型在概念上类似于多边形网络的矢量拓扑结构，对于每个三角形、边和节点都对应一个记录，如下：,三角形记录包括三个指向它三个边的记录的指针；,三角形,顶点,邻接三角形,a,b,c,c,d,a,b,e,c,c,e,d,e,b,g,b,h,g,边有四个指针字段，包括两个指向相邻三角形的指针和它的两个顶点的记录的指针；,边,顶点,相邻三角形,1,a,b,2,a,c,3,b,c,每个节点包括三个坐标值的字段，分别存储,X,Y,Z,坐标。,顶点,x,y,z,a,b,c,d,e,栅格数据模型和,TIN,数据模型的比较,对地理空间的划分,：,TIN,模型为不规则三角形；而栅格模型为规则格网；,空间对象的表示,：栅格数据模型既可以描述连续变化的地理现象，又可以表示离散的地理现象（点、线、面），而,TIN,模型只能表示联系变化的地理现象；但,TIN,能精确地表示曲面类型地理现象的形状以及特殊的地形要素，比如山脊、山峰等，而栅格模型不能精确表示；,表面模型的精度,：栅格使用统一的,CELL,大小来表示，在地形平坦的地方，存在大量的数据冗余，而,TIN,具有随坡度变化而不同的点密度，在坡度变化大的地区点密度较高；,栅格模型适合进行空间一致性分析、近邻分析、离散度分析及表面最低成本分析，,TIN,模型适合进行坡度、坡向、体积计算和视线分析等,4.5,三维空间数据模型,4.5.1,三维空间的目标分类,4.5.2,八叉树数据结构,4.5.3,四面体格网,在三维空间中，可将空间地物按维数分成零维（点），一维（线）、二维（面）和三维（体）四大类。,零维空间,：有点状地物和用来表示与弧段的关联关系的结点两类目标。,一维空间,：有,“,拓朴弧段,”,、,“,无拓朴弧段,”,和线状地物。其中,“,拓朴弧段,”,可以是构成多边形的边界线也可是构成各类网线（如水系网、交通网、城市地下管网）的网线段。,二维空间,：主要有三类目标，一个是构成面状地物的拓朴面片；第二个是像素，用它可组成面状要素；第三个是根据有限的离散数据建立数字表面模型。,三维空间,，有由若干个面片或由数字立体模型表示体状地物；以及根据有限的三维空间离散数据建成的数字立体模型。,4.5.1,八叉树数据结构,八叉树数据结构是三维栅格数据的压缩形式，是二维栅格数据中的四叉树在三维空间的推广，该数据结构是将所要表示的三维空间,V,按,X,、,Y,、,Z,三个方向从中间进行分割,，把,V,分割成八个立方体，然后根据每个立方体中所含的目标来决定是否对各立方体继续进行八等分的划分，一直划分到每个立方体被一个目标所充满，或没有目标，或其大小已成为预先定义的不可再分的体素为止。,三维空间体,V,及划分编码,三维空间,体,V,中的物体,八叉树,数据结构举例,八叉树编码,八叉树结构就是将空间区域不断地分解为八个同样大小的子区域,(,即将一个六面的立方体再分解为八个相同大小的小立方体,),，同,区域的属性相同。八叉树主要用来解决地理信息系统中的三维问题。,八叉树的主要,优点,在于可以非常方便地实现有广泛用途的,集合运算,（例如，可以求两个物体的并、交、差等运算）而这些恰是其它表示方法比较难以处理或者需要耗费许多计算资源的地方。此外，由于这种方法的有序性及分层性，因而对显示精度和速度的平衡，隐线和隐面的消除等，带来了很大的方便，特别有用。,4.5.2,四面体格,网,四面体格网（,Tetrahedral Network,TEN,）是将目标空间用紧密排列但不重叠的不规则四面体形成的格网来表示，其实质是,2D TIN,结构在,3D,空间上的扩展。在概念上首先将,2D,Voronoi,格网扩展到,3D,，形成,3D,Voronoi,多面体，然后将,TIN,结构扩展到,3D,形成四面体格网（,见图示,）。,四面体格网表示三维空间物体的例子,四面体格网表示三维空间物体的例子的数据结构,四面体格网由点、线、面和体四类基本元素组合而成。整个格网的几何变换可以变为每个四面体变换后的组合，这一特性便于许多复杂的空间数据分析。同时，四面体格网既具有体结构的优点，如快速几何变换、快速显示，又可以看成是一种特殊的边界表示，具有一些边界表示的优点，如 关系的快速处理。,矢量数据结构和栅格数据结构的相互转换是地理信息系统的基本功能之一，目前已经发展了许多高效的转换算法。但是从栅格到矢量数据的转换，特别是扫描图像的自动识别，仍然是研究的重点。,4.6,矢量数据结构与栅格数据结构的转换,（教材,P164,）,对于点实体，每个实体都仅由一个坐标对表示，其结构的转换不存在太大的技术问题。在这重点讲解一下线实体和多边形实体向栅格格式转换的过程。如下：,4.6.1,矢量格式向栅格格式的转换,线实体向栅格格式的转换,由于,GIS,中线实体是由顺次连接一组坐标点形成的折线段表达的，所以，线的栅格化可以分解为对做成线实体的折线段的栅格化。,对于线段的栅格化，先使用点栅格化的方法，栅格化线段的两个端点，然后再栅格化线段的中间部分。而对于线段中间的部分的栅格化，需要分两种情况来处理,:,设线段两端点的坐标分别为,(x1,y1),和,(x2,y2),栅格化后所队形的行列号分别为（,I1,J1)(I2,J2).,则行差为,I=,I1-I2,，列差为,J=,J1-J2,。分两种情况处理：一是列差大于行差,J,I,的情况，二是行差大于列差,I,J,的情况，运用扫描线算法实现。,当,J,I,时，平行于,y,轴做每一列栅格的中心线，称为扫描线。求每一条扫描线与线段的交点，按点栅格化的方法将交点转换为栅格坐标。,当,I,J,时，同理。,J I,I J,多边形矢量格式向栅格格式的转换,内部点扩散算法,射线算法和扫描算法,边界代数算法,1,内部点扩散法,每个面域多边形中选择一个,内部点（扩散种子）；,从种子点开始向,8,个邻域栅格扩散，分别判断,8,个栅格是否在多边形的边界上，有两种结果，一是在边界上，则这个栅格不再作为种子；二是不再边界上，这个栅格将作为新的种子,新的种子与原有种子一起继续参与扩撒运算,重复（,2,）（,3,），直到所有种子点填满该多边形为止。,扩散算法程序设计比较复杂，需要在栅格阵列中进行搜索，占用内存很大。,2,射线算法,射线算法可逐点判别数据栅格点在某多边形之外或在多边形内，由待判点向图外某点引射线，判断该射线与某多边形所有边界相交的总次数，如相交偶数次，则待判点在该多边形的外部，如为奇数次，则待判点在该多边形内部。,射线算法要计算与多边形交点，因此运算量大。另一个比较麻烦的问题是射线与多边形相交时有些特殊情况如相切、重合等，会影响交点的个数，必须予以排除，由此造成算法的不完善，并增加了编程的复杂性。,3,扫描算法,扫描算法是射线算法的改进，通常情况下，沿栅格阵列的行方向扫描，在每两次遇到多边形边界点的两个位置之间的栅格，属于该多边形。扫描算法省去了计算射线与多边形交点的大量运算，大大提高了效率，但一般需要预留一个较大的数组以存放边界点，而且扫描线与多边形边界相交的几种特殊情况仍然存在，需要加以判别。,4,边界代数算法,边界代数多边形填充算法（,Boundary Algebra Filling,，简称,BAF,），是任伏虎等设计并在微机地理信息系统上实现的一种基于积分思想的矢量格式向栅格格式转换算法。适合记录拓扑关系的多边形矢量数据转换为栅格数据。,事实上，每幅地图都是由多个多边形区域组成的。如果把不属于任何多边形的区域（包括无穷远点）看成一个编号为零的特殊区域，则每一条边界弧段都与两个不同编号的多边形相邻，,按边界弧段的前进方向分别称为左、右多边形,。对图,3,24,所示的,3,个多边形的,6,条边，有如表,3,5,所示的多边形编号。,表,3-5,线号与左右多边形号的对应关系,线号,左多边形,右多边形,0,n,1,n,2,0,n,3,n,2,n,1,n,2,n,3,0,n,3,n,1,n2,n1,n3,边界代数算法的基本思想：对每幅地图的全部具有左右多边形编号的边界弧段，沿其前进的方向逐个搜索，,当边界上行时，将边界线位置与左图框之间的网格点加上一个值,=,（左多边形编号）,-,（右多边形编号）；,当边界线下行时，将边界线位置与左图框的栅格点加上一个值,=,（右多边形编号）,-,（左多边形编号），,而不管边界线的排列顺序。,射线算法,单个多边形的转换,多个多边形的转换,线号,左多边形,右多边形,0,n,1,n,2,0,n,3,n,2,n,1,n,2,n,3,0,n,3,n,1,n2,n1,n3,n2,n1,n3,边界代数法与其它算法的不同之处在于它不是逐点搜寻判别边界，而是根据边界的拓扑信息，通过简单的加减代数运算将拓扑信息动态地赋予各栅格点，实现了矢量格式到栅格格式的转换。由于不需考虑边界与搜索轨迹之间的关系，因此算法简单，可靠性好，而且由于仅采用加减代数运算，每条边界仅计算一次，免去了公共边界重复运算，又可不考虑边界存放的顺序，因此运算速度快，同时较少受内存容量的限制，特别适用于微机地理信息系统。,栅格数据向矢量数据转换的,目的,有三：数据入库；数据压缩；矢量制图；,4.6.2,栅格格式向矢量格式的转换,1,）多边形边界提取：,（二值化，平滑，细化）,2,）边界线追踪,3,）拓扑关系生成,4,）去除多余点及曲线圆滑,栅格格式向矢量格式的转换的一般需要以下几个步骤,所谓的二值化，是在一个设定的灰度阙值的基础上，对扫描获得的灰度图像（如,256,级灰度）进行,0,或,1,的简化处理，即有无判断。算法如下：,1,）图像二值化,1,多边形边界提取,由于线不光滑以及扫描、摄像系统的分辨率限制，使得一些曲线目标带来多余的小分支（即毛刺噪声）；此外，还有空洞和凹陷噪声（如下图），就会造成细化误差和失真，这样最影响最终栅格的跟踪和矢量化。曲线目标越宽，提取骨架和去除轮廓所需的次数也就越多，因此误差的影响也越大。,2,）图像细化预处理二值图像平滑,去除毛刺和空洞,为了去除毛刺和空洞的影响，可以采用下面两个模板进行处理。处理过程如下：,按点阵格式扫描图像上的每一个像素，只要图像相应区域与模板（包括模板的,90,旋转）吻合，则判定为毛刺（或空洞），对应模板中心数值变给,0,（空洞模板将模板中心位置值改为,1,）,0,0,0,0,1,0,X,X,X,X,1,X,1,0,1,X,X,X,去除毛刺模板，,X,为任意值,去除空洞模板，,X,为任意值,3,）图像细化,线细化是处理包含线状地物二值图像的一种重要技术，在地图扫描处理中，由于地图上主要信息是不同粗细和不同形状的线，必须首先进行线细化，以准确有效地提取这些线信息，并进一步矢量化。,线细化就是不断去除曲线上不影响连通性的轮廓像素的过程，对细化的一般要求是：,保证细化后曲线的连通性；,细化结果是原曲线的中心线；,保留细线端点,下面介绍几种典型的细化方法,：,经典的细化算法,对于二值栅格图像中每个像素点,P,以及其直接相邻的,8,个像素点，令：,N(p,),为,p,的邻点的数值的和；,图像像素联结数,T(p,),；,P,w,P,E,P,S,P,N,分别指像素左侧、右侧、下边、上边邻点的数值,T(p,)=0,T(p,)=0,T(p,)=1,T(p,)=1,T(p,)=2,T(p,)=2,T(p,)=2,T(p,)=3,T(p,)=4,