高等级道路网的拓扑自动保持方法

Automatic Topology Maintenance Approach for High-level Road Networks

基于道路网的结构分析,提出了一种高等级道路网拓扑自动保持方法,适用于任意提取的高等级路网。首先根据道路的连通关系生成对偶图,利用最小生成树保持道路网的整体连通性;然后使用广度优先搜索和最短路径计算进行悬挂弧段连接和合理路径连接,保持高等级道路网的导航连通性;最后通过实验验证了本文方法所保持的道路网拓扑结构的有效性。实验结果表明,通过本方法保持的拓扑关系能够保持道路网的整体连通性,反映道路网的高等级结构模式特征,而且与基于原始划分的高等级道路网所规划的最短路径相比,拓扑自动保持后的高等级道路网能够合理地反映道路结点之间的导航路径规划。

This paper presents an automatic topology maintenance approach for any extracted high-level road network. Firstly, the minimum spanning tree （MST） is generated on dual graph of road net- works for maintaining the whole connectivity relationship. Secondly, the breadth-first search （BFS） and shortest path algorithm are applied to connect the dangling roads and rational roads, which are used to maintain the perceptual connecting relationship of the high-level road networks. An experiment was executed to verify the effectiveness of the approach. The experimental results show that the method achieves good and effective topology maintenance results, reflecting the structural characteristic of a high-level network. Furthermore, a comparison analysis to original high-level roads before and after topology maintenance was also carried out to show the rationalities of navigation path planning.