Quadtree¶

detroit.quadtree(data: list[T] | None = None, x: Callable[[T], float] | Callable[[T, int], float] | Callable[[T, int, list[Element]], float] = None, y: Callable[[T], float] | Callable[[T, int], float] | Callable[[T, int, list[Element]], float] = None) → Quadtree[T]¶

Creates a new, empty quadtree with an empty extent and the default x and y accessors. If data is specified, adds the specified iterable of data to the quadtree.

Parameters:

data (list[T] | None) – List of data values
x (Accessor[T, float]) – X accessor
y (Accessor[T, float]) – Y accessor

Returns:

Quadtree object

Return type:

Quadtree[T]

class detroit.quadtree.quadtree.Quadtree(x: Callable[[T], float] | Callable[[T, int], float] | Callable[[T, int, list[Element]], float], y: Callable[[T], float] | Callable[[T, int], float] | Callable[[T, int, list[Element]], float], x0: float, y0: float, x1: float, y1: float)¶

A quadtree recursively partitions two-dimensional space into squares, dividing each square into four equally-sized squares. Each distinct point exists in a unique leaf node; coincident points are represented by a linked list. Quadtrees can accelerate various spatial operations, such as the Barnes–Hut approximation for computing many-body forces, collision detection, and searching for nearby points.

Parameters:

x (Accessor[T, float]) – X accessor
y (Accessor[T, float]) – Y accessor
x0 (float) – Inclusive lower bound \(x_0\)
y0 (float) – Inclusive lower bound \(y_0\)
x1 (float) – Inclusive upper bound \(x_1\)
y1 (float) – Inclusive upper bound \(y_1\)

add(d: T) → Quadtree¶

Adds the specified datum to the quadtree, deriving its coordinates \((x, y)\) using the current x and y accessors, and returns the quadtree.

If the new point is outside the current extent of the quadtree, the quadtree is automatically expanded to cover the new point.

Parameters:: d (T) – Datum
Returns:: Itself
Return type:: Quadtree

add_all(data: list[T]) → Quadtree¶

Adds the specified iterable of data to the quadtree, deriving each element’s coordinates \((x, y)\) using the current x and y accessors, and return this quadtree.

Parameters:: data (list[T]) – List of data values
Returns:: Itself
Return type:: Quadtree

copy() → Quadtree¶

Returns a deep copy of itself.

Returns:: Deep copy of itself
Return type:: Quadtree

cover(x: float, y: float) → Quadtree¶

Expands the quadtree to cover the specified point \((x, y)\), and returns the quadtree.

Parameters:

x (float) – X value
y (float) – Y value

Returns:

Itself

Return type:

Quadtree

data() → list[T]¶

Returns an array of all data in the quadtree.

Returns:: List of all data
Return type:: list[T]

find(x: float, y: float, radius: float | None = None) → Quadtree¶

Returns the datum closest to the position \((x, y)\) with the given search radius. If radius is not specified, it defaults to infinity.

Parameters:

x (float) – x value
y (float) – y value
radius (float | None) – radius value

Returns:

Itself

Return type:

Quadtree

remove(d: T) → Quadtree¶

Removes the specified datum from the quadtree, deriving its coordinates \((x,y)\) using the current x and y accessors, and returns the quadtree.

Parameters:: d (T) – Datum
Returns:: Itself
Return type:: Quadtree

remove_all(data: list[T]) → Quadtree¶

Removes the specified data from the quadtree, deriving their coordinates \((x,y)\) using the current x and y accessors, and returns the quadtree.

Parameters:: data (list[T]) – List of data
Returns:: Itself
Return type:: Quadtree

set_extent(extent: list[tuple[float, float], tuple[float, float]]) → Quadtree¶

Expands the quadtree to cover the specified points [[x0, y0], [x1, y1]] and returns the quadtree.

Parameters:: extent (list[tuple[float, float], tuple[float, float]]) – Extent values
Returns:: Itself
Return type:: Quadtree

size() → float¶

Returns the total number of data in the quadtree.

Returns:: Total number of data in sthe quadtree.
Return type:: float

visit(callback: Callable[[list | dict | None, float, float, float, float], bool]) → Quadtree¶

Visits each node in the quadtree in pre-order traversal, invoking the specified callback with arguments node, x0, y0, x1, y1 for each node, where node is the node being visited, \((x_0, y_0)\) are the lower bounds of the node, and \((x_1, y_1)\) are the upper bounds, and returns the quadtree. (Assuming that positive x is right and positive y is down, as is typically the case in Canvas and SVG, \((x_0, y_0)\) is the top-left corner and \((x_1, y_1)\) is the lower-right corner; however, the coordinate system is arbitrary, so more formally \(x_0 \le x_1\) and \(y0 \le y1\).)

If the callback returns true for a given node, then the children of that node are not visited; otherwise, all child nodes are visited. This can be used to quickly visit only parts of the tree, for example when using the Barnes–Hut approximation. Note, however, that child quadrants are always visited in sibling order: top-left, top-right, bottom-left, bottom-right. In cases such as search, visiting siblings in a specific order may be faster.

Parameters:: callback (Callable[[list | dict | None, float, float, float, float], bool]) – Callback function
Returns:: Itself
Return type:: Quadtree

Notes

The number of arguments for the callback function is automatically determined. Therefore, you can pass 0 to 5 arguments to the callback function. For example, def callback(node): is a valid function.

visit_after(callback: Callable[[dict, float, float, float, float], bool]) → Quadtree¶

Visits each node in the quadtree in post-order traversal, invoking the specified callback with arguments node, x0, y0, x1, y1 for each node, where node is the node being visited, (x_0, y_0) are the lower bounds of the node, and (x_1, y_1) are the upper bounds, and returns the quadtree. (Assuming that positive x is right and positive y is down, as is typically the case in Canvas and SVG, (x_0, y_0) is the top-left corner and (x_1, y_1) is the lower-right corner; however, the coordinate system is arbitrary, so more formally \(x_0 \lt x_1\) and \(y0 \lt y1\).). Returns root.

Parameters:: callback (Callable[[dict, float, float, float, float], bool]) – Callback function
Returns:: Itself
Return type:: Quadtree

Notes

x(x: Callable[[T], float] | Callable[[T, int], float] | Callable[[T, int, list[Element]], float]) → Quadtree¶

Sets the x-coordinate accessor and returns the quadtree. The x accessor is used to derive the x coordinate of data when adding to and removing from the tree. It is also used when finding to re-access the coordinates of data previously added to the tree; therefore, the x and y accessors must be consistent, returning the same value given the same input.

Parameters:: x (Accessor[T, float]) – X accessor
Returns:: Itself
Return type:: Quadtree

y(y: Callable[[T], float] | Callable[[T, int], float] | Callable[[T, int, list[Element]], float]) → Quadtree¶

Sets the y-coordinate accessor and returns the quadtree. The y accessor is used to derive the y coordinate of data when adding to and removing from the tree. It is also used when finding to re-access the coordinates of data previously added to the tree; therefore, the x and y accessors must be consistent, returning the same value given the same input.

Parameters:: y (Accessor[T, float]) – Y accessor
Returns:: Itself
Return type:: Quadtree