2014 , Vol. 16 >Issue 6: 839 - 845

• 吴长彬 ,
• 闾国年

• 1. 南京师范大学 虚拟地理环境教育部重点实验室,南京 210023;2. 江苏省地理信息资源开发与利用协同创新中心,南京 210023

要求修回日期: 2014-02-07

网络出版日期: 2014-11-01

Representation and Calculation Method of Topological Relationships for Complex Line Objects

• WU Changbin ,
• LV Guonian
Expand
• 1. Key Laboratory of Virtual Geographic Environment, Ministry of Education, Nanjing Normal University, Nanjing 210023, China;2. Jiangsu Center for Collaborative Innovation in Geographical Information Resource Development and Application, Nanjing 210023, China
*Corresponding author: WU Changbin, E-mail:

Request revised date: 2014-02-07

Online published: 2014-11-01

《地球信息科学学报》编辑部 所有

### Abstract

Topological relationship is one of the basic topics of geographic information systems (GISs), and it has been widely applied to data organization and spatial analysis. Many scholars have studied the models of topological relationship and achieved some progresses, among which the 9-Intersections Model (9IM) is well known. This paper aims at finding a method to solve the prominent issue that current models of spatial topological relationships could not represent complex objects. Taking the line object as an example, according to the concepts of point set topology, the complexity of the line object is redefined and distinguished. A linear sequence model of topological relationships, which is based on 9-Intersections Model (9IM) for complex line objects, is proposed and it is represented by some composite basic 9IM matrices. To calculate and distinguish these topological relationships, we applied different methods according to the different relationships between the lines, e.g. some of the lines intersect, some overlap, and others may disjoint. Our main works are stated as follows: we designed an improved sweep-line algorithm to increase the efficiency of the program; we took rectangular envelope algorithm to reduce the execution times, and used vector cross product to determine whether there are any intersections between lines; and we also used coordinates and slopes to deal with some special situations. The test system is developed to prove the capability and efficiency of the model and the calculation method. The procedure is: firstly, the coordinates of two polylines are input; secondly, the polylines are drawn and displayed on the screen, and then the algorithm is executed; finally, the results of topological expressions are produced and shown. As a result, our model can successfully calculate most special relationships between complex polylines, but without the involvement of arc or self-intersection. Generally, this model is still incomplete at present and needs to be improved in future.

### 2 复杂线-线对象拓扑关系的描述

#### 2.1 线复杂性的区分

$L = ⋃ i = 1 n f i ( [ 0,1 ] )$ ,其中 $∀ 1 ≤ i ≤ n ： f i : [ 0,1 ] → R 2$ 是一个连续函数。
$f 0$ $f 1$ 表示的是线的2个节点。则当 $n = 1$ ,且 $∀ a , b ∈ [ 0,1 ] , a ≠ b : f ( a ) ≠ f ( b ) ， L$ 是条简单线,否则为复杂线;当 $a , b ∈ ( 0,1 ) , a ≠ b : f ( a ) = f ( b )$ ,L是条自相交的线;当 $∃ a ∈ { 0,1 } , b ∈ [ 0,1 ] : f ( a ) = f ( b )$ ,L是条自相接的线;当f(0)=f(1),L是条闭合的线。

#### 2.2 线-线的复杂拓扑关系的线性序列描述方法

##### Fig. 3 33 different topological relationships between two lines[20]

$CR ( L 1 , L 2 ) = ( 1 ) LL 1 + ( 2,6 ) LL 2 + ( 3,5 , 7,9 ) LL 24 + ( 4,8 ) LL 22$

##### Fig. 4 An example of complex topological relationship between lines

$CR ( L 1 , L 2 ) = ( 9 ) LL 1 + ( 4,8 ) LL 2 + ( 1,3 , 5,7 ) LL 24 + ( 2,6 ) LL 22$

### 3 线-线复杂拓扑关系的计算方法

（1）线-线是否相交的矢量叉乘法

①当z1z2的符号或方向相同时,nini+1mimi+1的同侧,线段不相交,如图5（a）所示;
##### Fig. 5 Vector cross multiplication to determine the intersection between two lines

②当z1z2的符号或方向相反时,nini+1mimi+1的异侧,线段相交,如图5（b）所示。
（2）线节点重合或共线的斜率坐标判断法

###### Tab. 1 Different methods by different topological relationships between lines

1 线-线相离 采用矢量叉乘的判断法
2 线-线相交 采用矢量叉乘的判断法
3 线-线外相接 采用坐标和斜率判断的方法,当斜率k不等,但有一个端点坐标相等
4 线-线内相接 采用坐标和斜率判断的方法,当斜率k不等,但有一个端点在另一直线上
5 线-线相等 采用坐标和斜率判断的方法,当斜率k相等,且两条线段的两个端点都相等时
6 线-线部分包含 采用坐标和斜率判断的方法,当斜率k相等,且两条线段的有一个端点坐标相等时
7 线-线完全包含 采用坐标和斜率判断的方法,当斜率k相等,且两条线段的两个端点都不相等,但都在另一直线上时
8 线-线部分重叠 采用坐标和斜率判断的方法,当斜率k相等,且两条线段的两个端点都不相等,但有一个端点在另一直线上时

### 5 结论与讨论

The authors have declared that no competing interests exist.

### 参考文献

 [1] Egenhofer M J, Sharma J, Mark D M.A critical comparison of the 4-intersection and 9-intersection models for spatial relations: Formal Analysis[J]. AutoCarto, 1993,11:1-11.
 [2] 杜世宏,秦其明,王桥.空间关系及其应用[J].地学前缘,2006,13(3):69-80.
 [3] Egenhofer M J, Franzosa R D.Point-set topological spatial relations[J]. Int. J. Geographical Information Systems, 1991,5(2):161-176.
 [4] Chen J, Li C M, Li Z L, et al.Improving 9-Intersection Model by replacing the complement with voronoi region[J]. Geo-spatial Information Science, 2000,3(1):1-10.
 [5] 吴建新,方裕,陈斌.拓扑空间关系描述理论研究现状与发展[J].地理与地理信息科学,2005,21(3):1-4.
 [6] Duboisset M, Pinet F, Kang M, et al.A general framework to implement topological relations on composite regions[C]. LNCS, 2007,4653:823-833.
 [7] Egenhofer M J.A reference system for topological relations between compound spatial objects[C]. ER 2009 Workshops, LNCS, 2009,5833:307-316.
 [8] Schneider M.Computing the Topological Relationship of Complex Regions[C]. Database and Expert Systems Applications, Lecture Notes in Computer Science, 2004,3180:844-853.
 [9] Schneider M, Behr T.Topological relationships between complex spatial objects[J]. ACM Trans.on Database Systems, 2006,31:39-81.
 [10] Praing R, Schneider M.Efficient implementation techniques for topological predicates on complex spatial objects[J]. Geoinformatica, 2008,12(3):313-356.
 [11] Mckenney M, Pauly A, Praing R, et al.Local topological relationships for complex regions[C]. In 10th Int. Symp. on Spatial and Temporal Databases, 2007,4605:203-220.
 [12] 吴长彬,闾国年.空间拓扑关系若干问题研究现状的评析[J].地球信息科学学报,2010,12(4):524-531.
 [13] 吴长彬,闾国年.线面拓扑和度量关系的细分描述和计算方法[J].计算机辅助设计与图形学学报,2009,21(11):1551-1557.
 [14] Kurata Y. The 9+-Intersection: A universal framework for modeling topological relations[C]. GIScience,LNCS,2008(5266):181-198.
 [15] Kurata Y.Three-valued 9-intersection for deriving possible topological relations from incomplete observations[R]. Lecture Notes in Geoinformation and Cartography, Advances in GIScience, 2009:289-308.
 [16] Li Z L, Deng M.A hierarchical approach to the line-line topological relations[C]. Progress in Spatial Data Handling, 2006:365-382.
 [17] 邓敏,李志林,祁华斌.GIS线目标间空间关系的集成表达方法[J].测绘学报,2007,36(4):421-427.
 [18] Liu K F, Shi W Z.Extended model of topological relations between spatial objects in geographic information systems[J]. International Journal of Applied Earth Observation and Geoinformation, 2007,9:264-275.
 [19] 邓敏,李志林,李永礼,等.GIS线目标间拓扑关系描述的4交差模型[J].武汉大学学报(信息科学版),2006,31(11):945-948
 [20] Egenhofer M J, Herring J R. Categorizing binary topological relationships between regions, lines and points in geographic databases[A]. A Framework for the Definition of Topological Relationships and An Approach to Spatial Reasoning within this Framework[C], 1991:1-28.
Options

/

 〈 〉