572 lines
16 KiB
JavaScript
572 lines
16 KiB
JavaScript
// Copyright 2008 The Closure Library Authors. All Rights Reserved.
|
|
//
|
|
// Licensed under the Apache License, Version 2.0 (the "License");
|
|
// you may not use this file except in compliance with the License.
|
|
// You may obtain a copy of the License at
|
|
//
|
|
// http://www.apache.org/licenses/LICENSE-2.0
|
|
//
|
|
// Unless required by applicable law or agreed to in writing, software
|
|
// distributed under the License is distributed on an "AS-IS" BASIS,
|
|
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
|
|
// See the License for the specific language governing permissions and
|
|
// limitations under the License.
|
|
|
|
/**
|
|
* @fileoverview Datastructure: A point Quad Tree for representing 2D data. Each
|
|
* region has the same ratio as the bounds for the tree.
|
|
*
|
|
* The implementation currently requires pre-determined bounds for data as it
|
|
* can not rebalance itself to that degree.
|
|
*
|
|
* @see ../demos/quadtree.html
|
|
*/
|
|
|
|
|
|
goog.provide('goog.structs.QuadTree');
|
|
goog.provide('goog.structs.QuadTree.Node');
|
|
goog.provide('goog.structs.QuadTree.Point');
|
|
|
|
goog.require('goog.math.Coordinate');
|
|
|
|
|
|
|
|
/**
|
|
* Constructs a new quad tree.
|
|
* @param {number} minX Minimum x-value that can be held in tree.
|
|
* @param {number} minY Minimum y-value that can be held in tree.
|
|
* @param {number} maxX Maximum x-value that can be held in tree.
|
|
* @param {number} maxY Maximum y-value that can be held in tree.
|
|
* @constructor
|
|
*/
|
|
goog.structs.QuadTree = function(minX, minY, maxX, maxY) {
|
|
|
|
/**
|
|
* The root node for the quad tree.
|
|
* @type {goog.structs.QuadTree.Node}
|
|
* @private
|
|
*/
|
|
this.root_ = new goog.structs.QuadTree.Node(
|
|
minX, minY, maxX - minX, maxY - minY);
|
|
};
|
|
|
|
|
|
/**
|
|
* Count of the number of items in the tree.
|
|
* @type {number}
|
|
* @private
|
|
*/
|
|
goog.structs.QuadTree.prototype.count_ = 0;
|
|
|
|
|
|
/**
|
|
* Returns a reference to the tree's root node. Callers shouldn't modify nodes,
|
|
* directly. This is a convenience for visualization and debugging purposes.
|
|
* @return {goog.structs.QuadTree.Node} The root node.
|
|
*/
|
|
goog.structs.QuadTree.prototype.getRootNode = function() {
|
|
return this.root_;
|
|
};
|
|
|
|
|
|
/**
|
|
* Sets the value of an (x, y) point within the quad-tree.
|
|
* @param {number} x The x-coordinate.
|
|
* @param {number} y The y-coordinate.
|
|
* @param {*} value The value associated with the point.
|
|
*/
|
|
goog.structs.QuadTree.prototype.set = function(x, y, value) {
|
|
var root = this.root_;
|
|
if (x < root.x || y < root.y || x > root.x + root.w || y > root.y + root.h) {
|
|
throw Error('Out of bounds : (' + x + ', ' + y + ')');
|
|
}
|
|
if (this.insert_(root, new goog.structs.QuadTree.Point(x, y, value))) {
|
|
this.count_++;
|
|
}
|
|
};
|
|
|
|
|
|
/**
|
|
* Gets the value of the point at (x, y) or null if the point is empty.
|
|
* @param {number} x The x-coordinate.
|
|
* @param {number} y The y-coordinate.
|
|
* @param {*=} opt_default The default value to return if the node doesn't
|
|
* exist.
|
|
* @return {*} The value of the node, the default value if the node
|
|
* doesn't exist, or undefined if the node doesn't exist and no default
|
|
* has been provided.
|
|
*/
|
|
goog.structs.QuadTree.prototype.get = function(x, y, opt_default) {
|
|
var node = this.find_(this.root_, x, y);
|
|
return node ? node.point.value : opt_default;
|
|
};
|
|
|
|
|
|
/**
|
|
* Removes a point from (x, y) if it exists.
|
|
* @param {number} x The x-coordinate.
|
|
* @param {number} y The y-coordinate.
|
|
* @return {*} The value of the node that was removed, or null if the
|
|
* node doesn't exist.
|
|
*/
|
|
goog.structs.QuadTree.prototype.remove = function(x, y) {
|
|
var node = this.find_(this.root_, x, y);
|
|
if (node) {
|
|
var value = node.point.value;
|
|
node.point = null;
|
|
node.nodeType = goog.structs.QuadTree.NodeType.EMPTY;
|
|
this.balance_(node);
|
|
this.count_--;
|
|
return value;
|
|
} else {
|
|
return null;
|
|
}
|
|
};
|
|
|
|
|
|
/**
|
|
* Returns true if the point at (x, y) exists in the tree.
|
|
* @param {number} x The x-coordinate.
|
|
* @param {number} y The y-coordinate.
|
|
* @return {boolean} Whether the tree contains a point at (x, y).
|
|
*/
|
|
goog.structs.QuadTree.prototype.contains = function(x, y) {
|
|
return this.get(x, y) != null;
|
|
};
|
|
|
|
|
|
/**
|
|
* @return {boolean} Whether the tree is empty.
|
|
*/
|
|
goog.structs.QuadTree.prototype.isEmpty = function() {
|
|
return this.root_.nodeType == goog.structs.QuadTree.NodeType.EMPTY;
|
|
};
|
|
|
|
|
|
/**
|
|
* @return {number} The number of items in the tree.
|
|
*/
|
|
goog.structs.QuadTree.prototype.getCount = function() {
|
|
return this.count_;
|
|
};
|
|
|
|
|
|
/**
|
|
* Removes all items from the tree.
|
|
*/
|
|
goog.structs.QuadTree.prototype.clear = function() {
|
|
this.root_.nw = this.root_.ne = this.root_.sw = this.root_.se = null;
|
|
this.root_.nodeType = goog.structs.QuadTree.NodeType.EMPTY;
|
|
this.root_.point = null;
|
|
this.count_ = 0;
|
|
};
|
|
|
|
|
|
/**
|
|
* Returns an array containing the coordinates of each point stored in the tree.
|
|
* @return {Array.<goog.math.Coordinate?>} Array of coordinates.
|
|
*/
|
|
goog.structs.QuadTree.prototype.getKeys = function() {
|
|
var arr = [];
|
|
this.traverse_(this.root_, function(node) {
|
|
arr.push(new goog.math.Coordinate(node.point.x, node.point.y));
|
|
});
|
|
return arr;
|
|
};
|
|
|
|
|
|
/**
|
|
* Returns an array containing all values stored within the tree.
|
|
* @return {Array.<Object>} The values stored within the tree.
|
|
*/
|
|
goog.structs.QuadTree.prototype.getValues = function() {
|
|
var arr = [];
|
|
this.traverse_(this.root_, function(node) {
|
|
// Must have a point because it's a leaf.
|
|
arr.push(node.point.value);
|
|
});
|
|
return arr;
|
|
};
|
|
|
|
|
|
/**
|
|
* Clones the quad-tree and returns the new instance.
|
|
* @return {goog.structs.QuadTree} A clone of the tree.
|
|
*/
|
|
goog.structs.QuadTree.prototype.clone = function() {
|
|
var x1 = this.root_.x;
|
|
var y1 = this.root_.y;
|
|
var x2 = x1 + this.root_.w;
|
|
var y2 = y1 + this.root_.h;
|
|
var clone = new goog.structs.QuadTree(x1, y1, x2, y2);
|
|
// This is inefficient as the clone needs to recalculate the structure of the
|
|
// tree, even though we know it already. But this is easier and can be
|
|
// optimized when/if needed.
|
|
this.traverse_(this.root_, function(node) {
|
|
clone.set(node.point.x, node.point.y, node.point.value);
|
|
});
|
|
return clone;
|
|
};
|
|
|
|
|
|
/**
|
|
* Traverses the tree and calls a function on each node.
|
|
* @param {function(?, goog.math.Coordinate, goog.structs.QuadTree)} fn
|
|
* The function to call for every value. This function takes 3 arguments
|
|
* (the value, the coordinate, and the tree itself) and the return value is
|
|
* irrelevant.
|
|
* @param {Object=} opt_obj The object to be used as the value of 'this'
|
|
* within {@ code fn}.
|
|
*/
|
|
goog.structs.QuadTree.prototype.forEach = function(fn, opt_obj) {
|
|
this.traverse_(this.root_, function(node) {
|
|
var coord = new goog.math.Coordinate(node.point.x, node.point.y);
|
|
fn.call(opt_obj, node.point.value, coord, this);
|
|
});
|
|
};
|
|
|
|
|
|
/**
|
|
* Traverses the tree depth-first, with quadrants being traversed in clockwise
|
|
* order (NE, SE, SW, NW). The provided function will be called for each
|
|
* leaf node that is encountered.
|
|
* @param {goog.structs.QuadTree.Node} node The current node.
|
|
* @param {function(goog.structs.QuadTree.Node)} fn The function to call
|
|
* for each leaf node. This function takes the node as an argument, and its
|
|
* return value is irrelevant.
|
|
* @private
|
|
*/
|
|
goog.structs.QuadTree.prototype.traverse_ = function(node, fn) {
|
|
switch (node.nodeType) {
|
|
case goog.structs.QuadTree.NodeType.LEAF:
|
|
fn.call(this, node);
|
|
break;
|
|
|
|
case goog.structs.QuadTree.NodeType.POINTER:
|
|
this.traverse_(node.ne, fn);
|
|
this.traverse_(node.se, fn);
|
|
this.traverse_(node.sw, fn);
|
|
this.traverse_(node.nw, fn);
|
|
break;
|
|
}
|
|
};
|
|
|
|
|
|
/**
|
|
* Finds a leaf node with the same (x, y) coordinates as the target point, or
|
|
* null if no point exists.
|
|
* @param {goog.structs.QuadTree.Node} node The node to search in.
|
|
* @param {number} x The x-coordinate of the point to search for.
|
|
* @param {number} y The y-coordinate of the point to search for.
|
|
* @return {goog.structs.QuadTree.Node} The leaf node that matches the target,
|
|
* or null if it doesn't exist.
|
|
* @private
|
|
*/
|
|
goog.structs.QuadTree.prototype.find_ = function(node, x, y) {
|
|
switch (node.nodeType) {
|
|
case goog.structs.QuadTree.NodeType.EMPTY:
|
|
return null;
|
|
|
|
case goog.structs.QuadTree.NodeType.LEAF:
|
|
return node.point.x == x && node.point.y == y ? node : null;
|
|
|
|
case goog.structs.QuadTree.NodeType.POINTER:
|
|
return this.find_(this.getQuadrantForPoint_(node, x, y), x, y);
|
|
|
|
default:
|
|
throw Error('Invalid nodeType');
|
|
}
|
|
};
|
|
|
|
|
|
/**
|
|
* Inserts a point into the tree, updating the tree's structure if necessary.
|
|
* @param {goog.structs.QuadTree.Node} parent The parent to insert the point
|
|
* into.
|
|
* @param {goog.structs.QuadTree.Point} point The point to insert.
|
|
* @return {boolean} True if a new node was added to the tree; False if a node
|
|
* already existed with the correpsonding coordinates and had its value
|
|
* reset.
|
|
* @private
|
|
*/
|
|
goog.structs.QuadTree.prototype.insert_ = function(parent, point) {
|
|
switch (parent.nodeType) {
|
|
case goog.structs.QuadTree.NodeType.EMPTY:
|
|
this.setPointForNode_(parent, point);
|
|
return true;
|
|
|
|
case goog.structs.QuadTree.NodeType.LEAF:
|
|
if (parent.point.x == point.x && parent.point.y == point.y) {
|
|
this.setPointForNode_(parent, point);
|
|
return false;
|
|
} else {
|
|
this.split_(parent);
|
|
return this.insert_(parent, point);
|
|
}
|
|
|
|
case goog.structs.QuadTree.NodeType.POINTER:
|
|
return this.insert_(
|
|
this.getQuadrantForPoint_(parent, point.x, point.y), point);
|
|
|
|
default:
|
|
throw Error('Invalid nodeType in parent');
|
|
}
|
|
};
|
|
|
|
|
|
/**
|
|
* Converts a leaf node to a pointer node and reinserts the node's point into
|
|
* the correct child.
|
|
* @param {goog.structs.QuadTree.Node} node The node to split.
|
|
* @private
|
|
*/
|
|
goog.structs.QuadTree.prototype.split_ = function(node) {
|
|
var oldPoint = node.point;
|
|
node.point = null;
|
|
|
|
node.nodeType = goog.structs.QuadTree.NodeType.POINTER;
|
|
|
|
var x = node.x;
|
|
var y = node.y;
|
|
var hw = node.w / 2;
|
|
var hh = node.h / 2;
|
|
|
|
node.nw = new goog.structs.QuadTree.Node(x, y, hw, hh, node);
|
|
node.ne = new goog.structs.QuadTree.Node(x + hw, y, hw, hh, node);
|
|
node.sw = new goog.structs.QuadTree.Node(x, y + hh, hw, hh, node);
|
|
node.se = new goog.structs.QuadTree.Node(x + hw, y + hh, hw, hh, node);
|
|
|
|
this.insert_(node, oldPoint);
|
|
};
|
|
|
|
|
|
/**
|
|
* Attempts to balance a node. A node will need balancing if all its children
|
|
* are empty or it contains just one leaf.
|
|
* @param {goog.structs.QuadTree.Node} node The node to balance.
|
|
* @private
|
|
*/
|
|
goog.structs.QuadTree.prototype.balance_ = function(node) {
|
|
switch (node.nodeType) {
|
|
case goog.structs.QuadTree.NodeType.EMPTY:
|
|
case goog.structs.QuadTree.NodeType.LEAF:
|
|
if (node.parent) {
|
|
this.balance_(node.parent);
|
|
}
|
|
break;
|
|
|
|
case goog.structs.QuadTree.NodeType.POINTER:
|
|
var nw = node.nw, ne = node.ne, sw = node.sw, se = node.se;
|
|
var firstLeaf = null;
|
|
|
|
// Look for the first non-empty child, if there is more than one then we
|
|
// break as this node can't be balanced.
|
|
if (nw.nodeType != goog.structs.QuadTree.NodeType.EMPTY) {
|
|
firstLeaf = nw;
|
|
}
|
|
if (ne.nodeType != goog.structs.QuadTree.NodeType.EMPTY) {
|
|
if (firstLeaf) {
|
|
break;
|
|
}
|
|
firstLeaf = ne;
|
|
}
|
|
if (sw.nodeType != goog.structs.QuadTree.NodeType.EMPTY) {
|
|
if (firstLeaf) {
|
|
break;
|
|
}
|
|
firstLeaf = sw;
|
|
}
|
|
if (se.nodeType != goog.structs.QuadTree.NodeType.EMPTY) {
|
|
if (firstLeaf) {
|
|
break;
|
|
}
|
|
firstLeaf = se;
|
|
}
|
|
|
|
if (!firstLeaf) {
|
|
// All child nodes are empty: so make this node empty.
|
|
node.nodeType = goog.structs.QuadTree.NodeType.EMPTY;
|
|
node.nw = node.ne = node.sw = node.se = null;
|
|
|
|
} else if (firstLeaf.nodeType == goog.structs.QuadTree.NodeType.POINTER) {
|
|
// Only child was a pointer, therefore we can't rebalance.
|
|
break;
|
|
|
|
} else {
|
|
// Only child was a leaf: so update node's point and make it a leaf.
|
|
node.nodeType = goog.structs.QuadTree.NodeType.LEAF;
|
|
node.nw = node.ne = node.sw = node.se = null;
|
|
node.point = firstLeaf.point;
|
|
}
|
|
|
|
// Try and balance the parent as well.
|
|
if (node.parent) {
|
|
this.balance_(node.parent);
|
|
}
|
|
|
|
break;
|
|
}
|
|
};
|
|
|
|
|
|
/**
|
|
* Returns the child quadrant within a node that contains the given (x, y)
|
|
* coordinate.
|
|
* @param {goog.structs.QuadTree.Node} parent The node.
|
|
* @param {number} x The x-coordinate to look for.
|
|
* @param {number} y The y-coordinate to look for.
|
|
* @return {goog.structs.QuadTree.Node} The child quadrant that contains the
|
|
* point.
|
|
* @private
|
|
*/
|
|
goog.structs.QuadTree.prototype.getQuadrantForPoint_ = function(parent, x, y) {
|
|
var mx = parent.x + parent.w / 2;
|
|
var my = parent.y + parent.h / 2;
|
|
if (x < mx) {
|
|
return y < my ? parent.nw : parent.sw;
|
|
} else {
|
|
return y < my ? parent.ne : parent.se;
|
|
}
|
|
};
|
|
|
|
|
|
/**
|
|
* Sets the point for a node, as long as the node is a leaf or empty.
|
|
* @param {goog.structs.QuadTree.Node} node The node to set the point for.
|
|
* @param {goog.structs.QuadTree.Point} point The point to set.
|
|
* @private
|
|
*/
|
|
goog.structs.QuadTree.prototype.setPointForNode_ = function(node, point) {
|
|
if (node.nodeType == goog.structs.QuadTree.NodeType.POINTER) {
|
|
throw Error('Can not set point for node of type POINTER');
|
|
}
|
|
node.nodeType = goog.structs.QuadTree.NodeType.LEAF;
|
|
node.point = point;
|
|
};
|
|
|
|
|
|
/**
|
|
* Enumeration of node types.
|
|
* @enum {number}
|
|
*/
|
|
goog.structs.QuadTree.NodeType = {
|
|
EMPTY: 0,
|
|
LEAF: 1,
|
|
POINTER: 2
|
|
};
|
|
|
|
|
|
|
|
/**
|
|
* Constructs a new quad tree node.
|
|
* @param {number} x X-coordiate of node.
|
|
* @param {number} y Y-coordinate of node.
|
|
* @param {number} w Width of node.
|
|
* @param {number} h Height of node.
|
|
* @param {goog.structs.QuadTree.Node=} opt_parent Optional parent node.
|
|
* @constructor
|
|
*/
|
|
goog.structs.QuadTree.Node = function(x, y, w, h, opt_parent) {
|
|
/**
|
|
* The x-coordinate of the node.
|
|
* @type {number}
|
|
*/
|
|
this.x = x;
|
|
|
|
/**
|
|
* The y-coordinate of the node.
|
|
* @type {number}
|
|
*/
|
|
this.y = y;
|
|
|
|
/**
|
|
* The width of the node.
|
|
* @type {number}
|
|
*/
|
|
this.w = w;
|
|
|
|
/**
|
|
* The height of the node.
|
|
* @type {number}
|
|
*/
|
|
this.h = h;
|
|
|
|
/**
|
|
* The parent node.
|
|
* @type {goog.structs.QuadTree.Node?}
|
|
*/
|
|
this.parent = opt_parent || null;
|
|
};
|
|
|
|
|
|
/**
|
|
* The node's type.
|
|
* @type {goog.structs.QuadTree.NodeType}
|
|
*/
|
|
goog.structs.QuadTree.Node.prototype.nodeType =
|
|
goog.structs.QuadTree.NodeType.EMPTY;
|
|
|
|
|
|
/**
|
|
* The child node in the North-West quadrant.
|
|
* @type {goog.structs.QuadTree.Node?}
|
|
*/
|
|
goog.structs.QuadTree.Node.prototype.nw = null;
|
|
|
|
|
|
/**
|
|
* The child node in the North-East quadrant.
|
|
* @type {goog.structs.QuadTree.Node?}
|
|
*/
|
|
goog.structs.QuadTree.Node.prototype.ne = null;
|
|
|
|
|
|
/**
|
|
* The child node in the South-West quadrant.
|
|
* @type {goog.structs.QuadTree.Node?}
|
|
*/
|
|
goog.structs.QuadTree.Node.prototype.sw = null;
|
|
|
|
|
|
/**
|
|
* The child node in the South-East quadrant.
|
|
* @type {goog.structs.QuadTree.Node?}
|
|
*/
|
|
goog.structs.QuadTree.Node.prototype.se = null;
|
|
|
|
|
|
/**
|
|
* The point for the node, if it is a leaf node.
|
|
* @type {goog.structs.QuadTree.Point?}
|
|
*/
|
|
goog.structs.QuadTree.Node.prototype.point = null;
|
|
|
|
|
|
|
|
/**
|
|
* Creates a new point object.
|
|
* @param {number} x The x-coordinate of the point.
|
|
* @param {number} y The y-coordinate of the point.
|
|
* @param {*=} opt_value Optional value associated with the point.
|
|
* @constructor
|
|
*/
|
|
goog.structs.QuadTree.Point = function(x, y, opt_value) {
|
|
/**
|
|
* The x-coordinate for the point.
|
|
* @type {number}
|
|
*/
|
|
this.x = x;
|
|
|
|
/**
|
|
* The y-coordinate for the point.
|
|
* @type {number}
|
|
*/
|
|
this.y = y;
|
|
|
|
/**
|
|
* Optional value associated with the point.
|
|
* @type {*}
|
|
*/
|
|
this.value = goog.isDef(opt_value) ? opt_value : null;
|
|
};
|