ARTICLES

An Efficient Algorithm to Construct Connectivity Topology for Road Network Using R-tree and B-tree Indexes

Expand
  • College of Resources and Environment, University of Chinese Academy of Sciences, Beijing 100049, China

Received date: 2013-01-21

  Revised date: 2013-03-15

  Online published: 2013-08-08

Abstract

A road network with topology is the basis for optimal path finding. According to the definition of connectivity topology by ISOGDF4.0 (Geographic Data File) model and the requirements of road network connectivity topology during the optimal path finding procedure, this paper presents an efficient algorithm to construct connectivity topology for road network using R-tree and B-tree indexes. The efficient algorithm contains two parts: the first part breaks the roads at intersections and generates anew road network; the second part constructs connectivity topology based on the new network. The procedure of building new road network breaks the roads into line segments and gets intersections at first, then reconstructs new roads with the line segments set and the intersections. During the procedure of getting intersections of any two line segments, the algorithm builds R-tree spatial index on the line segments to improve query operation efficiency significantly. What's more, our algorithm also builds B-tree index on serialized data of the roads such as the identity codes while constructing connectivity topology to improve the query operation efficiency on serialized data. This paper also tests the time complexity of the algorithm using road networks with different scales. Experiment results show that our algorithm builds connectivity topology of large-scale road network in very short time. (For a road network that contains about 30 thousands line segments and 25 thousands points, the quick algorithm completes connectivity topology construction in no more than 3 seconds). The time cost of our algorithm increases slightly while the traditional algorithm increases tremendously, to be exact, our algorithm's time cost grows at the rate of [O(vlog(v))]while the traditional one grows with the speed of [O(v2)], so we concluded that the quick algorithm has high efficiency and is valuable to practicable application.

Cite this article

HAN Zhi-Heng, RUI Xiao-Beng, SONG Xian-Feng, LIU Zhen-Tu, WANG Jing . An Efficient Algorithm to Construct Connectivity Topology for Road Network Using R-tree and B-tree Indexes[J]. Journal of Geo-information Science, 2013 , 15(4) : 498 -504 . DOI: 10.3724/SP.J.1047.2013.00498

References

[1] 李英姿,张飞舟,林耀海.智能交通系统中地理信息系统的研究[J].中国公路学报,2000,13(3):97-100.

[2] 孙棣华,肖锋,廖孝勇,等.基于预处理的城市路网拓扑结构构建算法[J].计算机工程与应用,2008,44(23):233-235.

[3] 蒋捷,韩刚,陈军.导航地理数据库[M].北京:科学出版社,2003.

[4] 何超英,蒋捷,韩刚,等.基于GDF的道路网完全拓扑生成算法[J].地理与地理信息科学,2004,20(2):30-33.

[5] 赵斌.导航地理数据生产系统及其关键技术研究[D].郑州:解放军信息工程大学,2006.

[6] 张小国,王庆,王宁,等.电子地图道路网模型及其自动生成算法研究[J].中国图象图形学报,2001,6(5):481-485.

[7] 李杰,张文栋,张樨.一种多边形道路网络拓扑生成算法的设计与实现[J].电子学报,2006,34(8):1396-1400.

[8] 王杰臣.多边形拓扑关系构建的栅格算法[J].测绘学报,2002,31(3):249-254.

[9] 熊少非,赵丕锡,李军.MapInfo中城市道路网络拓扑结构的自动生成[J].兵工自动化,2005,24(3):67-71.

[10] 宋维佳,张丽芬,王晓华,等.一种基于骨架化的道路拓扑生成算法[J].交通与计算机,2004,22(3):37-40.

[11] 张小国,王庆,万德钧.基于物理统一存储大规模数字导航地图道路网拓扑自动生成算法[J].中国惯性技术学报,2009,17(6):669-676.

[12] 吴长彬,闾国年.线面拓扑和度量关系的细分描述和计算方法[J].计算机辅助设计与图形学学报,2009,21(11):1551-1557.

[13] 邓敏,刘文宝,黄杏元,等.空间目标的拓扑关系及其GIS应用分析[J].中国图象图形学报,2006,11(12):1743-1749.

[14] 陆守一.地理信息系统[M].北京:高等教育出版社,2004.

[15] 徐立,孙群,杨帅,等.地图矢量数据拓扑关系生成算法[J].地理与地理信息科学,2012,28(4):18-21.

[16] 史文中,郭薇,彭奕彰.一种面向地理信息系统的空间索引方法[J].测绘学报,2001,30(2):156-161.

[17] 胡久乡,何松,钟瑜.空间数据库网格索引机制的最优划分[J].计算机学报,2002,25(11):1221-1230.

[18] 董鹏,杨崇俊,芮小平,等.一种基于改进四叉树的GIS空间选择查询算法[J].计算机工程与应用,2003(13):58-61.

[19] Theodoridis Y, Stefanakis E, Sellis T. Efficient cost models for spatial queries using R-trees[J]. IEEE Transactions on Knowledge and Data Engineering, 2000,12(1):19-32.

[20] 谷红亮,史元春,徐光祐.智能空间位置感知的伺候式服务模型[J].清华大学学报(自然科学版),2006,46(4):584-587.

[21] 张宏,温永宁,刘爱利,等.地理信息系统算法基础[M].北京:科学出版社,2006.

[22] Guttman A. R-Trees: Adynamic index structure for spatial search[J]. ACM SIGMOD Record,1984,14(2):47-57.

Outlines

/