基于物理统一存储大规模数字导航地图道路网拓扑自动生成算法  

Algorithm for automatically creating topological information for road networks in large scale digital maps based on physical-integral storage strategy

作　　者：张小国[1] 王庆[1] 万德钧[1] 

机构地区：[1]东南大学仪器科学与工程学院,南京210096

出　　处：《中国惯性技术学报》2009年第6期670-676,共7页Journal of Chinese Inertial Technology

基　　金：国土资源部公益性行业专项经费项目-土地巡查车标准研究(20081107)

摘　　要：道路网络的拓扑信息是GIS进行空间分析,如最优路径、地图匹配等算法的数据基础。目前,获取和建立道路网络的拓扑信息非常繁琐,不仅费时、费力,并且容易出错。采用逻辑分幅物理统一的存储策略,在探讨了拓扑生成的一般算法的前提下,提出了大规模超大规模数字地图自动生成道路网络拓扑关系的步骤和算法。该算法采用网格索引检索每个子图的元素,用hash索引映射实体ID和实体对象信息,并将整图的拓扑信息生成转化为对每个子图的拓扑求取,并对跨子图道路拓扑求解特别讨论。然后,对算法复杂度进行了分析,并且通过建立不同道路数的多个虚拟道路网络子图对算法性能进行了测试和比较。最后用本算法跟踪处理了南京市道路网络(部分),并给出了结果。本算法在保留地理数据完整性的前提下,解决了常规方法的内存限制,并且具有准线性的运算代价,并能够自动恢复数据处理。Topological information in road networks is critical for GIS system to support various kinds of functionalities such as spatial analysis, optimal path finding, and map-matching. Currently, to obtain and create such information is quite time-consuming, energy-consuming, and easy to put error data into database. In this paper, based on physically-integral-logic-division storage strategy and the basic algorithm of creating topological information, an automatic algorithm is proposed for creating topological information in large-scale digital navigation maps. The given algorithm utilizes grid index to search all entities in a sub-map, and uses hash index to map geographical object ID to a geographical object. Through tracing roads in each sub-map, the topological information in the whole large-scale digital map can be automatically updated. Then, the computing complexity of the algorithm is discussed, and the performance is evaluated using simulated road network with different road numbers. Finally, a Nanjing local-area road map is processed using the algorithm, and the result is given. The proposed algorithm can resolve memory limitation issue when handling large scale digital maps, and is featured with advantages such as quasi-linear-cost, being able to recover from interruption.

关 键 词：大规模数字地图 网络 拓扑 空间索引 算法复杂度 

分 类 号：U666.1[交通运输工程—船舶及航道工程]