OALib Journal期刊
利用双重索引快速构建道路网络连通拓扑
DOI: 10.3724/SP.J.1047.2013.00498
Keywords: 连通拓扑 ,双重索引 ,R-tree ,道路网 ,有效算法 ,B-tree
Abstract:
路网拓扑关系的生成是进行最优路径规划的基础。本文针对ISOGDF4.0模型对道路连通拓扑的定义,结合最优路径规划对道路网络连通拓扑的要求,提出一种使用R-tree空间索引和B-tree索引双重索引方式快速生成道路连通拓扑的算法。连通拓扑快速构建算法包括新道路生成和网络拓扑提取两部分,新道路生成过程中,首先,自上而下地打断道路形成直线段集并求交点,然后,自下而上地重构直线段集以生成新道路。在打断道路求交点过程中,对道路建立R-tree空间索引,显著提高了几何要素的查找速度。在网络拓扑提取过程中对序列化数据建立B-tree索引,使得其查找速度大大加快。通过对双重索引算法的时间复杂度分析与验证表明,本文提出的拓扑生成算法具有较高的执行效率。
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.
Full-Text
Contact Us
service@oalib.com
QQ:3279437679
WhatsApp +8615387084133
