Class Quadtree<T>

GoJS® Diagramming Components
version 4.0.0
by Northwoods Software®

This is an extension and not part of the main GoJS library. Note that the API for this class may change at any time. If you intend to use an extension in production, you should copy the code to your own source directory. See the Extensions intro page for more information.

Implementation of the quadtree data structure using the go.Rect class. Each Quadtree has defined bounds found at bounds, an array of member rectangles, and an array of child nodes (Quadtrees themselves). If the Quadtree has no children, the nodes array will have four nulls. To construct a Quadtree, you can call its constructor with no arguments. Then, to insert a rectangle, call add. This tree supports adding points (rectangles with 0 width and height), segments (rectangles with either 0 width or 0 height), and rectangles with nonzero widths and heights.

Quadtrees can be used to calculate intersections extremely quickly between a given rectangle and all of the rectangles in the quadtree. Use of this data structure prevents having to do precise intersection calculations for every rectangle in the tree. To calculate all of the rectangular intersections for a given rectangle, use intersecting.

Other common operations are detailed below.

Type Parameters

Index

Constructors

constructor

new Quadtree<T>(nodeCapacity?: number, maxLevel?: number, bounds?: Rect): Quadtree<T>
In most cases, simply calling this constructor with no arguments will produce the desired behaviour.
Type Parameters
- T
Parameters
- OptionalnodeCapacity: number
  The node capacity of this quadtree. This is the number of objects a node can contain before it splits. Defaults to 1.
- OptionalmaxLevel: number
  The maximum depth the Quadtree will allow before it will no longer split. Defaults to Infinity (no maximum depth).
- Optionalbounds: Rect
  The bounding box surrounding the entire Quadtree. If the bounds are unset or a node is inserted outside of the bounds, the tree will automatically grow.
Returns Quadtree<T>

Accessors

`Readonly`bounds

get bounds(): Rect
Gets the boundaries of the node. All nodes should be square.

Returns Rect

`Readonly`maxLevels

get maxLevels(): number
Gets the maximum depth the Quadtree will allow before it will no longer split..

Returns number

`Readonly`nodeCapacity

get nodeCapacity(): number
Gets the node capacity of this quadtree. This is the number of objects a node can contain before it splits.

Returns number

`Readonly`root

get root(): QuadNode<T>
Gets the root node of the tree

Returns QuadNode<T>

Methods

add

add(obj: T | QuadObj<T>, x?: number | Point | Rect, y?: number | Point | Size, w?: number, h?: number): void
Insert the object into the quadtree. If the node exceeds the capacity, it will split and add all objects to their corresponding nodes. If the object is outside the bounds of the tree's root node, the tree will grow to accomodate it. Possibly restructures the tree if a more efficient configuration can be found with the new dimensions. Bounds can be given either as a single go.Rect or as any combination of arguments which is valid for the go.Rect constructor.
Parameters
- obj: T | QuadObj<T>
  the object to insert
- Optionalx: number | Point | Rect
  The Rect bounds of the object, or top-left Point, or x value.
- Optionaly: number | Point | Size
  Bottom-right Point or Size or y value.
- Optionalw: number
  Width to be used if x,y are specified; must be non-negative.
- Optionalh: number
  Height to be used if x,y are specified;
Returns void

clear

clear(): void
Clears the Quadtree, removing all objects and children nodes. Keeps the current bounds of the root node.

Returns void

containing

containing(rect: Point | Rect): T[]
Return all objects that fully contain the given go.Rect or go.Point.
Parameters
- rect: Point | Rect
  the Rect or Point to check containing for. If a point is given, a Rect with size (0, 0) is created for containment calculations.
Returns T[]
array containing all containing objects

distanceSquared

distanceSquared(obj1: T, obj2: T): number
Returns the square of the distance from the centers of the given objects
Parameters
- obj1: T
- obj2: T
Returns number
square of the distance between the centers of obj1 and obj2

find

find(obj: T): QuadNode<T> | null
Return the node that contains the given object.
Parameters
- obj: T
  the object to find
Returns QuadNode<T> | null
the node containing the given object, null if the object is not found

findBounds

findBounds(bounds: Rect): Rect | null
Checks if any of the objects in the tree have the given boundaries
Parameters
- bounds: Rect
  the rectangle to check for
Returns Rect | null
the actual bounds object stored in the tree

findExtremeObjects

findExtremeObjects(): [T | null, T | null, T | null, T | null]
Finds the most furthest object in each direction stored in the tree. Bounds are tested using the center x and y coordinate.

Returns [T | null, T | null, T | null, T | null]
maximum and minimum objects in the tree, in the format [min x, max x, min y, max y].

forEach

forEach(callback: (obj: T) => void): void
Visits every object stored in the tree (depth first)
Parameters
- callback: (obj: T) => void
  the callback to execute on each object.
Returns void

has

has(obj: T): boolean
Convenience method, calls find and returns a boolean indicating whether or not the tree contains the given object
Parameters
- obj: T
  the object to check for
Returns boolean
whether or not the given object is present in the tree

intersecting

intersecting(rect: Point | Rect): T[]
Return all objects that intersect (wholly or partially) with the given go.Rect or go.Point. Touching edges and objects overlapping by 1e-7 or less (to account for floating point error) are both not considered intersections.
Parameters
- rect: Point | Rect
  the Rect or Point to check intersections for. If a point is given, a Rect with size (0, 0) is created for intersection calculations.
Returns T[]
array containing all intersecting objects

move

move(obj: T, x: number | Point, y?: number): boolean
Can be called as either (obj, x, y) or (obj, point). Translate the given object to given x and y coordinates or to a given go.Point.
Parameters
- obj: T
  the object to move
- x: number | Point
  the x coordinate or Point to move the object to
- Optionaly: number
  the y coordinate to move the object to
Returns boolean
whether or not the move was successful. False if the object was not in the tree.

remove

remove(obj: T): boolean
Remove the given object from the tree, restructuring to get rid of empty nodes that are unneeded.
Parameters
- obj: T
  the object to remove
Returns boolean
whether or not the deletion was successful. False when the object is not in the tree.

resize

resize(obj: T, width: number | Size, height?: number): boolean
Can be called as either (obj, width, height) or (obj, size). Resize the given object to given width and height or to a given go.Size.
Parameters
- obj: T
  the object to resize
- width: number | Size
  the width or Size to resize the object to
- Optionalheight: number
  the height to resize the object to
Returns boolean
whether or not the resize was successful. False if the object was not in the tree.

setTo

setTo(obj: T, x: number | Rect, y?: number, width?: number, height?: number): boolean
Updates the given object to have the bounds given, provided as either a go.Rect or x, y, width, and height.
Parameters
- obj: T
  the object to change the bounds of
- x: number | Rect
  the x-coordinate or Rect to set the object to
- Optionaly: number
  the y-coordinate to set the object to, unnecessary if a Rect was given
- Optionalwidth: number
  the width to set the object to, unnecessary if a Rect was given
- Optionalheight: number
  the height to set the object to, unnecessary if a Rect was given
Returns boolean

walk

walk(callback: (n: QuadNode<T>) => void, node?: QuadNode<T>, root?: boolean): void
Recursively traverses the tree (depth first) and executes the given callback on each node.
Parameters
- callback: (n: QuadNode<T>) => void
  the callback to execute on each node. Takes the form of (n: Quadtree) => void
- node: QuadNode<T> = ...
- root: boolean = true
  whether or not to execute the callback on the root node as well. Defaults to true
Returns void

Class Quadtree<T>

Type Parameters

Index

Constructors

Accessors

Methods

Constructors

constructor

Type Parameters

Parameters

Returns Quadtree<T>

Accessors

Readonlybounds

Returns Rect

ReadonlymaxLevels

Returns number

ReadonlynodeCapacity

Returns number

Readonlyroot

Returns QuadNode<T>

Methods

add

Parameters

Returns void

clear

Returns void

containing

Parameters

Returns T[]

distanceSquared

Parameters

Returns number

find

Parameters

Returns QuadNode<T> | null

findBounds

Parameters

Returns Rect | null

findExtremeObjects

Returns [T | null, T | null, T | null, T | null]

forEach

Parameters

Returns void

has

Parameters

Returns boolean

intersecting

Parameters

Returns T[]

move

Parameters

Returns boolean

remove

Parameters

Returns boolean

resize

Parameters

Returns boolean

setTo

Parameters

Returns boolean

walk

Parameters

Returns void

On This Page

`Readonly`bounds

`Readonly`maxLevels

`Readonly`nodeCapacity

`Readonly`root