fastquadtree.QuadTree¶

A spatial index for 2D points without object association.

Parameter Name Clarification

In the inherited methods below, the parameter geom refers to a point coordinate tuple (x, y).

For example:

insert(geom) means insert((x, y))
insert_many(geoms) means insert_many([(x1, y1), (x2, y2), ...])

Bases: _BaseQuadTree[Point]

Spatial index for 2D points without object association.

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

Parameters:

Name	Type	Description	Default
`bounds`	`Bounds`	World bounds as (min_x, min_y, max_x, max_y).	required
`capacity`	`int`	Maximum points 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

qt = QuadTree((0.0, 0.0, 100.0, 100.0), capacity=10)
point_id = qt.insert((10.0, 20.0))
results = qt.query((5.0, 5.0, 25.0, 25.0))
for id_, x, y in results:
    print(f"Point {id_} at ({x}, {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 points within a rectangular region.

Parameters:

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

Returns:

Type	Description
`list[_IdCoord]`	List of (id, x, y) tuples for points inside the rectangle.

Example

results = qt.query((10.0, 10.0, 20.0, 20.0))
for id_, x, y in results:
    print(f"Point {id_} at ({x}, {y})")

`query_np(rect)` ¶

Find all points within a rectangular region, 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, 2) and dtype matching the tree

Raises:

Type	Description
`ImportError`	If NumPy is not installed.

Example

ids, coords = qt.query_np((10.0, 10.0, 20.0, 20.0))
for id_, (x, y) in zip(ids, coords):
    print(f"Point {id_} at ({x}, {y})")

`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
`_IdCoord \| None`	Tuple of (id, x, y) or None if the tree is empty.

Example

nn = qt.nearest_neighbor((15.0, 15.0))
if nn is not None:
    id_, x, y = nn
    print(f"Nearest: {id_} at ({x}, {y})")

`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, where: id: int (uint64) coords: NDArray with shape (2,) and dtype matching tree

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[_IdCoord]`	List of (id, x, y) tuples in order of increasing distance.

Example

neighbors = qt.nearest_neighbors((15.0, 15.0), k=5)
for id_, x, y in neighbors:
    print(f"Neighbor {id_} at ({x}, {y})")

`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) where: ids: NDArray[np.uint64] with shape (k,) coords: NDArray with shape (k, 2) and dtype matching tree

Raises:

Type	Description
`ImportError`	If NumPy is not installed.

`delete(id_, x, y)` ¶

Remove a point 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 point to delete.	required
`x`	`float`	X coordinate of the point.	required
`y`	`float`	Y coordinate of the point.	required

Returns:

Type	Description
`bool`	True if the point was found and deleted, False if not found.

Example

point_id = qt.insert((10.0, 20.0))
success = qt.delete(point_id, 10.0, 20.0)
assert success is True

`delete_tuple(t)` ¶

Remove a point from the quadtree using a tuple.

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

Parameters:

Name	Type	Description	Default
`t`	`_IdCoord`	Tuple of (id, x, y) representing the point to delete.	required

Returns:

Type	Description
`bool`	True if the point was found and deleted, False if not found.

Example

point_id = qt.insert((10.0, 20.0))
success = qt.delete_tuple((point_id, 10.0, 20.0))
assert success is True

`update(id_, old_x, old_y, new_x, new_y)` ¶

Move a point to new coordinates.

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

Parameters:

Name	Type	Description	Default
`id_`	`int`	ID of the point to move.	required
`old_x`	`float`	Current X coordinate.	required
`old_y`	`float`	Current Y coordinate.	required
`new_x`	`float`	New X coordinate.	required
`new_y`	`float`	New Y coordinate.	required

Returns:

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

Raises:

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

Example

point_id = qt.insert((1.0, 1.0))
success = qt.update(point_id, 1.0, 1.0, 2.0, 2.0)
assert success is True

`update_tuple(id_, old_point, new_point)` ¶

Move an existing point 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 point to move.	required
`old_point`	`Point`	Current point as (x, y).	required
`new_point`	`Point`	New point as (x, y).	required

Returns:

Type	Description
`bool`	True if the update succeeded.

Raises:

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

Example

i = qt.insert((1.0, 1.0))
ok = qt.update_tuple(i, (1.0, 1.0), (2.0, 2.0))
assert ok is True

`contains(point)` ¶

Check if any item exists at the given point coordinates.

Parameters:

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

Returns:

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

Example

qt.insert((10.0, 20.0))
assert (10.0, 20.0) in qt
assert (5.0, 5.0) not in qt

`iter()` ¶

Iterate over all (id, x, y) tuples in the tree.

Example

for id_, x, y in qt:
    print(f"ID {id_} at ({x}, {y})")

fastquadtree.QuadTree¶

insert(geom, id_=None) ¶

insert_many(geoms) ¶

insert_many_np(geoms) ¶

clear() ¶

get_all_node_boundaries() ¶

get_inner_max_depth() ¶

to_bytes() ¶

from_bytes(data) classmethod ¶

query(rect) ¶

query_np(rect) ¶

nearest_neighbor(point) ¶

nearest_neighbor_np(point) ¶

nearest_neighbors(point, k) ¶

nearest_neighbors_np(point, k) ¶

delete(id_, x, y) ¶

delete_tuple(t) ¶

update(id_, old_x, old_y, new_x, new_y) ¶

update_tuple(id_, old_point, new_point) ¶

__contains__(point) ¶

__iter__() ¶

`insert(geom, id_=None)` ¶

`insert_many(geoms)` ¶

`insert_many_np(geoms)` ¶

`clear()` ¶

`get_all_node_boundaries()` ¶

`get_inner_max_depth()` ¶

`to_bytes()` ¶

`from_bytes(data)` `classmethod` ¶

`query(rect)` ¶

`query_np(rect)` ¶

`nearest_neighbor(point)` ¶

`nearest_neighbor_np(point)` ¶

`nearest_neighbors(point, k)` ¶

`nearest_neighbors_np(point, k)` ¶

`delete(id_, x, y)` ¶

`delete_tuple(t)` ¶

`update(id_, old_x, old_y, new_x, new_y)` ¶

`update_tuple(id_, old_point, new_point)` ¶

`contains(point)` ¶

`iter()` ¶