fastquadtree.RectQuadTreeObjects¶

A spatial index for axis-aligned rectangles with automatic Python 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, obj) means insert((min_x, min_y, max_x, max_y), obj) - inserts a rectangle with an associated object
insert_many(geoms) means insert_many([(min_x1, min_y1, max_x1, max_y1), ...]) when using coordinates only

Bases: _BaseQuadTreeObjects[Bounds, RectItem]

Spatial index for axis-aligned rectangles with Python object association.

This class provides fast spatial indexing for rectangles while allowing you to associate arbitrary Python objects with each rectangle. IDs are managed internally using dense allocation for efficient lookup.

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 = RectQuadTreeObjects((0.0, 0.0, 100.0, 100.0), capacity=10)
rect_id = rqt.insert((10.0, 20.0, 30.0, 40.0), obj="my data")
results = rqt.query((5.0, 5.0, 35.0, 35.0))
for item in results:
    print(f"Rect {item.id_} at ({item.min_x}, {item.min_y}, {item.max_x}, {item.max_y})")

`insert(geom, obj=None)` ¶

Insert a single geometry with an optional associated object.

IDs are auto-assigned using dense allocation for efficient object lookup. Custom IDs are not supported in Objects classes.

Parameters:

Name	Type	Description	Default
`geom`	`G`	Geometry (Point or Bounds).	required
`obj`	`Any`	Optional Python object to associate with this geometry.	`None`

Returns:

Type	Description
`int`	The auto-assigned ID.

Raises:

Type	Description
`ValueError`	If geometry is outside the tree bounds.

`insert_many(geoms, objs=None)` ¶

Bulk insert geometries with auto-assigned contiguous IDs.

Note

For performance, this method always appends new items and does not reuse IDs from the free-list created by deletions. Use insert() to fill holes.

Parameters:

Name	Type	Description	Default
`geoms`	`list[G]`	List of geometries.	required
`objs`	`list[Any] \| None`	Optional list of Python objects aligned with geoms.	`None`

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 or objs length doesn't match.

`insert_many_np(geoms, objs=None)` ¶

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

Note

For performance, this method always appends new items and does not reuse IDs from the free-list created by deletions. Use insert() to fill holes.

Parameters:

Name	Type	Description	Default
`geoms`	`Any`	NumPy array with dtype matching the tree's dtype.	required
`objs`	`list[Any] \| None`	Optional list of Python objects aligned with geoms.	`None`

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 or objs length doesn't match.
`ImportError`	If NumPy is not installed.

`query(rect)` ¶

Return all items that intersect/contain the 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[ItemType]`	List of Item objects.

`query_ids(rect)` ¶

Return IDs of all items that intersect/contain the query rectangle.

Fast path that only returns IDs without fetching items.

Parameters:

Name	Type	Description	Default
`rect`	`Bounds`	Query rectangle as (min_x, min_y, max_x, max_y).	required

Returns:

Type	Description
`list[int]`	List of integer IDs.

`query_np(rect)` ¶

Return all items as 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 is NDArray[np.int64] and coords matches tree dtype.

Raises:

Type	Description
`ImportError`	If NumPy is not installed.

`nearest_neighbor(point)` ¶

Return the single nearest neighbor to the query point.

Parameters:

Name	Type	Description	Default
`point`	`Point`	Query point (x, y).	required

Returns:

Type	Description
`ItemType \| None`	Item or None if the tree is empty.

`nearest_neighbor_np(point)` ¶

Return the single nearest neighbor 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.

Raises:

Type	Description
`ImportError`	If NumPy is not installed.

`nearest_neighbors(point, k)` ¶

Return the k nearest neighbors to the query point.

Parameters:

Name	Type	Description	Default
`point`	`Point`	Query point (x, y).	required
`k`	`int`	Number of neighbors to return.	required

Returns:

Type	Description
`list[ItemType]`	List of Item objects in order of increasing distance.

`nearest_neighbors_np(point, k)` ¶

Return the k nearest neighbors 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) as NumPy arrays.

Raises:

Type	Description
`ImportError`	If NumPy is not installed.

`delete(id_)` ¶

Delete an item by ID alone.

Parameters:

Name	Type	Description	Default
`id_`	`int`	The ID of the item to delete.	required

Returns:

Type	Description
`bool`	True if the item was found and deleted.

`delete_by_object(obj)` ¶

Delete all items with the given object (by identity, not equality).

Parameters:

Name	Type	Description	Default
`obj`	`Any`	The Python object to search for.	required

Returns:

Type	Description
`int`	Number of items deleted.

`delete_one_by_object(obj)` ¶

Delete one item with the given object (by identity).

If multiple items have this object, deletes the one with the lowest ID.

Parameters:

Name	Type	Description	Default
`obj`	`Any`	The Python object to search for.	required

Returns:

Type	Description
`bool`	True if an item was deleted.

`clear()` ¶

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

`get(id_)` ¶

Return the object associated with the given ID.

Parameters:

Name	Type	Description	Default
`id_`	`int`	The ID to look up.	required

Returns:

Type	Description
`Any \| None`	The associated object or None if not found.

`attach(id_, obj)` ¶

Attach or replace the Python object for an existing ID.

Parameters:

Name	Type	Description	Default
`id_`	`int`	The ID of the item.	required
`obj`	`Any`	The Python object to attach.	required

Raises:

Type	Description
`KeyError`	If the ID is not found.

`get_all_objects()` ¶

Return all tracked Python objects in the tree.

`get_all_items()` ¶

Return all Item wrappers in the tree.

`contains(geom)` ¶

Check if any item exists at the given coordinates.

Parameters:

Name	Type	Description	Default
`geom`	`G`	Geometry to check.	required

Returns:

Type	Description
`bool`	True if at least one item exists at these exact coordinates.

`iter()` ¶

Iterate over all Item objects in the tree.

`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(include_objects=False)` ¶

Serialize the quadtree to bytes.

Safety

include_objects=False (default): safe to load from untrusted data (no pickle executed)
include_objects=True: includes a pickle section; unsafe for untrusted data

Parameters:

Name	Type	Description	Default
`include_objects`	`bool`	If True, serialize Python objects using pickle (unsafe).	`False`

Returns:

Type	Description
`bytes`	Bytes representing the serialized quadtree.

`from_bytes(data, allow_objects=False)` `classmethod` ¶

Deserialize a quadtree from bytes.

Parameters:

Name	Type	Description	Default
`data`	`bytes`	Bytes from to_bytes().	required
`allow_objects`	`bool`	If True, load pickled Python objects (unsafe). If False (default), object payloads are silently ignored.	`False`

Returns:

Type	Description
	A new instance.

Note

Object deserialization uses pickle-like semantics. Never load serialized data from untrusted sources with allow_objects=True.

`delete_at(min_x, min_y, max_x, max_y)` ¶

Delete a rectangle at specific coordinates.

If multiple rectangles exist at the same coordinates, deletes the one with the lowest ID.

Parameters:

Name	Type	Description	Default
`min_x`	`float`	Minimum X coordinate.	required
`min_y`	`float`	Minimum Y coordinate.	required
`max_x`	`float`	Maximum X coordinate.	required
`max_y`	`float`	Maximum Y coordinate.	required

Returns:

Type	Description
`bool`	True if a rectangle was found and deleted, False otherwise.

Example

rqt.insert((5.0, 5.0, 10.0, 10.0))
success = rqt.delete_at(5.0, 5.0, 10.0, 10.0)
assert success is True

`update(id_, new_min_x, new_min_y, new_max_x, new_max_y)` ¶

Move a rectangle to new coordinates.

This is efficient because old coordinates are retrieved from internal storage.

Parameters:

Name	Type	Description	Default
`id_`	`int`	ID of the rectangle to move.	required
`new_min_x`	`float`	New minimum X coordinate.	required
`new_min_y`	`float`	New minimum Y coordinate.	required
`new_max_x`	`float`	New maximum X coordinate.	required
`new_max_y`	`float`	New maximum Y coordinate.	required

Returns:

Type	Description
`bool`	True if the update succeeded, False if the ID was not found.

Raises:

Type	Description
`ValueError`	If new coordinates are outside tree bounds.

Example

rect_id = rqt.insert((1.0, 1.0, 2.0, 2.0))
success = rqt.update(rect_id, 3.0, 3.0, 4.0, 4.0)
assert success is True

`update_by_object(obj, new_min_x, new_min_y, new_max_x, new_max_y)` ¶

Move a rectangle to new coordinates by finding it via its associated object.

If multiple items have the same object, updates the one with the lowest ID.

Parameters:

Name	Type	Description	Default
`obj`	`Any`	Python object to search for (by identity).	required
`new_min_x`	`float`	New minimum X coordinate.	required
`new_min_y`	`float`	New minimum Y coordinate.	required
`new_max_x`	`float`	New maximum X coordinate.	required
`new_max_y`	`float`	New maximum Y coordinate.	required

Returns:

Type	Description
`bool`	True if the update succeeded, False if object was not found.

Raises:

Type	Description
`ValueError`	If new coordinates are outside tree bounds.

Example

my_obj = {"data": "example"}
rqt.insert((1.0, 1.0, 2.0, 2.0), obj=my_obj)
success = rqt.update_by_object(my_obj, 3.0, 3.0, 4.0, 4.0)
assert success is True

fastquadtree.RectQuadTreeObjects¶

insert(geom, obj=None) ¶

insert_many(geoms, objs=None) ¶

insert_many_np(geoms, objs=None) ¶

query(rect) ¶

query_ids(rect) ¶

query_np(rect) ¶

nearest_neighbor(point) ¶

nearest_neighbor_np(point) ¶

nearest_neighbors(point, k) ¶

nearest_neighbors_np(point, k) ¶

delete(id_) ¶

delete_by_object(obj) ¶

delete_one_by_object(obj) ¶

clear() ¶

get(id_) ¶

attach(id_, obj) ¶

get_all_objects() ¶

get_all_items() ¶

__contains__(geom) ¶

__iter__() ¶

get_all_node_boundaries() ¶

get_inner_max_depth() ¶

to_bytes(include_objects=False) ¶

from_bytes(data, allow_objects=False) classmethod ¶

delete_at(min_x, min_y, max_x, max_y) ¶

update(id_, new_min_x, new_min_y, new_max_x, new_max_y) ¶

update_by_object(obj, new_min_x, new_min_y, new_max_x, new_max_y) ¶

`insert(geom, obj=None)` ¶

`insert_many(geoms, objs=None)` ¶

`insert_many_np(geoms, objs=None)` ¶

`query(rect)` ¶

`query_ids(rect)` ¶

`query_np(rect)` ¶

`nearest_neighbor(point)` ¶

`nearest_neighbor_np(point)` ¶

`nearest_neighbors(point, k)` ¶

`nearest_neighbors_np(point, k)` ¶

`delete(id_)` ¶

`delete_by_object(obj)` ¶

`delete_one_by_object(obj)` ¶

`clear()` ¶

`get(id_)` ¶

`attach(id_, obj)` ¶

`get_all_objects()` ¶

`get_all_items()` ¶

`contains(geom)` ¶

`iter()` ¶

`get_all_node_boundaries()` ¶

`get_inner_max_depth()` ¶

`to_bytes(include_objects=False)` ¶

`from_bytes(data, allow_objects=False)` `classmethod` ¶

`delete_at(min_x, min_y, max_x, max_y)` ¶

`update(id_, new_min_x, new_min_y, new_max_x, new_max_y)` ¶

`update_by_object(obj, new_min_x, new_min_y, new_max_x, new_max_y)` ¶