Magellan - Map Generation of Local Land Roads and Navigation

Date of Publication


Document Type

Bachelor's Thesis

Degree Name

Bachelor of Science in Computer Science


College of Computer Studies


Computer Science

Thesis Adviser

Caslon L. Chua

Defense Panel Member

Nelson Marcos
Teresita C. Limoanco


Geographic Information Systems or GIS has seen applications in various fields, such as navigation systems and location-based systems which require scalability, mobility and availability so as to fully achieve their purpose. As a result, the trend now is moving GIS into smaller scale devices such as handhelds which satisfies the abovementioned requirements. Instead of utilizing raster data which is the traditional approach for map representation, an alternative approach is to use vector points which can consume a smaller amount of memory as compared with the first type of representation. However, current vector approaches still store entire lines or polygons as spatial data.

This research focuses on representing the map as vector data consisting only of points, specifically as an intersection point. An appropriate path finding algorithm which follows a modified breadth-first search algorithm is developed and applied in determining a logical path given a start and an end point. All these information are rendered to a map by connecting the intersection points and displayed to the user in two-dimensional graphical form, all within the constraints of limited storage, processing power, and screen size on a handheld device.

A prototype is developed and installed on a Pocket PC device to demonstrate the validity of the algorithm which can be verified through a visual map trace or through a textual path description generated by the system. The system computes or traverses street parts of Metro Manila given a source and destination and computes for a path.

Abstract Format






Accession Number


Shelf Location

Archives, The Learning Commons, 12F, Henry Sy Sr. Hall

Physical Description

1 computer optical disc ; 4 3/4 in.

This document is currently not available here.