Difference between revisions of "MeeshQuest"

From CMSC 420
(clarification on data structures for part 1)
 
(19 intermediate revisions by 3 users not shown)
Line 1: Line 1:
 
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 project is divided into 4 parts:
 +
*[[Part 1]]
 +
*[[Part 2]]
 +
*[[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 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, [[PM Quadtree#PM3 Quadtree | PM3 Quadtree]] for part 2)
 +
# Road Adjacency List
  
There are two main concepts for this project:
+
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.
# Data Dictionary (TreeMaps and TreeSets for part 1)
 
#* Related commands:
 
#** createCity
 
#** deleteCity
 
#** listCities
 
#** clearAll
 
 
 
# 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 [http://www.cs.umd.edu/users/meesh/420/spr07/part1/p11/node26.html 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 ==
 
== Input ==
  
The input comes in the form of 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 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 probably 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.
 
 
== Part 1 (Due Friday March 30) ==
 
 
 
From the spec:
 
 
 
<blockquote>
 
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.
 
</blockquote>
 

Latest revision as of 01:27, 6 February 2017

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 4 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:

  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)
  3. 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; a handy XmlUtility for parsing the input is provided. If you are not familiar with XML, w3schools has a great tutorial that can be found here. The spec also has a decent amount of information on how to parse the XML.

Output[edit]

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 org.wc3.dom.Document. When required to print XML for output, you can use the same handy XmlUtility. The spec has a decent amount of information on how to use the utility to write to the DOM object.

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.

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 [1] makes this visualization easy.