editor
32
edits
Changes
→City Objects
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 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 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 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:
The project is divided into 4 parts:
*[[Part 1]]
*[[Part 1]]
*[[Part 2]]
*[[Part 2]]
*[[Part 3]]
*[[Part 3]]
*[[Part 4]]
(Remember: if you think this page could be better -- you can change it! Click the "edit" tab up top to get started.)
(Remember: if you think this page could be better -- you can change it! Click the "edit" tab up top to get started.)
== Data Structures ==
== Data Structures ==
There are two main concepts for this project:
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, 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 automatically mapped in the spatial map.
== Input ==
== Input ==
The input comes in the form of [http://en.wikipedia.org/wiki/XML XML] [http://www.cs.umd.edu/users/meesh/420/spr07/part1/p11/node19.html]; a handy [[XmlUtility]] for parsing the input is provided [http://www.cs.umd.edu/users/meesh/420/spr07/part1/p11/node20.html].
The input comes in the form of [http://en.wikipedia.org/wiki/XML XML]; a handy [https://www.cs.umd.edu/users/meesh/420/ProjectBook/cmsc420util.jar XmlUtility] for parsing the input is provided. If you are not familiar with XML, w3schools has a great tutorial that can be found [http://www.w3schools.com/xml/ here]. The spec also has a decent amount of information on how to parse the XML.
== Output ==
== Output ==
When required to print [http://en.wikipedia.org/wiki/XML XML] for output, you can use the same handy [[XmlUtility]] [http://www.cs.umd.edu/users/meesh/420/spr07/part1/p11/node21.html].
Output is stored in a DOM object that represents an XML file. A DOM document consists of a root Element that has any number of child Elements, each of which can have any number of child Elements. The DOM document building is handled by [http://java.sun.com/j2se/1.4.2/docs/api/org/w3c/dom/Document.html org.wc3.dom.Document]. When required to print [http://en.wikipedia.org/wiki/XML XML] for output, you can use the same handy [https://www.cs.umd.edu/users/meesh/420/ProjectBook/cmsc420util.jar XmlUtility]. The spec has a decent amount of information on how to use the utility to write to the DOM object.
== City Objects ==
== City Objects ==
You will want to create a <code>City</code> object to store basic information about cities; the spec recommends extending <code>java.awt.geom.Point2D.Float</code> [http://www.cs.umd.edu/users/meesh/420/spr07/part1/p11/node23.html].
You will want to create a <code>City</code> object to store basic information about cities; the spec recommends extending <code>[http://java.sun.com/j2se/1.5.0/docs/api/java/awt/geom/Point2D.Float.html java.awt.geom.Point2D.Float]</code>.
== Visualization ==
== Visualization ==
Since this is a visual project, it will help to be able to visualize your data structures. A nice graphics library called [[CanvasPlus]] [http://www.cs.umd.edu/users/meesh/420/spr07/part1/p11/node24.html] makes this visualization easy.
Since this is a visual project, it will help to be able to visualize your data structures. A nice graphics library called [http://wam.umd.edu/~bzoller/cmsc420/doc/cmsc420/drawing/CanvasPlus.html CanvasPlus] [http://www.cs.umd.edu/users/meesh/420/spr07/part1/p11/node24.html] makes this visualization easy.