Subversion Repositories Code-Repo

Rev

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

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