Building the Topology of Spatial Entities
-
摘要: 空间实体的拓扑关系是地理信息系统进行空间分析、决策支持的基础.拓扑关系的关键点在于拓扑结构的构建.首先介绍了点集拓扑理论, 归纳了有实际应用价值的各种拓扑关系, 分析了拓扑模型中的最基本拓扑元素和空间实体的关系; 然后提出了一种要素类的拓扑构建方法, 其算法以MAPGIS7.0空间实体的结构为依据, 主要体现要素分裂的思想.实践证明, 这些方法能够有效的构建空间实体的拓扑关系.Abstract: The topology relationship of spatial entities is the basis of GIS applications in spatial analysis and decision support. The crucial point of topology relationships is the building of topological structure. This paper firstly introduces the point set of topology theory, enumerating all kinds of topology relations which have practical application value. The relationship between a base topology element and spatial entity in the topology model is also analyzed.Then a topology building method is put forward, using feature classes. The algorithms accompany with the spatial entity model of MAPGIS7.0. These algorithms mainly present the idea of feature splitting. These methods are proved effective for building topological relationships of spatial entities in practice.
-
Key words:
- logical topological structure /
- topology building /
- split /
- topology element
-
0. 引言
地理信息系统以空间实体为对象.这些地理实物在计算机中用图形的方式将其表现出来.空间实体有其固有的空间关系, 比如邻接、相邻、相交等.在图形学中, 不考虑度量和方向的空间物体之间的关系被称为拓扑关系(吴信才, 2002).
1. 拓扑关系的理论基础
Egenhofer and Franzosa (1991)以点集拓扑学理论为工具, 对空间物体的拓扑关系进行了描述.对于全集X中的点集A和B, 这2个点集表示2个空间实体, 表示БA的边界, A0表示A的内域, 空间实体A和B的空间关系就由集合A和B的边界和内域来确定.这些关系可以用4元组来表示A0∩B0, A0∩БB, БA∩B0, БA∩БB.4个元组中每个元素的取值为空(Ф) 或(⇁Ф), 表明它们是相交还是相离.这个4元组的方法称为“四交模型(4-intersection) ”.可以计算出A, B的一切可能的拓扑关系为24=16种(郭仁忠, 2001).在这些关系中有些是没有实际意义的, 有些有用的关系没有能够充分的表达. 孙玉国(1993)和Egenhofer and Franzosa (1991)针对“四交模型”的弱点, 采用相同的思路对其进行了扩展, 将集合的余引入关系的描述, 集合x的子集A的余记为A-, 这样2个物体之间的关系用3×3的9元组来描述: БA∩B0, A0∩B0, A-∩B0, БA∩B-, A0∩B-, A-∩B-, БA∩БB, A0∩БB, A-∩БB.这一模型就是“九交模型”.无论是“四交模型”还是“九交模型”, 能够反映的都是几何体的位置关系, 集合本身是不能反映几何体的形状的.在实际的应用中, 往往需要反映出不同几何形状之间的拓扑关系, 具有实际意义的拓扑关系有19种, 包括: 点对点的相离、共位、相邻、包含; 点对线的相离、相邻、相交、包含; 点对区的相离、相邻、包含; 线对线的相离、相邻、相交、共位; 线对区的相离、相邻、相交、包含; 区对区的相离、相邻、相交、包含(韩鹏等, 2005).
2. 拓扑的逻辑结构
对于空间实体的拓扑关系表示通常是用结点-边-面来表示的, 结点、边、面在拓扑的逻辑结构中被称为拓扑元素.几何实体和拓扑元素的关系可以由图 1来表示(Egenhofer and Franzosa, 1991).
在图 1中, 空间实体分别对应拓扑逻辑结构中的结点、边和面, 它们之间有一定的对应关系.在拓扑结构内部也有其对应关系, 结点和边之间的关系是一个结点可以有多条边通过, 而一条边有2个节点, 边和面之间的关系是一条边对应左右2个面, 一个面对应1或者多条边组成(Erik et al., 2003).
3. 基于MAPGIS7.0空间实体结构的拓扑构建
拓扑关系是对空间实体进行建立的, 拓扑的构建方法也依赖于空间实体的组织方式.本文介绍的拓扑是建立在MAPGIS7.0的空间数据之上的.MAPGIS7.0的空间数据模型总体思想是将具有相同类型的地理实体归为一个要素类.同一个要素类中的要素具有相同的几何形态, 分为点要素类、线要素类、区要素类.拓扑构建就是对这些要素类构建拓扑关系.下面给出了拓扑元素的结构定义.
拓扑结点结构:
typedef struct
{
TYPE_ OBJ_IDid；
CArcIDs*edgeIDs；
D_DOT dot；
CSmart Array < FCLS_FID > *fcls_fID；
}Topo_ Nod.
其中, ID表示拓扑结点ID, edgeIDs表示通过结点的边的ID列表, CArcIDs是MAPGIS7.0中int 64型ID数组的宏定义, dot表示结点的坐标(x, y), fcls fID, 表示结点所在的要素类以及要素的ID结构.
拓扑边结构:
typedef struct
{
TYPE_OBJ_ID edgeID；
TYPE_OBJ_ID fromID；
TYPE_OBJ_ID toID；
TYPE_OBJ_ID left RegID；
TYPE_OBJ_ID right RegID；
CSmart Array < FCLS_FID > *fcls_fID；
CVar Line *ptvline；
}Topo_Edge.
其中, edgeID表示拓扑边的ID, fromID表示拓扑边的起始结点ID, toID表示拓扑边的终止结点ID, leftRegID表示拓扑边的左多边形ID, rightRegID表示拓扑边的右多边形ID.Fcls_fID表示线要素类和线要素ID的结构, ptvline是拓扑边的坐标数据((x, y) 坐标序列), CVarLine是MAPGIS7.0线坐标数据的一个封装类(MAPGIS7.0要素类详细设计文档, 2004).
拓扑面结构:
typedef str uct
{
TYPE_OBJ_IDid；
CArcIDs *edgeIDs；
CPolygon *polygon；
CSmart Array < FCLS_FID > *fcls_fID；
}Topo_Face.
其中, ID表示拓扑边的ID, edgeIDs表示拓扑面所包含的拓扑边的ID, polygon表示拓扑多变形的数据(起止坐标相同的(x, y) 坐标序列), CPolygon是MAPGIS7.0中多边形数据的一个封装类(MAPGIS7.0详细设计文档, 2004).
3.1 点-线拓扑构建
点-线拓扑构建是对MAPGIS7.0中的点要素类和线要素类建立拓扑关系.点-线拓扑构建的目标是能够表达出点要素和线要素的相邻或者相交关系.如图 2所示, 点要素类有3个点, 线要素类有一条线, 点要素类有点正好落在了线上, 拓扑构建之后, 将产生5个拓扑结点、2条拓扑边.其中拓扑结点1和拓扑结点3有一条拓扑边通过, 拓扑结点2有2条拓扑边通过, 结果如图 2.
生成过程描述: 遍历线要素类中的每一个线要素, 每一个线要素和点要素判断点是否落在线上.因为线是有序的坐标序列, 可以对线段建立索引来加速检索速度.该算法中采用的R树索引, lin1有5个坐标点构成, 分为3个线段, 就可以将3个线段的外包矩形插入R树中, 用点的外包矩形对R树进行检索, 再将得到的线段和点进行准确的位置判断.由解析结构知识可知点在线上的充要条件是(李滨和王青山, 2003) :
当判断得到点落在线上, 点就生成拓扑结点, 线在点的位置被打断, 分段后的线生成拓扑边.
3.2 线-线拓扑构建
线-线拓扑构建是MAPGIS7.0中线要素类和线要素类之间进行拓扑构建, 线-线拓扑构建的目标也是能够表现出线要素之间邻接、关联、相交、共享边界等关系.
生成过程描述: 线要素类A和线要素类B进行拓扑构建, 可以分成3个主要过程, 分裂过程算法如下:
(1) 分裂线形成交点.要素类A中的线lina1有n个点连接而成分成n-1段, 为lina1建立R树索引, 要素类B中的线linb1有m个点, 分成m-1段, 每一段外包矩形和linb1的R树求交, 将求得的lina1的线段和linb1的线段求交点.2线段求交点可能产生5种情况(图 3).
将求得的交点记录到下面的结构cross中, 其中dot表示交点坐标, Apart表示交点在lina1要素的线段的编号, Bpart表示交点在linb1的线段的编号.
(2) 处理交点.交点是在2线段求交的时候产生的, 并不是每一个交点都是拓扑结点, 在形成拓扑之前需要对交点进行处理, 一些交点需要删除.包括3种情况: (a) 在端点的交点需要删除, 如图 4a所示交点Dot1需要被删除, 应为该交点没有引起线段分裂; (b) 在线段的端点(线中间的点) 处产生的交点需要删除如图 4b所示, lin1和lin2 2条线求交点, 交点Dot3刚好落在lin1或者lin2本身的顶点上, lin1的第一部分和lin2的第一部分求交, 在Dot3处产生一个交点, lin1的第2部分和lin2的第1部分求交在Dot3处还是会产生一个交点, 也就是在Dot3处会有2次形成交点, 此时形成的交点需要删除一个; (c) 交点所在记录Apart和Bpart的前一个点和后一个点坐标相等, 去掉该交点.
如图 4c所示, 2条线相交产生3个交点: Dot6、Dot5、Dot7, 3个点同时都是2条线的顶点, 在生成拓扑弧段的时候, 应该只生成Dot6和Dot7之间生成一条拓扑边, 不需要在Dot5处在断开, 所以要将Dot5删除.
(3) 形成拓扑边和拓扑结点.将2条线的终点插入到交点中, 逐个循环交点, 分别从2条线的起点开始, 用Apart和Bpart控制交点插入的位置, 逐个生成拓扑结点和拓扑弧段.
lina1和linb1处理完之后, 在对lina1和linb2求交生成拓扑信息, 因为lina1已经被分裂过, 所以用lina1分裂之后的弧段和linb2求交, 在生成拓扑信息.在生成拓扑边信息之后, 删除被分裂的拓扑边, 同时更新拓扑结点的相关信息.循环要素类A和要素类B中的每一条线, 循环完毕, 拓扑构建结束.
3.3 线-区拓扑构建
线-区拓扑构建是MAPGIS7.0中线要素类和区要素类建立拓扑关系.生成过程描述:
(1) 区要素类的多边形和线要素类的线求交点生成拓扑结点和拓扑弧段, 方法和上述的线-线建立拓扑相同.多边形和线求交的过程中可以对线建立索引来减少检索速度.
(2) 多边形和每一条线求交以后, 进行拓扑多边形形成一次.多边形和线求交之后生成了拓扑结点和拓扑边, 在形成多边形之前首先对拓扑边进行过滤, 得到多边形的拓扑边集rset和与该多边行有2个交点的拓扑边集lset (线形成的拓扑边).根据线和多边形的图形特性, 提出一种基于二分思想的多边形构建法.每次取线要素类的一条边与多边形的边进行拓扑构建, 产生的结果总是2个多边形.以rset和lset进行拓扑构建为例, 从lset中的边出发, 相交的一条拓扑边将多边形分成2个, 每次都会形成2个拓扑多边形.如图 5所示, lin1和Reg1求交, 交于a, b2点.在进行过滤之后, 得到的rset拓扑边集合是{tp1, tp2, tp3 }, lset是{ab}.在进行多边形形成时, 从ab出发, 以a点为起点, 计算起始2点所在线段的斜率, 即图 5所示的分界线所在直线的斜率, 形成的2个多边形是以ab为起始边, 顺时针方向的多边形和逆时针方向的多边形.计算通过a点的其他拓扑边的起始2点的斜率(以a为起点), 形成逆时针多边形的线段, 是斜率在分界线上方拓扑边, 顺时针方向的是斜率在分界线下方的拓扑边.逐步探测拓扑边, 将符合条件的加入拓扑面弧段数组中, 当拓扑边的结点为b时, 搜索结束, 拓扑面形成.继续对lset中的边进行多边形构建, 将前面生成的结果多边形和lset中的下一条边继续二分, 直到lset中的边进行完为止.
(3) 当参见拓扑构建的多边形被分裂过, 找到该多边形被分裂的拓扑面, 这些拓扑面和线求交, 然后形成拓扑面, 形成方法和上述的一样, 在生成了新的拓扑面之后, 删除分裂的拓扑面, 同时更新拓扑边的左右多边形信息.
4. 结论
本文列举的对空间实体有实际意义的拓扑关系, 基于MAPGIS7.0空间数据模型, 介绍了几种基本的拓扑构建方法, 这几个拓扑构建方法都是对空间实体的分裂、点对线的分裂形成拓扑结点和拓扑边; 线对线的分裂生成拓扑结点和拓扑边; 线对区的分裂生成拓扑结点、拓扑边、拓扑面.对于线对区的分裂, 根据线和多边形的特点, 采用逐个二分的思想, 减少分裂的复杂性.拓扑关系是空间实体的基本关系, 拓扑关系的建立也是对空间实体进行分析应用的前提.建立准确完善的拓扑关系将有助于我们更好地利用空间信息解决实际问题.
-
[1] Egenhofer, M. J., Franzosa, R. D., 1991. Point-set topological spatial relations int. . Journal of GIS, 5 (2): 161-176. [2] Erik, H., Sudhakar, M., Scott, M., 2003. Building a robust relational-implementation of topology. Computer Science, Santorini Island, Greece. [3] Guo, R. Z., 2001. Spatial analyse. Higher Education Press, Beijing. 229 (in Chinese). [4] Han, P., Xu, Z. H., Zhu, H. F., 2005. The method of Arcobjects-The exploration of geographic in for mation system. Wuhan University Press, Wuhan. 216 (in Chinese). [5] Li, B., Wang, Q. S., 2003. Key technique anatomy of spatial database engine. Journal of Institute of Surveying and Mapping, 20 (1): 35-38 (in Chinese with English abstract). [6] Sun, Y. G., 1993. The description of topology spatial rela tionship and two DT-string spatial relationship expression[Dissertation]. Wuhan Technical University of Surveying and Mapping, Wuhan (inChinese). [7] Wu, X. C., 2002. The theory and technique of geographic information system. Electronics Industry Press, Beijing (in Chinese). [8] Zondy Cyber Corporation, 2004. MAPGIS7.0 detail design document of featureclass. Zondy Cyber Corporation, Wuhan (inChinese). [9] 郭仁忠, 2001. 空间分析. 北京: 高等教育出版社. 229. [10] 韩鹏, 徐占华, 褚海峰, 2005. 地理信息系统开发-Arcobjects方法. 武汉: 武汉大学出版社. 216. [11] 李滨, 王青山, 2003. 空间数据库引擎关键技术剖析. 测绘学院学报, 20 (1): 35-38. https://www.cnki.com.cn/Article/CJFDTOTAL-JFJC200301011.htm [12] 孙玉国, 1993. 拓扑空间关系描述与2DT-String空间关系表达[学位论文]. 武汉: 武汉测绘科技大学. [13] 吴信才, 2002. 地理信息系统原理与方法. 北京: 电子工业出版社. 30. [14] 中地数码有限公司, 2004. MAPGIS7.0要素类详细设计文档. 武汉: 中地数码有限公司. -
下载:
下载:
点击查看大图
计量
- 文章访问数: 3513
- HTML全文浏览量: 162
- PDF下载量: 4
- 被引次数: 0
