Research On Shortest Path Algorithms Based On Raster Terrain Data

Digital Elevation Model(DEM)has become one of the main data models in spatial terrain analysis and path planning based on DEM terrain data has also become a research hotspot.The shortest path problem is a classical problem in graph theory,which has been widely used in robot path planning,traveling salesman problem(TSP),navigation of electronic map,and other aspects.As a classical algorithm for single-point source problem,Dijkstra algorithm can effectively and accurately solve global optimal path of a single-point source in a graph structure.The time complexity of the classical Dijkstra algorithm is O(n2),and it can be reduced to O(nlogn)by using minimum heap storage structure.However,for solving the shortest path problem in terrain data,the algorithm's time will increase exponentially and its efficiency will decrease with the increase of number of nodes or edges of graph.It is not enough to solve the shortest path on large-scale three-dimensional terrain data.Therefore,how to make Dijkstra algorithm better solve the shortest path of large-scale and high-precision grid DEM terrain data has become one of the important research problems.This thesis mainly completes the following work:1)A shortest path method based on fast transformation of terrain data to graph structure is proposed.According to terrain grid neighboring model,the discrete 3-dimensional terrain data is transformed into graph data.Based on DEM topographic rules,the unqualified edges between nodes are deleted through praning operation to reduce the amount of graph structure data.More importantly,the data transformation method can be realized in parallel mode.After the transformation to graph data from 3-dimensinal terrain data,Dijkstra algorithm is used to solve the shortest path based on graph.The experimental results show that our algorithm on 3-dimensional terrain data can greatly improve the efficiency of shortest path and ensure the accuracy of the shortest path.2)A network optimization method based on MapReduce for Dijkstra parallelization algorithm is proposed.According to the characteristics of serial Dijkstra algorithm data parallelization,MapReduce parallel computing framework is selected.According to the idea of breadth-first traversal,Dijkstra algorithm based on MapReduce parallelization method is realized.In this thesis,the method of merging keywords in the Shuffle phase is used to reduce the network communication overhead and optimize the efficiency of algorithm parallelization.The experimental results show that our method can improve the efficiency of parallel computing of solving the shortest path in the face of a large-scale terrain data.3)A shortest path acceleration method based on the tile pyramid model is proposed.According to tile pyramid model,DEM topographic data with different resolution in the same region are used.Then,the lower-resolution terrain data nodes are mapped to the corresponding higher-resolution terrain data nodes using hierarchical spatial relations.In this thesis,the path obtained by low-resolution terrain data is used to effectively and accurately narrow the solution range of higher-resolution terrain data.The experimental results show that our method effectively inhibits the number of nodes in the search region,thus greatly improves the efficiency of solving shortest path.