Difference between revisions of "MeeshQuest"
Ben Zoller (talk | contribs) m (added links) |
Ben Zoller (talk | contribs) (→Data Structures: added road adjacency list) |
||
| Line 9: | Line 9: | ||
== Data Structures == | == Data Structures == | ||
| − | There are | + | There are three main concepts for this project: |
# Data Dictionary (TreeMaps and TreeSets for part 1, B-tree for parts 2 and 3) | # Data Dictionary (TreeMaps and TreeSets for part 1, B-tree for parts 2 and 3) | ||
# Spatial Map ([[PR Quadtree]] for part 1, [[PM Quadtree#PM3 Quadtree | PM3 Quadtree]] for part 2) | # Spatial Map ([[PR Quadtree]] for part 1, [[PM Quadtree#PM3 Quadtree | 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 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 mapped in the spatial map. | ||
Revision as of 02:08, 15 April 2007
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 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.
