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.

#### T

- 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

`Optional`

nodeCapacity: numberThe node capacity of this quadtree. This is the number of objects a node can contain before it splits. Defaults to 1.

`Optional`

maxLevel: numberThe maximum depth the Quadtree will allow before it will no longer split. Defaults to Infinity (no maximum depth).

`Optional`

bounds: RectThe 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>

`Readonly`

bounds: Rect

Gets the boundaries of the node. All nodes should be square.

`Readonly`

max: number

Gets the maximum depth the Quadtree will allow before it will no longer split..

`Readonly`

node: number

Gets the node capacity of this quadtree. This is the number of objects a node can contain before it splits.

`Readonly`

root: QuadNode<T>

Gets the root node of the tree

- 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

`Optional`

x: number | Point | RectThe Rect bounds of the object, or top-left Point, or x value.

`Optional`

y: number | Point | SizeBottom-right Point or Size or y value.

`Optional`

w: numberWidth to be used if x,y are specified; must be non-negative.

`Optional`

h: numberHeight to be used if x,y are specified;

#### Returns void

- 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(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

#### Returns T[]

array containing all intersecting objects

- 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

`Optional`

y: numberthe 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.

- 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

`Optional`

height: numberthe height to resize the object to

#### Returns boolean

whether or not the resize was successful. False if the object was not in the tree.

- set
To (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

`Optional`

y: numberthe y-coordinate to set the object to, unnecessary if a Rect was given

`Optional`

width: numberthe width to set the object to, unnecessary if a Rect was given

`Optional`

height: numberthe height to set the object to, unnecessary if a Rect was given

#### Returns boolean

- 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

- (n: QuadNode<T>): void
#### Parameters

##### n: QuadNode<T>

#### Returns 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

Copyright © 1998-2024 by Northwoods Software Corporation.

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.