CSC234 - Project 5 - Places

Materials

Places Android Project

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 need a GeoPoint object that can keep track of the latitude and longitude. You must implement two methods. One to calculate the Great Circle Distance between two GeoPoints and one to calculate the Bearing between two GeoPoints on the Earth. 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<E>>

Next, we define the superclass ProxDist, which will be the parent of QTLocation 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 the recentDist of pd, a positive integer if this is greater than the recentDist of 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

Methods

boolean getLoc() : returns the GeoPoint p
boolean getItem() : returns the E item
boolean setLoc() : sets the GeoPoint p
boolean setItem() : sets the E item

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
QTLocation<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 needs both an add and a remove 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 QTLocation 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 QTLocation to this child, otherwise create a new leaf containing the Location. If the new QTLocation is the same as the existing Location at this QuadNode, then discard the new QTLocation.
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.
QTLocation remove(GeoPoint where) : removes the closest QTLocation in this QuadTree to item.
Use the proximitySearch below to find the closest item, then search for it in the tree. Remove the leaf QuadNode pointing to this item from the parent. If this results in a QuadNode with only one child, then remove this last child and set its QTLocation to the QTLocation of its only child, and repeat for this node's parent.
ArrayList<E> proximitySearch(GeoPoint where, int k) : returns the k closest elements to the QTLocation 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 QTLocations found is less than k, remove the first item from the Heap. If it represents an individual QTLocation, then add it to the ArrayList of QTLocations to return. Otherwise, if it is a leaf, find the distance to its QTLocation and add this QTLocation to the Heap. If it is a QuadNode with children, then for each calculate the distance of the query QTLocation to each child QuadNode, and add them to the Heap.