线线拓扑关系五元组模型探讨

摘　要：线与线之间的拓扑关系相对复杂，目前很少有模型能对线线间的拓扑关系进行详细描述。本文运用两元组来描述内部与端点拓扑关系，再使用三元组来描述线线内部的拓扑关系，提出了线线五元组模型。

关键词：空间关系、线线拓扑关系、9 - Intersection模型、线线五元组模型
GIS主要是研究现实世界空间实体及其相互关系的描述和表达，在计算机环境下的空间数据组织、存取、分析、可视化，应用系统的设计、数据集成和业务化运作等。GIS的根本任务和功能在于对相关的空间数据进行处理和分析，提取有用的空间信息，这些功能都是通过空间分析实现的。因此空间分析是GIS区别于其它的信息系统及相关学科的主要功能特征，同时也是评价一个GIS功能的主要技术指标之一。
　　空间关系的表达有定量和定性两种表达方式，拓扑关系属于空间关系的定性表达，是空间关系研究的一个重要方向，它是指点、线和面之间在拓扑变换下保持不变的性质，如在平移、旋转和比例变换下，目标之间的相离、相邻和包含等。拓扑关系的描述一直是空间关系研究的主要内容，也是空间数据库查询和检索语言的重要组成部分，在用户和GIS交流中经常使用，给空间分析带来一种新的方法。因此拓扑关系的描述不仅要能够反映对象间几何上的关系，更重要的是能够与人们的认知概念一致，符合人们认识事物的方法，这样才能被人们所接受。
　 最具代表性的拓扑关系模型首推Egenhofer和Franzosa (1990)提出的4-Intersection模型及Egenhofer (1991)在基础上提出的9 - Intersection模型，但这些模型不能用于表示复杂的空间模型，难于描述复杂的目标间的复杂空间关系，特别是线线间的空间关系，本文针对此点，设计了一种新的拓扑关系模型。
拓扑关系
　　按照描述空间目标的维数，拓扑关系可分为二维空间和三维空间，其中二维欧氏空间中空间实体对象可分为点对象(0维)、线对象(1维)和面对象(2维)三类。
　　根据二维欧氏空间对空间实体的描述和分类，可以简单地对GIS中几何对象间的空间关系描述分为点点关系、点线关系、点面关系、线线关系、线面和面面关系。目标之间的拓扑关系主要是相离、相邻和相交等等。
　　
　　Egenhofer (1991) 提出的9 - Intersection模型是比较著名的拓扑关系模型，它能表示2种点点间关系、3种点线间关系、3种点面间关系、33种线线间关系、19种线面间关系及8种面面间关系。由于9交模型没有考虑到目标间的方向关系及相交的维数，因此9 - Intersection模型对某些线线关系是不能区分，例如：线线内部相邻、线线内部相交和线线部分重叠（图1)。
　　9 - Intersection模型也不能表示线线间相交的交点数，线的交点个数可以大于1，可以看出9 - Intersection模型只是对拓扑关系的一个定性描述，然而有时我们不仅要获取目标间定性的描述，有时还要获取定量的描述，比如，要获取两条线是否相交，以及交点的个数，这时9 - Intersection模型就不能描述了，因此，本文提出了一种新模型，来描述线线之间的拓扑关系，这个模型不仅能定性描述线线间的拓扑关系，还能描述定量线线间的拓扑关系。
线线拓扑新模型
　　在实际中，线线间的拓扑关系复杂，许多拓扑关系模型都很难精确描述。如果要精确描述线线拓扑关系，必须细分线线拓扑关系组成元素。本文根据线的内部和端点，根据线线间的内部和端点只有相离、相交、相接、相邻和重叠。给出了线线间的3大类拓扑关系，如下：
　　1) 线线间的内部与内部，有3种拓扑关系（如图2)，a. 内部相交；b. 内部相邻；c. 内部部分重叠。
　　　
　　2) 线线间的端点与端点，有3种拓扑关系（如图3)，a. 端点相邻；b. 端点相邻并部分重叠；c. 端点相离。

　　3)线线间的端点与内部，有5种拓扑关系（如图4)，a. 1端点与线内部相邻；b. 2端点与线内部相邻；c. 1端点与线内部重叠，另1端点与线内部相邻；d. 1端点与线内部重叠；e. 2端点与线内部重叠。

　　从上面可以得出，线线间的拓扑关系可以分为两个大类，1. 只与线线内部之间的拓扑关系，这类拓扑关系只有3种情况：a.内部相交，b.内部相邻，c.内部部分重叠；2. 与线端点有关的拓扑关系，这类拓扑关系只有8种情况。
线线五元组模型
　　在前一节，把线线间的拓扑关系可以分为两个大类，1)只与线线内部之间的拓扑关系；2)与线端点有关的拓扑关系。如果只要描述出这两类线线间的拓扑关系，就能把线线间的拓扑关系描述清楚。
　　对于第一类线线间拓扑关系，有3种情况可以使用一个3元组表示，其中每一元组表示其中的一种情况，其中的数字表示这种拓扑关系出现的次数，如果等于0，表示没有该种拓扑关系；大于0，表示该类拓扑关系出现的次数。3元组的定义为：第一元组表示内部交点的次数，第二元组表示内部相邻的次数，第三元组表示内部重叠的次数。
　　对于第二类线线间拓扑关系，主要是针对线线端点的。由于一条线只有两个端点，对于两条线就是两对端点，因此只要一个2元组就能表示这两对端点的拓扑关系。2元组的取值按表1取值，该表是按照每对端点可能存在的拓扑关系进行编号，每个取值都唯一对应一种拓扑关系。
    表1  2元组的取值表

　　线线五元组模型就是把上面的2元组和3元组进行合并，运用5个变量表示线线间的拓扑关系，达到对线内部和端点的拓扑关系进行表示，这种方法能对线线间的任意拓扑关系进行表示，并且查询方便，比如：要查询线线是否相交，只要查询元组是否为零，可以这样认为这种方法是一种比较理想并且查询方便的模型。

　　运用该模型表示线线间的拓扑关系，关键是细分拓扑关系的元素，正如上面所说的，线线间的拓扑关系可以分为2类，其中一类是只与线内部相关，另一类与线的端点有关。图5说明了五元组模型内部各个变量的意义，A和B分别表示线端点的拓扑关系，C、D和E分别表示线内部的拓扑关系。
　　下面举例说明如何使用线线五元组模型，在图6中，红色实线圆表示端点的拓扑关系，分别为两处，其中一处相邻，对应的取值为1；另一处相离，对应的取值为3。绿色虚线表示线内部的拓扑关系，共有两处，其中一处相交，另一处相邻，因此交点元组C的取值1，相邻元组D的取值1,又因为无线内部重叠出现，所以重叠元组E的取值为0。由此,可以得出五元组的取值为：[1、3、1、1、0]。

　　下面举例说明，9 - Intersection模型 所不能区分的线线拓扑关系模型，其中（a)两条线内部相邻，（b)两条线相交，然而它们用9 - Intersection模型表示有相同的9元组，因此无法区分。运用线线5元组模型，图1 (a)可以表示为：[3，3，0，1，0]，图1 (b)可以表示为：[3，3，1，0，0]，图1(c)可以表示为：[3，3，0，0，1]。
线线五元组模型实现
　　由于AutoCAD具有强大和快截的编辑功能，利用AutoCAD的二次开发工具ObjectARX，很容易实现线线五元组模型。通过提示选择两条多段线，进行判断，就能方便得到一个五元组数据，达到判断线线间的拓扑关系的目的。由此，证实了该模型在实际中是能容易实现的，可以用于判断线线间的拓扑关系。
结论
　　线线间的空间关系较复杂，运用9 - Intersection模型也很难描述一些较复杂的线线关系，所以本文提出了线线五元组模型，该模型通过对线线间的空间关系分类，达到表示线线间任意的拓扑关系。使用该模型比较容易判断线线间的拓扑关系，比如要判断线线间是否相交，直接检查相交元组C是否为0，如果不等于0，则表示线线间相交的次数。不过，因为该模型针对线线间的拓扑关系设计，因此只能描述线线间的拓扑关系。如果还要描述线线间的拓扑关系元素在线内的次序，需要扩展线线五元组模型，增加描述拓扑关系在线内的次序的变量。
　　线线五元组模型应用于线线间拓扑关系描述中，特别是线线间空间关系比较复杂，该模型会取得不错的效果。
参考文献：
[1] 陈军,赵仁亮. GIS 空间关系的基本问题与研究进展.测绘学报,1997 5(2):95-100.
[2] 刘万增,陈军等.线目标空间冲突自动检测方法研究,中国矿业大学学报,2006 11(6):768-771.
[3] 陈军,刘万增,李志林等,线目标间拓扑关系的细化计算方法, 测绘学报,2006 8(3):255-260.
[4] 邬伦,刘瑜,张晶等. 地理信息系统——原理、方法和应用.科学出版社, 2001.
[5] 龚健雅.地理信息系统基础.科学出版社，2001.
[6] Robert laurini, Derek Thompson. Fundamentals of spatial information systems. ACADEMIC PRESS,1999.
[7] EGENHOFERM, FRANZOSAR. Point-Set Topological Spatial Relations [J ] . International Journal of Geographical Information Systems , 1991, 5 ( 2 ):161-174. 本文链接：http://www.qk112.com/lwfw/jsjlw/zhinengkeji/232147.html