《地理信息系统原理(高勇)04空间数据结构.ppt》由会员分享，可在线阅读，更多相关《地理信息系统原理(高勇)04空间数据结构.ppt（79页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、北京大学遥感与地理信息系统研究所空间数据结构空间数据结构栅格数据结构矢量数据结构矢量栅格的转换空间关系空间数据结构空间数据结构l空间数据结构l是适合于计算机系统存储、管理和处理的地学图形的逻辑结构，是地理实体的空间排列方式和相互关系的抽象描述。l是对空间数据的一种理解和解释，只有充分理解GIS系统所使用的特定的数据结构，才能正确的使用系统。l分类l矢量数据结构l栅格数据结构l矢量和栅格都可用来描述地理实体的点、线、面三种基本类型l空间数据编码l是空间数据结构的实现l将各种空间数据按特定的数据结构转换为适合于计算机存储和处理的数据的过程栅格数据结构栅格数据结构l概念l将研究区域划分为大小均匀紧密
2、相邻的网格阵列l每个网格作为一个像元或像素由行、列定义l每个网格包含一个代码表示该像素的属性类型或量值，或者记录指向属性数据的指针l每个网格的大小代表空间分辨率l特征l以规则的阵列表示空间地物或现象分布的数据组织，组织中的每个数据表示地物或现象的非几何属性特征。l栅格结构表示的地表是不连续的，是量化和近似离散的数据。每一个单元格对应一个相应的地块l位置由栅格行、列号定义示例示例Real worldGridValue=0=1=2=3RASTERRASTERLineAreaRowColumnPoint点、线、面地物的栅格结构点、线、面地物的栅格结构l点状地物l用一个栅格单元表示l线状地物l沿线走向
3、的一组相邻栅格单元l每个栅格单元最多只有两个相邻单元在线上l面状地物l有区域属性的相邻栅格单元的集合l每个栅格单元可有多于两个的相邻单元同属一个区域LineAreaRowColumnPoint点点线线面面分辩率分辩率l一个像素代表的实际地理范围大小lx方向分辩率ly方向分辩率真实世界真实世界栅格数据栅格数据1 pixel =10mX10m 分辨率分辨率=10m10M10M1 Pixel栅格数据的定位栅格数据的定位l位置由栅格行、列号定义l绝对定位l基准点l左下点l左上点l行号、列号l分辩率x=x0+col*resolutiony=y0-row*resolution(x0,y0)(row,col
4、)resolutionxycolrow栅格数据的形状、尺寸及相关问题栅格数据的形状、尺寸及相关问题l栅格数据单元格经常是矩形（主要是正方形）的，但并不是必须如此。其单元格形状可以随应用的需要进行具体设定，比如设置为三角形l栅格数据的分辩率（比例尺）就是栅格单元大小与地表相应单元大小之比l栅格单元尺寸越小，其分辨率越高，数据量也越大l由于栅格结构对地表的离散，在计算面积、长度、距离、形状等空间指标时，若栅格尺寸较大，则造成较大的误差 l由于栅格单元中存在多种地物，而数据中常常只记录一个属性值，这会导致属性误差。比如，遥感数据中的“混合像元”问题决定栅格单元代码的方式决定栅格单元代码的方式l每一个
5、单元可能对应多个地物种类或多个属性值l原则：尽量保持地表的真实性，保证最大的信息容量 l中心点法 l用处于栅格中心处的地物类型或现象特性决定栅格代码 l常用于具有连续分布特性的地理要素，如降雨量分布、人口密度图等l面积占优法l以占栅格区域面积比例最大的地物类型或现象特性决定栅格单元的代码 l面积占优法常用于分类较细，地物类别斑块较小的情况 l重要性法 l根据栅格内不同地物的重要性，选取最重要的地物类型决定相应的栅格单元代码 l重要性法常用于具有特殊意义而面积较小的地理要素，特别是点、线状地理要素，如城镇、交通枢纽、交通线、河流水系等，在栅格中代码应尽量表示这些重要地物 l百分比法 l根据栅格区
6、域内各地理要素所占面积的百分比数确定栅格单元的代码 l适用于地物面积具有重要意义的分类体系 l其他方法 l如插值方法（平均值就是其中之一），或使用特定的计算函数等栅格数据的特点栅格数据的特点l属性明显l数据中直接记录了数据属性或指向数据属性的指针，因而可以直接得到地物的属性代码l定位隐含l所在位置则根据行列号转换为相应的坐标，也就是说定位是根据数据在数据集中的位置得到的l栅格结构是按一定的规则排列的，所表示的实体的位置很容易隐含在格网文件的存储结构中l简单方便l栅格数据结构结构容易实现，算法简单，且易于扩充、修改，也很直观l特别是易于同遥感影像的结合处理，给地理空间数据处理带来了极大的方便栅格
7、数据编码栅格数据编码l栅格数据编码方法分为两大类：l直接栅格编码 l压缩编码方法 l链码 l游程长度编码 l块码 l四叉树 直接栅格编码直接栅格编码l将栅格数据看作一个数据矩阵l逐行（或逐列）逐个记录代码l可以每行都从左到右逐个象元进行记录l也可以奇数行地从左到右而偶数行地从右向左记录l为了特定目的还可采用其他特殊的顺序 一些常用的栅格排列顺序一些常用的栅格排列顺序按行编码的栅格数据结构的实现按行编码的栅格数据结构的实现l数据可以使用一维数组或者二维数组实现l数据的类型由实际情况决定：byte,int,float,double,RGB等class Rasterint rows;/行数（高）in
8、t cols;/列数（宽）type*data;/数据，type可以是byte,int,float,double,RGB等 /或者 type data256256;double resolution;/分辩率，也可能是int等类型的type getValue(int r,int c)type value=datar*cols+c;return vlaue;栅格压缩编码方式栅格压缩编码方式l压缩编码的目的就是用尽可能少的数据量记录尽可能多的信息，其类型分为l信息无损编码l编码过程中没有任何信息损失，通过解码操作可以完全恢复原来的信息 l信息有损编码l为了提高编码效率，最大限度地压缩数据，在压缩过程
9、中损失一部分相对不太重要的信息，解码时这部分难以恢复l在地理信息系统中的压缩编码多采用信息无损编码，而对原始遥感影像进行压缩时也可以采取有损压缩编码方法l主要的栅格压缩编码方法l链码、游程长度编码、块码、四叉树链码链码l又称为弗里曼链码或边界链码l编码方法l将数据表示为由某一原点开始并按某些基本方向确定的单位矢量链l基本方向：八个基本方向，用07代表l前两个数字表示起点的位置（行，列）l从第三个数字开始每个数字表示单位矢量的方向l示例l3,2,0,7,1,1,2,2,1l优点：l对线、多边形的表示具有很强的数据压缩能力，且具有一定的运算功能，如面积和周长计算等，探测边界急弯和凹进部分等都比较容
10、易，比较适于存储图形数据。l缺点：l对叠置运算如组合、相交等则很难实施，对局部修改将改变整体结构，效率较低，而且由于链码以每个区域为单位存储边界，相邻区域的公共边界被重复存储会产生冗余01234567游程长度编码游程长度编码l对于一幅栅格图像，常常有行（或列）方向上相邻的若干点具有相同的属性代码，因而可采取某种方法压缩那些重复的记录内容l其实现方法有两种l（1）只在各行（或列）数据的代码发生变化时依次记录该代码以及相同的代码重复的个数，从而实现数据的压缩。l（2）逐个记录各行（或列）代码发生变化的位置和相应代码 l优点l压缩效率较高，且易于进行检索，叠加合并等操作，运算简单，适用于机器存储容量
11、小，数据需大量压缩，而又要避免复杂的编码解码运算增加处理和操作时间的情况 l缺点l对于图斑破碎，属性和边界多变的数据压缩效率较低，甚至压缩后的数据量比原始数据还大游程长度编码示例游程长度编码示例l按第一种编码方法（沿行方向）l(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)l用44个整数表达了原始数据中的64个栅格l按第二种编码方法（沿列方向）l(1,0)，(2,4)，(4,0)，(
12、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)块码块码l游程长度编码扩展到二维的情况，采用方形区域作为记录单元，每个记录单元包括相邻的若干栅格l数据结构：初始位置行号、初始位置列号、半径、代码值l(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,
13、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)四叉树编码四叉树编码l整个图像区逐步分解为一系列仅包含单一类型的方形区域，最小的方形区域为一个栅格象元l将一幅栅格地图或图像等分为四部分l逐块检查其栅格属性值(或灰度)。如果某个子区的所有栅格值都具有相同的值，则这个子区就不再继
14、续分割；否则还要把这个子区再分割成四个子区l这样依次地分割，直到每个子块都只含有相同的属性值或灰度为止l由上而下的方法运算量大，耗时长。实践中可以采用从下而上的方法l对栅格数据按如下的顺序进行检测：如果每相邻四个栅格值相同则进行合并，逐次往上递归合并，直到符合四叉树的原则为止。这种方法重复计算较少，运算速度较快l采用四叉树编码时，为了保证四叉树分解能不断地进行下去，要求图像必须为2n2 n的栅格阵列，对于非标准尺寸的图像需首先通过增加背景的方法将图像扩充为2 n 2 n的图像四叉树的划分过程四叉树的划分过程四叉树的编码方法四叉树的编码方法l常规四叉树l除了记录叶结点之外，还要记录中间结点。结点
15、之间借助指针联系，每个结点需要用六个量表达：四个叶结点指针，一个父结点指针和一个结点的属性或灰度值l线性四叉树l只存贮最后叶结点的信息。包括叶结点的位置、深度和本结点的属性或灰度值l线性四叉树示例l位置：叶子结点的路径叶子结点的深度，用二进制表示lSW0，SE1，NW2，NE3l下图中的结点：001110 0011l路径：SW-NE-NW 0-3-2 001110l深度：3 0011l位置属性数值四叉树编码示例四叉树编码示例 四叉树编码的优缺点四叉树编码的优缺点l优点l具有可变的分辨率，树的深度随数据的破碎程度而变化l有区域性质，压缩数据灵活l许多数据和转换运算可以在编码数据上直接实现，大大地
16、提高了运算效率l支持拓扑“洞”（嵌套多边形）的表达，是优秀的栅格压缩编码之一。l缺点l最大不足是其不稳定性，即同样的原始数据应用不同的算法进行编码可能会得到不同的编码结果。不利于数据分析。其他编码方式其他编码方式l如傅立叶变换、小波变换、余弦变换等，常常用于遥感原始数据的压缩。l由于它们多数是有损压缩，一般不用于需要进行分析的栅格数据。l在四叉树基础上发展而来的八叉树目前也是研究热点之一。常见栅格压缩编码方法总结常见栅格压缩编码方法总结l链码的压缩效率较高，已经近矢量结构，对边界的运算比较方便，但不具有区域的性质，区域运算困难 l游程长度编码既可以在很大程度上压缩数据，又最大限度地保留了原始栅
17、格结构，编码解码十分容易。但对破碎数据处理效果不好l块码和四叉树编码具有区域性质，又具有可变的分辨率，有较高的压缩效率，但运算效率是其瓶颈l四叉树编码可以直接进行大量图形图像运算，效率较高压缩编码的相关问题压缩编码的相关问题l压缩编码过程的主要矛盾l数据量压缩和运算时间之间的矛盾l为了更有效地利用空间资源，减少数据冗余，不得不花费更多的运算时间进行编码 l好的压缩编码方法l要在尽可能减少运算时间的基础上达到最大的数据压缩效率l算法适应性强，易于实现矢量数据结构矢量数据结构l通过记录坐标的方式尽可能精确地表示点、线、多边形等地理实体，坐标空间设为连续，允许任意位置、长度和面积的精确定义。l在一般
18、情况下，其精度比栅格数据结构高得多。其精度仅受数字化设备的精度和数值记录字长的限制l矢量结构允许最复杂的数据以最小的数据冗余进行存储，相对栅格结构来说，一般数据精度较高，所占空间较小，是高效的空间数据结构矢量数据结构的类型矢量数据结构的类型l点：空间上不能再分的地理实体，可以是抽象的或具体的l线：用来表示线状地物和多边形边界l多边形（面）：描述区域实体，特别是有名称属性或分类属性的Buildings.PolygonStreams,LineWells,PointRoads,LineZoning,PolygonMAP SHEETS矢量数据结构的特点矢量数据结构的特点l定位明显l其定位是根据坐标直接
19、存储的，无需任何推算l属性隐含 l属性一般存于文件头或数据结构中某些特定的位置上l 这种特点的影响l矢量数据结构图形运算的算法总体上比栅格数据结构复杂的多，在叠加运算、邻域搜索等操作时比较困难，有些甚至难以实现l但其也有便利和独到之处，在计算长度、面积、形状和图形编辑、几何变换操作中，矢量结构有很高的效率和精度点实体的矢量数据编码方法点实体的矢量数据编码方法l对于点实体，矢量结构中只记录其在特定坐标系下的坐标和属性代码l坐标由一对x、y表示(X,Y)点实体编码的实现点实体编码的实现l使用一对浮点型的坐标记录class Pointdoublex;doubley;线实体线实体l在数字化时即进行量化
20、，就是用一系列足够短的直线段首尾相接表示一条曲线l当曲线被分割成多而短的线段后，这些小线段可以近似地看成直线段l而这条曲线也可以足够精确地由这些小直线段序列表示l矢量结构中只记录这些小线段的端点坐标，将曲线表示为一个坐标序列l坐标之间认为是以直线段相连l在一定精度范围内可以逼真地表示各种形状的线状地物(X,Y)(X2,Y2)(X3,Y3)(X4,Y4)(X5,Y5)线实体的矢量数据编码方法线实体的矢量数据编码方法唯一标识码是系统排列序号；线标识码可以标识线的类型；起始点和终止点号可直接用坐标表示；显示信息是显示时的文本或符号等；与线相联系的非几何属性可以直接存储于线文件中，也可单独存储，而由标
21、识码联接查找 线实体的编码的实现线实体的编码的实现l点的序列，点的数组class Lineint number;/线上点的数目Point*points;/线上点的坐标对序列/或Point points256;多边形实体多边形实体l多边形在地理信息系统中是指一个任意形状、边界完全闭合的空间区域l其边界将整个空间划分为外部和内部。l多边形数据是描述地理信息的最重要的一类数据l在区域实体中，具有名称属性和分类属性的，多用多边形表示，如行政区、土地类型、植被分布等(X5,Y5)(X1,Y1)(X2,Y2)(X4,Y4)(X3,Y3)多边形实体的编码方法多边形实体的编码方法l需要表达的内容l位置和属性l
22、区域的拓扑性质，如形状、邻域和层次等l要求l存储效率l所表示的各多边形有各自独立的形状，可以计算各自的周长和面积等几何指标l各多边形拓扑关系的记录方式要一致，以便进行空间分析l要明确表示区域的层次，如岛-湖-岛的关系等l主要方法l坐标序列法l树状索引编码法 l拓扑结构编码法 坐标序列法坐标序列法l由多边形边界的(x,y)坐标对集合及说明信息组成l是最简单的一种多边形矢量编码坐标序列法的优缺点坐标序列法的优缺点l优点l文件结构简单l易于实现以多边形为单位的运算和显示 l缺点l多边形之间的公共边界被数字化和存储两次，由此产生冗余和碎屑多边形l每个多边形自成体系而缺少邻域信息，难以进行邻域处理，如消
23、除某两个多边形之间的共同边界l岛只作为一个单个的图形建造，没有与外包多边形的联系l不易检查拓扑错误坐标序列法的实现坐标序列法的实现l外围边界岛class PolygonLine ring;/外围边界，封闭的环int n;/岛的数目Line*islands;/岛的边界（环）的序列;l环的记录方法树状索引编码法树状索引编码法l采用树状索引以减少数据冗余并间接增加邻域信息l方法l对所有边界点进行数字化l将坐标对以顺序方式存储l由点索引与边界线号相联系，以线索引与各多边形相联系，形成树状索引结构树状索引编码法示例树状索引编码法示例树状索引编码法形成的文件记录树状索引编码法形成的文件记录树状索引编码法的
24、优势和不足树状索引编码法的优势和不足l优点l消除了相邻多边形边界的数据冗余和不一致的问题l在简化过于复杂的边界线或合并相邻多边形时可不必改造索引表l邻域信息和岛状信息可以通过对多边形文件的线索引处理得到l不足l比较繁琐，给相邻关系运算、消除无用边、处理岛状信息以及检查拓扑关系带来一定的困难l两个编码表都需要以人工方式建立，工作量大且容易出错拓扑结构编码法拓扑结构编码法l要彻底解决邻域和岛状信息处理问题必须建立一个完整的拓扑关系结构l这种结构应包括以下内容l唯一标识l多边形标识l外包多边形指针l邻接多边形指针l边界链接l范围（最大和最小x、y坐标值，即外包矩形信息）拓扑结构拓扑结构l区域l每个多
25、边形可以用一组封闭的线来表示，而不需要记录封闭线上的所有点l避免两次记录相邻多边形的公共边界l减少了数据冗余l邻接性l多边形之间的相互邻接性l连通性l指对弧段连接的判别双重独立地图编码双重独立地图编码lDIMEDual Independent Map EncodinglDIME是美国人口调查局在人口调查的基础上发展起来l它通过有向编码建立了多边形、边界、节点之间的拓扑关系lDIME编码成为其它拓扑编码结构的基础l它采用树状索引以减少数据冗余并间接增加邻域信息l方法是对所有边界点进行数字化，将坐标对以顺序方式存储，由点索引与边界线号相联系，以线索引与各多边形相联系，形成树状索引结构多边形的拓扑结
26、构多边形的拓扑结构l多边形表l按逆时针方向，依次记录弧的编号l反方向的弧，编号取负值l标识岛的开始，岛按顺时针方向记录弧的编号l（也可以多边形按顺时针，岛按逆时针）l弧段表l起始结点号，终止结点号l左多边形，右多边形l结点表l按逆时针（或顺时针）方向记录以该结点为端点的弧的编号多边形拓扑结构示例多边形拓扑结构示例polygon idarcsI1,2,-9II3,-7,8,9,0,10III-10IV6,7,4V5,-4,-3,-2arc idfrom nodeto node left polyright polypoints1(1)(6)I-12(6)(8)IV3(8)(21)IIV4(21)
27、(28)IVV5(6)(28)V-16(28)(19)IV-17(19)(21)IVII8(19)(1)II-19(1)(8)III10(33)(33)IIIIInode idarcs(1)-8,1,9(6)2,-1,5(8)-9,-2,3(19)-6,8,7(21)-7,-3,-4(28)6,-4,-5(33)10拓扑结构编码的特点拓扑结构编码的特点l优点l数据没有冗余，存储效率高l所有的邻域关系都能实现l岛与多边形的层次关系不受限制l可以较好地解决空间关系查询等问题l缺点l增加了算法的复杂性和数据存储量矢量数据结构的简单几何对象模型矢量数据结构的简单几何对象模型矢量数据结构编码总结矢量数据
28、结构编码总结l矢量编码保证了信息的完整性和运算的灵活性，这是由矢量结构自身的特点所决定的l目前并没有统一的最佳的矢量结构编码方法l在具体工作中应根据数据的特点和任务的要求而灵活设计矢量栅格数据结构的比较矢量栅格数据结构的比较l栅格结构：属性明显、位置隐含l矢量结构：位置明显、属性隐含l栅格结构和矢量结构在表示空间数据上可以是同样有效的l较为理想的方案是栅格结构与矢量结构并存优优点点缺点缺点矢量数据矢量数据1数据结构紧凑、冗余度低2有利于网络和检索分析3图形显示质量好、精度高1数据结构复杂2多边形叠加分析比较困难栅栅格数据格数据1数据结构简单2便于空间分析和地表模拟3现势性较强1数据量大2投影转
29、换比较复杂矢量栅格转换算法矢量栅格转换算法l点实体l每个实体仅由一个坐标对表示l矢量结构和栅格结构的相互转换：坐标变换l线实体l矢量转栅格l把坐标序列中坐标对变为栅格行列坐标l还需根据栅格精度要求，在坐标点之间插满一系列栅格点，这可以由两点式直线方程得到 l栅格转矢量l与栅格多边形边界转换为矢量结构相似 l多边形（面）实体l比较复杂多边形矢量转栅格多边形矢量转栅格l多边形的矢量格式向栅格格式转换又称为多边形填充l在矢量表示的多边形边界内部的所有栅格点上赋以相应的多边形编码 l内部点扩散算法l复数积分算法l射线算法和扫描算法l边界代数算法内部点扩散算法内部点扩散算法l算法l由每个多边形一个内部点
30、（种子点）开始，向其八个方向的邻点扩散l判断各个新加入点是否在多边形边界上l如果是边界上，则该新加入点不作为种子点l否则把非边界点的邻点作为新的种子点与原有种子点一起进行新的扩散运算，并将该种子点赋以该多边形的编号l重复上述过程直到所有种子点填满该多边形并遇到边界停止为止l特点l扩散算法程序设计比较复杂l在一定的栅格精度上，如果复杂图形的同一多边形的两条边界落在同一个或相邻的两个栅格内，会造成多边形不连通，这样一个种子点不能完成整个多边形的填充。复数积分算法复数积分算法l对全部栅格阵列逐个栅格单元地判断该栅格归属的多边形编码l判别方法是由待判点对每个多边形的封闭边界计算复数积分l对某个多边形，
31、如果积分值为2r，则该待判点属于此多边形，赋以多边形编号l否则在此多边形外部，不属于该多边形。射线算法和扫描算法射线算法和扫描算法l可逐点判断数据栅格点在某多边形之外或在多边形内l由待判点向图外某点引射线，判断该射线与某多边形所有边界相交的总次数l如相交偶数次，则待判点在该多边形外部l如为奇数次，则待判点在该多边形内部l采用射线算法，要注意的是l射线与多边形边界相交的一些特殊情况会影响交点的个数，必须排除l扫描算法是射线算法的改进l将射线改为沿栅格阵列列或行方向扫描线，判断与射线算法相似l扫描算法省去了计算射线与多边形边界交点的大量运算，大大提高了效率。边界代数法（边界代数法（1）l适合于记录
32、拓扑关系的多边形矢量数据转换为栅格结构l单个多边形的转换l多边形编号为a，初始化的栅格阵列各栅格值为零l以栅格行列为参考坐标轴，由多边形边界上某点开始顺时针搜索边界线l当边界上行时，位于该边界左侧所有栅格减去al当边界下行时，该边界左边所有栅格点加上al边界搜索完毕则完成了多边形的转换。边界代数法（边界代数法（2）l把不属于任何多边形的区域（包含无穷远点的区域）看成编号为0的特殊的多边形区域 l每一条边界弧段都与两个不同编号的多边形相邻，按弧段的前进方向称为左、右多边形l算法l当边界弧段上行时，该弧段与左图框之间栅格增加一个值l左多边形编号右多边形编号l当边界弧段下行时，该弧段与左图框之间栅格
33、增加一个值l右多边形编号左多边形编号多边形栅格转矢量多边形栅格转矢量l提取以相同的编号的栅格集合表示的多边形区域的边界和边界的拓扑关系，并表示由多个小直线段组成的矢量格式边界线的过程 l多边形边界提取：将栅格图像二值化或以特殊值标识边界点l边界线追踪：对每个边界弧段由一个结点向另一个结点搜索，通常对每个已知边界点需沿除了进入方向的其他7个方向搜索下一个边界点，直到连成边界弧段l拓扑关系生成：对于矢量表示的边界弧段数据，判断其与原图上各多边形的空间关系，以形成完整的拓扑结构并建立与属性数据的联系l去除多余点及曲线圆滑双边界搜索算法（双边界搜索算法（1）l算法概述l通过边界提取，将左右多边形信息保
34、存在边界点上，每条边界弧段分别记录该边界弧段的左右多边形编号l边界线搜索采用2*2栅格窗口，在每个窗口内的四个栅格数据的模式，可以唯一地确定下一个窗口的搜索方向和该弧段的拓扑关系，极大地加快了搜索速度，拓扑关系也很容易建立 双边界搜索算法（双边界搜索算法（2）l边界点和结点提取 l采用2*2栅格阵列作为窗口顺序沿行、列方向对栅格图像全图扫描l如果窗口内四个栅格有且仅有两个不同的编号，则该四个栅格标识为边界点l如果窗口内四个栅格有三个以上不同编号，则标识为结点 l边界点与结点的结构l结点的8种情况边界点的6种情况双边界搜索算法（双边界搜索算法（3）l边界线搜索与左右多边形信息记录l边界线搜索是逐
35、个弧段进行，对每个弧段由一组已标识的四个结点开始 l首先记录开始边界点的两个多边形编号，作为该弧段的左右多边形l下一点组的搜索方向由进入当前点的搜索方向和该点组的可能走向决定l每个边界点组只能有两个走向，一个是前点组进入的方向，另一个则可确定为将要搜索后续点组的方向l走向的确定l例如下图所示边界点组只可能有两个方向，即右方和下方l如果该边界点组由其下方的点组被搜索到，则其后续点组一定在其右方l反之，如果该点在其右方的点组之后被搜索到（即该弧段的左右多边形编号分别为b和a），对其后续点组的搜索应确定为下方l其他情况依此类推 双边界搜索算法（双边界搜索算法（4）l多余点去除l如果连续的三个点在一定
36、程度上在一条直线上，则去除中间点l双边界搜索算法的特点l双边界结构可以唯一地确定搜索方向，从而大大地减少搜索时间l形成的矢量结构带有左右多边形编号信息，容易建立拓扑结构和与属性数据的联系，提高转换的效率基于要素的空间关系基于要素的空间关系l空间关系l指空间实体之间存在的与空间特性有关的关系 l度量关系l方向关系l拓扑关系拓扑关系拓扑关系l拓扑属性l拓扑变换下能够保持不变的几何属性l一个弧段是一个简单弧段（弧段自身不相交）l一个点在一个区域的边界上l一个点在一个区域的内部l一个点在一个区域的外部l一个点在一个环的内部l一个面是一个简单面（面上没有“洞”）l拓扑关系l描述了两个对象之间的拓扑属性的
37、关系拓扑关系的表达拓扑关系的表达l地理要素之间的空间区位关系可抽象为点、线（或弧）、多边形（区域）之间的空间几何关系l9I模型与RCC模型点集拓扑点集拓扑l内部、外部、边界AoABoBA-B-UAoA-A9交模型交模型lEgenhofer等人构造了一个由简单几何实体的边界、内部和外部的点集组成的33的矩阵来描述空间拓扑关系，称为9交空间关系模型(9I Model)。该矩阵中的每一元素，都有“空”与“非空”两种取值。l9I矩阵l在这个3*3矩阵中，每个元素根据其交集的空或非空(可以用1和0表示)加以确定l不同的空间关系形成不同矩阵，从而分辨出各种空间关系（理论上讲，可以有29=512种关系）9I
38、矩阵示例（矩阵示例（1）l简单面简单面9I矩矩阵阵示示例例（2）l简单线简单线9I矩矩阵阵示示例例（3）l复杂线复杂线9I矩阵示例（矩阵示例（4）l线面9I模型的有缺点模型的有缺点l优点l简单模型l容易理解，容易实现OGC的实现l缺点l不能区分概念上不同的情况l9I的扩展ABABAB上述三个关系用9-I模型表达都是111111111基本的拓扑关系基本的拓扑关系l空间关系谓词ldisjointltoucheslcrosseslwithinloverlaps方向关系方向关系l空间方向关系又称为方位关系、延伸关系，它定义了空间对象之间的方位l主要描述为北、东、南、西4个主方向，以及进一步细分东北、东
39、南、西南和西北方向等等。l定量表达方式l东北35度l定性表达方式l东东北、东l三种参照方式l内部参照l直接参照l外部参照内部参照左直接参照左外部参照东主方向关系主方向关系l几种定义模型l锥形法l投影法lMBR法锥形法锥形法投影法投影法MBR法法度量关系度量关系l度量属性包括：l一元度量属性l面积、周长l二元度量属性l距离l距离可以表现为以下几种形式l大地测量距离l沿着地球大圆经过两个城市中心的距离l曼哈顿距离l街区l纬度差加上经度差l旅行时间距离l从一个城市到另一个城市的最短的时间可以用一系列指定的航线来表示（假设每个城市至少有一个飞机场）l词典编纂距离l在一个固定的地名册中一系列城市中它们位置之间的绝对差值