Near-infinitely scaling quadtree

Quadtree

/* Quadtree by Ozan Turgut ([email protected])

   A Quadtree is a structure for managing many nodes interacting in space by
   organizing them within a tree, where each node contains elements which may
   interact with other elements within the node. This is particularly useful in
   collision detection, in which a brute-force algorithm requires the checking of
   every element against every other element, regardless of their distance in space.

   This quadtree handles object in 2d space by their bounding boxes. It splits
   a node once it exceeds the object limit per-node. When a node is split, it's
   contents are divied up in to 4 smaller nodes to fulfill the per-node object limit.
   Nodes are infinitely divisible.

   If an object is inserted which exceeds the bounds of this quadtree, the quadtree
   will grow in the direction the object was inserted in order to encapsulate it. This is
   similar to a node split, except in this case we create a parent node and assign the existing
   quadtree as a quadrant within it. This allows the quadtree to contain any object, regardless of
   it's position in space.

   One function is exported which creates a quadtree given a width and height.

   The quadtree api has two methods:

   insert(bounds)
     	Inserts a bounding box (it should contain an x, y, width, and height property).

   	retrieve(bounds)
   		Retrieves a list of bounding boxes that share a node with the given bounds object.
*/

var createQuadtree = module.exports = function(width, height){
	var quadtree = new Quadtree(width, height);
	return getApi(quadtree);
};

function getApi(quadtree){
	var api = {};
	api.insert = quadtree.insert.bind(quadtree);
	api.retrieve = quadtree.retrieve.bind(quadtree);
	api.clear = quadtree.clear.bind(quadtree);
	api.getObjects = quadtree.getObjects.bind(quadtree);
	api.hasObject = quadtree.hasObject.bind(quadtree);
	return api;
}

function Quadtree(width){
	this.top = new Node(-(width / 2), -(width / 2), width, width);
}

Quadtree.prototype.insert = function(obj){
	this.top = this.top.insert(obj);
};

Quadtree.prototype.retrieve = function(obj){
	return this.top.getInteractableObjects(obj.x, obj.y, obj.width, obj.height);
};

Quadtree.prototype.clear = function(){
	this.top.clear();
};

Quadtree.prototype.getObjects = function(){
	return this.top.getObjects();
};

// Checks for collisions against a quadree
Quadtree.prototype.hasObject = function(x, y, width, height){
	var rectangles = this.top.getInteractableObjects(x, y, width, height),
		length = rectangles.length,
		index = 0,
		rectangle;

	for(; index < length; index++){
		rectangle = rectangles[index];
		
		// If there is intersection along the y-axis
		if((y < rectangle.y ?
			((y + height) > rectangle.y) :
			((rectangle.y + rectangle.height) > y)) && 
				// And if there is intersection along the x-axis
				(x < rectangle.x ?
					((x + width) > rectangle.x) :
					((rectangle.x + rectangle.width) > x))){
			
			// Then we have a collision
			return true;
		}
	}

	return false;
};

function Node(x, y, width, height, parent){
	this.objects = [];

	this.x = x;
	this.y = y;
	this.width = width;
	this.height = height;

	this.parent = parent;
}

Node.prototype.tl = void 0;
Node.prototype.tr = void 0;
Node.prototype.br = void 0;
Node.prototype.bl = void 0;

Node.prototype.OBJECT_LIMIT = 200;

Node.prototype.clear = function(){
	this.objects = [];

	if(this.tl){
		this.tl.clear();
		this.tr.clear();
		this.br.clear();
		this.bl.clear();
	}
};

Node.prototype.getObjects = function(){
	if(this.tl){
		return this.objects.concat(this.tl.getObjects(), this.tr.getObjects(), this.br.getObjects(), this.bl.getObjects());
	} else {
		return this.objects.slice();
	}
};

Node.prototype.split = function(){
	var childWidth = this.width / 2,
		childHeight = this.height / 2,
		x = this.x,
		y = this.y;

	this.tl = new Node(x, y, childWidth, childHeight, this);
	this.tr = new Node(x + childWidth, y, childWidth, childHeight, this);
	this.br = new Node(x + childWidth, y + childHeight, childWidth, childHeight, this);
	this.bl = new Node(x, y + childHeight, childWidth, childHeight, this);
};

// This can be called from ANY node in the tree, it'll return the top most node of the tree
// that can contain the element (it will grow the tree if nescessary)
Node.prototype.parentNode = function(obj){
	var node = this,
		parent;

	// If object is left of this node
	if(obj.x < node.x){
		// If object is to the top of this node
		if(obj.y < node.y){
			// Grow towards top left
			parent = node.grow(node.width, node.height);
		} else {
			// Grow towards bottom left
			parent = node.grow(node.width, 0);
		}
	// If object is right of this node
	} else if(obj.x > (node.x + node.width)){
		// If object is to the top of this node
		if(obj.y < node.y){
			// Grow towards top right
			parent = node.grow(0, node.height);
		} else {
			// Grow towards bottom right
			parent = node.grow(0, 0);
		} 

	// If object is within x-axis but top of node
	} else if(obj.y < node.y){
		// Grow towards top right (top left is just as valid though)
		parent = node.grow(0, node.height);
	// If object is within x-axis but bottom of node
	} else if(obj.y + obj.height > node.y + node.height){
		// Grow towards bottom right (bottom left is just as valid though)
		parent = node.grow(0, 0);
	}
	
	// If we had to grow, find the quadrant in the parent
	if(parent){
		return parent.parentNode(obj);
	}

	return node;
};

// Helper function which gets the quadrant node at a given x/y position
// caller function has to check to see if this node is split before calling this
Node.prototype.getQuadrantAt = function(x, y){
	var xMid = this.x + this.width / 2,
		yMid = this.y + this.height / 2;

	if(x < xMid){
		if(y < yMid){
			return this.tl.tl && this.tl.getQuadrantAt(x, y) || this.tl;
		} else {
			return this.bl.tl && this.bl.getQuadrantAt(x, y) || this.bl;
		}
	} else {
		if(y < yMid){
			return this.tr.tl && this.tr.getQuadrantAt(x, y) || this.tr;
		} else {
			return this.br.tl && this.br.getQuadrantAt(x, y) || this.br;
		}
	}
};

// Gets all the objects in quadrants within the given dimensions. 
// This assumes that the given dimensions can't be larger than a quadrant, 
// meaning it can at most touch 4 quadrants
Node.prototype.getInteractableObjects = function(x, y, width, height){
	if(!this.tl) return this.objects.slice();	

	var node = this.getQuadrant(x, y, width, height),
		quadrants = [node], // Keeps track of touched nodes
		objectsList = [node.objects],
		parent = node.parent;

	while(parent){
		quadrants.push(parent);
		objectsList.push(parent.objects);
		parent = parent.parent;
	}

	if(node.tl){
		// top left corner
		var quadrant = node.getQuadrantAt(x, y);
		if(!~quadrants.indexOf(quadrant)){
			quadrants.push(quadrant);
			objectsList.push(quadrant.objects);
		}

		// top right corner
		quadrant = node.getQuadrantAt(x + width, y);
		if(!~quadrants.indexOf(quadrant)){
			quadrants.push(quadrant);
			objectsList.push(quadrant.objects);
		}

		// bottom right corner
		quadrant = node.getQuadrantAt(x + width, y + height);
		if(!~quadrants.indexOf(quadrant)){
			quadrants.push(quadrant);
			objectsList.push(quadrant.objects);
		}

		// bottom left corner
		quadrant = node.getQuadrantAt(x, y + height);
		if(!~quadrants.indexOf(quadrant)){
			objectsList.push(quadrant.objects);
		}
	}

	return Array.prototype.concat.apply([], objectsList);
};

// Gets the quadrant a given bounding box dimensions would be inserted into
Node.prototype.getQuadrant = function(x, y, width, height){
	if(!this.tl) return this;

	var	xMid = this.x + this.width / 2,
		yMid = this.y + this.height / 2,
		topQuadrant = (y < yMid) && ((y + height) < yMid),
		bottomQuadrand = y > yMid;

	if((x < xMid) && ((x + width) < xMid)){
		if(topQuadrant){
			return this.tl.tl && this.tl.getQuadrant(x, y, width, height) || this.tl;
		} else if(bottomQuadrand){
			return this.bl.tl && this.bl.getQuadrant(x, y, width, height) || this.bl;
		}
	} else if(x > xMid){
		if(topQuadrant){
			return this.tr.tl && this.tr.getQuadrant(x, y, width, height) || this.tr;
		} else if(bottomQuadrand) {
			return this.br.tl && this.br.getQuadrant(x, y, width, height) || this.br;
		}
	}

	return this;
};

// Inserts the object to the Node, spliting or growing the tree if nescessary
// Returns the top-most node of this tree
Node.prototype.insert = function(obj){
	var quadrant,
		index,
		length,
		remainingObjects,
		objects,
		node;

	// This call will grow the tree if nescessary and return the parent node
	// if the tree doesn't need to grow, `node` will be `this`.
	node = this.parentNode(obj);
	quadrant = node.getQuadrant(obj.x, obj.y, obj.width, obj.height);

	if(quadrant !== node){
		quadrant.insert(obj);
	} else {
		objects = node.objects;
		objects.push(obj);
		index = 0;
		length = objects.length;
		if(length > node.OBJECT_LIMIT){
			// Split if not already split
			if(!node.tl) node.split();

			// For objects that don't fit to quadrants
			remainingObjects = [];
		
			// Iterate through all object and try to put them in a
			// Quadrant node, if that doesn't work, retain them	
			for(; index < length; index++){

				// Reusing the obj var
				obj = node.objects[index];
				quadrant = node.getQuadrant(obj.x, obj.y, obj.width, obj.height);
				if(quadrant !== node){
					quadrant.insert(obj);
				} else {
					remainingObjects.push(obj);
				}
			}

			node.objects = remainingObjects;
		}
	}

	return node;
};

// Creates a pre-split parent Node and attaches this Node as a
// node at the given x/y offset (so 0,0 would make this Node the top left node)
Node.prototype.grow = function(xOffset, yOffset){
	var x = this.x - xOffset,
		y = this.y - yOffset,
		parent = new Node(x, y, this.width * 2, this.height * 2);
	
	this.parent = parent;

	if(xOffset){
		if(yOffset){
			parent.br = this;
		} else {
			parent.tr = this;
		}
	} else if(yOffset) {
		parent.bl = this;
	} else {
		parent.tl = this;
	}

	parent.tl = parent.tl || new Node(x, y, this.width, this.height, this);
	parent.tr = parent.tr || new Node(x + this.width, y, this.width, this.height, this);
	parent.br = parent.br || new Node(x + this.width, y + this.height, this.width, this.height, this);
	parent.bl = parent.bl || new Node(x, y + this.height, this.width, this.height, this);

	return parent;
};

This is awesome you should publish this on NPM