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[edit]
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 automatically mapped in the spatial map.
Input[edit]
The input comes in the form of XML [1]; a handy XmlUtility for parsing the input is provided [2].
Output[edit]
Output is stored in a DOM object that represents an XML file. A DOM document consists of a root Element that has any number of child Elements, each of which can have any number of child Elements. The DOM document building is handled by [3]. When required to print XML for output, you can use the same handy XmlUtility [4].
City Objects[edit]
You will want to create a City object to store basic information about cities; the spec recommends extending java.awt.geom.Point2D.Float [5].
Visualization[edit]
Since this is a visual project, it will help to be able to visualize your data structures. A nice graphics library called CanvasPlus [6] makes this visualization easy.
