Class: Quadtree

Quadtree

new Quadtree (maxBounds, maxObjs, maxDepth) → {Quadtree}

Default Constructor

The Quadtree class implements a spatial partitioning data structure that helps accelerate queries for nearby objects in the scene. It provides functions for core operations such as inserting objects, removing objects, clearing the quadtree, and getting objects near a specified area. The quadtree is made up of QNodes which can either be split and store 4 child nodes, or have no children but contain object references.

Parameters:
Name Type Description
maxBounds Array Max bounds of World Space
maxObjs Number Max number of objects per QNode
maxDepth Number Max depth of the tree
Source:
Returns:
New instance of Quadtree
Type
Quadtree

Members

this.root :QNode

Root node for tree
Type:
Source:

this.maxObjects :int

Max number of objects per node
Type:
Source:

this.maxDepth :int

Max depth of the tree
Type:
Source:

this.quadLines :Array

Array for Quadrant Line Drawing
Type:
Source:

Methods

insert (object) → {void}

Inserts the given object into the tree
Parameters:
Name Type Description
object Object Object to be inserted into the tree
Source:
Returns:
Type
void

remove (object) → {void}

Removes the given object from the tree
Parameters:
Name Type Description
object Object Object to be removed from the tree
Source:
Returns:
Type
void

getMaxObjsPerNode () → {this.maxObjects}

Returns the max objects per node
Source:
Returns:
Max number of objects per QNode
Type
int

getMaxDepth () → {this.maxDepth}

Returns the max depth of the tree
Source:
Returns:
Max number of objects per QNode
Type
int

getQuadLines () → {this.quadLines}

Returns all of the LineRenderables to draw for drawing QuadLines
Source:
Returns:
Returns an array of LineRenderables for drawing the Quadrants
Type
Array

_traversealHelper (node, object, objBounds, d, out, func) → {void}

Recursive method that traverses the tree and executes the given function anytime it falls within the given object bounds.
Parameters:
Name Type Description
node QNode Current node you're at
object Object Object we want to do things with (add, remove, etc)
objBounds Array Boundaries of the given object for traversing the tree
d int Current depth of the tree the method is at
func Function The method’s form of output, really only used by getNearbyObjects
out Set Function to be executed once we reach the end case.
Source:
Returns:
Type
void

_insertHelper (node, object, depth, out) → {void}

Inserts a given object into the given QNode’s array and splits if it goes over the max objects allowed. Doesn’t split if the current depth is equal to the max depth. Is one of the possible functions assigned to func in _traversalHelper
Parameters:
Name Type Description
node QNode The QNode being modified
object Object The object being inserted
depth int The current depth in the tree
out Set Unused by the function
Source:
Returns:
Type
void

_removeHelper (node, object, depth, out) → {void}

Removes a given object from the given QNode’s array and adds it to the out set if it isn’t already present.
Parameters:
Name Type Description
node QNode The QNode being modified
object Object The object being removed
depth int Unused by the function
out Set Unused by the function
Source:
Returns:
Type
void

_getObjectsHelper (node, object, depth, out) → {void}

Puts the objects from the specified node into the out set if they are not already in it. Will always return the given object in the Set as well.
Parameters:
Name Type Description
node QNode The QNode to be checked
object Object Unused by the function
depth int Unused by the function
out Set Output for nearby objects
Source:
Returns:
Type
void

_calcObjectBounds (object) → {bounds}

Calculates the min and max x and y values from the given object.
Parameters:
Name Type Description
object Object Object to calculate bounds from
Source:
Returns:
Array of min and max bounds. [minX, maxX, minY, maxY]
Type
Array