CSC234 - Project 5 - Places

Overview

In this project, you will be building an Android application that can find the N closest locations on Centenary's campus.

We would like to efficiently search a space for nearby locations. The naive way to do this would be to walk through a list of objects and sort them based on their distance from the starting location, but with 1,000,000 entries, this is prohibitive.

In this project, you will implement a version of a Spatial DataBase for proximity search using a QuadTree and a Heap. A QuadTree is a two-dimensional version of a Binary Tree, such that instead of a left and a right, there is a NW, NE, SW and SE child. The particular version we will implement is called a PR (Point Region) QuadTree. Each child is exactly 1/4 of the size of it's parent.

To implement our QuadTree and proximity search, we will need a number of smaller instantiable objects. Each object should have the usual accessor and mutator methods for each data member, and a toString and equals method. Feel free to add other objects and methods you see fit to complete this project.

GeoPoint

First, we reuse your GeoPoint object from the WallDrug project. you will need to augment the distance function so that a GeoPoint can calculate the great circle distance between itself, QTLocations and QuadNodes.

double greatCircle(ProxDist pd) : calculates the distance between this GeoPoint and a ProxDist object. If the ProxDist object a QTLocation, return the distance bewteen this and the GeoPoint of the QTLocation. Otherwise, return the minimum distance between this GeoPoint and the four sides of the QuadNode.

ProxDist<E> implements Comparable<ProxDist>

Next, we define the superclass ProxDist, which will be the parent of Location and QuadNode. This class implements the Comparable interface.

Data Members

double recentDist : for saving the distance to the most recent location.

Methods

void setDistance(double d) : saves the most recent distance
double getDistance() : returns the saved distance
int compareTo(ProxDist<E> pd) : returns a negative integer if this is less than pd, a positive integer if this is greater than pd, otherwise returns 0 if they are equal.

QTLocation<E> extends ProxDist<E>

The QTLocation object represents unique locations on the map, as well as the name of the place interest to the proximity search.

Data Members

GeoPoint p : for the x,y coordinate
E item : for the item at the location

QTLocation only needs get and set methods for p and item.

QuadNode<E> extends ProxDist<E>

The QuadNode implements similar methods to the BinaryNode class discussed in class.

Data Members

QuadNode<E>[] children : to store the NW, NE, SW, and SE children of the tree
Location<E> item : for the data, if this is a leaf
GeoPoint upperLeft : for the upper left Point of the rectangle
GeoPoint lowerRight : for the lower right Point of the rectangle

Methods

boolean isLeaf() : returns true if all of the children are null

QuadTree<E> implements SpatialDB<E>

A full QuadTree should have an add and a remove method. For this project, we will only implement the add method. The key method of the QuadTree for us is the proximitySearch algorithm.

Data Members

QuadNode<E> root : for the top-most element of the tree
GeoPoint upperLeft : for the minimum bounds of the tree
GeoPoint lowerRight : for the maximum bounds of the tree

Methods

void add(GeoPoint where, E item) : adds a Location item to this QuadTree. If the root is null, create the root QuadNode with the initial upperLeft and lowerRight bounds.
If the root is not null, determine which subquadrant holds this Location. If that child exists, then repeat, trying to add the Location to this child, otherwise create a new leaf containing the Location. If the new Location is the same as the existing Location at this QuadNode, then discard the new Location.
If the QuadNode where the new leaf was added was a leaf (contains a Location itself and had no children), then set the current item to null and recursivelly call the add method to place the current item.
ArrayList<E> proximitySearch(GeoPoint where, int k) : returns the k closest elements to the Location item.
Create a Heap<ProxDist<E>> to keep the distances found in a priority queue. Initialize this Heap with the object based on the QuadTree root. Then, while the Heap still has elements or the ArrayList of Locations found is less than k, remove the first item from the Heap. If it represents an individual Location, then add it to the ArrayList of Locations to return. Otherwise, if it is a leaf, find the distance to its Location and add this Location to the Heap. If it is a QuadNode with children, then for each calculate the distance of the query Location to each child QuadNode, and add them to the Heap.