图形拓扑关系的构建

拓扑关系介绍1.1拓扑的来源1.2为什么要研究地图上的拓扑关系1.3建立拓扑关系的基本概念1.4基本的拓扑关系1.5拓扑关系的表示1.6Arc/Info中拓扑关系的构建1.1拓扑的来源1.拓扑的来源“拓扑（Topology）”一次来自希腊文，它的原意是“形状的研究”。拓扑学时几何学的一个分支，它研究在拓扑变换下能够保持不变的几何属性——拓扑属性。例子：设想一块高质量的橡皮，它的表面是欧几里的平面，这块橡皮可以任意被拉伸、压缩，但是不能够被扭转或折叠。在橡皮的表面上有由结点、弧、环、面组成的可能任意图形。我们对橡皮进行拉伸、压缩，在橡皮进行这些变换的过程中，图形的一些属性消失，一些属性将继续保持存在。设想象皮表面有一个多边形，里面有一个点。当拉伸、压缩橡皮时，点依旧在多边形中，点和多边形的位置关系不会发生变化，但是多边形的面积会发生变化。所以：“点的内置”是拓扑属性，而面积不是拓扑属性，拉伸和压缩就是拓扑变换。1.2为什么要研究地图上的拓扑？1.拓扑概念：拓扑学是研究图形在保持连续状态下变形时的那些不变的性质，也成为“橡皮板几何学”。在地图上仅用距离和方向参数描述地图上的目标之间的关系总是不圆满的。因为图上两点之间的距离和方向会随着地图投影的不同而发生变化，故仅用距离和方向参数还不能够确切地表示它们之间的空间关系。（如下图）2.描述目标间关系需要Longitude/Latitude投影Gauss-Krivger投影从上图可以看出，用拓扑关系表示，不论怎么变化，其邻接、关联、包含等关系都不改变。拓扑关系能够从质的方面和整体的概念上反映空间实体的空间结构关系。研究拓扑关系对于地图数据处理和正确显示将是十分重要的。1.3拓扑关系的基本概念地图要素可以抽象为点、线、面来表示，这种归纳正好适合于建立拓扑关系和建立拓扑表示。1.若地图平面上反映一定意义的零维图形的附近没有其它图形与之联系，则称这个零维图形为独立点（Point）。如水井3.地图平面上连接两结点的有一定意义的一维图形称为边（Edge），也叫弧段（Arc）。例如：连个城市之间的道路4.由一些边围成的有一定意义的闭合区域称为面（Area）。2.若在某个有一定意义的零维图形附近还存在另外有意义的零维图形与之联系，则称这个零维图形为结点（Node）。1.4基本的拓扑关系拓扑邻接和拓扑关联是用来描述网结构元素（比如结点、弧段、面域）之间的两类二元关系。基本拓扑关系分为拓扑邻接关系、拓扑关联关系和拓扑包含关系。拓扑邻接关系存在于同类型元素之间（注意是“偶对集合”）。一般用来描述面域邻接。拓扑关联关系存在于不同类型元素之间。一般用来描述结点与边、边与面的关系。拓扑包含关系用来说明面域包含于其中的点、弧段、面域的对应关系。包含关系有同类的，也有不同类的。1.5拓扑关系的表示拓扑关系的表示分为：显示表示和隐式表示。1.显示表示：就是将网结构元素（结点、弧段、面域）间的拓扑关系数据化，并作为地图数据的一部分给以存储，这就叫拓扑关系的显式表示。2.隐式表示：不直接存储拓扑关系，而是由几何数据临时推导生成所需的拓扑关系，这就叫拓扑关系的隐式表示。计算导出耗时的那部分拓扑关系用显式表示；其余的用隐式表示。例子：显示表示，美国人口统计局的双重独立地图编码。e11e10e9e8e7e6e5e4e3e2e1线段号始结点终结点左多边形右多边形e131NULLAe243NULLBe332ABe412NULLAe542BCe625NULLCe756ECe864DCe976DEe1074NULLDe1157NULLE结点号X坐标Y坐标1X1Y12X2Y23X3Y34X4Y45X5Y56X6Y67X7Y71.地图网络编码3.拓扑结构文件2.结点坐标文件双重独立地图编码（DIME）弧段起点终点e121e214e313e423e543e636e7e8e9e10e11e12弧段e1e2e3e4…坐标序列………(5，5)、(9，5)…1.Arc/Info中的“弧段与结点之间的拓扑结构”多边形弧段B4－6－7－10－8C3－10－9D7－5－2－9E1－5－6F8（一条弧线组成）Polygon－arc表弧线坐标序列e15,35,58,5……e67,46,3………Arc坐标表2.Arc/Info多边形与弧线拓扑结构弧线左多边形右多边形e1AEe2ADe3ACe4ABe5EDe6BEe7BDe8BFe9DCe10CB弧线坐标序列e15,35,58,5……e67,46,3………Arc坐标表左右多边形表3.Arc/Info中左右多边形拓扑结构（存储在Arc文件中）1.6Arc／Info拓扑结构小结Arc/Info利用拓扑结构在两个简单的坐标要素——弧线和结点的基础上表示附加的地理信息。也就是说：地理数据作为X，Y坐标对序列来存储，分别代表点、线、多边形。这些地理特征之间的关系通过拓扑结构来表达。相关的表格数据存储在表格中，通过内部标识号连接到地理特征上。拓扑结构数据模型可以更有效地存储数据，它提供了进行高级地理分析框架。例如：拓扑结构模型由组成多边形边界的弧的列表来构建多边形。当两个多边形共享一条公共边时，系统只存储公共弧坐标值一次。一个非拓扑结构数据模型把每个封闭的多边形作为一个独立的实体存储，邻接多边形公用的一条弧必须输入并存储两次，这通常通过数字化两次或者弧的拷贝来完成。这种重复数据是地理分析更为困难，因为系统不能够观察出这两个多边形的拓扑关系。非拓扑结构模型是许多CAD、绘图和制图系统支持的常见模型。1.7拓扑关系是空间数据处理拓扑关系的建立属于空间数据处理的内容。空间数据获取有各种不同的方法，但无论哪种方法获取的数据都可能存在这样或者那样的问题和误差，如数字化错误、数据格式不一致、比例尺或投影不统一、数据冗余等。因此：只有通过空间数据的处理才能使空间数据符合GIS数据库的要求，才能实现GIS的各种功能。空间数据处理的主要内容包括：图形编辑、自动拓扑、坐标变换、数据压缩、结构转换、数据内插等。建立多边形拓扑2.1弧段的组织2.2结点的匹配2.3检查多边形是否闭合2.4建立多边形2.1弧段的组织边（弧段）的组织：把弧段按一定顺序存储，如X坐标或者Y坐标的顺序，便于检索和查找，然后按顺序编号。弧段的中间相交：要求中间断开弧段的端点相交：要求结点匹配2.2结点匹配结点匹配结点匹配是指把一定限产诶的弧段的端点作为一个节点，其坐标值取多个端点的平均值，如图，然后，对结点顺序编号。2.3检查多边形是否闭合P检查多边形闭合可以通过判断一条弧的端点是否有与之匹配的端点来进行。图中弧段a的端点P没有与之匹配的端点，因此无法使用这条弧与其它弧组成闭合多边形。可能的原因是：结点匹配限差的问题造成端点未匹配；数字化误差较大，甚至数字化错误，这些都可以通过图形编辑或重新匹配来确定。另外如果该弧段本来就是悬挂弧线，不需要拓扑，做一个标记即可。2.4构建拓扑多边形2.4.1基本常识2.4.2多边形拓扑关系自动建立的两个算法2.4.2.1弧段跟踪法2.4.2.2栅格填充法2.4.1基本常识（1）1.顺时针方向构建多边形所谓顺时针方向构建多边形是指多边形在弧段的右侧。这需要定义弧线的方向。AB左边右边左边右边AB2.4.1基本常识（2）2.最靠右边的弧段acdb最靠右边的弧段是指从弧段的一个端点出发，在这个弧段的方向上最靠右边的一条弧段。如图：弧段a最靠右边的弧段是d.找最靠右边的弧段可以通过计算弧段的方向和夹角来实现。2.4.1基本常识（3）3.多边形面积的计算设构成多边形的坐标串为（Xi，Yi）（i=1，2，3，…n)，则多边形的面积可以用如下公式求出：niiiiiAxxyyS11121niiiiiAxxyyS11121niiiiiAxxyyS11121其中，当i=n时，yn+1＝y1，xn+1=x1；当i=1时,y0＝yn。根据该公式，当多边形右顺时针方向构成时，面积为正；否则为负。正负2.4.2.1弧段跟踪法此法是基于弧段的邻接关系，按照一定规则沿弧段跟踪形成各个闭合环，然后采用内点匹配法得到各个环与内点的包含关系，最后根据多边形结构特点，确定环与内点的圈定关系，即是建立多边形面域与弧段的关联关系。具体分为如下几步：1.弧段邻接关系的建立2.环的生成3.建立环与内点的包含关系4.建立环与内点的圈定关系弧段邻接关系的建立如果两条弧段具有相同的端点，则定义这两条弧段具有邻接关系。记录规则：邻接于弧段同一端点的各个邻接弧段按顺时针方向顺序记录；按照数字化方向，如果邻接弧段是首点邻接，则在其前面冠以正号，否则冠以负号。1首＋5，－2末－4，＋62首－7，－3末＋1，＋53首＋8，＋4末＋2，－74首＋3，＋8末＋6，－1弧段邻接关系表环的生成弧段2前端后端弧段3弧段1最靠左边的弧段弧段1前端后端弧段2弧段4最靠左边的弧段弧段4前端后端弧段1弧段3最靠左边的弧段弧段3前端后端弧段4弧段2最靠左边的弧段从弧段2开始跟踪，则圈定多边形A的环记录为：(+2，＋1，－4，＋3）建立环与内点的包含关系123456ⅠⅩⅨⅧⅦⅥⅤⅣⅢⅡ环号内点数目内点Ⅰ61，2，3，4，5，6Ⅱ32，4，5Ⅲ23，6Ⅳ23，6Ⅴ16Ⅵ12Ⅶ24，5Ⅷ15Ⅸ15Ⅹ16按环记录中的关键字，可将该环上各弧段坐标数据读出，对所有内点匹配，便能确定环与各内点的包含关系。环号与内点的圈定关系1123456ⅠⅩⅨⅧⅦⅥⅤⅣⅢⅡ从图中可以看出：一个多边形可能有一个或多个环，但是一个多边形只有一个内点（数字化的时候输入）。所以，环与内点的拓扑关系可能是一对一或多对一的关系。按照右图建立的环与内点的包含关系是纯几何上，也就是多对多的几何包含关系。拓扑结构需要确定一对一的点环关系，就是一个内点就要代表一个多边形。所以需要找出环是属于某一内点所代表的多边形的。即是建立多边形与轮廓的关联关系。环号与内点的圈定关系2ⅠⅡⅢⅩⅤⅨⅦⅣⅧⅥ654132点与环的对应关系就确定了。将包含关系表示成一颗形式化的树。从底层向上在关系树中不断搜索环与内点的圈定关系（一对一或多对一的关系），并从关系树中“剪去”的过程。