The expression and applications of topology on spatial data §4.3空间数据拓扑结构 的表达及应用 The expression and applications of topology on spatial data 王文宇 北京建筑工程学院 地图学与地理信息系统系

本次课主要内容 ★ 相关知识的回顾 拓扑学花絮 拓扑结构的表达 ★ 拓扑结构的应用 ★ ★ Review The Stories of Topology 拓扑结构的表达 The Expression of Topology in GIS 拓扑结构的应用 How Topology Works ★ ★ ★

一、相关知识的回顾( Review ) （一）空间特征Spatial features 和空间关系spatial relationships 铁路 空间特征 空间关系 点: ( x ,y ) 线: ( x1 , y1 ) , (x2 , y2 ) , … , ( xn , yn ) 面: ( x1 , y1 ) , (x2 , y2 ) , … , ( x1 , y1 ) Spatial features in maps Points, lines and polygons Human being interprets additional information from maps about the spatial relationships between features A route trace from an airport to a house Land contiguity adjacent to streets along which the lands are located 车站 从车站到家，怎么走？ 道路两旁的地类一样吗？ 黄色车道 高速路 蓝色车道

一、相关知识的回顾( Review ) （一）地理空间(Geographic Space) 理论基础是几何学（geometry） 投影变换 绝对空间 （几何空间） 几何意义 地理空间 相对空间 （拓扑空间） 空间逻辑结构 一般说来，地理空间被定义为绝对空间和相对空间两种形式 绝对空间是具有属性描述的空间位置的集合，它由一系列的空间坐标值组成 相对空间是具有空间属性特征的实体的集合，它是由不同实体之间的空间关系构成 地理空间的表达是地理数据组织、存储、运算、分析的理论基础 Topological characteristics are those which describe connectivity. •When thinking about topology, the qualitative relationships of connectednessand contiguityare more important that the quantitative attributes such as lengthand area. 理论基础是拓扑学（topology）

本次课主要内容 ★ 相关知识的回顾 ★ 拓扑花絮 ★ 拓扑结构的表达 ★ 拓扑结构的应用 Review ★ 相关知识的回顾 Review ★ 拓扑花絮 　　　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 Stories of Topology 参数说明： n: 顶点数（结点数） a: 边数（弧段数） p: 面数（多边形数） （二）欧拉定理 2 = n + p -a 条件：多面体同胚于一个球面 立体图变平面图 欧拉公式在GIS中有着重要的意义，主要用来检查空间拓扑关系的正确性，能发现点、线、面不匹配的情况和多余、遗漏的图形元素。 欧拉发现，不论什么形状的凸多面体，其顶点数V、棱数E、面数F之间总有关系V+F-E=2，此式称为欧拉公式。V+F-E即欧拉示性数，已成为“拓扑学”的基础概念。那么什么是“拓扑学”？ 欧拉是如何发现这个关系的？他是用什么方法研究的？今天让我们沿着欧拉的足迹，怀着崇敬的心情和欣赏的态度探索这个公式. 定理的意义（几点说明） （1）数学规律：公式描述了简单多面体中顶点数、面数、棱数之间特有的规律； （2）思想方法创新训练：在定理的发现及证明过程中，在观念上，假设它的表面是橡皮薄膜制成的，可随意拉伸；在方法上将底面剪掉，然后其余各面拉开铺平，化为平面图形（立体图→平面图）。 （3）引入拓扑新学科：“拉开图”与以前的展开图是不同的，从立体图到拉开图，各面的形状，以及长度、距离、面积、全等等与度量有关的量发生了变化，而顶点数，面数，棱数等不变。 事实上，定理在引导大家进入一个新几何学领域：拓扑学。我们用一种可随意变形但不得撕破或粘连的材料（如橡皮波）做成的图形，拓扑学就是研究图形在这种变形过程中的不变的性质。 n = 4， a = 5，p = 3 备注：p包含边界里面和外面的多边形

本次课主要内容 ★ 相关知识的回顾 ★ 拓扑花絮 ★ 拓扑结构的表达 ★ 拓扑结构的应用 Review ★ 相关知识的回顾 Review ★ 拓扑花絮 　　　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 全拓扑表or 部分拓扑表？ Arc From-Node To-Node Left-Polygon Right-Polygon 1 a b P1 2 P2 3

本次课主要内容 ★ 相关知识的回顾 ★ 拓扑花絮 ★ 拓扑结构的表达 ★ 拓扑结构的应用 Review ★ 相关知识的回顾 Review ★ 拓扑花絮 　　　The Stories of Topology ★ 拓扑结构的表达 The Expression of Topology in GIS ★ 拓扑结构的应用 How Topology Works

四 拓扑结构的应用 How Topology Works Intelligent GIS （一） 问题的提出 建立起拓扑结构，GIS可以回答用户提出的很多问题: 位置(location):在哪？ 邻接关系(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.

四 拓扑结构的应用 How Topology Works This is adjacency! 与北京市相邻接的行政区有哪些？ （一） 问题的提出

四 拓扑结构的应用 How Topology Works This is containment! （一） 问题的提出 国道105线(G105线)经过哪些省份？

四 拓扑结构的应用 How Topology Works This is connection! （一） 问题的提出 从连云港的新浦站到北京的最佳路径怎么走？

四 拓扑结构的应用 How Topology Works Intelligent GIS （一） 问题的提出 建立起拓扑结构，GIS可以回答用户提出的很多问题: 位置(location):在哪？ 邻接关系(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. GIS是如何回答关于空间关系的问题的呢？

四 拓扑结构的应用 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. 没有！！

下节课内容预告 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.

总结 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 什么是拓扑关系？ 空间数据的拓扑关系是如何建立的？ 结合拓扑分析，尝试着解释部分拓扑表建立的条件。 ★

敬请批评指导 谢谢！