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 datastructure that can be used to draw a picture. The basic spatial datastructure we will use is a quadtree -- a sort of 2-dimensional binary search tree.
The operations you will need to support can be gleaned from the input specification:
- createCity and deleteCity: You will need to be able to register cities with and remove them from the database. No two cities can have the same coordinates or name.
- mapCity and unmapCity: These take a city that's already registered in the database and add it to or remove it from the spatial datastructure.
- listCities: Output a sorted (XML) list of cities in the (database? spatial datastructure? graph?).
- rangeCity: This searches the spatial datastructure for all cities within a given radius of a given point.
- nearestCity: This finds the nearest city to a given point (in the database ?).
- printPRQuadtree: This outputs an XML (textual) representation of the spatial datastructure.
- saveMap: This outputs a visual representation (an image) of the spatial datastructure. See CanvasPlus.
- clearAll: Clears all of the datastructures, removing all elements.
Since this is a visual project, it will help to be able to visualize your datastructures. A nice graphics library called CanvasPlus (spec) makes this visualization easy.
