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 (constructParams) {
		var _MAX_ITEMS = 4;

		var _quad,
			_center,
			_items,
			_children;

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

		// Determine the index for an item within the quad for this node.
		// If you want to use Hilbert curves for a radius search or whatnot, you
		// should change this to return values appropriate to the matrix
		// [[0,3],
		//  [1,2]]
		_itemIndex = function (item) {
			if( item.x < _center.x ) {
				if( item.y > _center.y ) {
					return 0;
				} else {
					return 1;
				}
			} else {
				if( item.y > _center.y ) {
					return 3;
				} else {
					return 2;
				}
			}
			return	( 
						( item.x < _center.x ? 1 : 0 ) +
						( 2 * ( item.y < _center.y ? 1 : 0 ) )
					);
		}

		// Initialize _children and move all items.
		_generateChildren = function() {
			_children = [];

			// Can we speed this up?  Or at least make it look nicer?
			var quads = [];
			
			quads.push({xMin: _quad.xMin,xMax: _center.x,yMin: _center.y,yMax: _quad.yMax});
			quads.push({xMin: _quad.xMin,xMax: _center.x,yMin: _quad.yMin,yMax: _center.y});
			quads.push({xMin: _center.x,xMax: _quad.xMax,yMin: _quad.yMin,yMax: _center.y});
			quads.push({xMin: _center.x,xMax: _quad.xMax,yMin: _center.y,yMax: _quad.yMax});

			for( i in quads ) {
				_children[i] = new Node({quad: quads[i]});
			}

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

		}

		this.insertItem = function (item) {

			if( _children != null ) {
				if( _children[_itemIndex(item)] == undefined ) {
					console.log("ERR?");
					console.log(_children);
				}
				_children[_itemIndex(item)].insertItem(item);
			} else {
				_items.push(item);
				if( _items.length > _MAX_ITEMS ) {
					_generateChildren();
				}
			}

		}

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

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

			return items;
		}

		this.totalItems = function () {
			var count = 0;

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

			return count;
		}

	});

	var StaticQuadTree = (function (constructParams) {
		
		var _rootNode;

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

		__construct = function () {
			if( constructParams.quad == null ) {
				throw new TypeError("Parameter object must contain object property quad");
			}
			if( constructParams.quad.xMin == null || 
				typeof constructParams.quad.xMin != "number" ) {
				throw new TypeError("Parameter object quad must contain numeric property xMin");
			}
			if( constructParams.quad.yMin == null || 
				typeof constructParams.quad.yMin != "number" ) {
				throw new TypeError("Parameter object quad must contain numeric property yMin");
			}
			if( constructParams.quad.xMax == null || 
				typeof constructParams.quad.xMax != "number" ) {
				throw new TypeError("Parameter object quad must contain numeric property xMax");
			}
			if( constructParams.quad.yMax == null || 
				typeof constructParams.quad.yMax != "number" ) {
				throw new TypeError("Parameter object quad must contain numeric property yMax");
			}

			_rootNode = new Node({quad: {
				xMin: constructParams.quad.xMin,
				xMax: constructParams.quad.xMax,
				yMin: constructParams.quad.yMin,
				yMax: constructParams.quad.yMax
			}});
		}()

		this.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");
			}
			_rootNode.insertItem(item);
		}

		// TODO
		this.fetchItemsInQuad = function (quad) {
			return _rootNode.fetchItemsInQuad(quad);
		}

		this.totalItems = function (quad) {
			return _rootNode.totalItems();
		}

	});
	
	exports.StaticQuadTree = StaticQuadTree;

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