0,0 → 1,257 |
import java.util.LinkedList; |
import java.lang.Math; |
|
// Somewhat generic implementation of a PR QuadTree |
public class PRQuadTree { |
private PRQuadTreeNode root; // Root of the PR QuadTree |
private PRQuadTreeNodeFlyweight flyweight; // Flyweight representing empty nodes |
private int maxSize = 16384; // Maximum size of the grid |
|
// Constructor |
public PRQuadTree() { |
// Initialize a singleton flyweight object |
flyweight = new PRQuadTreeNodeFlyweight(); |
root = flyweight; |
} |
|
// Inserts given record into the tree |
public void insert(Record record) { |
// Recursively call function to insert a record |
this.root = insertRecursive(root, record, 0, 0, maxSize, maxSize); |
} |
|
// Removes a record from the tree given a set of coordinates |
public void remove(int x, int y) { |
// Recursively call function to remove a record |
this.root = removeRecursive(root, x, y, 0, 0, maxSize, maxSize); |
} |
|
// Searches for all records within radius and returns the results in the passed list |
public int search(int x, int y, int r, LinkedList<Record> results) { |
// Searches for all cities in radius of given point |
// Number of nodes looked at is returned while list of cities is stored in 'list' |
return searchRecursive(root, x, y, r, results, 0, 0, maxSize, maxSize); |
} |
|
// Removes all records from the tree |
public void clear() { |
// Set root to the flyweight to remove all nodes |
root = flyweight; |
} |
|
// Prints out all records from the tree |
public void debug(PRQuadTreeNode root) { |
// If root is the flyweight ... |
if (root == flyweight) { |
System.out.printf("E"); |
// If root is a leaf ... |
} else if (root instanceof PRQuadTreeNodeLeaf) { |
Record record = ((PRQuadTreeNodeLeaf) root).getFirst(); |
do { |
System.out.printf("%d,%d,%s", record.getX(), record.getY(), ((CityRecord) record).getName()); |
record = ((PRQuadTreeNodeLeaf) root).getNext(record); |
} while (record != null); |
System.out.printf("|"); |
// If root is an internal node ... |
} else { |
System.out.printf("I"); |
debug(((PRQuadTreeNodeInternal) root).getNW()); |
debug(((PRQuadTreeNodeInternal) root).getNE()); |
debug(((PRQuadTreeNodeInternal) root).getSW()); |
debug(((PRQuadTreeNodeInternal) root).getSE()); |
} |
} |
|
// Returns the root of the tree |
public PRQuadTreeNode getRoot() { |
return root; |
} |
|
// Recursively insert a record into a root node |
private PRQuadTreeNode insertRecursive(PRQuadTreeNode root, Record record, int originX, int originY, int sizeX, int sizeY) { |
// If root is the flyweight, create and return a leaf node with the record |
if (root == flyweight) { |
PRQuadTreeNodeLeaf newLeaf = new PRQuadTreeNodeLeaf(3); |
newLeaf.insert(record); |
return newLeaf; |
// If root is a leaf ... |
} else if (root instanceof PRQuadTreeNodeLeaf) { |
// Try to insert the record into the leaf, return leaf if successful |
if (((PRQuadTreeNodeLeaf) root).insert(record)) { |
return root; |
// Otherwise all nodes in the leaf are filled |
} else { |
// Create new internal node and populate it with flyweights |
PRQuadTreeNodeInternal newNode = new PRQuadTreeNodeInternal(flyweight); |
// Get the first record to insert into the internal node |
Record rec = ((PRQuadTreeNodeLeaf) root).getFirst(); |
do { |
// Insert every record from the full leaf into the internal node |
newNode = (PRQuadTreeNodeInternal) insertRecursive(newNode, rec, originX, originY, sizeX, sizeY); |
} while ((rec = ((PRQuadTreeNodeLeaf) root).getNext(rec)) != null); |
// Now insert the initial record into the internal node |
newNode = (PRQuadTreeNodeInternal) insertRecursive(newNode, record, originX, originY, sizeX, sizeY); |
// Return the newly created internal node |
return newNode; |
} |
// If root is an internal node ... |
} else { |
// Insert the record into the correct quadrant |
if (record.getX() < originX + sizeX/2 && record.getY() < originY + sizeY/2) { |
// Insert into NW quadrant |
((PRQuadTreeNodeInternal) root).setNW(insertRecursive(((PRQuadTreeNodeInternal) root).getNW(), record, originX, originY, sizeX/2, sizeY/2)); |
} else if (record.getX() >= originX + sizeX/2 && record.getY() < originY + sizeY/2) { |
// Insert into NE quadrant |
((PRQuadTreeNodeInternal) root).setNE(insertRecursive(((PRQuadTreeNodeInternal) root).getNE(), record, originX + sizeX/2, originY, sizeX - sizeX/2, sizeY/2)); |
} else if (record.getX() < originX + sizeX/2 && record.getY() >= originY + sizeY/2) { |
// Insert into SW quadrant |
((PRQuadTreeNodeInternal) root).setSW(insertRecursive(((PRQuadTreeNodeInternal) root).getSW(), record, originX, originY + sizeY/2, sizeX/2, sizeY - sizeY/2)); |
} else if (record.getX() >= originX + sizeX/2 && record.getY() >= originY + sizeY/2) { |
// Insert into SE quadrant |
((PRQuadTreeNodeInternal) root).setSE(insertRecursive(((PRQuadTreeNodeInternal) root).getSE(), record, originX + sizeX/2, originY + sizeY/2, sizeX - sizeX/2, sizeY - sizeY/2)); |
} |
// Return the internal node after inserting a record into it |
return root; |
} |
} |
|
// Recursively remove a record from a root node given the coordinates |
private PRQuadTreeNode removeRecursive(PRQuadTreeNode root, int x, int y, int originX, int originY, int sizeX, int sizeY) { |
// If root is the flyweight, return the root |
if (root == flyweight) { |
return root; |
// If root is a leaf ... |
} else if (root instanceof PRQuadTreeNodeLeaf) { |
// Try to remove element from the leaf |
((PRQuadTreeNodeLeaf) root).remove(x, y); |
// If the leaf is empty, return the flyweight |
if (root.isEmpty()) |
return flyweight; |
else |
return root; |
// If root is an internal node ... |
} else { |
// Remove the record from the correct quadrant |
if (x < originX + sizeX/2 && y < originY + sizeY/2) { |
// Insert into NW quadrant |
((PRQuadTreeNodeInternal) root).setNW(removeRecursive(((PRQuadTreeNodeInternal) root).getNW(), x, y, originX, originY, sizeX/2, sizeY/2)); |
} else if (x >= originX + sizeX/2 && y < originY + sizeY/2) { |
// Insert into NE quadrant |
((PRQuadTreeNodeInternal) root).setNE(removeRecursive(((PRQuadTreeNodeInternal) root).getNE(), x, y, originX + sizeX/2, originY, sizeX - sizeX/2, sizeY/2)); |
} else if (x < originX + sizeX/2 && y >= originY + sizeY/2) { |
// Insert into SW quadrant |
((PRQuadTreeNodeInternal) root).setSW(removeRecursive(((PRQuadTreeNodeInternal) root).getSW(), x, y, originX, originY + sizeY/2, sizeX/2, sizeY - sizeY/2)); |
} else if (x >= originX + sizeX/2 && y >= originY + sizeY/2) { |
// Insert into SE quadrant |
((PRQuadTreeNodeInternal) root).setSE(removeRecursive(((PRQuadTreeNodeInternal) root).getSE(), x, y, originX + sizeX/2, originY + sizeY/2, sizeX - sizeX/2, sizeY - sizeY/2)); |
} |
|
// Return a flyweight if the internal node is empty after removal |
if (root.isEmpty()) { |
return flyweight; |
// Otherwise if the internal node contains all leaves or flyweights ... |
} else if (((PRQuadTreeNodeInternal) root).containsAllLeavesOrFlyweight()) { |
// If the number of records in subleaves is under 3, create and return a new leaf holding all records |
if (((PRQuadTreeNodeInternal) root).countOfAllLeafNodes() <= 3) { |
PRQuadTreeNodeLeaf newLeaf = new PRQuadTreeNodeLeaf(3); |
if (((PRQuadTreeNodeInternal) root).countOfLeafNode(((PRQuadTreeNodeInternal) root).getNW()) != 0) { |
newLeaf.insert((PRQuadTreeNodeLeaf)((PRQuadTreeNodeInternal) root).getNW()); |
} |
if (((PRQuadTreeNodeInternal) root).countOfLeafNode(((PRQuadTreeNodeInternal) root).getNE()) != 0) { |
newLeaf.insert((PRQuadTreeNodeLeaf)((PRQuadTreeNodeInternal) root).getNE()); |
} |
if (((PRQuadTreeNodeInternal) root).countOfLeafNode(((PRQuadTreeNodeInternal) root).getSW()) != 0) { |
newLeaf.insert((PRQuadTreeNodeLeaf)((PRQuadTreeNodeInternal) root).getSW()); |
} |
if (((PRQuadTreeNodeInternal) root).countOfLeafNode(((PRQuadTreeNodeInternal) root).getSE()) != 0) { |
newLeaf.insert((PRQuadTreeNodeLeaf)((PRQuadTreeNodeInternal) root).getSE()); |
} |
// Return the new leaf that holds all records from the internal node |
return newLeaf; |
// If there are more than 3 records in subleaves, return the internal node |
} else { |
return root; |
} |
// Otherwise return the internal node if it contains internal nodes |
} else { |
return root; |
} |
} |
} |
|
// Recursively searches for records within radius of given coordinates |
private int searchRecursive(PRQuadTreeNode root, int x, int y, int radius, LinkedList<Record> results, int originX, int originY, int sizeX, int sizeY) { |
// If root is the flyweight ... |
if (root == flyweight) { |
return 1; |
// If root is a leaf ... |
} else if (root instanceof PRQuadTreeNodeLeaf) { |
// Loop through each record in the leaf node |
Record record = ((PRQuadTreeNodeLeaf) root).getFirst(); |
do { // Note: the first record can never be null (else it'll be a flyweight) |
// Check each record to see if it lies within the specified radius of the point |
if ((x - record.getX()) * (x - record.getX()) + |
(y - record.getY()) * (y - record.getY()) <= radius * radius) { |
// If it is, add it to the list |
results.add(record); |
} |
record = ((PRQuadTreeNodeLeaf) root).getNext(record); |
} while (record != null); |
// Return the number of nodes looked at (1, this node) |
return 1; |
// If root is an internal node ... |
} else { |
int ret = 0; |
// Check each quadrant to see if any intersect with the circle/radius |
// NW quadrant |
if (intersects(x, y, radius, sizeX/2.0, sizeY/2.0, originX + (sizeX-1)/4.0, originY + (sizeY-1)/4.0)) { |
ret += searchRecursive(((PRQuadTreeNodeInternal) root).getNW(), x, y, radius, results, originX, originY, sizeX/2, sizeY/2); |
} |
// NE quadrant |
if (intersects(x, y, radius, sizeX - sizeX/2.0, sizeY/2.0, originX + (sizeX-1) - (sizeX-1)/4.0, originY + (sizeY-1)/4.0)) { |
ret += searchRecursive(((PRQuadTreeNodeInternal) root).getNE(), x, y, radius, results, originX + sizeX/2, originY, sizeX - sizeX/2, sizeY - sizeY/2); |
} |
// SW quadrant |
if (intersects(x, y, radius, sizeX/2.0, sizeY - sizeY/2.0, originX + (sizeX-1)/4.0, originY + (sizeY-1) - (sizeY-1)/4.0)) { |
ret += searchRecursive(((PRQuadTreeNodeInternal) root).getSW(), x, y, radius, results, originX, originY + sizeY/2, sizeX - sizeX/2, sizeY - sizeY/2); |
} |
// SE quadrant |
if (intersects(x, y, radius, sizeX - sizeX/2.0, sizeY - sizeY/2.0, originX + (sizeX-1) - (sizeX-1)/4.0, originY + (sizeY-1) - (sizeY-1)/4.0)) { |
ret += searchRecursive(((PRQuadTreeNodeInternal) root).getSE(), x, y, radius, results, originX + sizeX/2, originY + sizeY/2, sizeX - sizeX/2, sizeY - sizeY/2); |
} |
ret++; |
return ret; |
} |
} |
|
// Calculates if any points in a circle intersects with a rectangle |
private boolean intersects(int cX, int cY, int cR, double rW, double rH, double rX, double rY) { |
// Reference: http://stackoverflow.com/questions/401847/circle-rectangle-collision-detection-intersection/402010#402010 |
|
// Distance from center of circle to center of rectangle |
double xCircleDistance = Math.abs(cX - rX); |
double yCircleDistance = Math.abs(cY - rY); |
|
// If Distance > width of rectangle + radius, circle cannot overlap rectangle |
if (xCircleDistance > (rW/2 + cR)) { |
return false; |
} |
if (yCircleDistance > (rH/2 + cR)) { |
return false; |
} |
|
// If distance <= width of rectangle, circle must overlap rectangle |
if (xCircleDistance <= (rW/2)) { |
return true; |
} |
if (yCircleDistance <= (rH/2)) { |
return true; |
} |
|
// Check for overlap on corners |
double cornerDist = (xCircleDistance - rW/2) * (xCircleDistance - rW/2) + |
(yCircleDistance - rH/2) * (yCircleDistance - rH/2); |
|
return (cornerDist <= cR * cR); |
} |
} |