The expression and applications of topology on spatial data 北京建筑工程学院 §3.2空间数据拓扑结构 的表达及应用 The expression and applications of topology on spatial data 王文宇 测绘与城市空间信息学院

本次课主要内容 ★ 一 问题提出 二 拓扑花絮 三 拓扑表达 ★ 四 拓扑求解 ★ ★ The Proposals of Our Questions 二 拓扑花絮 The Stories of Topology 三 拓扑表达 The Expression of Topology in GIS 四 拓扑求解 How Topology Works ★ ★ ★

一 问题的提出 The Proposals of Our Questions 一个常规的地理信息系统可以回答用户提出的很多空间问题: 位置(location):在哪？ 距离（distance）：多远？ 邻接关系(adjacency): 周围是什么？ 包含关系(containment):位于里面还是外面？ 关联关系 (connectivity)：怎么走？ Intelligent Vector Data – Topology The mathematical terms for these answers is: Topology represents the structuring of coordinate data which clearly describes adjacency, containment, and connectivity.

一 问题的提出 The Proposals of Our Questions 与北京市相邻接的行政区有哪些？ 邻接关系(adjacency)

一 问题的提出 The Proposals of Our Questions 国道105线(G105线)经过哪些省份？ 包含关系(containment)

一 问题的提出 The Proposals of Our Questions 从连云港的新浦站到北京的最佳路径怎么走？ 关联关系 connectivity

本次课主要内容 ★ 一 问题提出 二 拓扑花絮 三 拓扑表达 ★ 四 拓扑求解 ★ ★ The Proposals of Our Questions 二 拓扑花絮 The Stories of Topology 三 拓扑表达 The Expression of Topology in GIS 四 拓扑求解 How Topology Works ★ ★ ★

二 拓扑花絮 The Stories of Topology B C A D 拓扑等价 哥尼斯堡七桥问题 欧拉与一笔画 一笔画与拓扑学 拓扑学起源于公元1736年一个著名问题——哥尼斯堡七桥问题——的解决。哥尼斯堡是位于普累格河上的一座城市，它包含两个岛屿及连接它们的七座桥。该河流经城区的这两个岛．岛与河岸之间架有六座桥，另一座桥则连接着两个岛，如图所示。城中的居民经常沿河过桥散步，于是提出了一个问题：能否一次走遍7座桥，而每座桥只许通过一次，最后仍回到起始地点。这就是七桥问题，一个著名的图论问题。 18世纪时，欧洲有一个风景秀丽的小城哥尼斯堡，那里有七座桥。如图1所示：河中的小岛A与河的左岸B、右岸C各有两座桥相连结，河中两支流间的陆地D与A、B、C各有一座桥相连结。当时哥尼斯堡的居民中流传着一道难题：一个人怎样才能一次走遍七座桥，每座桥只走过一次，最后回到出发点？大家都试图找出问题的答案，但是谁也解决不了这个问题……… 这个问题看起来似乎不难，但人们始终没有能找到答案，最后问题提到了瑞士数学家欧拉(Leonhard Euler，1707—1783)那里。欧拉以深邃的洞察力很快证明了这样的走法不存在。欧拉是这样解决问题的：既然陆地是桥梁的连接地点，不妨把图中被河隔开的陆地看成A、B、C、D 4个点，7座桥表示成7条连接这4个点的线。于是“七桥问题”就等价于图1-3-7 b)中所画图形的一笔画问题了。欧拉注意到，每个点如果有进去的边就必须有出来的边，从而每个点连接的边数必须有偶数个才能完成一笔画。图1-3-7 b)的每个点都连接着奇数条边，因此不可能一笔画出，这就说明不存在一次走遍7座桥，而每座桥只许通过一次的走法。 欧拉由分析一笔画起步，而创始了拓扑学，现在拓扑学已成为一门出色的学科。欧拉对“七桥问题”的研究是图论研究的开始，同时也为拓扑学的研究提供了一个初等的例子。 欧拉解决七桥问题给我们了某种启示：那就是有些空间问题的求解， 不需要利用坐标或距离，可以确定空间实体的位置关系 通常叫做橡皮板几何学, 又叫质量几何学 含有拓扑关系的空间数据有利于GIS的拓扑查询和空间分析。 更确切的定义不适合在这里写出来，大家只要知道：有拓扑结构后，“连续”这个概念就可以定义了。直线、平面、三维欧氏空间、各种曲线、曲面、多面体......都可以作为拓扑空间的例子。 因为这些关系的空间逻辑意义重于其几何意义, 所以把它们称为拓扑关系 拓扑学（Topology）是研究图形在连续变形情况下, 图形所具有的不变性。 七桥问题给了我们什么启迪呢？ 在连续形变下，点、线、面的什么关系不变呢？

本次课主要内容 ★ 一 问题提出 二 拓扑花絮 三 拓扑表达 ★ 四 拓扑求解 ★ ★ The Proposals of Our Questions 二 拓扑花絮 The Stories of Topology 三 拓扑表达 The Expression of Topology in GIS 四 拓扑求解 How Topology Works ★ ★ ★

三 拓扑结构的表达 The expression of topology （一）基本拓扑元素 Vertex To-Node ①节点(Node) ②弧段(Arc) ③多边形（Polygon) From-Node 1 b 为弧段上的起点和终点; 顶点（Vertex）为弧段上的中间点。 3 P1 2 a 相连 P2 许多GIS系统中，点、线、面不同的拓扑元素是分开存贮的，单一图层之间的分析以及多个图层之间的叠置分析，在GIS中基本的拓扑关系由 指满足拓扑几何学原理的各空间数据间的相互关系。即用结点、弧段和多边形所表示的实体之间的邻接、关联和包含等关系。 点(结点)、线(链、弧段、边)、面(多边形)三种要素是拓扑元素。它们( 点、线、面)三种要素之间最基本的拓扑关系是邻接和关联。 邻接：相同拓扑元素之间的关系。如结点与结点，链与链，面与面等。 关联：不同拓扑元素之间的关系。如结点与链，链与多边形等。 在GIS的分析和应用功能中，还可能用到其它拓扑关系，如： 1)包含关系：面与其它拓扑元素之间的关系。如果点、线、面在该面内，则称为被该面包含。如某省包含的湖泊、河流等。 2)几何关系：拓扑元素之间的距离关系。如拓扑元素之间距离不超过某一半径的关系。 3)层次关系:相同拓扑元素之间的等级关系。如国家由省(自治区、直辖市)组成，省(自治区、直辖市)由县组成等。 GIS要对拓扑关系进行管理和分析，就必须定义其拓扑结构。拓扑结构是如何定义的呢？下面，我们一起来学习第二部分拓扑表的建立，也是本次课的重点和难点. 拓扑关系在地图上是通过图形来识别和解释的，而在计算机中，则必须按照拓扑结构加以定义。 结点（NODE）：弧段的交点。岛结点是特殊结点。 弧段（ARC）：相邻两结点之间的坐标链。岛边界弧段是特殊弧段。 多边形（polygon）（图斑或面）有限弧段组成的封闭区。 节点（node）为弧段上的起点和终点，图2-4-1中from-node 是弧段上的起点；to-node是弧段上的终点； 顶点（vertex）为弧段上的中间节点； 弧段(arc)由起始 node 及其间的一系列 vertex 构成，有公共 node 的 arc 称为“相连”； 多边形（polygon）由若干条 arc 围成有公共 arc的 polygon 称为“相邻”。 由起始 node 及其间的一系列 vertex 构成。 相邻 由若干条 arc 围成。

三 拓扑结构的表达 The expression of topology （二） 拓扑关系 拓扑关联(Connectivity) 拓扑邻接(Adjacency) To Node 关联是不同拓扑元素之间的关系，点与线、线与面之间的关系。 Left Polygon Arc Right Polygon 拓扑关联Connectivity - from and to nodes 多边形定义Area definition- Polygon Enclosure 拓扑邻接Adjacency - from Direction 邻接是相同拓扑元素之间的关系，即点与点、线与线、面与面之间的关系。 From Node

三 拓扑结构的表达 The expression of topology （二） 拓扑关系 拓扑包含(Containment) ：包含指不同级别或不同层次的多边形图形实体之间的拓扑关系。 面包含点 面包含线 线包含点 面的简单包含 面的多层包含 面的等价包含 P1 P2 P3

三 拓扑结构的表达 The expression of topology （三） 拓扑关系的分解 Network 地图(M) M Polygon 1 b P1 P2 3 P1 拓扑 分解 2 a Arc 1 2 3 P2 从拓扑关系的角度，地图是由点、线、面构成的。拓扑关系的分解就是从点、线、面之间的相互关系开始。 我们建立起地图点、线、面三层构架之间的关系。 对于关系的表达，在GIS中通常采用关系模型，也就是关系表。大家都知道，以关系模型为基础的关系型数据库及其管理软件是信息时代的成功案例，结构化的表单适合数据的检索和分析。 在矢量数据中拓扑关系可以由四个表格来表示。目前商用GIS还没有超出这四个表格的拓扑关系。 Node a b GIS对关系的表达通常采用何种方法?

三 拓扑结构的表达 The expression of topology （三） 多边形 弧段拓扑关系的表达 Polygon-arc Topology 地图 Polygon Arc 1,2 2,3 1 1 b P1 P1 ★ a Arc-polygon Topology 2 2 P2 P2 Arc Left Polygon Right Polygon 3 3 P1 P1 P2 ２张拓扑表之间信息独立吗？

拓扑结构的表达 The expression of topology （三） 弧段 节点拓扑关系的表达 ★ Arc-node Topology 地图 Arc From-Node To-Node a b P1 P2 2 1 3 1 a b 2 3 在GIS中拓扑表的生成通常是由软件自动生成的，在ARC/INFO中,拓扑结构是由BUILD和CLEAN两条命令自动生成和修改的。 Node-arc Topology Node Arc a 1,2,3 b

拓扑结构的表达 The expression of topology （五） 拓扑表的其他表达形式 ★ ★ Arc-polygon Topology Arc Left Polygon Right Polygon 1 P1 2 P2 3 Arc-node Topology Arc From-Node To-Node 1 a b 2 3 Arc From-Node To-Node Left-Polygon Right-Polygon 1 a b P1 2 P2 3

本次课主要内容 ★ 一 问题提出 二 拓扑花絮 三 拓扑表达 ★ 四 拓扑求解 ★ ★ The Proposals of Our Questions 二 拓扑花絮 The Stories of Topology 三 拓扑表达 The Expression of Topology in GIS 四 拓扑求解 How Topology Works ★ ★ ★

四 拓扑求解 How Topology Works （一） 拓扑遍历（Traversing Topology） Easy!! a b P1 P2 2 1 3 与多边形P1邻接的多边形是哪个？邻接的边是哪一条？ 我如何才能从节点b转到节点a，然后在回到节点b？ 有那些弧段落在多边形P1中？ Easy!! Easy!! What polygon is P1 next to, and where are they adjacent: P1 is next to P2 because Line 2 has polygon P1 to the left and P2 to the right. This is adjacency. How do I traverse from node b, to node a, and then back to node b: Easy! Take line 3 to node a, and you have a choice to take either line 2 or 3 back to node b. This is connectivity. What lines does polygon P1 fall inside of: Easy! Polygon P1 is contained by lines 1 and 2. This is containment Polygon Lines P1 1,2 P2 2,3 Arc From-Node To-Node Left-Polygon Right-Polygon a b 0 P1 a b P1 P2 3 b a 0 P2

四 拓扑求解 How Topology Works （二）数字化错误(Topological Errors) 是否数字化的地图直接就可以建立拓扑关系呢？ 想象一下如果弧段3没有连接上节点a，我们就得不到闭合的多边形。 或者，如果弧段2延伸过了节点b（我们表识为弧段4） 。那么，弧段4的左右多边形是什么呢？ 4 a b P1 P2 2 1 3 P2无法创建！！ Topology – the big picture You probably want to know what this has to do with digitizing. When you are digitizing data for use in a GIS, you are basically building a topological representation of the data that we just talked about. When you digitize, you need to be aware of these kinds of errors. That’s why we talked earlier about letting the software work for you. The software can either flag these errors, or perform some automatic snapping. These errors are called topological errors. To make your data work within a GIS, it should be topologically clean, an free of errors. 没有！！

四 拓扑求解 How Topology Works （三）水文分析 (Hydrological Analysis） 如何从图中提取出各个河段的交点呢？ 河网可视为树，树的端点是汇流点。 树的枝干就是溪流的通道。 两个溪流通道的交点（节点）就视为出水口。

总结 Summary 万变不离其中 拓扑结构和拓扑结构的表达 拓扑元素 拓扑关系 节点 拓扑邻接 弧段 拓扑关联 拓扑结构的应用 多边形 　拓扑学 　拓扑结构和拓扑结构的表达 　拓扑结构的应用 节点 弧段 多边形 拓扑元素 拓扑邻接 拓扑关联 拓扑包含 拓扑关系 拓扑关系能清楚地反映实体之间的逻辑结构关系，它比几何数据有更大的稳定性，不随地图投影而变化。 拓扑结构是地理要素存储的最高形式，通过存储某一要素相对于其它要素的位置信息，拓扑结构提供了许多地理分析的基础，并且节省了存储空间，避免重复检索，提高效率。如连通性、路程确定都可通过拓扑分析直接产生 如邻接性、路程确定都可通过拓扑分析直接产生。 拓扑结构通过存储拓扑关系表加以定义；拓扑结构提供了许多地理分析的基础。 Why topology – Enforce geometric rules for spatial representation and maintain data integrity (having implications in data interoperability) – Reduce data redundancy – Improve data access/update efficiency 拓扑结构 拓扑表的建立 学会结合案例，自主进行分析和学习

思考题 Questions 根据拓扑求解的思路，尝试着给出问题集1-3（邻接关系，包含关系和关联关系）的解决方案。

下节课内容预告 Prevue of Next Lesson 下次课为配套的实验课程，我们将和大家来学习拓扑查错。 　　ARCGIS提供了丰富的拓扑规则（topology rules）来帮助我们规范化地图数据。 Go On… Topology – the big picture You probably want to know what this has to do with digitizing. When you are digitizing data for use in a GIS, you are basically building a topological representation of the data that we just talked about. When you digitize, you need to be aware of these kinds of errors. That’s why we talked earlier about letting the software work for you. The software can either flag these errors, or perform some automatic snapping. These errors are called topological errors. To make your data work within a GIS, it should be topologically clean, an free of errors.