QuadTree¶

class quads.QuadTree(center, width, height, capacity=None)¶

Usage:

>>> import quads
>>> tree = quads.QuadTree(
...     (0, 0),  # The center point
...     10,  # The width
...     10,  # The height
... )

>>> tree.insert((1, 2))
True

>>> tree.find((1, 2))
Point(1, 2)

>>> tree.find((4, -4))
None

>>> tree.nearest_neighbors((0, 1), count=2)
[
    Point(1, 2),
    Point(4, -4),
]

convert_to_point(val)¶

Converts a value to a Point object.

This is to allow shortcuts, like providing a tuple for a point.

Parameters:	val (Point\|tuple\|None) – The value to convert.
Returns:	A point object.
Return type:	Point

find(point)¶

Searches for a Point within the quadtree.

Parameters:	point (Point\|tuple\|None) – The point to search for.
Returns:	Returns the Point (including it’s data) if found. None if the point is not found.
Return type:	Point\|None

insert(point, data=None)¶

Inserts a Point into the quadtree.

Parameters:	point (Point\|tuple\|None) – The point to insert. data (any) – Optional. Corresponding data for that point. Default is None.
Returns:	True if insertion succeeded, otherwise False.
Return type:	bool

nearest_neighbors(point, count=10)¶

Returns the nearest points of a given point, sorted by distance (closest first).

The desired point does not need to exist within the quadtree, but does need to be within the tree’s boundaries.

Parameters:	point (Point) – The desired location to search around. count (int) – Optional. The number of neighbors to return. Default is 10.
Returns:	The nearest Point neighbors.
Return type:	list

node_class¶: alias of QuadNode

point_class¶: alias of Point

within_bb(bb)¶

Checks if a bounding box is within the quadtree’s bounding box.

Primarily for internal use, but stable API if you need it.

Parameters:	bb (BoundingBox) – The bounding box to check.
Returns:	True if the bounding boxes intersect, otherwise False.
Return type:	bool