MeeshQuest
The idea of the MeeshQuest project is to emulate some of the functionality of map sites like MapQuest or Google Maps. We will need a database of cities, which are just named points in the plane. From this, we want to be able to draw pictures of a given region showing the cities contained in that region. We will get cities from the database and insert them into a spatial data structure that can be used to draw a picture. The basic spatial data structure we will use is a quadtree -- a sort of 2-dimensional binary search tree.
The project is divided into 3 parts:
(Remember: if you think this page could be better -- you can change it! Click the "edit" tab up top to get started.)
Data Structures
There are three main concepts for this project:
- Data Dictionary (TreeMaps and TreeSets for part 1, B-tree for parts 2 and 3)
- Spatial Map (PR Quadtree for part 1, PM3 Quadtree for part 2)
- Road Adjacency List
An important concept to remember is that the data dictionary is not the same as the spatial map. If you create a city, it is not mapped in the spatial map.
Input
The input comes in the form of XML [1]; a handy XmlUtility for parsing the input is provided [2].
Output
When required to print XML for output, you can use the same handy XmlUtility [3].
City Objects
You will want to create a City object to store basic information about cities; the spec recommends extending java.awt.geom.Point2D.Float [4].
Visualization
Since this is a visual project, it will help to be able to visualize your data structures. A nice graphics library called CanvasPlus [5] makes this visualization easy.