Bureaucrats, editor
7
edits
Changes
From CMSC 420
Initial edit
The idea of the MeeshQuest project is to emulate some of the functionality of map sites like [http://www.mapquest.com/ MapQuest] or [http://maps.google.com/ 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 [http://www.cs.umd.edu/users/meesh/420/spr07/part1/p11/node26.html 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]] [http://www.cs.umd.edu/users/meesh/420/spr07/part1/p11/node24.html (spec)] makes this visualization easy.
The operations you will need to support can be gleaned from the [http://www.cs.umd.edu/users/meesh/420/spr07/part1/p11/node26.html 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]] [http://www.cs.umd.edu/users/meesh/420/spr07/part1/p11/node24.html (spec)] makes this visualization easy.
