2.第二章空间数据结构(6学时)(四叉树编码)

地理信息系统原理（★第2章空间数据结构）2.1空间数据模型的类型在GIS中与空间信息有关的空间数据模型主要有两个基于场(field-based)的空间模型把地理空间的事物和现象作为连续的变量或体来看待，表示了在二维或者三维空间中，空间实体的属性信息被看作是连续变化的数据。AcollectionofspatialdistributionsContinuousdata.Examplesaltitude,rainfall,temperature,cropyield.有毒气体扩散分析基于对象(object-based)的模型强调了离散对象,将研究的整个地理空间看成一个空间域，地理实体和现象作为独立的对象分布在该空间域中，根据它们的边界线以及它们的组成或者与它们相关的其它对象，可以详细地描述离散对象。任何现象，无论大小，都可以被确定为一个对象(Object)，且假设它可以从概念上与其邻域现象相分离。在欧氏（Euclidean）空间中主要有点对象、线对象、多边形对象和体。composedofidentifiableentitiesDiscretedata.Examplesroads,rivers,landparcels,islandboreholes地理信息系统两种数据类型是通过两种空间数据结构来实现：栅格（raster）and矢量（vector）。栅格数据模型是典型的基于域的模型。矢量数据模型是典型的基于对象的模型。cells(grid)pixels(image)Field-baseddataObject-baseddataRastermodelVectormodellllll1122112311333332pointslinespolygons2.2栅格数据结构将工作区域的平面表象按一定分解力作行和列的规则划分，形成许多格网，每个网格单元称为象素(pixel)。根据所表示实体的表象信息差异，各象元可用不同的“灰度值”来表示。若每个象元规定N比特，则其灰度值范围可在0到2N—1之间；把白～灰色～黑的连续变化量化成8比特（bit），其灰度值范围就允许在0～255之间；若每个象元只规定1比特，则灰度值仅为0和1，这就是所谓二值图像。点实体在栅格数据中表示为一个像元；线实体则表示为在一定方向上连接成串的相邻像元集合；面实体由聚集在一起的相邻像元集合表示。arealinepointployon栅格数据结构实际上就是象元阵列，即象元按矩阵形式的集合(二维数组），每个象元是栅格数据中最基本的信息存储单元，其坐标位置可以用行号和列号确定。右图在计算机内是一个4*4阶的矩阵。但在外部设备上，通常是以左上角开始逐行逐列存贮。存贮顺序为：AAAAABBBAABBAAAB，当每个像元都有唯一一个属性值时，一层内的编码就需要m行×n列×3(x,y和属性编码值)个存储单元。Row#(Y-coord)regionscellsAAAAABBBAABBAAABColumn#(X-coord)PunctualLinealArealSurficial0-d1-d2-d3-d+12014012331122112311333332RealworldVeryFinegridMediumgridCoarsegrid分辨率（resolution）Resolutionisdependentonthegridcellsize.Changingtheresolutionaffectsclassification,area,perimeter,accuracy,etc...中心归属法：每个栅格单元的值以网格中心点对应的面域属性值确定。面积占优法：以在该网格单元中占据最大面积的属性值确定。长度占优法：以网格中线的大部分长度所对应的面域的属性值来确定。重要性法：根据栅格内不同地物的重要性程度，选取特别重要的空间实体决定对应的栅格单元值.2.2.1栅格数据取值方法栅格数据的值11221123113333321.71.82.02.01.71.82.02.21.81.82.32.22.22.22.22.0aabbaabcaacccccb整数值：如土壤分类字母：蔬菜类型、土地分区实数：如高程值2.2.2栅格数据组织方法栅格数据以层的方式来组织文件，在栅格数据结构中，物体的空间位置就用其在笛卡尔平面网格中的行号和列号坐标表示，物体的属性用象元的取值表示，每个象元在一个网格中只能取值一次，同一象元要表示多重属性的事物就要用多个笛卡尔平面网格，称为层。以像元为序。不同层上同一像元位置上的各属性值表示为一个列数组。以层为基础。每一层又以像元为序记录它的坐标和属性值。以层为基础。但每一层内以多边形为序记录多边形的属性值和充满多边形的各像元的坐标。栅格数据文件像元1X坐标Y坐标层2属性值层1属性值…层n属性值…像元2像元n栅格数据文件层1像元1层2…X,Y,属性值像元2X,Y,属性值……像元nX,Y,属性值层n栅格数据文件层1多边形1层2…属性值像元1坐标…多边形N像元n坐标层n2.2.3栅格数据存储编码直接编码链式编码行程编码块式编码四叉树编码1.直接编码直接编码是最简单最直观而又非常重要的一种栅格结构编码方法，通常称这种编码为图像文件或栅格文件。直接编码就是将栅格数据看作一个数据矩阵，逐行（或逐列）逐个记录代码.33344444333344441333444211333222111132221111222211111222111112221333444442333344443133344424113332225111132226111122227111112228111112222.链式编码(ChainCodes)1(N)0(E)3(S)2(W)02102103303322324303051012012023303222323221243232212212221213又称弗里曼链码（Freeman1961），多边形边界可以表示为由某一原点开始并按某些基本方向确定的单位矢量链。基本方向：东=0，南=3，西=2，北=1+只在各行（或列）数据的代码发生变化时依次记录该代码以及重复出现次数。即按（属性值,重复次数）编码。3.行程编码(Run-lengthencoding)逐个记录各行（或列）代码发生变化的位置和相应的代码，即按（位置，属性值）编码。如图按列：4.块式编码(Blockencoding)1x1:(0,2,1,1)(0,3,1,1)(0,4,1,1)(2,1,1,1)(3,1,1,1)(4,0,1,1)(4,1,1,1)(5,0,1,1)(5,5,1,1)(6,0,1,1)(6,8,1,1)(8,3,1,1)(11,8,1,1)(12,8,1,1)(14,3,1,1)(14,4,1,1)2x2:(3,7,2,2)(4,9,2,2)(5,7,2,2)(7,7,2,2)(8,2,2,2)(9,7,2,2)(12,4,2,2)(13,2,2,2)(14,6,2,2)3x3:(5,3,3,3)(11,7,3,3)4x4:(1,5,4,4)把多边形范围划分成由象元组成的正方形，然后对各个正方形进行编码。块式编码数据结构中包括3个数字：块的初始位置（行、列号）和块的大小（块包括的象元数），再加上记录单元的代码组成。5.四叉树编码(Quadtrees)NWNESESWNWSWSENE(1)四叉树分割：将图像区域按大小相同的象限4等分，每个象限又可根据一定规则判断是否继续等分为次一层的4个象限。子象限只含一种属性代码，则停止继续分割。图像区域的栅格阵列应为2n×2n(2)四叉树结构：把2n×2n象元组成的阵列当作树根，树的高度为n，每个节点分别代表南西（SW）、南东（SE）、北西（NW）、北东（NE）。四个分支中要么是树叶、树叉。树叶代表一种代码。树叉继续再分。对一幅2n×2n的栅格阵列，最大深度为n，层次可能为0,1,…,n(3)线性四叉树编码:(马里兰大学的GIS系统)记录每个叶结点的地址和值，值就是子区的属性代码，其中地址包括两部分，共32位（二进制）最右边4位记录该叶结点的深度，左边的28位记录路径，从右边第5位往左记录从叶节点到根结点的路径。0，1，2，3分别表示SW，SE，NW，NE。第10号结点编码为：0000……00001101|0011通过记录叶结点的深度码和层次码来描述叶结点的位置(4)十进制Morton码的编码行号5=0101列号7=0111Morton码=00110111=55这样就可将用行列表示的二维图像，用Morton码写成一维数据，通过Morton码就可知象元位置。把一幅2n×2n的图像压缩成线性四叉树的过程为：按Morton码把图象读入一维数组。相邻的四个象元比较，一致的合并，只记录第一个象元的Morton码。比较所形成的大块，相同的再合并，直到不能合并为止。对用上述线性四叉树的编码方法所形成的数据还可进一步用游程长度编码压缩。压缩时只记录第一个象元的Morton码。例：ABBBBBBBAAAAAAAA0213891011121314154567四叉树Morton码编码结果解码时，据Morton码，可知象元在图像中位置。从左上角，本Morton码和下一个Morton码之差即为象元个数。知道了象元的个数和象元的位置就可恢复出图像了。课堂练习：1、栅格数据如何进行取值？2、栅格数据存储压缩编码方法主要有哪几种？每种方法是如何编码的？3、写出4*4图像对应的Morton码2.1矢量数据结构2.1.1矢量数据概念2.1.2矢量数据编码内容2.1.3地理关系的类型2.1.3拓扑关系理论2.1.4拓扑数据结构2.1.1基本概念矢量数据就是代表地图图形的各离散点平面坐标（x，y）的有序集合。Point-simpleprimitiveLine-chainofpointsArea-closedchainofpointsPoints,linesandpolygonsPointscanrepresent:avertexanodealabelapointfeaturePolygonscanrepresent:anareafeatureaclosedringoflinesLinescanrepresent:aboundaryofapolygonanetworklinkingpointfeaturesalinearfeature2.1.2矢量数据结构存储方式标识码属性码空间对象编码唯一连接空间和属性数据数据库独立编码点:(x,y)线:(x1,y1),(x2,y2),…,(xn,yn)面:(x1,y1),(x2,y2),…,(x1,y1)点位字典点:点号文件线:点号串面:点号串点号XY1112223344………n5566存储方法1.点实体方向字体排列指针与线相交的角度如果是简单点符号符号字符大小简单点文字说明结点唯一识别符比例尺方向x，y坐标其它有关的属性点实体类型序列号有关的属性如果是文字说明如果是结点2.线实体唯一标识码线标识码起始点终止点坐标对序列显示信息非几何属性线实体3.面实体多边形矢量编码，不但要表示位置和属性，更重要的是能表达区域的拓扑特征，如形状、邻域和层次结构等，以便使这些基本的空间单元可以作为专题图的资料进行显示和操作。2.1.3空间关系的理论空间关系可以是由空间实体的几何特性(包括空间物体的地理位置与形状)引起的空间关系，如距离、方位、连通性、相似性等；也可以是由空间实体的几何特性和非几何特性(包括度量属性如高程值、坡度值、气温值等，名称属性如地名、物体名称等)共同引起的空间关系，如空间分布现象的统计相关、空间自相关、空间相互作用、空间依赖等；还有一种是完全由空间实体的非几何属性所导出的空间关系，如由两个城市的人口数的比较所产生的大小关系、时间上的先后关系、等级上的高低关系以及成因上的因果关系等都属于此类关系。Spatial-spatialrelationship邻接相交重合相离包含点—