Class Quadtree<T>
Implementation of the quadtree data structure using the Rect class.
Namespace: Northwoods.Go.Layouts.Extensions
Assembly: PackedWinForms.dll
Syntax
public class Quadtree<T>Type Parameters
| 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
Quadtree(int, int, Rect)
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; }Property Value
| Type | Description |
|---|---|
| Rect |
MaxLevels
Gets the maximum depth the Quadtree will allow before it will no longer split.
Declaration
public double MaxLevels { get; }Property Value
| 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; }Property Value
| Type | Description |
|---|---|
| double |
Root
Gets the root node of the tree.
Declaration
public QuadNode<T> Root { get; }Property Value
| Type | Description |
|---|---|
| QuadNode<T> |
Methods
Add(T, Rect)
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 |
Add(QuadObj<T>)
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 |
|---|---|---|
| QuadObj<T> | obj | 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 |
|---|---|
| QuadNode<T> | 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 |
Returns
| 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 |
Walk(Action<QuadNode<T>>, QuadNode<T>, 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 |
|---|---|---|
| Action<QuadNode<T>> | callback | the callback to execute on each node. Takes the form of (n: Quadtree) => void |
| QuadNode<T> | node | |
| bool | root | whether or not to execute the callback on the root node as well. Defaults to true |
Walk(Action<QuadNode<T>>, bool)
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 |
|---|---|---|
| Action<QuadNode<T>> | callback | 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 |