A circuitous shortest path algorithm labeled by previous-arc vector group in navigation GIS

Lin Yang; Shunping Zhou; Bo Wan; Xiaofang Pan

doi:10.1117/12.812847

5 November 2008 A circuitous shortest path algorithm labeled by previous-arc vector group in navigation GIS

Lin Yang, Shunping Zhou, Bo Wan, Xiaofang Pan

Proceedings Volume 7144, Geoinformatics 2008 and Joint Conference on GIS and Built Environment: The Built Environment and Its Dynamics; 71442Q (2008) https://doi.org/10.1117/12.812847
Event: Geoinformatics 2008 and Joint Conference on GIS and Built Environment: Geo-Simulation and Virtual GIS Environments, 2008, Guangzhou, China

Abstract

Path planning, as the core module of navigation GIS, its efficiency and accuracy has a crucial impact on the navigation system. General shortest-path algorithm is based on the classic node label-setting algorithm, which does not consider the situation of including circuitous road sections. Therefore, sometimes it will neglect the closer circuitous path at hand but find the farther path or even failed to find any path in the real road network with complicated traffic restrictions. For the sake of finding more accurate path, this paper presents a circuitous shortest path algorithm labeled by previous-arc vector group. Firstly, we generate incremental network topological relationships according to two random positions travelers are interested in. Secondly, we construct a vector group including previous arc, and seek the way by labeling the previous-arc vector group. Finally, the shortest path in the sense of mathematics which may contain circuitous road sections can be acquired. An experimental work has been done with this algorithm using the map of Beijing, which showed that the algorithm not only well improved the accuracy of the shortest path result between the two random positions in the road network, but also kept the efficiency of the classic node labeled algorithm.

Citation Download Citation

Lin Yang, Shunping Zhou, Bo Wan, and Xiaofang Pan "A circuitous shortest path algorithm labeled by previous-arc vector group in navigation GIS", Proc. SPIE 7144, Geoinformatics 2008 and Joint Conference on GIS and Built Environment: The Built Environment and Its Dynamics, 71442Q (5 November 2008); https://doi.org/10.1117/12.812847

ACCESS THE FULL ARTICLE

INSTITUTIONAL
Select your institution to access the SPIE Digital Library.

SELECT YOUR INSTITUTION

PERSONAL
Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.

PERSONAL SIGN IN

No SPIE Account? Create one

PURCHASE THIS CONTENT

SUBSCRIBE TO DIGITAL LIBRARY

50 downloads per 1-year subscription

Members: $195

Non-members: $335 ADD TO CART

25 downloads per 1 - year subscription

Members: $145

Non-members: $250 ADD TO CART

PURCHASE SINGLE ARTICLE

Includes PDF, HTML & Video, when available