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 spec is divided into 3 parts:

• Part 1
• Part 2
• Part 3

(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, B-tree for parts 2 and 3)
2. Spatial Map (PR Quadtree for part 1, PM3 Quadtree for part 2)

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

Web Accessibility