利用双重索引快速构建道路网络连通拓扑

路网拓扑关系的生成是进行最优路径规划的基础。本文针对ISO GDF4.0模型对道路连通拓扑的定义,结合最优路径规划对道路网络连通拓扑的要求,提出一种使用R-tree空间索引和B-tree索引双重索引方式快速生成道路连通拓扑的算法。连通拓扑快速构建算法包括新道路生成和网络拓扑提取两部分,新道路生成过程中,首先,自上而下地打断道路形成直线段集并求交点,然后,自下而上地重构直线段集以生成新道路。在打断道路求交点过程中,对道路建立R-tree空间索引,显著提高了几何要素的查找速度。在网络拓扑提取过程中对序列化数据建立B-tree索引,使得其查找速度大大加快。通过对双重索引算法的时间复杂度分析与验证表明,本文提出的拓扑生成算法具有较高的执行效率。

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

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（v log（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.