基于导航数据最短路径算法的实现及在GIS中的应用

发布时间：2018-06-22 09:17

本文选题：GIS + 导航数据　；参考：《南京理工大学》2013年硕士论文

【摘要】：近年来,随着地理信息系统(Geographic Information System,简称GIS)和导航技术的快速发展,二者的结合在社会的各行各业中得到了广泛的应用。最短路径计算作为二者理论和应用中最基本、最关键的技术,它既是计算机科学和地理信息科学领域的一个研究热点,也是GIS和导航应用中的一个重点。广泛应用于交通、旅游、城市规划、物流、电力电子导航等多个领域。最短路径计算作为GIS网络分析功能和导航功能的计算理论基础,在实际应用中,并非纯理论上的最短路径计算,而是以具体的导航数据为出发点,考虑各种实际限制条件进行计算的。本文正是基于这一点,详细地论述了基于实际导航数据的最短路径算法的实现与优化的方法。具体包括四个方面的内容： (1)详细分析了课题使用的导航数据的格式,在此基础上对课题使用到的数据结构进行提炼和组织。 (2)对导航数据进行预处理,主要包括整理、优化、归类和排序等,最终形成课题需要的数据。 (3)结合本课题导航数据数的特点,设计了“尾点判断”算法,实现了课题中的禁止规则的计算。 (4)采用以节点为基准,建立了节点数据、路段数据及禁止数据三者之间的排序拓扑结构,采用对所有已标识节点到所有未标识节点的距离进行按升序排序的方法提高Dijkstra算法的速度和效率。并以此为基础,实现了在禁止规则限制条件下以Dijkstra算法为基础的地图上任意两点间的最短路径的计算。
[Abstract]:In recent years, with the rapid development of Geographic Information system (GIS) and navigation technology, the combination of them has been widely used in all walks of life. As the most basic and key technology in both theories and applications, shortest path calculation is not only a research hotspot in the field of computer science and geographic information science, but also a key point in GIS and navigation applications. Widely used in transportation, tourism, urban planning, logistics, power electronic navigation and other fields. As the theoretical basis of GIS network analysis function and navigation function, the calculation of shortest path is not purely theoretical calculation of shortest path, but based on specific navigation data. Taking into account various practical constraints to calculate. Based on this, the realization and optimization of the shortest path algorithm based on actual navigation data are discussed in detail in this paper. It includes four aspects: (1) the format of navigation data is analyzed in detail, on the basis of which the data structure is extracted and organized. (2) the navigation data is preprocessed. It mainly includes sorting, optimizing, classifying and sorting, and finally forms the data needed by the subject. (3) according to the characteristics of the navigation data of this subject, the algorithm of "tail point judgment" is designed. The calculation of prohibition rules in the subject is realized. (4) the sorting topology of node data, link data and forbidden data is established by taking node as the benchmark. The speed and efficiency of Dijkstra algorithm are improved by sorting the distance between all identified nodes and all unmarked nodes in ascending order. On this basis, the calculation of the shortest path between any two points on the map based on Dijkstra algorithm under the restriction of forbidden rules is realized.
【学位授予单位】：南京理工大学
【学位级别】：硕士
【学位授予年份】：2013
【分类号】：P208;TP301.6

【参考文献】