《2.第二章空间数据结构(6学时)(四叉树编码)解析》由会员分享，可在线阅读，更多相关《2.第二章空间数据结构(6学时)(四叉树编码)解析（60页珍藏版）》请在金锄头文库上搜索。
1、地理信息系统原理（第第2 2章章 空间数据结构）空间数据结构）2.12.1空间数据模型的类型空间数据模型的类型在在在在GISGISGISGIS中与空间信息有关的空间数据模型主要有两个中与空间信息有关的空间数据模型主要有两个中与空间信息有关的空间数据模型主要有两个中与空间信息有关的空间数据模型主要有两个 基基基基于于于于场场场场( ( ( (field-based)field-based)field-based)field-based)的的的的空空空空间间间间模模模模型型型型把把把把地地地地理理理理空空空空间间间间的的的的事事事事物物物物和和和和现现现现象象象象作作作作为为为为连连连连续续续续的
2、的的的变变变变量量量量或或或或体体体体来来来来看看看看待待待待，表表表表示示示示了了了了在在在在二二二二维维维维或或或或者者者者三三三三维维维维空空空空间间间间中中中中，空空空空间间间间实实实实体体体体的的的的属属属属性性性性信信信信息息息息被被被被看看看看作作作作是是是是连连连连续变化的数据。续变化的数据。续变化的数据。续变化的数据。n nA collection of spatial distributionsA collection of spatial distributionsn nContinuous data. Continuous data. n nExamplesExampl
3、esn naltitude, altitude, n nrainfall,rainfall,n ntemperature, temperature, n ncrop yield.crop yield. 有毒气体扩散分析有毒气体扩散分析 基于对象基于对象基于对象基于对象( ( ( (object-based)object-based)object-based)object-based)的模型的模型的模型的模型强调了离散对强调了离散对强调了离散对强调了离散对象象象象, , , ,将研究的整个地理空间看成一个空间域，地理实将研究的整个地理空间看成一个空间域，地理实将研究的整个地理空间看成一个空间域，
4、地理实将研究的整个地理空间看成一个空间域，地理实体和现象作为独立的对象分布在该空间域中，体和现象作为独立的对象分布在该空间域中，体和现象作为独立的对象分布在该空间域中，体和现象作为独立的对象分布在该空间域中，根据根据根据根据它们的边界线以及它们的组成或者与它们相关的其它们的边界线以及它们的组成或者与它们相关的其它们的边界线以及它们的组成或者与它们相关的其它们的边界线以及它们的组成或者与它们相关的其它对象，可以详细地描述离散对象。它对象，可以详细地描述离散对象。它对象，可以详细地描述离散对象。它对象，可以详细地描述离散对象。 任何现象，无论大小，都可以被确定为一个对任何现象，无论大小，都可以被确
5、定为一个对任何现象，无论大小，都可以被确定为一个对任何现象，无论大小，都可以被确定为一个对象象象象( ( ( (Object)Object)Object)Object)，且假设它可以从概念上与其邻域现象且假设它可以从概念上与其邻域现象且假设它可以从概念上与其邻域现象且假设它可以从概念上与其邻域现象相分离。在欧氏（相分离。在欧氏（相分离。在欧氏（相分离。在欧氏（EuclideanEuclideanEuclideanEuclidean）空间中主要空间中主要空间中主要空间中主要有点对象、有点对象、有点对象、有点对象、线对象、多边形对象和体线对象、多边形对象和体线对象、多边形对象和体线对象、多边形对象
6、和体。n ncomposed of identifiable entities composed of identifiable entities n nDiscrete data. Discrete data. n nExamplesExamplesn nroads,rivers,roads,rivers,n nland parcels,islandland parcels,islandn nboreholesboreholes地理信息系统两种数据类型是通过两种空间数据地理信息系统两种数据类型是通过两种空间数据结构来实现：结构来实现：栅格栅格（rasterraster）andand矢量矢量（
7、vectorvector）。）。栅格数据模型是典型的基于域的模型。矢量数据模型是典型的基于对象的模型。cells(grid)pixels(image)Field-baseddataObject-baseddataRastermodelVectormodelpointslinespolygons2.2栅格数据结构n将工作区域的平面表象按一定分解力作行和列的规则划分，形成许多格网，每个网格单元称为象素(pixel)。根据所表示实体的表象信息差异，各象元象元可用不同的“灰度值灰度值”来表示。n若每个象元规定N比特，则其灰度值范围可在0到2N1之间；把白灰色黑的连续变化量化成8比特（bit），其灰度值
8、范围就允许在0255之间；若每个象元只规定1比特，则灰度值仅为0和1，这就是所谓二值图像。n点实体在栅格数据中表示为一个像元；线实体则表示为在一定方向上连接成串的相邻像元集合；面实体由聚集在一起的相邻像元集合表示。arealinepointployon栅格数据结构实际上就是象象元元阵阵列列，即象元按矩阵形式的集合(二维数组），每个象元是栅格数据中最基本的信息存储单元，其坐标位置可以用行号和列号确定。右图在计算机内是一个4*4阶的矩阵。但在外部设备上，通常是以左上角开始逐行逐列存贮。存贮顺序为： A A A A A B B B A A B B A A A B ，当每个像元都有唯一一个属性值时，一
9、层内的编码就需要m行n列3(x,y和属性编码值)个存储单元。Row#(Y-coord)regionscellsAAAAABBBAABBAAABColumn#(X-coord)PunctualLinealArealSurficial0-d1-d2-d3-d+12014012331122112311333332 Real world Very Fine grid Medium grid Coarse grid Real world Very Fine grid Medium grid Coarse grid分辨分辨分辨分辨率（率（率（率（resolutionresolution）n nResolu
10、tionisdependentontheResolutionisdependentonthegridcellsizegridcellsize. .n nChangingtheresolutionaffectsChangingtheresolutionaffectsclassificationclassification, ,areaarea, ,perimeterperimeter, ,accuracyaccuracy,etc.,etc. 中心归属法中心归属法：每个栅格单元的值以：每个栅格单元的值以网格中心点对应的面域属性值确定。网格中心点对应的面域属性值确定。面积占优法面积占优法：以在该网格
11、单元中占据以在该网格单元中占据最大面积的属性值确定。最大面积的属性值确定。长度占优法长度占优法：以网格中线的大部分以网格中线的大部分长度所对应的面域的属性值来确长度所对应的面域的属性值来确定。定。重要性法重要性法：根据栅格内不同地物的重要性根据栅格内不同地物的重要性程度，选取特别重要的空间实体决定对应程度，选取特别重要的空间实体决定对应的栅格单元值的栅格单元值. .2.2.12.2.1栅格数据取值方法栅格数据取值方法栅格数据的值n n整数值：如土壤分类整数值：如土壤分类n n字母字母：蔬菜类型、土地分区：蔬菜类型、土地分区 n n实数：如高程值实数：如高程值2.2.22.2.2栅格数据组织方法
12、栅格数据组织方法栅格数据以栅格数据以层层的方式来组织文件，的方式来组织文件，在栅格数据结构中，在栅格数据结构中，物体的物体的空间位置空间位置就用就用其在笛卡尔平面网格其在笛卡尔平面网格中的中的行号和列号坐标行号和列号坐标表示，物体的表示，物体的属性属性用用象元的取值象元的取值表示，每表示，每个象元在一个网格中个象元在一个网格中只能取值一次，同一只能取值一次，同一象元要表示多重属性象元要表示多重属性的事物就要用的事物就要用多个笛多个笛卡尔平面网格卡尔平面网格，称为，称为层。层。n n以像元为序。不同层上同一像元位置上的各属性值表示为一以像元为序。不同层上同一像元位置上的各属性值表示为一以像元为序
13、。不同层上同一像元位置上的各属性值表示为一以像元为序。不同层上同一像元位置上的各属性值表示为一个列数组。个列数组。个列数组。个列数组。n n以层为基础。每一层又以层为基础。每一层又以层为基础。每一层又以层为基础。每一层又以像元为序以像元为序以像元为序以像元为序记录它的坐标和属性值。记录它的坐标和属性值。记录它的坐标和属性值。记录它的坐标和属性值。n n以层为基础。但每一层内以层为基础。但每一层内以层为基础。但每一层内以层为基础。但每一层内以多边形以多边形以多边形以多边形为为序序序序记录记录多多多多边边形的属性形的属性形的属性形的属性值值和充和充和充和充满满多多多多边边形的各像元的坐形的各像元的
14、坐形的各像元的坐形的各像元的坐标标。栅格数据文件像元1X坐标Y坐标层2属性值层1属性值层n属性值像元2像元n栅格数据文件层1像元1层2X,Y,属性值像元2X,Y,属性值像元nX,Y,属性值层n栅格数据文件层1多边形1层2属性值像元1坐标多边形N像元n坐标层n2.2.32.2.3栅格数据存储编码栅格数据存储编码n n直接编码直接编码n n链式编码链式编码n n行程编码行程编码n n块式编码块式编码n n四叉树编码四叉树编码1.直接编码直接编码直接编码是最简单最直观而又非常重要的一种栅格直接编码是最简单最直观而又非常重要的一种栅格结构编码方法，通常称这种编码为图像文件或栅格结构编码方法，通常称这种
15、编码为图像文件或栅格文件。直接编码就是将栅格数据看作一个数据矩阵，文件。直接编码就是将栅格数据看作一个数据矩阵，逐行（或逐列）逐个记录代码逐行（或逐列）逐个记录代码. .333444443334444433334444333344441333444213334442113332221133322211113222111132221111222211112222111112221111122211111222111112221333444442333344443133344424113332225111132226111122227111112228111112222.链式编码链式编码(Chai
16、nCodes)1 (N)0 (E)3 (S)2 (W)0 02 2 1 1 0 02 2 1 1 0 03 3 3 3 0 03 3 3 32 2 2 2 3 3 2 24 4 3 3 0 0 3 3 0 05 5 1 1 0 0 1 12 2 0 0 1 1220 022 3 33 3 0303222 2223 32 23 32 2221212443 32 23 3 2 2221 12 2 22 1 1222 2221211213 3又称弗里曼链码（Freeman1961），多边形边界可以表示为由某一原点开始并按某些基本方向确定的单位矢量链。基本方向：东=0，南=3，西=2，北=1+只在各行
17、（或列）数据的代码发生变化时依次记录只在各行（或列）数据的代码发生变化时依次记录该代码以及重复出现次数。即按（该代码以及重复出现次数。即按（属性值属性值,重复次数重复次数）编码。编码。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,
18、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个个数
19、数字字：块块的的初初始始位位置置（行行、列列号号）和和块块的的大大小小（块块包包括括的的象象元元数数），再再加加上上记记录录单元的代码组成。单元的代码组成。5.四叉树编码四叉树编码(Quadtrees)NWNESESWNWSWSENE(1)(1)四叉树分割：四叉树分割：四叉树分割：四叉树分割：将图像区域按大小相同的象限4等分，每个象限又可根据一定规则判断是否继续等分为次一层的4个象限。子象限只含一种属性代码，则停止继续分割。图像区域的栅格阵列应为2n2n(2)四叉树结构：四叉树结构：把2n2n象元组成的阵列当作树根，树的高度为n，每个节点分别代表南西（SW）、南东（SE）、北西（NW）、北东（
20、NE）。四个分支中要么是树叶、树叉。树叶代表一种代码。树叉继续再分。对一幅2n2n的栅格阵列，最大深度为n，层次可能为0,1,n(3)线性线性四叉树编码四叉树编码:(马里兰大学的马里兰大学的GIS系统系统)记录每个叶结点的地址和值，值就是子区的属性代码，其中地址包括两部分，共32位（二进制）最右边4位记录该叶结点的深度，左边的28位记录路径，从右边第5位往左记录从叶节点到根结点的路径。0，1，2，3分别表示SW，SE，NW，NE。第10号结点编码为：000000001101|0011通过记录叶结点的通过记录叶结点的深度码深度码和和层次码层次码来描述叶结点的位置来描述叶结点的位置(4)十进制Mo
21、rton码的编码行号行号 5 = 0 1 0 1 5 = 0 1 0 1列号列号 7= 0 1 1 1 7= 0 1 1 1Morton Morton 码码 = 0 0 1 1 0 1 1 1 = 55 = 0 0 1 1 0 1 1 1 = 55这样就可将用行列表示的二维图像，用这样就可将用行列表示的二维图像，用MortonMorton码写成一维数据，通过码写成一维数据，通过MortonMorton码就可知码就可知象元象元位置位置。把一幅把一幅2n2n的图像的图像压缩压缩压缩压缩成线性四叉树的过程成线性四叉树的过程为：为：按按MortonMorton码把图象读入一维数组。码把图象读入一维数组
22、。相邻的四个象元比较，一致的合并，只记相邻的四个象元比较，一致的合并，只记录第一个象元的录第一个象元的MortonMorton码。码。 比较所形成的大块，相同的再合并，直到比较所形成的大块，相同的再合并，直到不能合并为止。不能合并为止。 对用上述线性四叉树的编码方法所形成的数据还对用上述线性四叉树的编码方法所形成的数据还可进一步用游程长度编码压缩。压缩时只记录第一可进一步用游程长度编码压缩。压缩时只记录第一个象元的个象元的MortonMorton码。码。n n例：四叉树Morton码编码结果 解码时，据解码时，据解码时，据解码时，据MortonMorton码，可知象元在图像中位置。从左码，可知
23、象元在图像中位置。从左码，可知象元在图像中位置。从左码，可知象元在图像中位置。从左上角，本上角，本上角，本上角，本MortonMorton码和下一个码和下一个码和下一个码和下一个MortonMorton码之差即为象元个码之差即为象元个码之差即为象元个码之差即为象元个数。知道了象元的个数和象元的位置就可恢复出图像了。数。知道了象元的个数和象元的位置就可恢复出图像了。数。知道了象元的个数和象元的位置就可恢复出图像了。数。知道了象元的个数和象元的位置就可恢复出图像了。课堂练习：课堂练习：1、栅格数据如何进行取值？、栅格数据如何进行取值？2、栅格数据存储压缩编码方法主要有、栅格数据存储压缩编码方法主要
24、有哪几种？每种方法是如何编码的？哪几种？每种方法是如何编码的？3、写出、写出4* *4图像对应的图像对应的Morton码码2.1矢量数据结构矢量数据结构n2.1.12.1.1矢量数据概念矢量数据概念n2.1.22.1.2矢量数据编码内容矢量数据编码内容n2.1.32.1.3地理关系的类型地理关系的类型n2.1.32.1.3拓扑关系理论拓扑关系理论 n2.1.42.1.4拓扑数据结构拓扑数据结构2.1.12.1.1基本概念基本概念n n矢量数据就是代表地图图形的各离散点平面坐标（x，y）的有序集合。Point - simple primitiveLine - chain of pointsAre
25、a - closed chain of pointsPoints,linesandpolygonsPointscanrepresent:canrepresent:n navertexavertexn nanodeanoden nalabelalabeln napointfeatureapointfeaturePolygonscancanrepresent:represent:n nanareafeatureanareafeaturen naclosedringoflinesaclosedringoflinesLinescanrepresent:canrepresent:n naboundary
26、ofapolygonaboundaryofapolygonn nanetworklinkingpointanetworklinkingpointfeaturesfeaturesn nalinearfeaturealinearfeature2.1.22.1.2矢量数据结构存储方式矢量数据结构存储方式标识码标识码属性码属性码空间对象编码唯一连接空间和属性数据数据库独立编码点:(x ,y )线:(x1 , y1 ),(x2 , y2 ), ,(xn , yn )面:(x1 , y1 ),(x2 , y2 ),(x1 , y1 )点位字典点:点号文件线:点号串面:点号串点号点号X XY Y1 1111
27、122222 233334444n n55556666存储方法存储方法1.点点实实体体2.线线实实体体唯一标识码线标识码起始点终止点坐标对序列显示信息非几何属性线实体3.面面实实体体多边形矢量编码，多边形矢量编码，不但要表示位置不但要表示位置和属性，更重要和属性，更重要的是能表达区域的是能表达区域的的拓扑特征拓扑特征，如，如形状、邻域和层形状、邻域和层次结构等，以便次结构等，以便使这些基本的空使这些基本的空间单元可以作为间单元可以作为专题图的资料进专题图的资料进行显示和操作。行显示和操作。 2.1.32.1.3空间关系的理论空间关系的理论 空间关系可以是由空间实体的空间关系可以是由空间实体的空
28、间关系可以是由空间实体的空间关系可以是由空间实体的几何特性几何特性几何特性几何特性( ( ( (包括空包括空包括空包括空间物体的地理位置与形状间物体的地理位置与形状间物体的地理位置与形状间物体的地理位置与形状) ) ) )引起的空间关系，如距离、引起的空间关系，如距离、引起的空间关系，如距离、引起的空间关系，如距离、方位、连通性、相似性等；也可以是由空间实体的方位、连通性、相似性等；也可以是由空间实体的方位、连通性、相似性等；也可以是由空间实体的方位、连通性、相似性等；也可以是由空间实体的几几几几何特性和非几何特性何特性和非几何特性何特性和非几何特性何特性和非几何特性( ( ( (包括度量属性
29、如高程值、坡度包括度量属性如高程值、坡度包括度量属性如高程值、坡度包括度量属性如高程值、坡度值、气温值等，名称属性如地名、物体名称等值、气温值等，名称属性如地名、物体名称等值、气温值等，名称属性如地名、物体名称等值、气温值等，名称属性如地名、物体名称等) ) ) )共同共同共同共同引起引起引起引起的空间关系，如空间分布现象的统计相关、空间的空间关系，如空间分布现象的统计相关、空间的空间关系，如空间分布现象的统计相关、空间的空间关系，如空间分布现象的统计相关、空间自相关、空间相互作用、空间依赖等；还有一种是完自相关、空间相互作用、空间依赖等；还有一种是完自相关、空间相互作用、空间依赖等；还有一种
30、是完自相关、空间相互作用、空间依赖等；还有一种是完全由空间实体的全由空间实体的全由空间实体的全由空间实体的非几何属性非几何属性非几何属性非几何属性所导出的空间关系，如由所导出的空间关系，如由所导出的空间关系，如由所导出的空间关系，如由两个城市的人口数的比较所产生的大小关系、时间上两个城市的人口数的比较所产生的大小关系、时间上两个城市的人口数的比较所产生的大小关系、时间上两个城市的人口数的比较所产生的大小关系、时间上的先后关系、等级上的高低关系以及成因上的因果关的先后关系、等级上的高低关系以及成因上的因果关的先后关系、等级上的高低关系以及成因上的因果关的先后关系、等级上的高低关系以及成因上的因果
31、关系等都属于此类关系系等都属于此类关系系等都属于此类关系系等都属于此类关系 。 Spatial-spatial relationship邻接相交重合相离包含点点点线点面线面面面线线 这里，我们这里，我们这里，我们这里，我们限定限定限定限定，空间关系是指空间实体空间关系是指空间实体空间关系是指空间实体空间关系是指空间实体之间之间之间之间存在的存在的存在的存在的在一定区域上构成的，在一定区域上构成的，在一定区域上构成的，在一定区域上构成的，由空间实体的几何特由空间实体的几何特由空间实体的几何特由空间实体的几何特征征征征( ( ( (位置、形状位置、形状位置、形状位置、形状) ) ) )引起的，与空
32、间特性有关的各种联引起的，与空间特性有关的各种联引起的，与空间特性有关的各种联引起的，与空间特性有关的各种联系系系系. . . .主要空间关系有：拓扑关系、顺序关系和度量关主要空间关系有：拓扑关系、顺序关系和度量关主要空间关系有：拓扑关系、顺序关系和度量关主要空间关系有：拓扑关系、顺序关系和度量关系系系系 。 空间关系是空间关系是空间关系是空间关系是GISGISGISGIS的重要理论问题之一，在的重要理论问题之一，在的重要理论问题之一，在的重要理论问题之一，在GISGISGISGIS空空空空间数据建模、空间查询、空间分析、空间推理、制间数据建模、空间查询、空间分析、空间推理、制间数据建模、空间
33、查询、空间分析、空间推理、制间数据建模、空间查询、空间分析、空间推理、制图综合、地图理解等过程中起着重要的作用。图综合、地图理解等过程中起着重要的作用。图综合、地图理解等过程中起着重要的作用。图综合、地图理解等过程中起着重要的作用。早期人们认为早期人们认为GIS空间关系主要分为顺序关系、空间关系主要分为顺序关系、度量关系、拓扑关系三大类。度量关系、拓扑关系三大类。Egenhofer指出空间关系指出空间关系(或空间介词或空间介词)表达了空表达了空间数据之间的一种约束，其中度量关系对空间数据的间数据之间的一种约束，其中度量关系对空间数据的约束最为强烈约束最为强烈,而顺序关系次之而顺序关系次之,拓扑
34、关系最弱。拓扑关系最弱。度量关系属于定量关系，拓扑与顺序关系则属于度量关系属于定量关系，拓扑与顺序关系则属于定性关系。定性关系。但是定性的关系与定量的关系之间并不是绝对的，但是定性的关系与定量的关系之间并不是绝对的，而是可以互相转化的。而是可以互相转化的。这里重点介绍空间拓扑关系这里重点介绍空间拓扑关系。n n1.1.1.1.图论（图论（图论（图论（Graph theoryGraph theory） 在在图图论论中中，点点叫叫做做0-0-cellscells ，线线叫叫做做1-1-cellscells， 区区叫叫做做2-2-cellscells。 1-1-cellscells连接连接0-0-c
35、ellscells 形成形成2-cells2-cells。3.3.拓扑关系拓扑关系拓扑关系拓扑关系拓扑所研究的是几何图形的一些性质，它们在拓扑所研究的是几何图形的一些性质，它们在拓扑所研究的是几何图形的一些性质，它们在拓扑所研究的是几何图形的一些性质，它们在图形被弯曲、拉大、缩小或任意的变形下保持不变，图形被弯曲、拉大、缩小或任意的变形下保持不变，图形被弯曲、拉大、缩小或任意的变形下保持不变，图形被弯曲、拉大、缩小或任意的变形下保持不变，只要在变形过程中只要在变形过程中只要在变形过程中只要在变形过程中不使原来不同的点重合为同一个不使原来不同的点重合为同一个不使原来不同的点重合为同一个不使原来不
36、同的点重合为同一个点，又不产生新点点，又不产生新点点，又不产生新点点，又不产生新点。换句话说，这种变换的条件是：在原来图形的换句话说，这种变换的条件是：在原来图形的换句话说，这种变换的条件是：在原来图形的换句话说，这种变换的条件是：在原来图形的点与变换了图形的点之间存在着一一对应的关系，点与变换了图形的点之间存在着一一对应的关系，点与变换了图形的点之间存在着一一对应的关系，点与变换了图形的点之间存在着一一对应的关系，并且邻近的点还是邻近的点。这样的变换叫做并且邻近的点还是邻近的点。这样的变换叫做并且邻近的点还是邻近的点。这样的变换叫做并且邻近的点还是邻近的点。这样的变换叫做拓扑拓扑拓扑拓扑变换
37、变换变换变换。几何与拓扑的相对关系几何与拓扑的相对关系几何与拓扑的相对关系几何与拓扑的相对关系几何（Geometry）是与点的位置有关。拓扑（topology）是与点的空间关系有关Note: Geometry has changedTopology is identical拓扑有一个形象说法拓扑有一个形象说法拓扑有一个形象说法拓扑有一个形象说法橡皮几何学橡皮几何学橡皮几何学橡皮几何学。因为如。因为如。因为如。因为如果图形都是用橡皮做成的，就能把许多图形进行拓果图形都是用橡皮做成的，就能把许多图形进行拓果图形都是用橡皮做成的，就能把许多图形进行拓果图形都是用橡皮做成的，就能把许多图形进行拓扑变换
38、。扑变换。扑变换。扑变换。例如：一个橡皮圈能变形成一个圆圈或一个方例如：一个橡皮圈能变形成一个圆圈或一个方例如：一个橡皮圈能变形成一个圆圈或一个方例如：一个橡皮圈能变形成一个圆圈或一个方圈。但是一个橡皮圈不能由拓扑变换成为一个阿拉圈。但是一个橡皮圈不能由拓扑变换成为一个阿拉圈。但是一个橡皮圈不能由拓扑变换成为一个阿拉圈。但是一个橡皮圈不能由拓扑变换成为一个阿拉伯数字伯数字伯数字伯数字8 8。因为不把圈上的两个点重合在一起，圈。因为不把圈上的两个点重合在一起，圈。因为不把圈上的两个点重合在一起，圈。因为不把圈上的两个点重合在一起，圈就不会变成就不会变成就不会变成就不会变成8 8。拓扑空间关系是指
39、拓扑变换下的拓扑不变量，拓扑空间关系是指拓扑变换下的拓扑不变量，拓扑空间关系是指拓扑变换下的拓扑不变量，拓扑空间关系是指拓扑变换下的拓扑不变量，拓扑关系是指网结构元素结点、弧段、面域之间的拓扑关系是指网结构元素结点、弧段、面域之间的拓扑关系是指网结构元素结点、弧段、面域之间的拓扑关系是指网结构元素结点、弧段、面域之间的空间关系，主要表现为下列三种关系：拓扑邻接关空间关系，主要表现为下列三种关系：拓扑邻接关空间关系，主要表现为下列三种关系：拓扑邻接关空间关系，主要表现为下列三种关系：拓扑邻接关系（系（系（系（ AdjacencyAdjacency ）、拓扑关联关系（）、拓扑关联关系（）、拓扑关联
40、关系（）、拓扑关联关系（ IncidenceIncidence ）、）、）、）、拓扑包含关系（拓扑包含关系（拓扑包含关系（拓扑包含关系（ EnclosureEnclosure）。(1)邻接关系邻接关系（Adjacency）：同类拓扑元素之间的关系同类拓扑元素之间的关系同类拓扑元素之间的关系同类拓扑元素之间的关系TwotopologicalentitiesofthesamekindshareatopologicalentityofanotherkindTwo0cellsshareacommon1cell(0/0cell)Two1cellsshareacommon0cell(1/1cell)Two
41、2cellsshareacommon1cell(2/2cell)(2)关联关系（关联关系（Incidence）：）：不同类拓扑元素之间的关系不同类拓扑元素之间的关系 ManytopologicalentitiesofthesamekindconvergeonanentityofanotherkindMany1cellsconvergeonacommon0cell(1/0cellincidence)Many0cellsconvergeonacommon1cell(0/1cellincidence)Many2cellsconvergeonacommon1cell(2/1cellincidence)
42、(3)(3)包含关系（包含关系（包含关系（包含关系（ EnclosureEnclosure ）：）：）：）： 不同级的元素之间的拓扑关系不同级的元素之间的拓扑关系不同级的元素之间的拓扑关系不同级的元素之间的拓扑关系拓扑的Endpoint(point,arc)点是弧的端点Simple-nonself-intersection(arc)非自交的弧On-boundary(point,region)温哥华在加拿大和美国的边界上Inside(point,region)明尼阿波利斯市在明尼苏达州内Outside(point,region)麦迪逊市在明尼苏达州之外Open(region)加拿大的内部是个开域
43、（不包括其边界）Close(region)Carleton郡是个闭域（包括其边界）Connected(region)瑞士是个连通域，而日本不是连通域Inside(point,loop)点在环中Crosses(arc,region)路（弧）穿过森林（区域）Touches(region,region)明尼苏达州是威斯康星州的邻州Touches(arc,region)土地覆盖（区）和土地利用（区）相重叠非拓扑的Euclidean-distancepoint,point两点间的距离Direction(point,point)麦迪逊市在明尼阿波利斯市的东面Length(arc)单位向量的长度是1个单位P
44、erimeter(area)单位正方形的周长是4个单位Area(region)单位正方形的面积是1个平方单位4.拓扑和非拓扑操作举例2.1.52.1.5矢量数据结构矢量数据结构n n1.1.1.1.面条数据结构面条数据结构面条数据结构面条数据结构（spaghettispaghetti） n n2.2.2.2.索引式数据结构索引式数据结构索引式数据结构索引式数据结构n n3.3.3.3. DIME DIME数据结构数据结构数据结构数据结构n n4.4.4.4.链状双重独立式链状双重独立式链状双重独立式链状双重独立式n n5.5.5.5.POLYVRTPOLYVRT结构结构结构结构n n6. 6.
45、 ArcInfo topologyArcInfo topology只记录空间对象的位置坐标和属性信息，只记录空间对象的位置坐标和属性信息，只记录空间对象的位置坐标和属性信息，只记录空间对象的位置坐标和属性信息，不记录拓扑关系不记录拓扑关系不记录拓扑关系不记录拓扑关系。n n存储：存储：存储：存储：n n独立存储：独立存储：独立存储：独立存储：物体以独立的实体存贮，不存贮点、线、面原始物体以独立的实体存贮，不存贮点、线、面原始物体以独立的实体存贮，不存贮点、线、面原始物体以独立的实体存贮，不存贮点、线、面原始空间关系，只存几何特征。空间关系，只存几何特征。空间关系，只存几何特征。空间关系，只存几
46、何特征。空间对象位置直接跟随空间对象；空间对象位置直接跟随空间对象；空间对象位置直接跟随空间对象；空间对象位置直接跟随空间对象；n n点位字典：点坐标独立存储，线、面由点号组成点位字典：点坐标独立存储，线、面由点号组成点位字典：点坐标独立存储，线、面由点号组成点位字典：点坐标独立存储，线、面由点号组成n n特征特征特征特征n n无拓扑关系，主要用于显示、输出及一般查询无拓扑关系，主要用于显示、输出及一般查询无拓扑关系，主要用于显示、输出及一般查询无拓扑关系，主要用于显示、输出及一般查询n n公共边重复存储，存在数据冗余，难以保证数据独立性和一公共边重复存储，存在数据冗余，难以保证数据独立性和一
47、公共边重复存储，存在数据冗余，难以保证数据独立性和一公共边重复存储，存在数据冗余，难以保证数据独立性和一致性致性致性致性n n多边形分解和合并不易进行，邻域处理较复杂；多边形分解和合并不易进行，邻域处理较复杂；多边形分解和合并不易进行，邻域处理较复杂；多边形分解和合并不易进行，邻域处理较复杂；n n处理嵌套多边形比较麻烦处理嵌套多边形比较麻烦处理嵌套多边形比较麻烦处理嵌套多边形比较麻烦n n适用范围：适用范围：适用范围：适用范围：制图及一般查询，不适合复杂的空间分析制图及一般查询，不适合复杂的空间分析制图及一般查询，不适合复杂的空间分析制图及一般查询，不适合复杂的空间分析1.实体实体(面条面条
48、)数据结构数据结构（spaghetti）一幅地图可以划一幅地图可以划一幅地图可以划一幅地图可以划分成许多多边形，分成许多多边形，分成许多多边形，分成许多多边形，每个多边形由一每个多边形由一每个多边形由一每个多边形由一条或若干条弧段条或若干条弧段条或若干条弧段条或若干条弧段组成，每条弧段组成，每条弧段组成，每条弧段组成，每条弧段由一串有序的由一串有序的由一串有序的由一串有序的x x，y y坐标对组成，坐标对组成，坐标对组成，坐标对组成，每条弧段的两端每条弧段的两端每条弧段的两端每条弧段的两端点为结点，每个点为结点，每个点为结点，每个点为结点，每个结点连接两条以结点连接两条以结点连接两条以结点连接
49、两条以上的弧段，多边上的弧段，多边上的弧段，多边上的弧段，多边形矢量编码主要形矢量编码主要形矢量编码主要形矢量编码主要用于表示空间图用于表示空间图用于表示空间图用于表示空间图形为多边形的面形为多边形的面形为多边形的面形为多边形的面状要素，每个多状要素，每个多状要素，每个多状要素，每个多边形在数据库中边形在数据库中边形在数据库中边形在数据库中是相互独立、分是相互独立、分是相互独立、分是相互独立、分开存储的。开存储的。开存储的。开存储的。直接存储直接存储直接存储直接存储2.索引式索引式(点位字典点位字典)线与点之间的树状索引线与点之间的树状索引 多边形与线之间的树状索引多边形与线之间的树状索引 点
50、号点号坐标坐标1 1X1,y1X1,y12 2X2,y2X2,y2. .3131X31,y31X31,y31线号线号 起点起点 终点终点点号点号a a1 15 51 1，2 2，3 3，4 4，5 5b b5 58 85 5，6 6，7 7，8 8j j242431312424，2525，2626，2727，2828，2929，3030，3131多边形号多边形号边界线号边界线号A Aa a，b b，h hB Bc c，f f，g g，h h，j j. .E Eb b，c c，I I，d d线线点点索索引引文文件件多多边边形形线线索索引引文文件件点点坐坐标标文文件件3.DIME结构结构n双 重
51、独 立 地 图 编 码 ， 简 称 DIME结 构 （ Dual IndependentMapEncoding）。是一种把几何量度信息（直角坐标）与拓扑逻辑信息结合起来的系统。(美国人口统计系统采用的一种编码方式)nDIME文件的基本元素是连接两个端点（结点）的一条线段（街段）、线段始结点和终结点标识符、伴有这两个结点的坐标及线段两侧的区域代码（左区号和右区号）。根据结点标识符和结点坐标建立结点坐标文件。根据结点、线段、多边形间的拓扑关系建立拓扑结构文件。在这种结构中，线段通常被认为是直线型的，复杂的曲线由一系列逼近曲线的直线段来表示。结点与结点或者面域与面域之间为邻接关系，而结点与线段或面域
52、与线段之间为关联关系,。 4.链状双重独立式链状双重独立式链状双重独立式数据结构是DIME数据结构的一种改进。在的一种改进。在DIMEDIME中，一条边只能用直线两中，一条边只能用直线两端点的序号及相邻的面域来表示，而在链状数据端点的序号及相邻的面域来表示，而在链状数据结构中，将结构中，将若干直线段合为一个弧段若干直线段合为一个弧段（或链段），（或链段），每个弧段可以有许多中间点。每个弧段可以有许多中间点。在链状双重独立数据结构中，主要有四个文件：在链状双重独立数据结构中，主要有四个文件：多边形文件、弧段文件、弧段坐标文件、结点文多边形文件、弧段文件、弧段坐标文件、结点文件。件。弧段文件弧段文
53、件弧段文件弧段文件弧段文件弧段文件弧段号弧段号起始点起始点终结点终结点左多边形左多边形右多边右多边形形aa551100AAbb8855EEAAcc161688EEBBdd19195500EEee1515191900DDff15151616DDBBgg11151500BBhh8811AABBii16161919DDEEjj31313131BBCC弧段坐标文件弧段坐标文件弧段坐标文件弧段坐标文件弧段坐标文件弧段坐标文件弧段号弧段号点点号号aa5,4,3,2,15,4,3,2,1bb8,7,6,58,7,6,5cc16,17,816,17,8dd19,18,519,18,5ee15,23,22,21
54、,20,1915,23,22,21,20,19ff15,16,15,16,gg1,10,11,12,13,14,151,10,11,12,13,14,15hh8,9,18,9,1ii16,1916,19jj31,30,29,28,27,26,25,24,3131,30,29,28,27,26,25,24,31链状双重独立式链状双重独立式多边形文件多边形文件多边形文件多边形文件多边形文件多边形文件多边形号多边形号弧段号弧段号周长周长面积面积中心点中心点坐标坐标AAh,b,ah,b,aBBg,f,c,h,-jg,f,c,h,-jCCjjDDe,i,fe,i,fEEe,i,d,be,i,d,b5.P
55、OLYVRT结构结构(多边形转换器多边形转换器多边形转换器多边形转换器)POLYVRT结构由哈佛大学计算机图形与空间分析结构由哈佛大学计算机图形与空间分析实验室开发，是实验室开发，是ArcInfo拓扑模型的前身。拓扑模型的前身。基本元素是基本元素是“弧段弧段”。“弧段弧段”在两端有结点，在两端有结点，并伴随有共享该弧段的左右多边形的码，并伴随有共享该弧段的左右多边形的码， “弧段弧段”可可以由任意多个结点构成。此外，在以由任意多个结点构成。此外，在POLYVRT中还为中还为每个多边形建立了一个环绕边界的弧段目录表，以及每个多边形建立了一个环绕边界的弧段目录表，以及为点建立一个点所关联的弧段目录
56、表，并在弧段关系为点建立一个点所关联的弧段目录表，并在弧段关系表中，将表中，将点所关联的弧段和组成多边形的边界弧段用点所关联的弧段和组成多边形的边界弧段用点所关联的弧段和组成多边形的边界弧段用点所关联的弧段和组成多边形的边界弧段用串行指针连接起来串行指针连接起来串行指针连接起来串行指针连接起来。结点集合面域集合弧段集合F1F2F3e1e2N2N1N4e6e3e4e5N3F06.ArcInfotopologyNodetopologyNodetopology： twonodestwonodesrelatedtoeachrelatedtoeacharcarcArctopologyArctopolog
57、y ：thetwothetwopolygonsonpolygonsoneithersideareeithersidearerelatedtoeachrelatedtoeacharcarcPolygontopologyPolygontopology ：thearcsarerelatedthearcsarerelatedtoeachpolygon.toeachpolygon.b34 acfde2 5ABC14ZDIME模型与模型与POLYVRT模型的比较模型的比较DIME与POLYVRT模型本质是一样的，区别在于：n描述多边形的空间关系并作为关系文件记录的基本单元的边的选择策略不同。nDIME模型
58、以两个数据点间的线段为关系的描述和记录单元，而POLYVRT模型以两个结点的链为记录单元。两种模型都不能对线性要素间的邻接关系进行显示描述。2.3.矢量与栅格数据对比矢量与栅格数据对比矢量数据矢量数据n n数据存储量小数据存储量小n n空间位置精度高空间位置精度高n n用用网网络络连连接接法法能能完完整整描描述述拓拓扑扑关系关系n n输输出出简简单单容容易易，绘绘图图细细腻腻、精精确、美观确、美观n n可可对对图图形形及及其其属属性性进进行行检检索索、更新和综合更新和综合n n数据结构复杂数据结构复杂n n 获取数据慢获取数据慢n n 数学模拟困难数学模拟困难n n多种地图叠合分析困难多种地图
59、叠合分析困难n n不能直接处理数字图像信息不能直接处理数字图像信息n n 空间分析不容易实现空间分析不容易实现n n 边界复杂、模糊事物难以描述边界复杂、模糊事物难以描述n n 数据输出的费用较高数据输出的费用较高栅格数据栅格数据n n数据存储量大数据存储量大n n空间位置精度低空间位置精度低n n难于建立网络连接关系难于建立网络连接关系n n输输出出速速度度快快，但但绘绘图图粗粗糙糙、不不美观美观n n便于面状数据处理便于面状数据处理n n数据结构简单数据结构简单n n快速获取大量数据快速获取大量数据n n数学模拟方便数学模拟方便n n多种地图叠合分析方便多种地图叠合分析方便n n能直接处理数字图像信息能直接处理数字图像信息n n空间分析易于进行空间分析易于进行n n容容易易描描述述边边界界复复杂杂、模模糊糊的的事事物物n n技术开发费用低技术开发费用低课堂练习：课堂练习：1、什么叫拓扑关系？拓扑关系有哪几种？、什么叫拓扑关系？拓扑关系有哪几种？2、举例说明索引式数据结构、举例说明索引式数据结构、DIME数据结数据结构、链状双重独立式数据结构构、链状双重独立式数据结构3、比较矢量、栅格数据结构的特点、比较矢量、栅格数据结构的特点
