We would like to efficiently search this 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.
In this project, you will implement a version of this type of 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 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.
Data Members
double x : for the x coordinate
double y : for the y coordinate
double distance(Point p) : returns the Euclidean distance between two points
boolean equals(Object o) : returns true when the two points have the same x and y coordinates.
Data Members
Point p : for the x,y coordinate
String name : for the name of the location
double distance(QuadNode q) : calculates the distance between this Location
and a QuadNode object. If the QuadNode is specific to a Location, return the distance bewteen
the two Points of the Locations. Otherwise, return the minimum distance betwee the Location's
Point and the four sides of the QuadNode.
Data Members
QuadNode[] children : to store the NW, NE, SW, and SE children of the tree
Location item : for the data, if this is a leaf
Point upperLeft : for the upper left Point of the rectangle
Point lowerRight : for the lower right Point of the rectangle
boolean isLeaf() : returns true if all of the children are null
Data Members
QuadNode root : for the top-most element of the tree
Point upperLeft : for the minimum bounds of the tree
Point lowerRight : for the maximum bounds of the tree
void add(Location 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 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<Location> proximitySearch(Location item, int k) : returns
the k closest elements to the Location item.
Create a Heap<DistHolder> to keep the distances found in a priority queue. Initialize this Heap with a DistHolder object based on the distance of the search Location and the QuadNode 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 (such that it is a leaf and the upperLeft is equal to the lower right) then add it to the ArrayList of Locations to return. Otherwise, if it is a leaf, create a DistHolder object with a new QuadNode object to represent an individual Location and add it to the Heap. If it is a QuadNode with children, then create a DistHolder object for each child based on the distance calculation of a Location vs a QuadNode, and add them to the Heap.
Data Members
QuadNode q : for the x,y coordinate
double distance : the distance between the QuadNode and current search Location
boolean isLocation : returns true if the QuadNode represents a single Location (different from isLeaf()).
int compareTo(DistHolder dh) : returns -1 if the distance in dh is larger than this.distance,
+1 if the distance is smaller than this.distance, and 0 if they are equal.
The main method of your ProximitySearch.java class should begin by asking the user for a file to load with the geographical data. The first line of this file will contain four numbers. The first two are the minimum x,y coordinates for the upper left corner, and the second two are the maximum x,y coordinates for the lower right corner. All subsequent lines will be three data values, the first being the x coordinate, the second being the y coordinate, and the third being the name of the location. Your program should add the rest of this data into a QuadTree following the QuadTree construction algorithm above.
The user is then asked for a starting location x and y, and the number of results they would like to see.
Your program should then begin searching the QuadTree for locations near to the starting location. Internally, you should use a Heap (the code is linked below) to store your DistHolder, such that the closest QuadNode is searched next, and the children of that QuadNode are placed on the Heap to be found later.
The results of this search are then displayed to the user in the format of Name, Distance, X, Y, with one entry per line.
You can test your code with the following data files:
Implement an efficient remove method for the QuadTree class. Test this method in your ProximitySearch main method.
ssh username@cs.centenary.edu to connect with the cs server.
mkdir csc234/project4
logout
scp filenames username@cs.centenary.edu:"csc234/project3"