Quadtree

Quadtree

A Quadtree implementation that supports collision detection for rectangles.

Constructor

new Quadtree(bounds, optionsopt)

Parameters:
Name Type Attributes Description
bounds Rectangle

The outer bounds of the region
options object <optional>

Additional options which configure the Quadtree

Properties
Name Type Attributes Default Description
maxObjects number <optional>
 20

The maximum number of objects per node
maxDepth number <optional>
 4

The maximum number of levels within the root Quadtree
_depth number <optional>
 0

The depth level of the sub-tree. For internal use
_root number <optional>

The root of the quadtree. For internal use

Members

all

Return an array of all the objects in the Quadtree (recursive)

bounds :Rectangle

The bounding rectangle of the region

Type:

depth :number

The depth of this node within the root Quadtree

Type:
  • number

INDICES :number

A constant that enumerates the index order of the quadtree nodes from top-left to bottom-right.

Type:
  • number

maxDepth :number

The maximum number of levels that the base quadtree is allowed

Type:
  • number

maxObjects :number

The maximum number of objects allowed within this node before it must split

Type:
  • number

nodes :Array.<Quadtree>

Children of this node

Type:

objects :Array.<QuadtreeObject>

The objects contained at this level of the tree

Type:

root :Quadtree

The root Quadtree

Type:

Methods

clear() → {Quadtree}

Clear the quadtree of all existing contents

Returns:

The cleared Quadtree

Type
Quadtree

getAdjacentNodes() → {Array.<Quadtree>}

Identify all nodes which are adjacent to this one within the parent Quadtree.

Returns:
Type
Array.<Quadtree>

getChildNodes(rect) → {Array.<Quadtree>}

Obtain the child nodes within the current node which a rectangle belongs to. Note that this function is not recursive, it only returns nodes at the current or child level.

Parameters:
Name Type Description
rect Rectangle

The target rectangle.
Returns:

The Quadtree nodes to which the target rectangle belongs

Type
Array.<Quadtree>

getLeafNodes(rect) → {Array.<Quadtree>}

Obtain the leaf nodes to which a target rectangle belongs. This traverses the quadtree recursively obtaining the final nodes which have no children.

Parameters:
Name Type Description
rect Rectangle

The target rectangle.
Returns:

The Quadtree nodes to which the target rectangle belongs

Type
Array.<Quadtree>

getObjects(rect, _sopt) → {Set}

Get all the objects which could collide with the provided rectangle

Parameters:
Name Type Attributes Description
rect NormalizedRectangle

The normalized target rectangle
_s Set <optional>

The existing result set, for internal use.
Returns:

The objects in the Quadtree which represent potential collisions

Type
Set

insert(obj) → {Array.<Quadtree>}

Add a rectangle object to the tree

Parameters:
Name Type Description
obj QuadtreeObject

The object being inserted
Returns:

The Quadtree nodes the object was added to.

Type
Array.<Quadtree>

remove(target) → {Quadtree}

Remove an object from the quadtree

Parameters:
Name Type Description
target *

The quadtree target being removed
Returns:

The Quadtree for method chaining

Type
Quadtree

split() → {Quadtree}

Split this node into 4 sub-nodes.

Returns:

The split Quadtree

Type
Quadtree

visualize(objectsopt)

Visualize the nodes and objects in the quadtree

Parameters:
Name Type Attributes Description
objects boolean <optional>

Visualize the rectangular bounds of objects in the Quadtree. Default is false.