Class: 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:
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
clear
()
→ {void}
Wipes the entire 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
Classes
Documentation created on Sun Mar 15 2020