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

Print

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

Share

COinS