Class Quadtree<T>

Namespace

Northwoods.Go.Layouts.Extensions

Assembly

PackedWinForms.dll

Implementation of the quadtree data structure using the Rect class.

public class Quadtree<T>

Type Parameters

T

Inheritance

object

Quadtree<T>

Inherited Members

object.Equals(object)

object.Equals(object, object)

object.GetHashCode()

object.GetType()

object.MemberwiseClone()

object.ReferenceEquals(object, object)

object.ToString()

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.

public Quadtree(int nodeCapacity = 1, int maxLevel = 2147483647, Rect bounds = default)

Parameters

nodeCapacity int

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

maxLevel int

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

bounds 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.

Properties

Bounds

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

public Rect Bounds { get; }

Property Value

Rect

MaxLevels

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

public double MaxLevels { get; }

Property Value

double

NodeCapacity

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

public double NodeCapacity { get; }

Property Value

double

Root

Gets the root node of the tree.

public QuadNode<T> Root { get; }

Property Value

QuadNode<T>

Methods

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.

public void Add(QuadObj<T> obj)

Parameters

obj QuadObj<T>

the object to insert

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.

public void Add(T obj, Rect bounds)

Parameters

obj T

the object to insert

bounds Rect

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.

public void Add(T obj, double x, double y, double w, double h)

Parameters

obj T

the object to insert

x double

The x value.

y double

The y value.

w double

The width, must be non-negative.

h double

The height, must be non-negative

Clear()

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

public void Clear()

Containing(Point)

Return all objects that fully contain the given Point.

public List<T> Containing(Point point)

Parameters

point Point

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

Returns

List<T>

list containing all containing objects

Containing(Rect)

Return all objects that fully contain the given Rect.

public List<T> Containing(Rect rect)

Parameters

rect Rect

the Rect to check containing for.

Returns

List<T>

list containing all containing objects

DistanceSquared(T, T)

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

public double DistanceSquared(T obj1, T obj2)

Parameters

obj1 T

obj2 T

Returns

double

square of the distance between the centers of obj1 and obj2

Find(T)

Return the node that contains the given object.

public QuadNode<T> Find(T obj)

Parameters

obj T

the object to find

Returns

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.

public Rect? FindBounds(Rect bounds)

Parameters

bounds Rect

the rectangle to check for

Returns

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.

public (T, T, T, T) FindExtremeObjects()

Returns

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

public void ForEach(Action<T> callback)

Parameters

callback Action<T>

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.

public bool Has(T obj)

Parameters

obj T

the object to check for

Returns

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.

public List<T> Intersecting(Point point)

Parameters

point Point

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

Returns

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.

public List<T> Intersecting(Rect rect)

Parameters

rect Rect

the Rect to check intersections for.

Returns

List<T>

list containing all intersecting objects

Move(T, Point)

Translate the given object to a given Point.

public bool Move(T obj, Point p)

Parameters

obj T

the object to move

p Point

the Point to move the object to

Returns

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.

public bool Move(T obj, double x, double y)

Parameters

obj T

the object to move

x double

the x coordinate to move the object to

y double

the y coordinate to move the object to

Returns

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.

public bool Remove(T obj)

Parameters

obj T

the object to remove

Returns

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.

public bool Resize(T obj, Size size)

Parameters

obj T

the object to resize

size Size

the Size to resize the object to

Returns

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.

public bool Resize(T obj, double width, double height)

Parameters

obj T

the object to resize

width double

the width to resize the object to

height double

the height to resize the object to

Returns

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.

public bool SetTo(T obj, Rect rect)

Parameters

obj T

the object to change the bounds of

rect Rect

the Rect to set the object to

Returns

bool

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

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

public bool SetTo(T obj, double x, double y, double width, double height)

Parameters

obj T

the object to change the bounds of

x double

the x-coordinate to set the object to

y double

the y-coordinate to set the object to

width double

the width to set the object to

height double

the height to set the object to

Returns

bool

Walk(Action<QuadNode<T>>, QuadNode<T>, bool)

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

public void Walk(Action<QuadNode<T>> callback, QuadNode<T> node, bool root = true)

Parameters

callback Action<QuadNode<T>>

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

node QuadNode<T>

root bool

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.

public void Walk(Action<QuadNode<T>> callback, bool root = true)

Parameters

callback Action<QuadNode<T>>

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

root bool

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