An approach to graph derivation for shortest path algorithm on a three dimensional environment

• Main Author: Cubero, Cliff Anthony A.
• Format: text
• Language: English
• Published: Animo Repository 2007
• Subjects: Geographic information systems; Spatial systems; Three-dimensional modeling; Algorithms; Graph algorithms; Computer Sciences
• Online Access: https://animorepository.dlsu.edu.ph/etd_masteral/3548; https://animorepository.dlsu.edu.ph/context/etd_masteral/article/10386/viewcontent/CDTG004302_P.pdf
• Institution: De La Salle University

The research implements a shortest path algorithm on a three-dimensional model of a building. The model of the building is represented and illustrated through Geographical Information Systems (GIS) stored in spatial databases. To be able to implement a shortest path algorithm to the model, a graph will be derived from the model using a graph derivation algorithm. The system gives the user a shortest path from the current location of the user to the destination stated within the query. The nodes are categorized since the query of the user will be focused on the functionality of the destination object within the building model. The research is another variation of transforming a three-dimensional model into a graph since graphs are best derived from two-dimensional models. Also, the research contributes to the study about shortest path problems associated with three-dimensional data. The accuracy of the graph derivation algorithm is 80% according the survey conducted on 50 students of the test case, Gokongwei building. The survey was conducted to compare the optimal path as a result of the algorithm with the optimal path according to human perception. The algorithm was also tested with seven different test cases to verify the correctness of the algorithm. Keywords: Geographical Information Systems (GIS), spatial database, three-dimensional model, shortest path algorithm, graph derivation.