Go to most recent revision | Blame | Compare with Previous | Last modification | View Log | Download | RSS feed
import java.util.LinkedList;import java.lang.Math;// Somewhat generic implementation of a PR QuadTreepublic class PRQuadTree {private Handle root;private Handle flyweight;private int maxSize = 16384; // Maximum size of the gridNodeSerializer serializer;// Constructorpublic PRQuadTree(MemManager memManager) {serializer = new NodeSerializer(memManager);// Initialize a singleton flyweight objectflyweight = new Handle(-1);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;serializer.clearMemory();}// Prints out all records from the tree as well as memory manager and buffer informationpublic void printDebug() {System.out.printf(">> ");debug(root);System.out.printf("\n");serializer.printDebug();}// Prints out all records below the rootpublic void debug(Handle root) {PRQuadTreeNode r = serializer.handleToNode(root);// If root is the flyweight ...if (root.getAddress() == -1) {System.out.printf("*");// If root is a leaf ...} else if (r instanceof PRQuadTreeNodeLeaf) {Record record = ((PRQuadTreeNodeLeaf) r).getFirst();do {System.out.printf("%d,%d,%s:", record.getX(), record.getY(), ((CityRecord) record).getName());record = ((PRQuadTreeNodeLeaf) r).getNext(record);} while (record != null);System.out.printf("|");// If root is an internal node ...} else {System.out.printf("(");debug(((PRQuadTreeNodeInternal) r).getNW());debug(((PRQuadTreeNodeInternal) r).getNE());debug(((PRQuadTreeNodeInternal) r).getSW());debug(((PRQuadTreeNodeInternal) r).getSE());System.out.printf(")");}}// Returns the root of the treepublic Handle getRoot() {return root;}// Recursively insert a record into a root nodeprivate Handle insertRecursive(Handle root, Record record, int originX, int originY, int sizeX, int sizeY) {PRQuadTreeNode rootNode = serializer.handleToNode(root);serializer.removeHandle(root);// If root is the flyweight, create and return a leaf node with the recordif (root.getAddress() == -1) {PRQuadTreeNodeLeaf newLeaf = new PRQuadTreeNodeLeaf(3);newLeaf.insert(record);Handle newHandle = serializer.nodeToHandle(newLeaf);return newHandle;// If root is a leaf ...} else if (rootNode instanceof PRQuadTreeNodeLeaf) {// Try to insert the record into the leaf, return leaf if successfulif (((PRQuadTreeNodeLeaf) rootNode).insert(record)) {return serializer.nodeToHandle(rootNode);// Otherwise all nodes in the leaf are filled} else {// Create new internal node and populate it with flyweightsPRQuadTreeNodeInternal newNode = new PRQuadTreeNodeInternal(flyweight, serializer);Handle newHandle = serializer.nodeToHandle(newNode);// Get the first record to insert into the internal nodeRecord rec = ((PRQuadTreeNodeLeaf) rootNode).getFirst();do {// Insert every record from the full leaf into the internal nodenewHandle = insertRecursive(newHandle, rec, originX, originY, sizeX, sizeY);rec = ((PRQuadTreeNodeLeaf) rootNode).getNext(rec);} while (rec != null);// Now insert the initial record into the internal nodenewHandle = insertRecursive(newHandle, record, originX, originY, sizeX, sizeY);// Remove the old node// Return the newly created internal nodereturn newHandle;}// 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) rootNode).setNW(insertRecursive(((PRQuadTreeNodeInternal) rootNode).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) rootNode).setNE(insertRecursive(((PRQuadTreeNodeInternal) rootNode).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) rootNode).setSW(insertRecursive(((PRQuadTreeNodeInternal) rootNode).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) rootNode).setSE(insertRecursive(((PRQuadTreeNodeInternal) rootNode).getSE(), record, originX + sizeX/2, originY + sizeY/2, sizeX - sizeX/2, sizeY - sizeY/2));}// Return the internal node after inserting a record into itreturn serializer.nodeToHandle(rootNode);}}// Recursively remove a record from a root node given the coordinatesprivate Handle removeRecursive(Handle root, int x, int y, int originX, int originY, int sizeX, int sizeY) {PRQuadTreeNode rootNode = serializer.handleToNode(root);// If root is the flyweight, return the rootif (root.getAddress() == -1) {return root;// If root is a leaf ...} else if (rootNode instanceof PRQuadTreeNodeLeaf) {if (((PRQuadTreeNodeLeaf) rootNode).find(x, y) != null) {serializer.removeHandle(root);((PRQuadTreeNodeLeaf) rootNode).remove(x, y);if (rootNode.isEmpty()) {return flyweight;}}return serializer.nodeToHandle(rootNode);// 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) rootNode).setNW(removeRecursive(((PRQuadTreeNodeInternal) rootNode).getNW(), x, y, originX, originY, sizeX/2, sizeY/2));} else if (x >= originX + sizeX/2 && y < originY + sizeY/2) {// Insert into NE quadrant((PRQuadTreeNodeInternal) rootNode).setNE(removeRecursive(((PRQuadTreeNodeInternal) rootNode).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) rootNode).setSW(removeRecursive(((PRQuadTreeNodeInternal) rootNode).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) rootNode).setSE(removeRecursive(((PRQuadTreeNodeInternal) rootNode).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 (rootNode.isEmpty()) {serializer.removeHandle(root);return flyweight;// Otherwise if the internal node contains all leaves or flyweights ...} else if (((PRQuadTreeNodeInternal) rootNode).containsAllLeavesOrFlyweight()) {// If the number of records in subleaves is under 3, create and return a new leaf holding all recordsif (((PRQuadTreeNodeInternal) rootNode).countOfAllLeafNodes() <= 3) {PRQuadTreeNodeLeaf newLeaf = new PRQuadTreeNodeLeaf(3);if (((PRQuadTreeNodeInternal) rootNode).countOfLeafNode(serializer.handleToNode(((PRQuadTreeNodeInternal) rootNode).getNW())) != 0) {newLeaf.insert((PRQuadTreeNodeLeaf)serializer.handleToNode(((PRQuadTreeNodeInternal) rootNode).getNW()));serializer.removeHandle(((PRQuadTreeNodeInternal) rootNode).getNW());}if (((PRQuadTreeNodeInternal) rootNode).countOfLeafNode(serializer.handleToNode(((PRQuadTreeNodeInternal) rootNode).getNE())) != 0) {newLeaf.insert((PRQuadTreeNodeLeaf)serializer.handleToNode(((PRQuadTreeNodeInternal) rootNode).getNE()));serializer.removeHandle(((PRQuadTreeNodeInternal) rootNode).getNE());}if (((PRQuadTreeNodeInternal) rootNode).countOfLeafNode(serializer.handleToNode(((PRQuadTreeNodeInternal) rootNode).getSW())) != 0) {newLeaf.insert((PRQuadTreeNodeLeaf)serializer.handleToNode(((PRQuadTreeNodeInternal) rootNode).getSW()));serializer.removeHandle(((PRQuadTreeNodeInternal) rootNode).getSW());}if (((PRQuadTreeNodeInternal) rootNode).countOfLeafNode(serializer.handleToNode(((PRQuadTreeNodeInternal) rootNode).getSE())) != 0) {newLeaf.insert((PRQuadTreeNodeLeaf)serializer.handleToNode(((PRQuadTreeNodeInternal) rootNode).getSE()));serializer.removeHandle(((PRQuadTreeNodeInternal) rootNode).getSE());}// Remove the internal nodeserializer.removeHandle(root);// Return the new leaf that holds all records from the internal nodereturn serializer.nodeToHandle(newLeaf);// If there are more than 3 records in subleaves, return the internal node} else {serializer.removeHandle(root);return serializer.nodeToHandle(rootNode);}// Otherwise return the internal node if it contains internal nodes} else {// Remove the internal nodeserializer.removeHandle(root);return serializer.nodeToHandle(rootNode);}}}// Recursively searches for records within radius of given coordinatesprivate int searchRecursive(Handle root, int x, int y, int radius, LinkedList<Record> results, int originX, int originY, int sizeX, int sizeY) {PRQuadTreeNode rootNode = serializer.handleToNode(root);// If root is the flyweight ...if (root.getAddress() == -1) {return 1;// If root is a leaf ...} else if (rootNode instanceof PRQuadTreeNodeLeaf) {// Loop through each record in the leaf nodeRecord record = ((PRQuadTreeNodeLeaf) rootNode).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) rootNode).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) rootNode).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) rootNode).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) rootNode).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) rootNode).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);}}