gistfile1.txt

/**
 * Static Quad Tree
 * This is a one-way tree that only allows insertion for maximum efficiency.
 * @author David Overcash <funnylookinhat@gmail.com>
 * Credit to https://github.com/mikechambers/ExamplesByMesh for a great example.
 */
(function(exports) {

  var Node = function (xMin,xMax,yMin,yMax) {
		this._quad = {
			xMin: xMin,
			xMax: xMax,
			yMin: yMin,
			yMax: yMax
		};
		this._center = {
			x: Math.floor( this._quad.xMin + ( ( this._quad.xMax - this._quad.xMin ) / 2 ) ),
			y: Math.floor( this._quad.yMin + ( ( this._quad.yMax - this._quad.yMin ) / 2 ) )
		}
		this._items = [];
		this._children = null;
	}

	Node.MAX_ITEMS = 4;

	Node._pointInQuad = function(point,quad) {
		return 	(
					point.x >= quad.xMin &&
					point.x <= quad.xMax &&
					point.y >= quad.yMin &&
					point.y <= quad.yMax
				);
	}

	Node.prototype._itemIndex = function (item) {
		return	( 
					( item.y < _center.y ? 1 : 0 ) +
					( item.x < _center.x ? 0 : 2 )
				);
	}

	Node.prototype._generateChildren = function() {
		this._children = [];

		// Can we speed this up?  Or at least make it look nicer?
		
		this._children[0] = new Node(this._quad.xMin, this._center.x, this._center.y, this._quad.yMax);
		this._children[1] = new Node(this._quad.xMin, this._center.x, this._quad.yMin, this._center.y);
		this._children[2] = new Node(this._center.x, this._quad.xMax, this._quad.yMin, this._center.y);
		this._children[0] = new Node(this._center.x, this._quad.xMax, this._center.y, this._quad.yMax);

		var item = null;
		while( this._items.length ) {
			item = this._items.pop();
			this._children[this._itemIndex(item)].insertItem(item);
		}
		
		_items = null;
	}

	Node.prototype.insertItem = function (item) {
		if( this._children != null ) {
			this._children[this._itemIndex(item)].insertItem(item);
		} else {
			this._items.push(item);
			if( this._items.length > Node._MAX_ITEMS ) {
				this._generateChildren();
			}
		}
	}

	Node.prototype.fetchItemsInQuad = function (quad) {
		var items = [];

		if( Node._pointInQuad(this._center,quad) ) {
			if( this._items != null ) {
				items.concat(this._items);
			} else {
				for( i in this._children ) {
					items.concat(this._children[i].fetchItemsInQuad(quad));
				}
			}
		}

		return items;
	}

	Node.prototype.totalItems = function () {
		var count = 0;

		if( this._items != null ) {
			count += this._items.length;
		} else {
			for ( i in this._children ) {
				count += this._children[i].totalItems();
			}
		}

		return count;
	}

	var StaticQuadTree =  function (xMin,xMax,yMin,yMax) {
		if( xMin == null || 
			typeof xMin != "number" ) {
			throw new TypeError("xMin must be numeric.");
		}
		if( yMin == null || 
			typeof yMin != "number" ) {
			throw new TypeError("yMin must be numeric.");
		}
		if( xMax == null || 
			typeof xMax != "number" ) {
			throw new TypeError("xMax must be numeric.");
		}
		if( yMax == null || 
			typeof yMax != "number" ) {
			throw new TypeError("yMax must be numeric.");
		}
		this._rootNode = new Node(xMin, xMax, yMin, yMax);
	}

	StaticQuadTree.prototype.insertItem = function (item) {
		if( typeof item != "object" ) {
			throw new TypeError("Parameter item must be an object");
		}
		if( item.x == null ||
			typeof item.x != "number" ) {
			throw new TypeError("Parameter item must contain numeric property x");
		}
		if( item.y == null ||
			typeof item.y != "number" ) {
			throw new TypeError("Parameter item must container numeric property y");
		}
		this._rootNode.insertItem(item);
	}

	StaticQuadTree.prototype.fetchItemsInQuad = function (quad) {
		return this._rootNode.fetchItemsInQuad(quad);
	}
	
	StaticQuadTree.prototype.totalItems = function() {
		return this._rootNode.totalItems();
	}		
	
	exports.Node = Node;
	exports.StaticQuadTree = StaticQuadTree;

})(typeof global === "undefined" ? window : exports);