Subversion Repositories Code-Repo

Rev

Rev 94 | Details | Compare with Previous | Last modification | View Log | RSS feed

Rev Author Line No. Line
94 Kevin 1 
import java.util.LinkedList;
2 
import java.lang.Math;
3 
 
4 
// Somewhat generic implementation of a PR QuadTree
5 
public class PRQuadTree {
6 
	private PRQuadTreeNode root;	// Root of the PR QuadTree
7 
	private PRQuadTreeNodeFlyweight flyweight;	// Flyweight representing empty nodes
8 
	private int maxSize = 16384;	// Maximum size of the grid
9 
 
10 
	// Constructor
11 
	public PRQuadTree() {
12 
		// Initialize a singleton flyweight object
13 
		flyweight = new PRQuadTreeNodeFlyweight();
14 
		root = flyweight;
15 
	}
16 
 
17 
	// Inserts given record into the tree
18 
	public void insert(Record record) {
19 
		// Recursively call function to insert a record
20 
		this.root = insertRecursive(root, record, 0, 0, maxSize, maxSize);
21 
	}
22 
 
23 
	// Removes a record from the tree given a set of coordinates
24 
	public void remove(int x, int y) {
25 
		// Recursively call function to remove a record
26 
		this.root = removeRecursive(root, x, y, 0, 0, maxSize, maxSize);
27 
	}
28 
 
29 
	// Searches for all records within radius and returns the results in the passed list
30 
	public int search(int x, int y, int r, LinkedList<Record> results) {
31 
		// Searches for all cities in radius of given point
32 
		// Number of nodes looked at is returned while list of cities is stored in 'list'
33 
		return searchRecursive(root, x, y, r, results, 0, 0, maxSize, maxSize);
34 
	}
35 
 
36 
	// Removes all records from the tree
37 
	public void clear() {
38 
		// Set root to the flyweight to remove all nodes
39 
		root = flyweight;
40 
	}
41 
 
42 
	// Prints out all records from the tree
43 
	public void debug(PRQuadTreeNode root) {
44 
		// If root is the flyweight ...
45 
		if (root == flyweight) {
46 
			System.out.printf("E");
47 
		// If root is a leaf ...
48 
		} else if (root instanceof PRQuadTreeNodeLeaf) {
49 
			Record record = ((PRQuadTreeNodeLeaf) root).getFirst();
50 
			do {
51 
				System.out.printf("%d,%d,%s", record.getX(), record.getY(), ((CityRecord) record).getName());
52 
				record = ((PRQuadTreeNodeLeaf) root).getNext(record);
53 
			} while (record != null);
54 
			System.out.printf("|");
55 
		// If root is an internal node ...
56 
		} else {
57 
			System.out.printf("I");
58 
			debug(((PRQuadTreeNodeInternal) root).getNW());
59 
			debug(((PRQuadTreeNodeInternal) root).getNE());
60 
			debug(((PRQuadTreeNodeInternal) root).getSW());
61 
			debug(((PRQuadTreeNodeInternal) root).getSE());
62 
		}
63 
	}
64 
 
65 
	// Returns the root of the tree
66 
	public PRQuadTreeNode getRoot() {
67 
		return root;
68 
	}
69 
 
70 
	// Recursively insert a record into a root node
71 
	private PRQuadTreeNode insertRecursive(PRQuadTreeNode root, Record record, int originX, int originY, int sizeX, int sizeY) {
72 
		// If root is the flyweight, create and return a leaf node with the record
73 
		if (root == flyweight) {
74 
			PRQuadTreeNodeLeaf newLeaf = new PRQuadTreeNodeLeaf(3);
75 
			newLeaf.insert(record);
76 
			return newLeaf;
77 
		// If root is a leaf ...
78 
		} else if (root instanceof PRQuadTreeNodeLeaf) {
79 
			// Try to insert the record into the leaf, return leaf if successful
80 
			if (((PRQuadTreeNodeLeaf) root).insert(record)) {
81 
				return root;
82 
			// Otherwise all nodes in the leaf are filled
83 
			} else {
84 
				// Create new internal node and populate it with flyweights
85 
				PRQuadTreeNodeInternal newNode = new PRQuadTreeNodeInternal(flyweight);
86 
				// Get the first record to insert into the internal node
87 
				Record rec = ((PRQuadTreeNodeLeaf) root).getFirst();
88 
				do {
89 
					// Insert every record from the full leaf into the internal node
90 
					newNode = (PRQuadTreeNodeInternal) insertRecursive(newNode, rec, originX, originY, sizeX, sizeY);
91 
				} while ((rec = ((PRQuadTreeNodeLeaf) root).getNext(rec)) != null);
92 
				// Now insert the initial record into the internal node
93 
				newNode = (PRQuadTreeNodeInternal) insertRecursive(newNode, record, originX, originY, sizeX, sizeY);
94 
				// Return the newly created internal node
95 
				return newNode;
96 
			}
97 
		// If root is an internal node ...
98 
		} else {
99 
			// Insert the record into the correct quadrant
100 
			if (record.getX() < originX + sizeX/2 && record.getY() < originY + sizeY/2) {
101 
				// Insert into NW quadrant
102 
				((PRQuadTreeNodeInternal) root).setNW(insertRecursive(((PRQuadTreeNodeInternal) root).getNW(), record, originX, originY, sizeX/2, sizeY/2));
103 
			} else if (record.getX() >= originX + sizeX/2 && record.getY() < originY + sizeY/2) {
104 
				// Insert into NE quadrant
105 
				((PRQuadTreeNodeInternal) root).setNE(insertRecursive(((PRQuadTreeNodeInternal) root).getNE(), record, originX + sizeX/2, originY, sizeX - sizeX/2, sizeY/2));
106 
			} else if (record.getX() < originX + sizeX/2 && record.getY() >= originY + sizeY/2) {
107 
				// Insert into SW quadrant
108 
				((PRQuadTreeNodeInternal) root).setSW(insertRecursive(((PRQuadTreeNodeInternal) root).getSW(), record, originX, originY + sizeY/2, sizeX/2, sizeY - sizeY/2));
109 
			} else if (record.getX() >= originX + sizeX/2 && record.getY() >= originY + sizeY/2) {
110 
				// Insert into SE quadrant
111 
				((PRQuadTreeNodeInternal) root).setSE(insertRecursive(((PRQuadTreeNodeInternal) root).getSE(), record, originX + sizeX/2, originY + sizeY/2, sizeX - sizeX/2, sizeY - sizeY/2));
112 
			}
113 
			// Return the internal node after inserting a record into it
114 
			return root;
115 
		}
116 
	}
117 
 
118 
	// Recursively remove a record from a root node given the coordinates
119 
	private PRQuadTreeNode removeRecursive(PRQuadTreeNode root, int x, int y, int originX, int originY, int sizeX, int sizeY) {
120 
		// If root is the flyweight, return the root
121 
		if (root == flyweight) {
122 
			return root;
123 
		// If root is a leaf ...
124 
		} else if (root instanceof PRQuadTreeNodeLeaf) {
125 
			// Try to remove element from the leaf
126 
			((PRQuadTreeNodeLeaf) root).remove(x, y);
127 
			// If the leaf is empty, return the flyweight
128 
			if (root.isEmpty())
129 
				return flyweight;
130 
			else
131 
				return root;
132 
		// If root is an internal node ...
133 
		} else {
134 
			// Remove the record from the correct quadrant
135 
			if (x < originX + sizeX/2 && y < originY + sizeY/2) {
136 
				// Insert into NW quadrant
137 
				((PRQuadTreeNodeInternal) root).setNW(removeRecursive(((PRQuadTreeNodeInternal) root).getNW(), x, y, originX, originY, sizeX/2, sizeY/2));
138 
			} else if (x >= originX + sizeX/2 && y < originY + sizeY/2) {
139 
				// Insert into NE quadrant
140 
				((PRQuadTreeNodeInternal) root).setNE(removeRecursive(((PRQuadTreeNodeInternal) root).getNE(), x, y, originX + sizeX/2, originY, sizeX - sizeX/2, sizeY/2));
141 
			} else if (x < originX + sizeX/2 && y >= originY + sizeY/2) {
142 
				// Insert into SW quadrant
143 
				((PRQuadTreeNodeInternal) root).setSW(removeRecursive(((PRQuadTreeNodeInternal) root).getSW(), x, y, originX, originY + sizeY/2, sizeX/2, sizeY - sizeY/2));
144 
			} else if (x >= originX + sizeX/2 && y >= originY + sizeY/2) {
145 
				// Insert into SE quadrant
146 
				((PRQuadTreeNodeInternal) root).setSE(removeRecursive(((PRQuadTreeNodeInternal) root).getSE(), x, y, originX + sizeX/2, originY + sizeY/2, sizeX - sizeX/2, sizeY - sizeY/2));
147 
			}
148 
 
149 
			// Return a flyweight if the internal node is empty after removal
150 
			if (root.isEmpty()) {
151 
				return flyweight;
152 
			// Otherwise if the internal node contains all leaves or flyweights ...
153 
			} else if (((PRQuadTreeNodeInternal) root).containsAllLeavesOrFlyweight()) {
154 
				// If the number of records in subleaves is under 3, create and return a new leaf holding all records
155 
				if (((PRQuadTreeNodeInternal) root).countOfAllLeafNodes() <= 3) {
156 
					PRQuadTreeNodeLeaf newLeaf = new PRQuadTreeNodeLeaf(3);
157 
					if (((PRQuadTreeNodeInternal) root).countOfLeafNode(((PRQuadTreeNodeInternal) root).getNW()) != 0) {
158 
						newLeaf.insert((PRQuadTreeNodeLeaf)((PRQuadTreeNodeInternal) root).getNW());
159 
					}
160 
					if (((PRQuadTreeNodeInternal) root).countOfLeafNode(((PRQuadTreeNodeInternal) root).getNE()) != 0) {
161 
						newLeaf.insert((PRQuadTreeNodeLeaf)((PRQuadTreeNodeInternal) root).getNE());
162 
					}
163 
					if (((PRQuadTreeNodeInternal) root).countOfLeafNode(((PRQuadTreeNodeInternal) root).getSW()) != 0) {
164 
						newLeaf.insert((PRQuadTreeNodeLeaf)((PRQuadTreeNodeInternal) root).getSW());
165 
					}
166 
					if (((PRQuadTreeNodeInternal) root).countOfLeafNode(((PRQuadTreeNodeInternal) root).getSE()) != 0) {
167 
						newLeaf.insert((PRQuadTreeNodeLeaf)((PRQuadTreeNodeInternal) root).getSE());
168 
					}
169 
					// Return the new leaf that holds all records from the internal node
170 
					return newLeaf;
171 
				// If there are more than 3 records in subleaves, return the internal node
172 
				} else {
173 
					return root;
174 
				}
175 
			// Otherwise return the internal node if it contains internal nodes
176 
			} else {
177 
				return root;
178 
			}
179 
		}
180 
	}
181 
 
182 
	// Recursively searches for records within radius of given coordinates
183 
	private int searchRecursive(PRQuadTreeNode root, int x, int y, int radius, LinkedList<Record> results, int originX, int originY, int sizeX, int sizeY) {
184 
		// If root is the flyweight ...
185 
		if (root == flyweight) {
186 
			return 1;
187 
		// If root is a leaf ...
188 
		} else if (root instanceof PRQuadTreeNodeLeaf) {
189 
			// Loop through each record in the leaf node
190 
			Record record = ((PRQuadTreeNodeLeaf) root).getFirst();
191 
			do {	// Note: the first record can never be null (else it'll be a flyweight)
192 
				// Check each record to see if it lies within the specified radius of the point
193 
				if ((x - record.getX()) * (x - record.getX()) +
194 
						(y - record.getY()) * (y - record.getY()) <= radius * radius) {
195 
					// If it is, add it to the list
196 
					results.add(record);
197 
				}
198 
				record = ((PRQuadTreeNodeLeaf) root).getNext(record);
199 
			} while (record != null);
200 
			// Return the number of nodes looked at (1, this node)
201 
			return 1;
202 
		// If root is an internal node ...
203 
		} else {
204 
			int ret = 0;
205 
			// Check each quadrant to see if any intersect with the circle/radius
206 
			// NW quadrant
207 
			if (intersects(x, y, radius, sizeX/2.0, sizeY/2.0, originX + (sizeX-1)/4.0, originY + (sizeY-1)/4.0)) {
208 
				ret += searchRecursive(((PRQuadTreeNodeInternal) root).getNW(), x, y, radius, results, originX, originY, sizeX/2, sizeY/2);
209 
			}
210 
			// NE quadrant
211 
			if (intersects(x, y, radius, sizeX - sizeX/2.0, sizeY/2.0, originX + (sizeX-1) - (sizeX-1)/4.0, originY + (sizeY-1)/4.0)) {
212 
				ret += searchRecursive(((PRQuadTreeNodeInternal) root).getNE(), x, y, radius, results, originX + sizeX/2, originY, sizeX - sizeX/2, sizeY - sizeY/2);
213 
			}
214 
			// SW quadrant
215 
			if (intersects(x, y, radius, sizeX/2.0, sizeY - sizeY/2.0, originX + (sizeX-1)/4.0, originY + (sizeY-1) - (sizeY-1)/4.0)) {
216 
				ret += searchRecursive(((PRQuadTreeNodeInternal) root).getSW(), x, y, radius, results, originX, originY + sizeY/2, sizeX - sizeX/2, sizeY - sizeY/2);
217 
			}
218 
			// SE quadrant
219 
			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)) {
220 
				ret += searchRecursive(((PRQuadTreeNodeInternal) root).getSE(), x, y, radius, results, originX + sizeX/2, originY + sizeY/2, sizeX - sizeX/2, sizeY - sizeY/2);
221 
			}
222 
			ret++;
223 
			return ret;
224 
		}
225 
	}
226 
 
227 
	// Calculates if any points in a circle intersects with a rectangle
228 
	private boolean intersects(int cX, int cY, int cR, double rW, double rH, double rX, double rY) {
229 
		// Reference: http://stackoverflow.com/questions/401847/circle-rectangle-collision-detection-intersection/402010#402010
230 
 
231 
		// Distance from center of circle to center of rectangle
232 
		double xCircleDistance = Math.abs(cX - rX);
233 
		double yCircleDistance = Math.abs(cY - rY);
234 
 
235 
		// If Distance > width of rectangle + radius, circle cannot overlap rectangle
236 
		if (xCircleDistance > (rW/2 + cR)) {
237 
			return false;
238 
		}
239 
		if (yCircleDistance > (rH/2 + cR)) {
240 
			return false;
241 
		}
242 
 
243 
		// If distance <= width of rectangle, circle must overlap rectangle
244 
		if (xCircleDistance <= (rW/2)) {
245 
			return true;
246 
		}
247 
		if (yCircleDistance <= (rH/2)) {
248 
			return true;
249 
		}
250 
 
251 
		// Check for overlap on corners
252 
	    double cornerDist = (xCircleDistance - rW/2) * (xCircleDistance - rW/2) +
253 
	    		(yCircleDistance - rH/2) * (yCircleDistance - rH/2);
254 
 
255 
	    return (cornerDist <= cR * cR);
256 
	}
257 
}