Difference between revisions of "MeeshQuest"
Ben Zoller (talk | contribs) (→Data Structures: added road adjacency list) |
|||
| Line 14: | Line 14: | ||
# Road Adjacency List | # 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 mapped in the spatial map. | + | 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 == | == Input == | ||
Revision as of 07:31, 1 October 2009
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]
When required to print XML for output, you can use the same handy XmlUtility [3].
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 [4].
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 [5] makes this visualization easy.
