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.

(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 two main concepts for this project:

1. Data Dictionary (TreeMaps and TreeSets for part 1)
   • Related commands:
     • createCity
     • deleteCity
     • listCities
     • clearAll

1. Spatial Map (PR Quadtree for part 1)
   • Related commands:
     • deleteCity (if the city is mapped)
     • mapCity
     • unmapCity
     • rangeCities
     • nearestCity
     • saveMap
     • clearAll

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.

Basic Operations

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. (The spec refers to this database as a "dictionary.") 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 data structure.
• listCities: Output a sorted (XML) list of cities in the database.
• rangeCities: This searches the spatial data structure for all cities within a given radius of a given point.
• nearestCity: This finds the nearest city to a given point in the spatial map.
• printPRQuadtree: This outputs an XML (textual) representation of the spatial data structure.
• saveMap: This outputs a visual representation (an image) of the spatial data structure. See CanvasPlus.
• clearAll: Clears all of the data structures, removing all elements.

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 probably 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.

Part 1 (Due Friday March 30)

From the spec:

For the first part of your project, you will implement a data dictionary that supports both city names and city coordinates as keys. You will also need to write an interpreter that will be able to handle basic XML commands. Your data dictionary can be written by merely playing games with comparators, thereby convincing a good old TreeMap or TreeSet to act like it's something else altogether. Commands will require you to insert verified cities into the spatial map, and to delete them from the spatial map. The role of the spatial map is to support range searches where, given a location in 2-d space and a radius, you will find all the cities within that circle, including on the border. These types of operations are not efficient using the treemap of coordinates.

Web Accessibility