Subversion Repositories Code-Repo

Rev

Blame | Last modification | View Log | RSS feed

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);
        }
}