图形拓扑关系的构建.ppt

拓扑关系介绍 1.1 拓扑的来源 1.2 为什么要研究地图上的拓扑关系 1.3 建立拓扑关系的基本概念 1.4 基本的拓扑关系 1.5 拓扑关系的表示 1.6 Arc/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.隐式表示：不直接存储拓扑关系，而是由几何数据临时推 导生成所需的拓扑关系，这就叫拓扑关系的隐式表示。 计算导出耗时的那部分拓扑关系用显式表示；其余的用 隐式表示。 例子：显示表示，美国人口统计局的双重独立地图编码。 e11 e10 e9 e8 e7 e6 e5 e4 e3 e2 e1 线段号始结点终结 点左多边形右多边形 e131NULLA e243NULLB e332AB e412NULLA e542BC e625NULLC e756EC e864DC e976DE e1074NULLD e1157NULLE 结点号X坐标Y坐标 1X1Y1 2X2Y2 3X3Y3 4X4Y4 5X5Y5 6X6Y6 7X7Y7 1.地图网络编码 3.拓扑结构文件 2.结点坐标文件 双重独立地图编码（DIME） 弧段起点终 点 e121 e214 e313 e423 e543 e636 e7 e8 e9 e10 e11 e12 弧 段e1e2e3e4 坐标序列(5，5)、(9，5) 1.Arc/Info中的“弧段与结点之间的拓扑结构” 多边形弧 段 B467108 C3109 D7529 E156 F 8（一条弧线组 成 ） Polygonarc表 弧线坐标序列 e15,3 5,5 8,5 e67,4 6,3 Arc坐标表 2.Arc/Info多边形与弧线拓扑结构 弧 线左多边形右多边形 e1AE e2AD e3AC e4AB e5ED e6BE e7BD e8BF e9DC e10CB 弧线坐标序列 e15,3 5,5 8,5 e67,4 6,3 Arc坐标表 左右多边形表 3.Arc/Info中左右多边形拓扑结构（存储在Arc文件中） 1.6 ArcInfo拓扑结构小结 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.顺时针方向构建多边形 所谓顺时针方向构建多边形是指多边形在弧段的右侧。这 需要定义弧线的方向。 A B 左边 右边 左边 右边 A B 2.4.1 基本常识（2） 2.最靠右边的弧段 a c d b 最靠右边的弧段是指从弧段的 一个端点出发，在这个弧段的方向 上最靠右边的一条弧段。 如图：弧段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.建立环与内点的圈定关系 弧段邻接关系的建立 如果两条弧段具有相同的端点， 则定义这两条弧段具有邻接关系。 记录规则：邻接于弧段同一端点的各个邻接弧段按 顺时针方向顺序记录；按照数字化方向，如果邻接弧段 是首点邻接，则在其前面冠以正号，否则冠以负号。 1首5，2 末4，6 2首7，3 末1，5 3首8，4 末2，7 4首3，8 末6，1 弧段邻接关系表 环的生成 弧段2 前端 后端 弧段3 弧段1 最靠左边的弧段 弧段1 前端 后端 弧段2 弧段4 最靠左边的弧段 弧段4 前端 后端 弧段1 弧段3 最靠左边的弧段 弧段3 前端 后端 弧段4 弧段2 最靠左边的弧段 从弧段2开始跟踪，则圈定多边形A的 环记录为：(+2，1，4，3） 建立环与内点的包含关系 1 23 4 5 6 环 号内点数目 内 点 61，2，3，4，5，6 32，4，5 23，6 23，6 16 12 24，5 15 15 16 按环记录中的关键字，可将该环上各弧段坐标数据读出，对 所有内点匹配，便能确定环与各内点的包含关系。 环号与内点的圈定关系1 1 23 4 5 6 从图中可以看出：一个多边 形可能有一个或多个环，但是一 个多边形只有一个内点（数字化 的时候输入）。所以，环与内点 的拓扑关系可能是一对一或多对 一的关系。