图形拓扑关系的构建PPT学习教案

1、会计学1图形拓扑关系的构建图形拓扑关系的构建Longitude/Latitude投影Gauss-Krivger投影 从上图可以看出，用拓扑关系表示，不论怎么变化，其邻接、关联、包含等关系都不改变。拓扑关系能够从质的方面和整体的概念上反映空间实体的空间结构关系。 研究拓扑关系对于地图数据处理和正确显示将是十分重要的。第2页/共26页 地图要素可以抽象为点、线、面来表示，这种归纳正好适合于建立拓扑关系和建立拓扑表示。1.若地图平面上反映一定意义的零维图形的附近没有其它图形与之联系，则称这个零维图形为独立点（Point）。如水井3.地图平面上连接两结点的有一定意义的一维图形称为边（Edge） ，也叫

2、弧段（Arc）。例如：连个城市之间的道路4.由一些边围成的有一定意义的闭合区域称为面（Area）。2.若在某个有一定意义的零维图形附近还存在另外有意义的零维图形与之联系，则称这个零维图形为结点（Node）。第3页/共26页 拓扑邻接和拓扑关联是用来描述网结构元素（比如结点、弧段、面域）之间的两类二元关系。 基本拓扑关系分为拓扑邻接关系、拓扑关联关系和拓扑包含关系。 拓扑邻接关系存在于同类型元素之间（注意是“偶对集合”）。一般用来描述面域邻接。 拓扑关联关系存在于不同类型元素之间。一般用来描述结点与边、边与面的关系。 拓扑包含关系用来说明面域包含于其中的点、弧段、面域的对应关系。包含关系有同类的

3、，也有不同类的。第4页/共26页拓扑关系的表示分为：显示表示和隐式表示。1.显示表示：就是将网结构元素（结点、弧段、面域）间的拓扑关系数据化，并作为地图数据的一部分给以存储，这就叫拓扑关系的显式表示。2.隐式表示：不直接存储拓扑关系，而是由几何数据临时推导生成所需的拓扑关系，这就叫拓扑关系的隐式表示。 计算导出耗时的那部分拓扑关系用显式表示；其余的用隐式表示。例子：显示表示，美国人口统计局的双重独立地图编码。第5页/共26页e11e10e9e8e7e6e5e4e3e2e1线段号始结点终结点左多边形右多边形e131NULLAe243NULLBe332ABe412NULLAe542BCe625NU

4、LLCe756ECe864DCe976DEe1074NULLDe1157NULLE结点号X坐标Y坐标1X1Y12X2Y23X3Y34X4Y45X5Y56X6Y67X7Y71.地图网络编码3.拓扑结构文件2.结点坐标文件双重独立地图编码（DIME）第6页/共26页弧段起点终点e121e214e313e423e543e636e7e8e9e10e11e12弧 段e1e2e3e4坐标序列(5，5)、(9，5)1.Arc/Info中的“弧段与结点之间的拓扑结构”第7页/共26页多边形弧 段B467108C3109D7529E156F8（一条弧线组成）Polygonarc表弧线坐标序列e15,3 5,5

5、8,5e67,4 6,3 Arc坐标表2.Arc/Info多边形与弧线拓扑结构第8页/共26页弧 线左多边形右多边形e1AEe2ADe3ACe4ABe5EDe6BEe7BDe8BFe9DCe10CB弧线坐标序列e15,3 5,5 8,5e67,4 6,3 Arc坐标表左右多边形表3.Arc/Info中左右多边形拓扑结构（存储在Arc文件中）第9页/共26页 Arc/Info利用拓扑结构在两个简单的坐标要素弧线和结点的基础上表示附加的地理信息。也就是说：地理数据作为X，Y坐标对序列来存储，分别代表点、线、多边形。这些地理特征之间的关系通过拓扑结构来表达。相关的表格数据存储在表格中，通过内部标识号

6、连接到地理特征上。 拓扑结构数据模型可以更有效地存储数据，它提供了进行高级地理分析框架。例如：拓扑结构模型由组成多边形边界的弧的列表来构建多边形。当两个多边形共享一条公共边时，系统只存储公共弧坐标值一次。 一个非拓扑结构数据模型把每个封闭的多边形作为一个独立的实体存储，邻接多边形公用的一条弧必须输入并存储两次，这通常通过数字化两次或者弧的拷贝来完成。这种重复数据是地理分析更为困难，因为系统不能够观察出这两个多边形的拓扑关系。非拓扑结构模型是许多CAD、绘图和制图系统支持的常见模型。第10页/共26页拓扑关系的建立属于空间数据处理的内容。 空间数据获取有各种不同的方法，但无论哪种方法获取的数据都

7、可能存在这样或者那样的问题和误差，如数字化错误、数据格式不一致、比例尺或投影不统一、数据冗余等。 因此：只有通过空间数据的处理才能使空间数据符合GIS数据库的要求，才能实现GIS的各种功能。 空间数据处理的主要内容包括：图形编辑、自动拓扑、坐标变换、数据压缩、结构转换、数据内插等。第11页/共26页2.1 弧段的组织2.2 结点的匹配2.3 检查多边形是否闭合2.4 建立多边形第12页/共26页 边（弧段）的组织：把弧段按一定顺序存储，如X坐标或者Y坐标的顺序，便于检索和查找，然后按顺序编号。弧段的中间相交：要求中间断开弧段的端点相交：要求结点匹配第13页/共26页结点匹配 结点匹配是指把一定

8、限产诶的弧段的端点作为一个节点，其坐标值取多个端点的平均值，如图，然后，对结点顺序编号。第14页/共26页P 检查多边形闭合可以通过判断一条弧的端点是否有与之匹配的端点来进行。 图中弧段a的端点P没有与之匹配的端点，因此无法使用这条弧与其它弧组成闭合多边形。 可能的原因是：结点匹配限差的问题造成端点未匹配；数字化误差较大，甚至数字化错误，这些都可以通过图形编辑或重新匹配来确定。另外如果该弧段本来就是悬挂弧线，不需要拓扑，做一个标记即可。第15页/共26页基本常识多边形拓扑关系自动建立的两个算法 弧段跟踪法 栅格填充法第16页/共26页1.顺时针方向构建多边形 所谓顺时针方向构建多边形是指多边形

9、在弧段的右侧。这需要定义弧线的方向。AB左边右边左边右边AB第17页/共26页2.最靠右边的弧段acdb 最靠右边的弧段是指从弧段的一个端点出发，在这个弧段的方向上最靠右边的一条弧段。如图：弧段a最靠右边的弧段是d. 找最靠右边的弧段可以通过计算弧段的方向和夹角来实现。第18页/共26页3.多边形面积的计算 设构成多边形的坐标串为（Xi，Yi）（i=1，2，3，n)，则多边形的面积可以用如下公式求出：niiiiiAxxyyS11121niiiiiAxxyyS11121niiiiiAxxyyS11121 其中，当i=n时，yn+1y1，xn+1=x1；当i=1时,y0yn。根据该公式，当多边形右

10、顺时针方向构成时，面积为正；否则为负。正负第19页/共26页 此法是基于弧段的邻接关系，按照一定规则沿弧段跟踪形成各个闭合环，然后采用内点匹配法得到各个环与内点的包含关系，最后根据多边形结构特点，确定环与内点的圈定关系，即是建立多边形面域与弧段的关联关系。具体分为如下几步：1.弧段邻接关系的建立2.环的生成3.建立环与内点的包含关系4.建立环与内点的圈定关系第20页/共26页 如果两条弧段具有相同的端点，则定义这两条弧段具有邻接关系。 记录规则：邻接于弧段同一端点的各个邻接弧段按顺时针方向顺序记录；按照数字化方向，如果邻接弧段是首点邻接，则在其前面冠以正号，否则冠以负号。1首5，2末4，62首

11、7，3末1，53首8，4末2，74首3，8末6，1弧段邻接关系表第21页/共26页弧段2前端后端弧段3弧段1最靠左边的弧段弧段1前端后端弧段2弧段4最靠左边的弧段弧段4前端后端弧段1弧段3最靠左边的弧段弧段3前端后端弧段4弧段2最靠左边的弧段从弧段2开始跟踪，则圈定多边形A的环记录为：(+2，1，4，3）第22页/共26页123456环 号内点数目 内 点61，2，3，4，5，632，4，523，623，6161224，5151516按环记录中的关键字，可将该环上各弧段坐标数据读出，对所有内点匹配，便能确定环与各内点的包含关系。第23页/共26页123456 从图中可以看出：一个多边形可能有一个或多个环，但是一个多边形只有一个内点（数字化的时候输入）。所以，环与内点的拓扑关系可能是一对一或多对一的关系。 按照右图建立的环与内点的包含关系是纯几何上，也就是多对多的几何包含关系。 拓扑结构需要确定一对一的点环关