GoDiagram®
v10.0.10
by Northwoods Software®

Implementation of the quadtree data structure using the Rect class.

##### Syntax
``public class Quadtree<T>``
Name Description
T
##### Remarks

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(T, Rect). 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(Rect).

Other common operations are detailed below.

### Constructors

In most cases, simply calling this constructor with no arguments will produce the desired behaviour.

##### Declaration
``public Quadtree(int nodeCapacity = 1, int maxLevel = 2147483647, Rect bounds = default)``
##### Parameters
Type Name Description
int nodeCapacity

The node capacity of this quadtree. This is the double of objects a node can contain before it splits. Defaults to 1.

int maxLevel

The maximum depth the Quadtree will allow before it will no longer split. Defaults to double.PositiveInfinity (no maximum depth).

Rect bounds

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.

### Properties

#### Bounds

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

##### Declaration
``public Rect Bounds { get; }``
Type Description
Rect

#### MaxLevels

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

##### Declaration
``public double MaxLevels { get; }``
Type Description
double

#### NodeCapacity

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

##### Declaration
``public double NodeCapacity { get; }``
Type Description
double

#### Root

Gets the root node of the tree.

##### Declaration
``public QuadNode<T> Root { get; }``
Type Description

### Methods

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.

##### Declaration
``public void Add(T obj, Rect bounds)``
##### Parameters
Type Name Description
T obj

the object to insert

Rect bounds

The Rect bounds of the object

#### Add(T, double, double, double, double)

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.

##### Declaration
``public void Add(T obj, double x, double y, double w, double h)``
##### Parameters
Type Name Description
T obj

the object to insert

double x

The x value.

double y

The y value.

double w

The width, must be non-negative.

double h

The height, must be non-negative

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.

##### Declaration
``public void Add(QuadObj<T> obj)``
##### Parameters
Type Name Description

the object to insert

#### Clear()

Clears the Quadtree, removing all objects and children nodes. Keeps the current bounds of the root node.

##### Declaration
``public void Clear()``

#### Containing(Point)

Return all objects that fully contain the given Point.

##### Declaration
``public List<T> Containing(Point point)``
##### Parameters
Type Name Description
Point point

the Point to check containing for. A Rect with size (0, 0) is created for containment calculations.

##### Returns
Type Description
List<T>

list containing all containing objects

#### Containing(Rect)

Return all objects that fully contain the given Rect.

##### Declaration
``public List<T> Containing(Rect rect)``
##### Parameters
Type Name Description
Rect rect

the Rect to check containing for.

##### Returns
Type Description
List<T>

list containing all containing objects

#### DistanceSquared(T, T)

Returns the square of the distance from the centers of the given objects.

##### Declaration
``public double DistanceSquared(T obj1, T obj2)``
##### Parameters
Type Name Description
T obj1
T obj2
##### Returns
Type Description
double

square of the distance between the centers of obj1 and obj2

#### Find(T)

Return the node that contains the given object.

##### Declaration
``public QuadNode<T> Find(T obj)``
##### Parameters
Type Name Description
T obj

the object to find

##### Returns
Type Description

the node containing the given object, null if the object is not found

#### FindBounds(Rect)

Checks if any of the objects in the tree have the given boundaries.

##### Declaration
``public Rect? FindBounds(Rect bounds)``
##### Parameters
Type Name Description
Rect bounds

the rectangle to check for

##### Returns
Type Description
Rect?

the actual bounds object stored in the tree

#### FindExtremeObjects()

Finds the furthest object in each direction stored in the tree. Bounds are tested using the center x and y coordinate.

##### Declaration
``public (T, T, T, T) FindExtremeObjects()``
##### Returns
Type Description
(T, T, T, T)

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

#### ForEach(Action<T>)

Visits every object stored in the tree (depth first).

##### Declaration
``public void ForEach(Action<T> callback)``
##### Parameters
Type Name Description
Action<T> callback

the callback to execute on each object.

#### Has(T)

Convenience method, calls Find(T) and returns a bool indicating whether or not the tree contains the given object.

##### Declaration
``public bool Has(T obj)``
##### Parameters
Type Name Description
T obj

the object to check for

##### Returns
Type Description
bool

whether or not the given object is present in the tree

#### Intersecting(Point)

Return all objects that intersect (wholly or partially) with the given Point. Touching edges and objects overlapping by 1e-7 or less (to account for floating point error) are both not considered intersections.

##### Declaration
``public List<T> Intersecting(Point point)``
##### Parameters
Type Name Description
Point point

the Point to check intersections for. A Rect with size (0, 0) is created for intersection calculations.

##### Returns
Type Description
List<T>

list containing all intersecting objects

#### Intersecting(Rect)

Return all objects that intersect (wholly or partially) with the given Rect. Touching edges and objects overlapping by 1e-7 or less (to account for floating point error) are both not considered intersections.

##### Declaration
``public List<T> Intersecting(Rect rect)``
##### Parameters
Type Name Description
Rect rect

the Rect to check intersections for.

##### Returns
Type Description
List<T>

list containing all intersecting objects

#### Move(T, Point)

Translate the given object to a given Point.

##### Declaration
``public bool Move(T obj, Point p)``
##### Parameters
Type Name Description
T obj

the object to move

Point p

the Point to move the object to

##### Returns
Type Description
bool

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

#### Move(T, double, double)

Translate the given object to given x and y coordinates.

##### Declaration
``public bool Move(T obj, double x, double y)``
##### Parameters
Type Name Description
T obj

the object to move

double x

the x coordinate to move the object to

double y

the y coordinate to move the object to

##### Returns
Type Description
bool

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

#### Remove(T)

Remove the given object from the tree, restructuring to get rid of empty nodes that are unneeded.

##### Declaration
``public bool Remove(T obj)``
##### Parameters
Type Name Description
T obj

the object to remove

##### Returns
Type Description
bool

whether or not the deletion was successful. False when the object is not in the tree.

#### Resize(T, Size)

Resize the given object to a given Size.

##### Declaration
``public bool Resize(T obj, Size size)``
##### Parameters
Type Name Description
T obj

the object to resize

Size size

the Size to resize the object to

##### Returns
Type Description
bool

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

#### Resize(T, double, double)

Resize the given object to given width and height.

##### Declaration
``public bool Resize(T obj, double width, double height)``
##### Parameters
Type Name Description
T obj

the object to resize

double width

the width to resize the object to

double height

the height to resize the object to

##### Returns
Type Description
bool

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

#### SetTo(T, Rect)

Updates the given object to have the bounds given, provided as a Rect.

##### Declaration
``public bool SetTo(T obj, Rect rect)``
##### Parameters
Type Name Description
T obj

the object to change the bounds of

Rect rect

the Rect to set the object to

Type Description
bool

#### SetTo(T, double, double, double, double)

Updates the given object to have the bounds given, provided as x, y, width, and height.

##### Declaration
``public bool SetTo(T obj, double x, double y, double width, double height)``
##### Parameters
Type Name Description
T obj

the object to change the bounds of

double x

the x-coordinate to set the object to

double y

the y-coordinate to set the object to

double width

the width to set the object to

double height

the height to set the object to

##### Returns
Type Description
bool

Recursively traverses the tree (depth first) and executes the given callback on each node.

##### Declaration
``public void Walk(Action<QuadNode<T>> callback, QuadNode<T> node, bool root = true)``
##### Parameters
Type Name Description

the callback to execute on each node. Takes the form of (n: Quadtree) => void

bool root

whether or not to execute the callback on the root node as well. Defaults to true

Recursively traverses the tree (depth first) and executes the given callback on each node.

##### Declaration
``public void Walk(Action<QuadNode<T>> callback, bool root = true)``
##### Parameters
Type Name Description