Class QuadTree<E>

constructor

• new QuadTree<E extends QuadTreeEntry>(
      bounds: RectLike,
      maxEntriesPerQuad?: number,
      maxDepth?: number,
  ): QuadTree<E>

  Construct a new quad tree.

  Type Parameters

  • E extends QuadTreeEntry

  Parameters

  • bounds: RectLike

    Overall bounds of the quad tree
  • maxEntriesPerQuad: number = 64

    Max entries a quad can contain until it has to be subdivided
  • maxDepth: number = 4

    Max subdivision depth. A quad will not be subdivided further if this value is met - even if maxEntriesPerQuad is exceeded

  Returns QuadTree<E>

Readonlybounds

size

• get size(): number

  Number of entries in the quad tree.

  Returns number

add

• add(entry: E): boolean

  Try to add an entry to the quad tree.

  Parameters

  • entry: E

    Entry to add

  Returns boolean

  true if the entry was added, false if the entry was outside quad tree bounds

clear

• clear(): void

  Clear the quad tree.

  Returns void

delete

• delete(entry: E, merge?: boolean): boolean

  Delete an entry from the quad tree.

  Parameters

  • entry: E

    Entry to delete (via reference comparison)
  • merge: boolean = false

    If true, try to merge quads after the deletion

  Returns boolean

  true if entry was deleted

  Remarks

  Traverses the whole tree to ensure the entry is deleted. If the entry's position and size has not changed, use QuadTree.deleteSpatial for a delete that uses the quad tree's fast spatial query.

deleteSpatial

• deleteSpatial(entry: E, merge?: boolean): boolean

  Delete an entry from the quad tree.

  Parameters

  • entry: E

    Entry to delete (via reference comparison)
  • merge: boolean = false

    If true, try to merge quads after the deletion

  Returns boolean

  true if entry was deleted

  Remarks

  If the entry's position or shape has changed, use QuadTree.delete to ensure its deletion.

filter

• filter(
      entryPredicate: (entry: E) => boolean,
      quadPredicate: (rect: ReadonlyRect) => boolean,
      results?: ArraySet<E>,
  ): ArraySet<E>

  Get all entries that match the predicate.

  Parameters

  • entryPredicate: (entry: E) => boolean

    Entry predicate
  • quadPredicate: (rect: ReadonlyRect) => boolean

    Quad predicate. Will be called with quad bounds
  • Optionalresults: ArraySet<E>

    Optional Set to put results into. Will allocate a new Set otherwise

  Returns ArraySet<E>

  A Set containing all matched entries

intersections

• intersections(rect: RectLike, results?: ArraySet<E>): ArraySet<E>

  Get all entries that intersect rect.

  Parameters

  • rect: RectLike

    Rect to intersect with
  • Optionalresults: ArraySet<E>

    Optional Set to put results into. Will allocate a new Set otherwise

  Returns ArraySet<E>

  A Set containing all intersecting entries

merge

• merge(): void

  Merge subdivided quads that fall below the max entry value.

  Returns void

quads

• quads(): Generator<Quad>

  Get an iterator of all quads in the quad tree.

  Returns Generator<Quad>

update

• update(entry: E, merge?: boolean): boolean

  Update an entry in the tree after it was transformed. Entry may be added to the tree if it was not present before. It may also be deleted even if it was present if the new shape is outside the quad tree's bounds.

  Parameters

  • entry: E

    Entry to update
  • merge: boolean = false

    If true, try to merge quads after the deletion

  Returns boolean

  true if the entry is present after this operation

  Remarks

  Combines both QuadTree.add and QuadTree.delete into one operation which removes the need to traverse part of the tree again in QuadTree.add.