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

摘要：

道路网络的拓扑信息是GIS进行空间分析,如最优路径、地图匹配等算法的数据基础.目前,获取和建立道路网络的拓扑信息非常繁琐,不仅费时、费力,并且容易出错.采用逻辑分幅物理统一的存储策略,在探讨了拓扑生成的一般算法的前提下,提出了大规模超大规模数字地图自动生成道路网络拓扑关系的步骤和算法.该算法采用网格索引检索每个子图的元素,用hash索引映射实体ID和实体对象信息,并将整图的拓扑信息生成转化为对每个子图的拓扑求取,并对跨子图道路拓扑求解特别讨论.然后,对算法复杂度进行了分析,并且通过建立不同道路数的多个虚拟道路网络子图对算法性能进行了测试和比较.最后用本算法跟踪处理了南京市道路网络(部分),并给出了结果.本算法在保留地理数据完整性的前提下,解决了常规方法的内存限制,并且具有准线性的运算代价,并能够自动恢复数据处理.

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

所属期刊栏目：17

分类号：U666.1 (船舶工程)

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

在线出版日期：2010-03-02（万方平台首次上网日期，不代表论文的发表时间）

页数：共7页

页码：670-676