地球信息科学学报 ›› 2014, Vol. 16 ›› Issue (6): 839-845.doi: 10.3724/SP.J.1047.2014.00839

• •    下一篇

复杂线-线对象的拓扑关系描述与计算方法

吴长彬(), 闾国年   

  1. 1. 南京师范大学 虚拟地理环境教育部重点实验室,南京 210023;2. 江苏省地理信息资源开发与利用协同创新中心,南京 210023
  • 收稿日期:2014-01-07 修回日期:2014-02-07 出版日期:2014-11-10 发布日期:2014-11-01
  • 作者简介:

    作者简介:吴长彬(1977-),男,博士,副教授,研究方向为GIS、空间关系、时空数据模型。E-mail:wuchangbin @njnu.edu.cn

  • 基金资助:
    国家自然科学基金项目(41101350,41471318);江苏高校优势学科建设工程资助项目

Representation and Calculation Method of Topological Relationships for Complex Line Objects

WU Changbin(), LV Guonian   

  1. 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
  • Received:2014-01-07 Revised:2014-02-07 Online:2014-11-10 Published:2014-11-01
  • About author:

    *The author: WANG Jiacheng, E-mail:shanqiangw@fync.edu.cn

摘要:

空间拓扑关系是GIS中空间查询和分析的基础。针对当前空间拓扑关系模型在表达较复杂对象间拓扑关系存在局限性的突出问题,以线对象为实例,根据点集拓扑理论,重新定义和区分线对象的复杂性;以9I模型为基础,提出一种适合二维复杂线对象的拓扑关系的线性序列描述模型,将复杂线-线的拓扑关系表示成基本拓扑关系的组合。分析不同情形下线之间拓扑关系不同的计算方法。为实现复杂线-线拓扑关系的计算,提高扫描线算法的效率,探讨包络矩形粗滤、线节点重合或共线的斜率坐标判断法等改进方法,提出判断线-线是否相交的矢量叉乘法,具有快速高效的特点。最后,通过实验系统导入线坐标串,进行图形绘制、拓扑关系计算并输出结果,从而验证该模型和算法的可行性。

关键词: 拓扑关系, 线性序列, 9I模型, 扫描线算法, 矢量叉乘

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.

Key words: topological relationships, linear sequence, 9I model, sweep-line algorithm, vector cross product