Date of Publication
2007
Document Type
Master's Thesis
Degree Name
Master of Science in Computer Science
Subject Categories
Computer Sciences
College
College of Computer Studies
Department/Unit
Computer Science
Thesis Adviser
Caslon Chua
Defense Panel Chair
Nelson Marcos
Defense Panel Member
Rigan P. Ap-apid
Calson Chua
Abstract/Summary
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.
Abstract Format
html
Language
English
Format
Accession Number
TG04302; CDTG004302
Shelf Location
Archives, The Learning Commons, 12F Henry Sy Sr. Hall
Physical Description
vii, 79 leaves ; 28 cm. + 1 computer optical disc.
Keywords
Geographic information systems; Spatial systems; Three-dimensional modeling; Algorithms; Graph algorithms
Upload Full Text
wf_yes
Recommended Citation
Cubero, C. A. (2007). An approach to graph derivation for shortest path algorithm on a three dimensional environment. Retrieved from https://animorepository.dlsu.edu.ph/etd_masteral/3548