Skip to content

fastquadtree.RectQuadTree

Bases: _BaseQuadTree[Bounds, _IdRect, RectItem]

Rectangle version of the quadtree. All geometries are axis-aligned rectangles. (min_x, min_y, max_x, max_y) High-level Python wrapper over the Rust quadtree engine.

Performance characteristics

Inserts: average O(log n)
Rect queries: average O(log n + k) where k is matches returned
Nearest neighbor: average O(log n)

Thread-safety

Instances are not thread-safe. Use external synchronization if you mutate the same tree from multiple threads.

Parameters:

Name Type Description Default
bounds Bounds

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

 required
capacity int

Max number of points per node before splitting.

 required
max_depth int | None

Optional max tree depth. If omitted, engine decides.

 None
track_objects bool

Enable id <-> object mapping inside Python.

 False
dtype str

Data type for coordinates and ids in the native engine. Default is 'f32'. Options are 'f32', 'f64', 'i32', 'i64'.

 'f32'

Raises:

Type Description
ValueError

If parameters are invalid or inserts are out of bounds.

to_dict()

Serialize the quadtree to a dict suitable for JSON or other serialization.

Returns:

Type Description
dict[str, Any]

Includes a binary 'core' key for the native engine state, plus other metadata such as bounds and capacity and the obj store if tracking is enabled.
Example 
state = qt.to_dict()
assert "core" in state and "bounds" in state

to_bytes()

Serialize the quadtree to bytes.

Returns:

Type Description
bytes

Bytes representing the serialized quadtree. Can be saved as a file or loaded with from_bytes().
Example 
blob = qt.to_bytes()
with open("tree.fqt", "wb") as f:
    f.write(blob)

from_bytes(data, dtype='f32') classmethod

Deserialize a quadtree from bytes. Specifiy the dtype if the original tree that was serialized used a non-default dtype.

Parameters:

Name Type Description Default
data bytes

Bytes representing the serialized quadtree from to_bytes().

 required
dtype str

The data type used in the native engine ('f32', 'f64', 'i32', 'i64') when saved to bytes.

 'f32'

Returns:

Type Description
Self

A new quadtree instance with the same state as when serialized.
Example 
blob = qt.to_bytes()
qt2 = type(qt).from_bytes(blob)
assert qt2.count_items() == qt.count_items()

insert(geom, *, obj=None)

Insert a single item.

Parameters:

Name Type Description Default
geom G

Point (x, y) or Rect (x0, y0, x1, y1) depending on quadtree type.

 required
obj Any | None

Optional Python object to associate with id if tracking is enabled.

 None

Returns:

Type Description
int

The id used for this insert.

Raises:

Type Description
ValueError

If geometry is outside the tree bounds.
Example 
id0 = point_qt.insert((10.0, 20.0))  # for point trees
id1 = rect_qt.insert((0.0, 0.0, 5.0, 5.0), obj="box")  # for rect trees
assert isinstance(id0, int) and isinstance(id1, int)

insert_many(geoms, objs=None) 

insert_many(geoms: Sequence[G], objs: list[Any] | None = None) -> int

insert_many(geoms: NDArray[Any], objs: list[Any] | None = None) -> int

Bulk insert with auto-assigned contiguous ids. Faster than inserting one-by-one.
Can accept either a Python sequence of geometries or a NumPy array of shape (N,2) or (N,4) with a dtype that matches the quadtree's dtype.

If tracking is enabled, the objects will be bulk stored internally. If no objects are provided, the items will have obj=None (if tracking).

Parameters:

Name Type Description Default
geoms NDArray[Any] | Sequence[G]

List of geometries.

 required
objs list[Any] | None

Optional list of Python objects aligned with geoms.

 None

Returns:

Type Description
int

Number of items inserted.

Raises:

Type Description
ValueError

If any geometry is outside bounds.
Example 
n = qt.insert_many([(1.0, 1.0), (2.0, 2.0)])
assert n == 2

import numpy as np
arr = np.array([[3.0, 3.0], [4.0, 4.0]], dtype=np.float32)
n2 = qt.insert_many(arr)
assert n2 == 2

delete(id_, geom)

Delete an item by id and exact geometry.

Parameters:

Name Type Description Default
id_ int

The id of the item to delete.

 required
geom G

The geometry of the item to delete.

 required

Returns:

Type Description
bool

True if the item was found and deleted.
Example 
i = qt.insert((1.0, 2.0))
ok = qt.delete(i, (1.0, 2.0))
assert ok is True

attach(id_, obj)

Attach or replace the Python object for an existing id. Tracking must be enabled.

Parameters:

Name Type Description Default
id_ int

The id of the item to attach the object to.

 required
obj Any

The Python object to attach.

 required
Example 
i = qt.insert((2.0, 3.0), obj=None)
qt.attach(i, {"meta": 123})
assert qt.get(i) == {"meta": 123}

delete_by_object(obj)

Delete an item by Python object identity. Tracking must be enabled.

Parameters:

Name Type Description Default
obj Any

The Python object to delete.

 required
Example 
i = qt.insert((3.0, 4.0), obj="tag")
ok = qt.delete_by_object("tag")
assert ok is True

clear()

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

If tracking is enabled, the id -> object mapping is also cleared. The ids are reset to start at zero again.

Example 
_ = qt.insert((5.0, 6.0))
qt.clear()
assert qt.count_items() == 0 and len(qt) == 0

get_all_objects()

Return all tracked Python objects in the tree.

Example 
_ = qt.insert((7.0, 8.0), obj="a")
_ = qt.insert((9.0, 1.0), obj="b")
objs = qt.get_all_objects()
assert set(objs) == {"a", "b"}

get_all_items()

Return all Item wrappers in the tree.

Example: 

_ = qt.insert((1.0, 1.0), obj=None)
items = qt.get_all_items()
assert hasattr(items[0], "id_") and hasattr(items[0], "geom")

get_all_node_boundaries()

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

Example 
bounds = qt.get_all_node_boundaries()
assert isinstance(bounds, list)

get(id_)

Return the object associated with id, if tracking is enabled.

Example 
i = qt.insert((1.0, 2.0), obj={"k": "v"})
obj = qt.get(i)
assert obj == {"k": "v"}

count_items()

Return the number of items currently in the tree (native count).

Example 
before = qt.count_items()
_ = qt.insert((2.0, 2.0))
assert qt.count_items() == before + 1

get_inner_max_depth()

Return the maximum depth of the quadtree core. Useful if you let the core chose the default max depth based on dtype by constructing with max_depth=None.

Example 
depth = qt.get_inner_max_depth()
assert isinstance(depth, int)

query(rect, *, as_items=False) 

query(rect: Bounds, *, as_items: Literal[False] = ...) -> list[_IdRect]

query(rect: Bounds, *, as_items: Literal[True]) -> list[RectItem]

Query the tree for all items that intersect the given rectangle.

Parameters:

Name Type Description Default
rect Bounds

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

 required
as_items bool

If True, return Item wrappers. If False, return raw tuples.

 False

Returns:

Type Description
list[_IdRect] | list[RectItem]

If as_items is False: list of (id, x0, y0, x1, y1) tuples.
list[_IdRect] | list[RectItem]

If as_items is True: list of Item objects.
Example 
results = rqt.query((10.0, 10.0, 20.0, 20.0), as_items=True)
for item in results:
    print(f"Found rect id={item.id_} at {item.geom} with obj={item.obj}")

query_np(rect)

Return all points inside an axis-aligned rectangle as NumPy arrays. The first array is an array of IDs, and the second is a corresponding array of rectangle coordinates.

Requirements

NumPy must be installed to use this method.

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, locations) where: ids: NDArray[np.uint64] with shape (N,) locations: NDArray[np.floating] with shape (N, 4)
Example 
ids, locations = rqt.query_np((10.0, 10.0, 20.0, 20.0))
for id_, (x0, y0, x1, y1) in zip(ids, locations):
    print(f"Found rect id={id_} at ({x0}, {y0}, {x1}, {y1})")