Go to most recent revision | Blame | Compare with Previous | Last modification | View Log | RSS feed
import java.util.LinkedList;import java.lang.Math;// Somewhat generic implementation of a PR QuadTreepublic class PRQuadTree {private PRQuadTreeNode root; // Root of the PR QuadTreeprivate PRQuadTreeNodeFlyweight flyweight; // Flyweight representing empty nodesprivate int maxSize = 16384; // Maximum size of the grid// Constructorpublic PRQuadTree() {// Initialize a singleton flyweight objectflyweight = new PRQuadTreeNodeFlyweight();root = flyweight;}// Inserts given record into the treepublic void insert(Record record) {// Recursively call function to insert a recordthis.root = insertRecursive(root, record, 0, 0, maxSize, maxSize);}// Removes a record from the tree given a set of coordinatespublic void remove(int x, int y) {// Recursively call function to remove a recordthis.root = removeRecursive(root, x, y, 0, 0, maxSize, maxSize);}// Searches for all records within radius and returns the results in the passed listpublic 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 treepublic void clear() {// Set root to the flyweight to remove all nodesroot = flyweight;}// Prints out all records from the treepublic 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 treepublic PRQuadTreeNode getRoot() {return root;}// Recursively insert a record into a root nodeprivate 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 recordif (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 successfulif (((PRQuadTreeNodeLeaf) root).insert(record)) {return root;// Otherwise all nodes in the leaf are filled} else {// Create new internal node and populate it with flyweightsPRQuadTreeNodeInternal newNode = new PRQuadTreeNodeInternal(flyweight);// Get the first record to insert into the internal nodeRecord rec = ((PRQuadTreeNodeLeaf) root).getFirst();do {// Insert every record from the full leaf into the internal nodenewNode = (PRQuadTreeNodeInternal) insertRecursive(newNode, rec, originX, originY, sizeX, sizeY);} while ((rec = ((PRQuadTreeNodeLeaf) root).getNext(rec)) != null);// Now insert the initial record into the internal nodenewNode = (PRQuadTreeNodeInternal) insertRecursive(newNode, record, originX, originY, sizeX, sizeY);// Return the newly created internal nodereturn newNode;}// If root is an internal node ...} else {// Insert the record into the correct quadrantif (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 itreturn root;}}// Recursively remove a record from a root node given the coordinatesprivate PRQuadTreeNode removeRecursive(PRQuadTreeNode root, int x, int y, int originX, int originY, int sizeX, int sizeY) {// If root is the flyweight, return the rootif (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 flyweightif (root.isEmpty())return flyweight;elsereturn root;// If root is an internal node ...} else {// Remove the record from the correct quadrantif (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 removalif (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 recordsif (((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 nodereturn 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 coordinatesprivate 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 nodeRecord 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 pointif ((x - record.getX()) * (x - record.getX()) +(y - record.getY()) * (y - record.getY()) <= radius * radius) {// If it is, add it to the listresults.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 quadrantif (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 quadrantif (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 quadrantif (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 quadrantif (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 rectangleprivate 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 rectangledouble xCircleDistance = Math.abs(cX - rX);double yCircleDistance = Math.abs(cY - rY);// If Distance > width of rectangle + radius, circle cannot overlap rectangleif (xCircleDistance > (rW/2 + cR)) {return false;}if (yCircleDistance > (rH/2 + cR)) {return false;}// If distance <= width of rectangle, circle must overlap rectangleif (xCircleDistance <= (rW/2)) {return true;}if (yCircleDistance <= (rH/2)) {return true;}// Check for overlap on cornersdouble cornerDist = (xCircleDistance - rW/2) * (xCircleDistance - rW/2) +(yCircleDistance - rH/2) * (yCircleDistance - rH/2);return (cornerDist <= cR * cR);}}