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
  minLevels: 0,   // optional, default:  0
  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

ObjectsType extends Rectangle | Circle | Line | Indexable

Index

Constructors

constructor

new Quadtree<
    ObjectsType extends
        Indexable
        | Rectangle<void>
        | Circle<void>
        | Line<void>,
>(
    props: QuadtreeProps,
    level?: number,
): Quadtree<ObjectsType>
Quadtree Constructor
Type Parameters
- ObjectsType extends Indexable | Rectangle<void> | Circle<void> | Line<void>
Parameters
- props: QuadtreeProps
  bounds and properties of the node
- level: number = 0
  depth level (internal use only, required for subnodes)
Returns Quadtree<ObjectsType>
- Defined in Quadtree.ts:132

Properties

`Readonly`bounds

bounds: NodeGeometry

The numeric boundaries of this node.

`Readonly`level

level: number

The level of this node.

Default Value

0

`Readonly`maxLevels

maxLevels: number

Total max nesting levels of the root Quadtree node.

Default Value

4

`Readonly`maxObjects

maxObjects: number

Max objects this node can hold before it splits.

Default Value

10

`Readonly`minLevels

minLevels: number

Minimum nesting levels of the root Quadtree node.

Default Value

0

`Readonly`nodes

nodes: Quadtree<ObjectsType>[]

Subnodes of this node

Default Value

[]

`Readonly`objects

objects: ObjectsType[]

Array of objects in this node.

Default Value

[]

Methods

clear

clear(): void

Clear the Quadtree.

Returns void

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

getIndex

getIndex(obj: Indexable | Rectangle<void> | Circle<void> | Line<void>): number[]
Get the quadrant (subnode indexes) an object belongs to.
Parameters
- obj: Indexable | Rectangle<void> | Circle<void> | Line<void>
  object to be checked
Returns number[]
Array containing indexes of intersecting subnodes (0-3 = top-right, top-left, bottom-left, bottom-right).
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]
```
- Defined in Quadtree.ts:172

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.

Parameters

obj: ObjectsType
Object to be added.

Returns void

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'} }));

join

join(): ObjectsType[]
The opposite of a split: merge and dissolve subnodes (when total object count doesn't exceed maxObjects).

Returns ObjectsType[]
The objects from this node and all subnodes combined.
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
```
- Defined in Quadtree.ts:409

remove

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

Beta

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.

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).

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);
 }

retrieve

retrieve(
obj: Indexable | Rectangle<void> | Circle<void> | Line<void>,
): ObjectsType[]
Return all objects that could collide with the given geometry.
Parameters
- obj: Indexable | Rectangle<void> | Circle<void> | Line<void>
  geometry to be checked
Returns ObjectsType[]
Array containing all detected objects.
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'} }));
```
- Defined in Quadtree.ts:279

split

split(): void
Internal
Split the node into 4 subnodes. Mostly for internal use! You should only call this yourself if you know what you are doing.

Returns void
Example: Manual split:
```
const tree = new Quadtree({ width: 100, height: 100 });
tree.split();
console.log(tree); // now tree has four subnodes
```
- Defined in Quadtree.ts:187

update

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

Beta

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.

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

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);
 }

Class Quadtree<ObjectsType>

Example

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

Type Parameters

Index

Constructors

Properties

Methods

Constructors

constructor

Type Parameters

Parameters

Returns Quadtree<ObjectsType>

Properties

Readonlybounds

Readonlylevel

Default Value

ReadonlymaxLevels

Default Value

ReadonlymaxObjects

Default Value

ReadonlyminLevels

Default Value

Readonlynodes

Default Value

Readonlyobjects

Default Value

Methods

clear

Returns void

Example

getIndex

Parameters

Returns number[]

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

insert

Parameters

Returns void

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

join

Returns ObjectsType[]

Example: Manual join:

remove

Parameters

Returns boolean

Example

Example: Bulk fast removals and final cleanup:

retrieve

Parameters

Returns ObjectsType[]

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

split

Returns void

Example: Manual split:

update

Parameters

Returns void

Example

Example: Bulk fast update and final cleanup:

Settings

On This Page

`Readonly`bounds

`Readonly`level

`Readonly`maxLevels

`Readonly`maxObjects

`Readonly`minLevels

`Readonly`nodes

`Readonly`objects