Options
All
  • Public
  • Public/Protected
  • All
Menu

Class Quadtree<ObjectsType>

Class representing a Quadtree node.

example
const tree = new Quadtree({
  width: 100,
  height: 100,
  x: 0,           // optional, default:  0
  y: 0,           // optional, default:  0
  maxObjects: 10, // optional, default: 10
  maxLevels: 4,   // optional, default:  4
});
example

Typescript: If you like to be explicit, you optionally can pass in a generic type for objects to be stored in the Quadtree:

class GameEntity extends Rectangle {
  ...
}
const tree = new Quadtree<GameEntity>({
  width: 100,
  height: 100,
});

Type parameters

Hierarchy

  • Quadtree

Index

Constructors

Properties

Methods

Constructors

constructor

Properties

bounds

bounds: NodeGeometry

The numeric boundaries of this node.

readonly

level

level: number

The level of this node.

defaultvalue

0

readonly

maxLevels

maxLevels: number

Total max nesting levels of the root Quadtree node.

defaultvalue

4

readonly

maxObjects

maxObjects: number

Max objects this node can hold before it splits.

defaultvalue

10

readonly

nodes

nodes: Quadtree<ObjectsType>[]

Subnodes of this node

defaultvalue

[]

readonly

objects

objects: ObjectsType[]

Array of objects in this node.

defaultvalue

[]

readonly

Methods

clear

  • clear(): void

  • Clear the Quadtree.

    example
    const tree = new Quadtree({ width: 100, height: 100 });
    tree.insert(new Circle({ x: 25, y: 25, r: 10 }));
    tree.clear();
    console.log(tree); // tree.objects and tree.nodes are empty

    Returns void

getIndex

  • Get the quadrant (subnode indexes) an object belongs to.

    example

    Mostly for internal use but you can call it like so:

    const tree = new Quadtree({ width: 100, height: 100 });
    const rectangle = new Rectangle({ x: 25, y: 25, width: 10, height: 10 });
    const indexes = tree.getIndex(rectangle);
    console.log(indexes); // [1]

    Parameters

    Returns number[]

    Array containing indexes of intersecting subnodes (0-3 = top-right, top-left, bottom-left, bottom-right).

insert

  • insert(obj: ObjectsType): void

  • Insert an object into the node. If the node exceeds the capacity, it will split and add all objects to their corresponding subnodes.

    example

    you can use any shape here (or object with a qtIndex method, see README):

    const tree = new Quadtree({ width: 100, height: 100 });
    tree.insert(new Rectangle({ x: 25, y: 25, width: 10, height: 10, data: 'data' }));
    tree.insert(new Circle({ x: 25, y: 25, r: 10, data: 512 }));
    tree.insert(new Line({ x1: 25, y1: 25, x2: 60, y2: 40, data: { custom: 'property'} }));

    Parameters

    • obj: ObjectsType

      Object to be added.

    Returns void

join

  • join(): ObjectsType[]

  • The opposite of a split: try to merge and dissolve subnodes.

    beta
    internal

    Mostly for internal use! You should only call this yourself if you know what you are doing.

    example

    Manual join:

    const tree = new Quadtree({ width: 100, height: 100 });
    tree.split();
    console.log(tree.nodes.length); // 4
    tree.join();
    console.log(tree.nodes.length); // 0

    Returns ObjectsType[]

    The objects from this node and all subnodes combined.

remove

  • remove(obj: ObjectsType, fast?: boolean): boolean

  • Remove an object from the tree. If you have to remove many objects, consider clearing the entire tree and rebuilding it or use the fast flag to cleanup after the last removal.

    beta
    example
    const tree = new Quadtree({ width: 100, height: 100 });
    const circle = new Circle({ x: 25, y: 25, r: 10, data: 512 });
    tree.insert(circle);
    tree.remove(circle);
    example

    Bulk fast removals and final cleanup:

    const tree = new Quadtree({ width: 100, height: 100 });
    const rects = [];
     for(let i=0; i<20; i++) {
       rects[i] = new Rectangle({ x: 25, y: 25, width: 50, height: 50 });
       tree.insert(rects[i]);
     }
     for(let i=rects.length-1; i>0; i--) {
       //fast=true – just remove the object (may leaves vacant subnodes)
       //fast=false – cleanup empty subnodes (default)
       const fast = (i !== 0);
       tree.remove(rects[i], fast); 
     }

    Parameters

    • obj: ObjectsType

      Object to be removed.

    • fast: boolean = false

      Set to true to increase performance temporarily by preventing cleanup of empty subnodes (optional, default: false).

    Returns boolean

    Weather or not the object was removed from THIS node (no recursive check).

retrieve

  • Return all objects that could collide with the given geometry.

    example

    Just like insert, you can use any shape here (or object with a qtIndex method, see README):

    tree.retrieve(new Rectangle({ x: 25, y: 25, width: 10, height: 10, data: 'data' }));
    tree.retrieve(new Circle({ x: 25, y: 25, r: 10, data: 512 }));
    tree.retrieve(new Line({ x1: 25, y1: 25, x2: 60, y2: 40, data: { custom: 'property'} }));

    Parameters

    Returns ObjectsType[]

    Array containing all detected objects.

split

  • split(): void

  • Split the node into 4 subnodes.

    internal

    Mostly for internal use! You should only call this yourself if you know what you are doing.

    example

    Manual split:

    const tree = new Quadtree({ width: 100, height: 100 });
    tree.split();
    console.log(tree); // now tree has four subnodes

    Returns void

update

  • update(obj: ObjectsType, fast?: boolean): void

  • Update an object already in the tree (shorthand for remove and insert). If you have to update many objects, consider clearing and rebuilding the entire tree or use the fast flag to cleanup after the last update.

    beta
    example
    const tree = new Quadtree({ width: 100, height: 100, maxObjects: 1 });
    const rect1 = new Rectangle({ x: 25, y: 25, width: 10, height: 10 });
    const rect2 = new Rectangle({ x: 25, y: 25, width: 10, height: 10 });
    tree.insert(rect1);
    tree.insert(rect2);
    rect1.x = 75;
    rect1.y = 75;
    tree.update(rect1);
    example

    Bulk fast update and final cleanup:

    const tree = new Quadtree({ width: 100, height: 100 });
    const rects = [];
     for(let i=0; i<20; i++) {
       rects[i] = new Rectangle({ x: 20, y: 20, width: 20, height: 20 });
       tree.insert(rects[i]);
     }
     for(let i=rects.length-1; i>0; i--) {
       rects[i].x = 20 + Math.random()*60;
       rects[i].y = 20 + Math.random()*60;
       //fast=true – just re-insert the object (may leaves vacant subnodes)
       //fast=false – cleanup empty subnodes (default)
       const fast = (i !== 0);
       tree.update(rects[i], fast); 
     }

    Parameters

    • obj: ObjectsType

      Object to be updated.

    • fast: boolean = false

      Set to true to increase performance temporarily by preventing cleanup of empty subnodes (optional, default: false).

    Returns void

Generated using TypeDoc