Debian Codegraph @

closure-library/closure/goog/structs/quadtree.js

raw
1 // Copyright 2008 The Closure Library Authors. All Rights Reserved.
2 //
3 // Licensed under the Apache License, Version 2.0 (the "License");
4 // you may not use this file except in compliance with the License.
5 // You may obtain a copy of the License at
6 //
7 // http://www.apache.org/licenses/LICENSE-2.0
8 //
9 // Unless required by applicable law or agreed to in writing, software
10 // distributed under the License is distributed on an "AS-IS" BASIS,
11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 // See the License for the specific language governing permissions and
13 // limitations under the License.
14
15 /**
16 * @fileoverview Datastructure: A point Quad Tree for representing 2D data. Each
17 * region has the same ratio as the bounds for the tree.
18 *
19 * The implementation currently requires pre-determined bounds for data as it
20 * can not rebalance itself to that degree.
21 *
22 * @see ../demos/quadtree.html
23 */
24
25
26 goog.provide('goog.structs.QuadTree');
27 goog.provide('goog.structs.QuadTree.Node');
28 goog.provide('goog.structs.QuadTree.Point');
29
30 goog.require('goog.math.Coordinate');
31
32
33
34 /**
35 * Constructs a new quad tree.
36 * @param {number} minX Minimum x-value that can be held in tree.
37 * @param {number} minY Minimum y-value that can be held in tree.
38 * @param {number} maxX Maximum x-value that can be held in tree.
39 * @param {number} maxY Maximum y-value that can be held in tree.
40 * @constructor
41 * @final
42 */
43 goog.structs.QuadTree = function(minX, minY, maxX, maxY) {
44 /**
45 * Count of the number of items in the tree.
46 * @private {number}
47 */
48 this.count_ = 0;
49
50 /**
51 * The root node for the quad tree.
52 * @private {goog.structs.QuadTree.Node}
53 */
54 this.root_ =
55 new goog.structs.QuadTree.Node(minX, minY, maxX - minX, maxY - minY);
56 };
57
58
59 /**
60 * Returns a reference to the tree's root node. Callers shouldn't modify nodes,
61 * directly. This is a convenience for visualization and debugging purposes.
62 * @return {goog.structs.QuadTree.Node} The root node.
63 */
64 goog.structs.QuadTree.prototype.getRootNode = function() {
65 return this.root_;
66 };
67
68
69 /**
70 * Sets the value of an (x, y) point within the quad-tree.
71 * @param {number} x The x-coordinate.
72 * @param {number} y The y-coordinate.
73 * @param {*} value The value associated with the point.
74 */
75 goog.structs.QuadTree.prototype.set = function(x, y, value) {
76 var root = this.root_;
77 if (x < root.x || y < root.y || x > root.x + root.w || y > root.y + root.h) {
78 throw new Error('Out of bounds : (' + x + ', ' + y + ')');
79 }
80 if (this.insert_(root, new goog.structs.QuadTree.Point(x, y, value))) {
81 this.count_++;
82 }
83 };
84
85
86 /**
87 * Gets the value of the point at (x, y) or null if the point is empty.
88 * @param {number} x The x-coordinate.
89 * @param {number} y The y-coordinate.
90 * @param {*=} opt_default The default value to return if the node doesn't
91 * exist.
92 * @return {*} The value of the node, the default value if the node
93 * doesn't exist, or undefined if the node doesn't exist and no default
94 * has been provided.
95 */
96 goog.structs.QuadTree.prototype.get = function(x, y, opt_default) {
97 var node = this.find_(this.root_, x, y);
98 return node ? node.point.value : opt_default;
99 };
100
101
102 /**
103 * Removes a point from (x, y) if it exists.
104 * @param {number} x The x-coordinate.
105 * @param {number} y The y-coordinate.
106 * @return {*} The value of the node that was removed, or null if the
107 * node doesn't exist.
108 */
109 goog.structs.QuadTree.prototype.remove = function(x, y) {
110 var node = this.find_(this.root_, x, y);
111 if (node) {
112 var value = node.point.value;
113 node.point = null;
114 node.nodeType = goog.structs.QuadTree.NodeType.EMPTY;
115 this.balance_(node);
116 this.count_--;
117 return value;
118 } else {
119 return null;
120 }
121 };
122
123
124 /**
125 * Returns true if the point at (x, y) exists in the tree.
126 * @param {number} x The x-coordinate.
127 * @param {number} y The y-coordinate.
128 * @return {boolean} Whether the tree contains a point at (x, y).
129 */
130 goog.structs.QuadTree.prototype.contains = function(x, y) {
131 return this.get(x, y) != null;
132 };
133
134
135 /**
136 * @return {boolean} Whether the tree is empty.
137 */
138 goog.structs.QuadTree.prototype.isEmpty = function() {
139 return this.root_.nodeType == goog.structs.QuadTree.NodeType.EMPTY;
140 };
141
142
143 /**
144 * @return {number} The number of items in the tree.
145 */
146 goog.structs.QuadTree.prototype.getCount = function() {
147 return this.count_;
148 };
149
150
151 /**
152 * Removes all items from the tree.
153 */
154 goog.structs.QuadTree.prototype.clear = function() {
155 this.root_.nw = this.root_.ne = this.root_.sw = this.root_.se = null;
156 this.root_.nodeType = goog.structs.QuadTree.NodeType.EMPTY;
157 this.root_.point = null;
158 this.count_ = 0;
159 };
160
161
162 /**
163 * Returns an array containing the coordinates of each point stored in the tree.
164 * @return {!Array<goog.math.Coordinate?>} Array of coordinates.
165 */
166 goog.structs.QuadTree.prototype.getKeys = function() {
167 var arr = [];
168 this.traverse_(this.root_, function(node) {
169 arr.push(new goog.math.Coordinate(node.point.x, node.point.y));
170 });
171 return arr;
172 };
173
174
175 /**
176 * Returns an array containing all values stored within the tree.
177 * @return {!Array<Object>} The values stored within the tree.
178 */
179 goog.structs.QuadTree.prototype.getValues = function() {
180 var arr = [];
181 this.traverse_(this.root_, function(node) {
182 // Must have a point because it's a leaf.
183 arr.push(node.point.value);
184 });
185 return arr;
186 };
187
188
189 /**
190 * Clones the quad-tree and returns the new instance.
191 * @return {!goog.structs.QuadTree} A clone of the tree.
192 */
193 goog.structs.QuadTree.prototype.clone = function() {
194 var x1 = this.root_.x;
195 var y1 = this.root_.y;
196 var x2 = x1 + this.root_.w;
197 var y2 = y1 + this.root_.h;
198 var clone = new goog.structs.QuadTree(x1, y1, x2, y2);
199 // This is inefficient as the clone needs to recalculate the structure of the
200 // tree, even though we know it already. But this is easier and can be
201 // optimized when/if needed.
202 this.traverse_(this.root_, function(node) {
203 clone.set(node.point.x, node.point.y, node.point.value);
204 });
205 return clone;
206 };
207
208
209 /**
210 * Traverses the tree and calls a function on each node.
211 * @param {function(?, goog.math.Coordinate, goog.structs.QuadTree)} fn
212 * The function to call for every value. This function takes 3 arguments
213 * (the value, the coordinate, and the tree itself) and the return value is
214 * irrelevant.
215 * @param {Object=} opt_obj The object to be used as the value of 'this'
216 * within {@ code fn}.
217 */
218 goog.structs.QuadTree.prototype.forEach = function(fn, opt_obj) {
219 this.traverse_(this.root_, function(node) {
220 var coord = new goog.math.Coordinate(node.point.x, node.point.y);
221 fn.call(opt_obj, node.point.value, coord, this);
222 });
223 };
224
225
226 /**
227 * Traverses the tree depth-first, with quadrants being traversed in clockwise
228 * order (NE, SE, SW, NW). The provided function will be called for each
229 * leaf node that is encountered.
230 * @param {goog.structs.QuadTree.Node} node The current node.
231 * @param {function(this:goog.structs.QuadTree, goog.structs.QuadTree.Node)} fn
232 * The function to call for each leaf node. This function takes the node as
233 * an argument, and its return value is irrelevant.
234 * @private
235 */
236 goog.structs.QuadTree.prototype.traverse_ = function(node, fn) {
237 switch (node.nodeType) {
238 case goog.structs.QuadTree.NodeType.LEAF:
239 fn.call(this, node);
240 break;
241
242 case goog.structs.QuadTree.NodeType.POINTER:
243 this.traverse_(node.ne, fn);
244 this.traverse_(node.se, fn);
245 this.traverse_(node.sw, fn);
246 this.traverse_(node.nw, fn);
247 break;
248 }
249 };
250
251
252 /**
253 * Finds a leaf node with the same (x, y) coordinates as the target point, or
254 * null if no point exists.
255 * @param {goog.structs.QuadTree.Node} node The node to search in.
256 * @param {number} x The x-coordinate of the point to search for.
257 * @param {number} y The y-coordinate of the point to search for.
258 * @return {goog.structs.QuadTree.Node} The leaf node that matches the target,
259 * or null if it doesn't exist.
260 * @private
261 */
262 goog.structs.QuadTree.prototype.find_ = function(node, x, y) {
263 switch (node.nodeType) {
264 case goog.structs.QuadTree.NodeType.EMPTY:
265 return null;
266
267 case goog.structs.QuadTree.NodeType.LEAF:
268 return node.point.x == x && node.point.y == y ? node : null;
269
270 case goog.structs.QuadTree.NodeType.POINTER:
271 return this.find_(this.getQuadrantForPoint_(node, x, y), x, y);
272
273 default:
274 throw new Error('Invalid nodeType');
275 }
276 };
277
278
279 /**
280 * Inserts a point into the tree, updating the tree's structure if necessary.
281 * @param {goog.structs.QuadTree.Node} parent The parent to insert the point
282 * into.
283 * @param {goog.structs.QuadTree.Point} point The point to insert.
284 * @return {boolean} True if a new node was added to the tree; False if a node
285 * already existed with the correpsonding coordinates and had its value
286 * reset.
287 * @private
288 */
289 goog.structs.QuadTree.prototype.insert_ = function(parent, point) {
290 switch (parent.nodeType) {
291 case goog.structs.QuadTree.NodeType.EMPTY:
292 this.setPointForNode_(parent, point);
293 return true;
294
295 case goog.structs.QuadTree.NodeType.LEAF:
296 if (parent.point.x == point.x && parent.point.y == point.y) {
297 this.setPointForNode_(parent, point);
298 return false;
299 } else {
300 this.split_(parent);
301 return this.insert_(parent, point);
302 }
303
304 case goog.structs.QuadTree.NodeType.POINTER:
305 return this.insert_(
306 this.getQuadrantForPoint_(parent, point.x, point.y), point);
307
308 default:
309 throw new Error('Invalid nodeType in parent');
310 }
311 };
312
313
314 /**
315 * Converts a leaf node to a pointer node and reinserts the node's point into
316 * the correct child.
317 * @param {goog.structs.QuadTree.Node} node The node to split.
318 * @private
319 */
320 goog.structs.QuadTree.prototype.split_ = function(node) {
321 var oldPoint = node.point;
322 node.point = null;
323
324 node.nodeType = goog.structs.QuadTree.NodeType.POINTER;
325
326 var x = node.x;
327 var y = node.y;
328 var hw = node.w / 2;
329 var hh = node.h / 2;
330
331 node.nw = new goog.structs.QuadTree.Node(x, y, hw, hh, node);
332 node.ne = new goog.structs.QuadTree.Node(x + hw, y, hw, hh, node);
333 node.sw = new goog.structs.QuadTree.Node(x, y + hh, hw, hh, node);
334 node.se = new goog.structs.QuadTree.Node(x + hw, y + hh, hw, hh, node);
335
336 this.insert_(node, oldPoint);
337 };
338
339
340 /**
341 * Attempts to balance a node. A node will need balancing if all its children
342 * are empty or it contains just one leaf.
343 * @param {goog.structs.QuadTree.Node} node The node to balance.
344 * @private
345 */
346 goog.structs.QuadTree.prototype.balance_ = function(node) {
347 switch (node.nodeType) {
348 case goog.structs.QuadTree.NodeType.EMPTY:
349 case goog.structs.QuadTree.NodeType.LEAF:
350 if (node.parent) {
351 this.balance_(node.parent);
352 }
353 break;
354
355 case goog.structs.QuadTree.NodeType.POINTER:
356 var nw = node.nw, ne = node.ne, sw = node.sw, se = node.se;
357 var firstLeaf = null;
358
359 // Look for the first non-empty child, if there is more than one then we
360 // break as this node can't be balanced.
361 if (nw.nodeType != goog.structs.QuadTree.NodeType.EMPTY) {
362 firstLeaf = nw;
363 }
364 if (ne.nodeType != goog.structs.QuadTree.NodeType.EMPTY) {
365 if (firstLeaf) {
366 break;
367 }
368 firstLeaf = ne;
369 }
370 if (sw.nodeType != goog.structs.QuadTree.NodeType.EMPTY) {
371 if (firstLeaf) {
372 break;
373 }
374 firstLeaf = sw;
375 }
376 if (se.nodeType != goog.structs.QuadTree.NodeType.EMPTY) {
377 if (firstLeaf) {
378 break;
379 }
380 firstLeaf = se;
381 }
382
383 if (!firstLeaf) {
384 // All child nodes are empty: so make this node empty.
385 node.nodeType = goog.structs.QuadTree.NodeType.EMPTY;
386 node.nw = node.ne = node.sw = node.se = null;
387
388 } else if (firstLeaf.nodeType == goog.structs.QuadTree.NodeType.POINTER) {
389 // Only child was a pointer, therefore we can't rebalance.
390 break;
391
392 } else {
393 // Only child was a leaf: so update node's point and make it a leaf.
394 node.nodeType = goog.structs.QuadTree.NodeType.LEAF;
395 node.nw = node.ne = node.sw = node.se = null;
396 node.point = firstLeaf.point;
397 }
398
399 // Try and balance the parent as well.
400 if (node.parent) {
401 this.balance_(node.parent);
402 }
403
404 break;
405 }
406 };
407
408
409 /**
410 * Returns the child quadrant within a node that contains the given (x, y)
411 * coordinate.
412 * @param {goog.structs.QuadTree.Node} parent The node.
413 * @param {number} x The x-coordinate to look for.
414 * @param {number} y The y-coordinate to look for.
415 * @return {goog.structs.QuadTree.Node} The child quadrant that contains the
416 * point.
417 * @private
418 */
419 goog.structs.QuadTree.prototype.getQuadrantForPoint_ = function(parent, x, y) {
420 var mx = parent.x + parent.w / 2;
421 var my = parent.y + parent.h / 2;
422 if (x < mx) {
423 return y < my ? parent.nw : parent.sw;
424 } else {
425 return y < my ? parent.ne : parent.se;
426 }
427 };
428
429
430 /**
431 * Sets the point for a node, as long as the node is a leaf or empty.
432 * @param {goog.structs.QuadTree.Node} node The node to set the point for.
433 * @param {goog.structs.QuadTree.Point} point The point to set.
434 * @private
435 */
436 goog.structs.QuadTree.prototype.setPointForNode_ = function(node, point) {
437 if (node.nodeType == goog.structs.QuadTree.NodeType.POINTER) {
438 throw new Error('Can not set point for node of type POINTER');
439 }
440 node.nodeType = goog.structs.QuadTree.NodeType.LEAF;
441 node.point = point;
442 };
443
444
445 /**
446 * Enumeration of node types.
447 * @enum {number}
448 */
449 goog.structs.QuadTree.NodeType = {
450 EMPTY: 0,
451 LEAF: 1,
452 POINTER: 2
453 };
454
455
456
457 /**
458 * Constructs a new quad tree node.
459 * @param {number} x X-coordiate of node.
460 * @param {number} y Y-coordinate of node.
461 * @param {number} w Width of node.
462 * @param {number} h Height of node.
463 * @param {goog.structs.QuadTree.Node=} opt_parent Optional parent node.
464 * @constructor
465 * @final
466 */
467 goog.structs.QuadTree.Node = function(x, y, w, h, opt_parent) {
468 /**
469 * The x-coordinate of the node.
470 * @type {number}
471 */
472 this.x = x;
473
474 /**
475 * The y-coordinate of the node.
476 * @type {number}
477 */
478 this.y = y;
479
480 /**
481 * The width of the node.
482 * @type {number}
483 */
484 this.w = w;
485
486 /**
487 * The height of the node.
488 * @type {number}
489 */
490 this.h = h;
491
492 /**
493 * The parent node.
494 * @type {goog.structs.QuadTree.Node?}
495 */
496 this.parent = opt_parent || null;
497 };
498
499
500 /**
501 * The node's type.
502 * @type {goog.structs.QuadTree.NodeType}
503 */
504 goog.structs.QuadTree.Node.prototype.nodeType =
505 goog.structs.QuadTree.NodeType.EMPTY;
506
507
508 /**
509 * The child node in the North-West quadrant.
510 * @type {goog.structs.QuadTree.Node?}
511 */
512 goog.structs.QuadTree.Node.prototype.nw = null;
513
514
515 /**
516 * The child node in the North-East quadrant.
517 * @type {goog.structs.QuadTree.Node?}
518 */
519 goog.structs.QuadTree.Node.prototype.ne = null;
520
521
522 /**
523 * The child node in the South-West quadrant.
524 * @type {goog.structs.QuadTree.Node?}
525 */
526 goog.structs.QuadTree.Node.prototype.sw = null;
527
528
529 /**
530 * The child node in the South-East quadrant.
531 * @type {goog.structs.QuadTree.Node?}
532 */
533 goog.structs.QuadTree.Node.prototype.se = null;
534
535
536 /**
537 * The point for the node, if it is a leaf node.
538 * @type {goog.structs.QuadTree.Point?}
539 */
540 goog.structs.QuadTree.Node.prototype.point = null;
541
542
543
544 /**
545 * Creates a new point object.
546 * @param {number} x The x-coordinate of the point.
547 * @param {number} y The y-coordinate of the point.
548 * @param {*=} opt_value Optional value associated with the point.
549 * @constructor
550 * @final
551 */
552 goog.structs.QuadTree.Point = function(x, y, opt_value) {
553 /**
554 * The x-coordinate for the point.
555 * @type {number}
556 */
557 this.x = x;
558
559 /**
560 * The y-coordinate for the point.
561 * @type {number}
562 */
563 this.y = y;
564
565 /**
566 * Optional value associated with the point.
567 * @type {*}
568 */
569 this.value = goog.isDef(opt_value) ? opt_value : null;
570 };