| 0,0 → 1,289 |
|---|
| import java.util.LinkedList; |
| import java.lang.Math; |
| |
| // Somewhat generic implementation of a PR QuadTree |
| public class PRQuadTree { |
| private Handle root; |
| private Handle flyweight; |
| private int maxSize = 16384; // Maximum size of the grid |
| NodeSerializer serializer; |
| |
| // Constructor |
| public PRQuadTree(MemManager memManager) { |
| serializer = new NodeSerializer(memManager); |
| // Initialize a singleton flyweight object |
| flyweight = new Handle(-1); |
| 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; |
| serializer.clearMemory(); |
| } |
| |
| // Prints out all records from the tree as well as memory manager and buffer information |
| public void printDebug() { |
| System.out.printf(">> "); |
| debug(root); |
| System.out.printf("\n"); |
| serializer.printDebug(); |
| } |
| |
| // Prints out all records below the root |
| public 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 tree |
| public Handle getRoot() { |
| return root; |
| } |
| |
| // Recursively insert a record into a root node |
| private 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 record |
| if (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 successful |
| if (((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 flyweights |
| PRQuadTreeNodeInternal newNode = new PRQuadTreeNodeInternal(flyweight, serializer); |
| Handle newHandle = serializer.nodeToHandle(newNode); |
| // Get the first record to insert into the internal node |
| Record rec = ((PRQuadTreeNodeLeaf) rootNode).getFirst(); |
| do { |
| // Insert every record from the full leaf into the internal node |
| newHandle = insertRecursive(newHandle, rec, originX, originY, sizeX, sizeY); |
| rec = ((PRQuadTreeNodeLeaf) rootNode).getNext(rec); |
| } while (rec != null); |
| // Now insert the initial record into the internal node |
| newHandle = insertRecursive(newHandle, record, originX, originY, sizeX, sizeY); |
| // Remove the old node |
| // Return the newly created internal node |
| return newHandle; |
| } |
| // 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) 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 it |
| return serializer.nodeToHandle(rootNode); |
| } |
| } |
| |
| // Recursively remove a record from a root node given the coordinates |
| private 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 root |
| if (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 quadrant |
| if (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 removal |
| if (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 records |
| if (((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 node |
| serializer.removeHandle(root); |
| // Return the new leaf that holds all records from the internal node |
| return 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 node |
| serializer.removeHandle(root); |
| return serializer.nodeToHandle(rootNode); |
| } |
| } |
| } |
| |
| // Recursively searches for records within radius of given coordinates |
| private 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 node |
| Record 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 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) 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 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) rootNode).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) rootNode).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) rootNode).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) 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 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); |
| } |
| } |