Modified incremental single sink shortest path algorithm for three-dimensional city model
Date
2015-03
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Universiti Teknologi Malaysia
Abstract
Successful network-constrained navigation depends mainly on accurate geometry and semantics of a network and visualization technique for optimal navigation routes. The current navigation is primarily implemented under the framework of Geographic Information System, a two-dimensional (2D) environment which lacks effective and comprehensive consideration of multi-dimensional and dynamic navigation information along with a good visual landmark map. However this can be addressed by means of navigable surfaces on a true three-dimensional (3D) geometric model. Therefore this study has developed a prototype of an outdoor navigation application based on a practical 3D city model environment that combines two impedance factors. In the prototype, the first factor is a new technique to calculate 3D shortest path routes that support the dynamic changes of information on road networks by using a modified Dijkstra Incremental Single Sink Shortest Path algorithm. The algorithm maintains a given property P on a graph subject to dynamic changes, such as edge insertions, edge deletions or edge weight updates. Furthermore, it processes queries on property P quickly, and performs update operations faster than recomputing from beginning, as carried out by standard algorithm. Following that, the second factor automatically generates an informative map for outdoor navigation that utilizes the focus 3D map using a visual landmark dominance enhancer based on a dominance function. The prototype was then tested and evaluated with other algorithms. Results of the evaluation showed that prototype is able to compute a large city test data in less than twelve seconds with algorithm complexity . Besides that, the use of dominance function to automatically generate saliency landmarks along the shortest 3D network has improved the quality of map presentation. Thus, users also would able to recognize real world objects from the 3D model and use these prominent landmarks as navigational aids. In conclusion, the prototype has shown that the proposed impedance factors applied within the 3D city models are able to perform a true 3D navigation in comparison to existing 2D environment which only provides 2D calculation
Description
Thesis (Ph.D (Geoinformation))
Keywords
Geoinformation and real estate