Skip to content

fastquadtree.RectQuadTree

A spatial index for axis-aligned rectangles without object association.

Parameter Name Clarification

In the inherited methods below, the parameter geom refers to a rectangle coordinate tuple (min_x, min_y, max_x, max_y).

For example:

  • insert(geom) means insert((min_x, min_y, max_x, max_y))
  • insert_many(geoms) means insert_many([(min_x1, min_y1, max_x1, max_y1), ...])

Bases: _BaseQuadTree[Bounds]

Spatial index for axis-aligned rectangles without object association.

This class provides fast spatial indexing for rectangles using integer IDs that you can correlate with external data structures. For automatic object association, see RectQuadTreeObjects.

Parameters:

Name Type Description Default
bounds Bounds

World bounds as (min_x, min_y, max_x, max_y).

 required
capacity int

Maximum rectangles per node before splitting.

 required
max_depth int | None

Optional maximum tree depth (uses engine default if not specified).

 None
dtype QuadTreeDType

Coordinate data type ('f32', 'f64', 'i32', 'i64'). Default: 'f32'.

 'f32'
Performance
  • Inserts: O(log n) average
  • Queries: O(log n + k) average, where k is the number of matches
  • Nearest neighbor: O(log n) average
Thread Safety

Not thread-safe. Use external synchronization for concurrent access.

Raises:

Type Description
ValueError

If parameters are invalid or geometry is outside bounds.
Example 
rqt = RectQuadTree((0.0, 0.0, 100.0, 100.0), capacity=10)
rect_id = rqt.insert((10.0, 20.0, 30.0, 40.0))
results = rqt.query((5.0, 5.0, 35.0, 35.0))
for id_, min_x, min_y, max_x, max_y in results:
    print(f"Rect {id_} at ({min_x}, {min_y}, {max_x}, {max_y})")

insert(geom, id_=None)

Insert a single geometry.

IDs are auto-assigned by default. You can optionally provide a custom ID to correlate with external data structures.

Warning: Mixing auto-assigned and custom IDs is dangerous. The quadtree does not track which IDs have been used. If you provide a custom ID that collides with an auto-assigned ID, both entries will exist with the same ID, leading to undefined behavior. Users who provide custom IDs are responsible for ensuring uniqueness.

Parameters:

Name Type Description Default
geom G

Geometry (Point or Bounds).

 required
id_ int | None

Optional custom ID. If None, auto-assigns the next ID.

 None

Returns:

Type Description
int

The ID used for this geometry.

Raises:

Type Description
ValueError

If geometry is outside the tree bounds.

insert_many(geoms)

Bulk insert geometries with auto-assigned contiguous IDs.
IDs start at 0 and increment by 1, so they will be aligned with the indexes of the input list if the tree started empty.

Custom IDs are not supported for bulk insertion. Use single insert() calls if you need custom IDs.

Parameters:

Name Type Description Default
geoms Sequence[G]

Sequence of geometries.

 required

Returns:

Type Description
InsertResult

InsertResult with count, start_id, and end_id.

Raises:

Type Description
TypeError

If geoms is a NumPy array (use insert_many_np instead).
ValueError

If any geometry is outside bounds.
Example 
# Point Quadtree Example:

points = [(1.0, 2.0), (3.0, 4.0), (5.0, 6.0)]
qt = QuadTree(bounds=(0.0, 0.0, 10.0, 10.0), capacity=16)
result = qt.insert_many(points) # Each point's ID corresponds to its index in the points list
print(result)  # InsertResult(count=3, start_id=0, end_id=2)

insert_many_np(geoms)

Bulk insert geometries from NumPy array with auto-assigned contiguous IDs.

Parameters:

Name Type Description Default
geoms Any

NumPy array with dtype matching the tree's dtype.

 required

Returns:

Type Description
InsertResult

InsertResult with count, start_id, and end_id.

Raises:

Type Description
TypeError

If geoms is not a NumPy array or dtype doesn't match.
ValueError

If any geometry is outside bounds.
ImportError

If NumPy is not installed.

clear()

Empty the tree in place, preserving bounds, capacity, and max_depth.

get_all_node_boundaries()

Return all node boundaries in the tree. Useful for visualization.

get_inner_max_depth()

Return the maximum depth of the quadtree.

Useful if you constructed with max_depth=None.

to_bytes()

Serialize the quadtree to bytes.

Returns:

Type Description
bytes

Bytes representing the serialized quadtree.

from_bytes(data) classmethod

Deserialize a quadtree from bytes.

Parameters:

Name Type Description Default
data bytes

Bytes from to_bytes().

 required

Returns:

Type Description
_BaseQuadTree[G]

A new instance.

query(rect)

Find all rectangles that intersect with a query rectangle.

Parameters:

Name Type Description Default
rect Bounds

Query rectangle as (min_x, min_y, max_x, max_y).

 required

Returns:

Type Description
list[_IdRect]

List of (id, min_x, min_y, max_x, max_y) tuples for intersecting rectangles.
Example 
results = rqt.query((10.0, 10.0, 20.0, 20.0))
for id_, min_x, min_y, max_x, max_y in results:
    print(f"Rect {id_} at ({min_x}, {min_y}, {max_x}, {max_y})")

query_np(rect)

Find intersecting rectangles, returning NumPy arrays.

Parameters:

Name Type Description Default
rect Bounds

Query rectangle as (min_x, min_y, max_x, max_y).

 required

Returns:

Type Description
tuple[Any, Any]

Tuple of (ids, coords) where: - ids: NDArray[np.int64] with shape (N,) - coords: NDArray with shape (N, 4) and dtype matching the tree

Raises:

Type Description
ImportError

If NumPy is not installed.
Example 
ids, coords = rqt.query_np((10.0, 10.0, 20.0, 20.0))
for id_, (min_x, min_y, max_x, max_y) in zip(ids, coords):
    print(f"Rect {id_} at ({min_x}, {min_y}, {max_x}, {max_y})")

nearest_neighbor(point)

Find the nearest rectangle to a query point.

Distance is measured as Euclidean distance to the nearest edge of each rectangle.

Parameters:

Name Type Description Default
point Point

Query point as (x, y).

 required

Returns:

Type Description
_IdRect | None

Tuple of (id, min_x, min_y, max_x, max_y), or None if tree is empty.
Example 
nn = rqt.nearest_neighbor((15.0, 15.0))
if nn is not None:
    id_, min_x, min_y, max_x, max_y = nn
    print(f"Nearest: {id_} at ({min_x}, {min_y}, {max_x}, {max_y})")

nearest_neighbor_np(point)

Return the single nearest rectangle as NumPy array.

Parameters:

Name Type Description Default
point Point

Query point (x, y).

 required

Returns:

Type Description
tuple[int, Any] | None

Tuple of (id, coords) or None if tree is empty, where: id: int (uint64) coords: NDArray with shape (4,) and dtype matching tree

Raises:

Type Description
ImportError

If NumPy is not installed.

nearest_neighbors(point, k)

Return the k nearest rectangles to the query point.

Uses Euclidean distance to the nearest edge of rectangles.

Parameters:

Name Type Description Default
point Point

Query point (x, y).

 required
k int

Number of neighbors to return.

 required

Returns:

Type Description
list[_IdRect]

List of (id, min_x, min_y, max_x, max_y) tuples in order of increasing distance.
Example 
neighbors = rqt.nearest_neighbors((15.0, 15.0), k=5)
for id_, min_x, min_y, max_x, max_y in neighbors:
    print(f"Neighbor {id_} at ({min_x}, {min_y}, {max_x}, {max_y})")

nearest_neighbors_np(point, k)

Return the k nearest rectangles as NumPy arrays.

Parameters:

Name Type Description Default
point Point

Query point (x, y).

 required
k int

Number of neighbors to return.

 required

Returns:

Type Description
tuple[Any, Any]

Tuple of (ids, coords) where: ids: NDArray[np.uint64] with shape (k,) coords: NDArray with shape (k, 4) and dtype matching tree

Raises:

Type Description
ImportError

If NumPy is not installed.

delete(id_, min_x, min_y, max_x, max_y)

Remove a rectangle from the quadtree.

Coordinates must be provided since this class doesn't store geometry internally.

Parameters:

Name Type Description Default
id_ int

ID of the rectangle to delete.

 required
min_x float

Minimum x coordinate of the rectangle.

 required
min_y float

Minimum y coordinate of the rectangle.

 required
max_x float

Maximum x coordinate of the rectangle.

 required
max_y float

Maximum y coordinate of the rectangle.

 required

Returns:

Type Description
bool

True if the rectangle was found and deleted, False if not found.
Example 
rect_id = rqt.insert((10.0, 20.0, 30.0, 40.0))
success = rqt.delete(rect_id, 10.0, 20.0, 30.0, 40.0)
assert success is True

delete_tuple(t)

Remove a rectangle from the quadtree using a tuple.

This is a convenience method that accepts the rectangle data as a single tuple, typically from query results.

Parameters:

Name Type Description Default
t _IdRect

Tuple of (id, min_x, min_y, max_x, max_y) representing the rectangle to delete.

 required

Returns:

Type Description
bool

True if the rectangle was found and deleted, False if not found.
Example 
rect_id = rqt.insert((10.0, 20.0, 30.0, 40.0))
success = rqt.delete_tuple((rect_id, 10.0, 20.0, 30.0, 40.0))
assert success is True

update(id_, old_min_x, old_min_y, old_max_x, old_max_y, new_min_x, new_min_y, new_max_x, new_max_y)

Move an existing rectangle to a new location.

Old geometry is required because this class doesn't store it.

Parameters:

Name Type Description Default
id_ int

The ID of the rectangle to move.

 required
old_min_x float

Current min x coordinate.

 required
old_min_y float

Current min y coordinate.

 required
old_max_x float

Current max x coordinate.

 required
old_max_y float

Current max y coordinate.

 required
new_min_x float

New min x coordinate.

 required
new_min_y float

New min y coordinate.

 required
new_max_x float

New max x coordinate.

 required
new_max_y float

New max y coordinate.

 required

Returns:

Type Description
bool

True if the update succeeded.

Raises:

Type Description
ValueError

If new coordinates are outside bounds.
Example 
i = rqt.insert((1.0, 1.0, 2.0, 2.0))
ok = rqt.update(i, 1.0, 1.0, 2.0, 2.0, 3.0, 3.0, 4.0, 4.0)
assert ok is True

update_tuple(id_, old_rect, new_rect)

Move an existing rectangle to a new location using tuple geometry.

This is a convenience method that accepts geometry as tuples, reducing the number of parameters compared to update().

Parameters:

Name Type Description Default
id_ int

The ID of the rectangle to move.

 required
old_rect Bounds

Current rectangle as (min_x, min_y, max_x, max_y).

 required
new_rect Bounds

New rectangle as (min_x, min_y, max_x, max_y).

 required

Returns:

Type Description
bool

True if the update succeeded.

Raises:

Type Description
ValueError

If new coordinates are outside bounds.
Example 
i = rqt.insert((1.0, 1.0, 2.0, 2.0))
ok = rqt.update_tuple(i, (1.0, 1.0, 2.0, 2.0), (3.0, 3.0, 4.0, 4.0))
assert ok is True

__contains__(rect)

Check if any item exists at the given rectangle coordinates.

Parameters:

Name Type Description Default
rect Bounds

Rectangle as (min_x, min_y, max_x, max_y).

 required

Returns:

Type Description
bool

True if at least one item exists at these exact coordinates.
Example 
rqt.insert((10.0, 20.0, 30.0, 40.0))
assert (10.0, 20.0, 30.0, 40.0) in rqt
assert (5.0, 5.0, 10.0, 10.0) not in rqt

__iter__()

Iterate over all (id, min_x, min_y, max_x, max_y) tuples in the tree.

Example 
for id_, min_x, min_y, max_x, max_y in rqt:
    print(f"ID {id_} at ({min_x}, {min_y}, {max_x}, {max_y})")