图形拓扑关系的构建.ppt

拓扑关系介绍,1.1拓扑的来源1.2为什么要研究地图上的拓扑关系1.3建立拓扑关系的基本概念1.4基本的拓扑关系1.5拓扑关系的表示1.6Arc/Info中拓扑关系的构建,1.1拓扑的来源,1.拓扑的来源,“拓扑（Topology）”一次来自希腊文，它的原意是“形状的研究”。拓扑学时几何学的一个分支，它研究在拓扑变换下能够保持不变的几何属性拓扑属性。,例子：设想一块高质量的橡皮，它的表面是欧几里的平面，这块橡皮可以任意被拉伸、压缩，但是不能够被扭转或折叠。在橡皮的表面上有由结点、弧、环、面组成的可能任意图形。我们对橡皮进行拉伸、压缩，在橡皮进行这些变换的过程中，图形的一些属性消失，一些属性将继续保持存在。设想象皮表面有一个多边形，里面有一个点。当拉伸、压缩橡皮时，点依旧在多边形中，点和多边形的位置关系不会发生变化，但是多边形的面积会发生变化。所以：“点的内置”是拓扑属性，而面积不是拓扑属性，拉伸和压缩就是拓扑变换。,1.2为什么要研究地图上的拓扑？,1.拓扑概念：拓扑学是研究图形在保持连续状态下变形时的那些不变的性质，也成为“橡皮板几何学”。,在地图上仅用距离和方向参数描述地图上的目标之间的关系总是不圆满的。,因为图上两点之间的距离和方向会随着地图投影的不同而发生变化，故仅用距离和方向参数还不能够确切地表示它们之间的空间关系。（如下图）,2.描述目标间关系需要,从上图可以看出，用拓扑关系表示，不论怎么变化，其邻接、关联、包含等关系都不改变。拓扑关系能够从质的方面和整体的概念上反映空间实体的空间结构关系。研究拓扑关系对于地图数据处理和正确显示将是十分重要的。,1.3拓扑关系的基本概念,地图要素可以抽象为点、线、面来表示，这种归纳正好适合于建立拓扑关系和建立拓扑表示。,1.若地图平面上反映一定意义的零维图形的附近没有其它图形与之联系，则称这个零维图形为独立点（Point）。如水井,3.地图平面上连接两结点的有一定意义的一维图形称为边（Edge），也叫弧段（Arc）。例如：连个城市之间的道路,4.由一些边围成的有一定意义的闭合区域称为面（Area）。,2.若在某个有一定意义的零维图形附近还存在另外有意义的零维图形与之联系，则称这个零维图形为结点（Node）。,1.4基本的拓扑关系,拓扑邻接和拓扑关联是用来描述网结构元素（比如结点、弧段、面域）之间的两类二元关系。,基本拓扑关系分为拓扑邻接关系、拓扑关联关系和拓扑包含关系。,拓扑邻接关系存在于同类型元素之间（注意是“偶对集合”）。一般用来描述面域邻接。,拓扑关联关系存在于不同类型元素之间。一般用来描述结点与边、边与面的关系。,拓扑包含关系用来说明面域包含于其中的点、弧段、面域的对应关系。包含关系有同类的，也有不同类的。,1.5拓扑关系的表示,拓扑关系的表示分为：显示表示和隐式表示。,1.显示表示：就是将网结构元素（结点、弧段、面域）间的拓扑关系数据化，并作为地图数据的一部分给以存储，这就叫拓扑关系的显式表示。,2.隐式表示：不直接存储拓扑关系，而是由几何数据临时推导生成所需的拓扑关系，这就叫拓扑关系的隐式表示。,计算导出耗时的那部分拓扑关系用显式表示；其余的用隐式表示。,例子：显示表示，美国人口统计局的双重独立地图编码。,1.地图网络编码,3.拓扑结构文件,2.结点坐标文件,双重独立地图编码（DIME）,1,2,3,4,5,6,7,8,e1,e2,e3,e4,e5,e6,e7,e8,e9,e10,e11,e12,1.Arc/Info中的“弧段与结点之间的拓扑结构”,e1,e8,e6,e7,e5,e10,e9,e2,e4,e3,F,C,B,A,D,E,Polygonarc表,Arc坐标表,2.Arc/Info多边形与弧线拓扑结构,e1,e8,e6,e7,e5,e10,e9,e2,e4,e3,F,C,B,A,D,E,Arc坐标表,左右多边形表,3.Arc/Info中左右多边形拓扑结构（存储在Arc文件中）,1.6ArcInfo拓扑结构小结,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检查多边形是否闭合,a,P,检查多边形闭合可以通过判断一条弧的端点是否有与之匹配的端点来进行。,图中弧段a的端点P没有与之匹配的端点，因此无法使用这条弧与其它弧组成闭合多边形。,可能的原因是：结点匹配限差的问题造成端点未匹配；数字化误差较大，甚至数字化错误，这些都可以通过图形编辑或重新匹配来确定。另外如果该弧段本来就是悬挂弧线，不需要拓扑，做一个标记即可。,2.4构建拓扑多边形,2.4.1基本常识2.4.2多边形拓扑关系自动建立的两个算法2.4.2.1弧段跟踪法2.4.2.2栅格填充法,2.4.1基本常识（1）,1.顺时针方向构建多边形,所谓顺时针方向构建多边形是指多边形在弧段的右侧。这需要定义弧线的方向。,2.4.1基本常识（2）,2.最靠右边的弧段,最靠右边的弧段是指从弧段的一个端点出发，在这个弧段的方向上最靠右边的一条弧段。,如图：弧段a最靠右边的弧段是d.,找最靠右边的弧段可以通过计算弧段的方向和夹角来实现。,2.4.1基本常识（3）,3.多边形面积的计算,设构成多边形的坐标串为（Xi，Yi）（i=1，2，3，n)，则多边形的面积可以用如下公式求出：,其中，当i=n时，yn+1y1，xn+1=x1；当i=1时,y0yn。根据该公式，当多边形右顺时针方向构成时，面积为正；否则为负。,2.4.2.1弧段跟踪法,此法是基于弧段的邻接关系，按照一定规则沿弧段跟踪形成各个闭合环，然后采用内点匹配法得到各个环与内点的包含关系，最后根据多边形结构特点，确定环与内点的圈定关系，即是建立多边形面域与弧段的关联关系。,具体分为如下几步：1.弧段邻接关系的建立2.环的生成3.建立环与内点的包含关系4.建立环与内点的圈定关系,弧段邻接关系的建立,如果两条弧段具有相同的端点，则定义这两条弧段具有邻接关系。,8,7,6,5,4,3,2,1,A,记录规则：邻接于弧段同一端点的各个邻接弧段按顺时针方向顺序记录；按照数字化方向，如果邻接弧段是首点邻接，则在其前面冠以正号，否则冠以负号。,弧段邻接关系表,环的生成,8,7,6,5,4,3,2,1,A,+,+,+,-,从弧段2开始跟踪，则圈定多边形A的环记录为：(+2，1，4，3）,建立环与内点的包含关系,1,2,3,4,5,6,按环记录中的关键字，可将该环上各弧段坐标数据读出，对所有内点匹配，便能确定环与各内点的包含关系。,环号与内点的圈定关系1,1,2,3,4,5,6,从图中可以看出：一个多边形可能有一个或多个环，但是一个多边形只有一个内点（数字化的时候输入）。所以，环与内点的拓扑关系可能是一对一或多对一的关系。,按照右图建立的环与内点的包含关系是纯几何上，也就是多对多的几何包含关系。,拓扑结构需要确定一对一的点环关系，就是一个内点就要代表一个多边形。所以需要找出环是属于某一内点所代表的多边形的。即是建立多边形与轮廓的关联关系。,环号与内点的圈定关系2,6,5,4,1,3,2,点与环的对应关系就确定了。,将包含关系表示成一颗形式化的树。从底层向上在关系树中不断搜索环与内点的圈定关系（一对一或多对一的关系），并从关系树中“剪去”的过程。,