2.1.1

• Wheels are now built for CPython 3.9+ (previously 3.8+) to match the project’s supported Python range.
• Documentation dependencies are now split into a separate optional group, speeding up standard dev installs.

If you’re on Python 3.8, the latest compatible fastquadtree release is 1.2.1.

fastquadtree (FQT) will continue to support Python 3.9+ for the foreseeable future. If we ever raise the minimum (e.g., to 3.10+), it will be in a future major release (i.e. FQT 3.0).

Full Changelog: 2.1.0...2.1.1

2.1.0 - Rust Object Collection

• Major query speedup for QuadTreeObjects and RectQuadTreeObjects: the Rust core can now gather items/objects directly from the ObjStore, reducing the amount of Python list indexing.
• The pyqtree drop-in shim gets the same faster query path, so existing pyqtree code benefits immediately.

Speed-Up Example

Configuration

• Points: 500,000
• Queries: 500
• Repeats: 1

Results

Variant	Build	Query	Total
QuadTreeObjects (Before)	0.668	1.783	2.451
QuadTreeObjects (After)	0.659	0.832	1.492

Query time dropped by more than 50%!

Full Changelog: 2.0.4...2.1.0

2.0.4 - Switch to UV

Switched the package management and publishing tool to UV.

Full Changelog: 2.0.3...2.0.4

2.0.3

Full Changelog: 2.0.2...2.0.3

2.0.2

• Doc and README changes
• Ball pit interactive demo optimization and more info displayed
• Aliases for lowercase Quadtree to the QuadTree class across all quadtree types.

Full Changelog: 2.0.1...2.0.2

2.0.1

Full Changelog: 2.0.0...2.0.1

2.0.0 - A Cleaner API

fastquadtree 2.0 Release Notes

fastquadtree 2.0 is a major release focused on API clarity, predictable behavior, and zero-overhead defaults. This release includes breaking changes that simplify the library and improve performance for all use cases.

Breaking Changes

Class Split: track_objects Removed

The track_objects parameter has been removed. Object association is now determined by which class you use.

v1.x	v2.0
QuadTree(..., track_objects=False)	QuadTree(...)
QuadTree(..., track_objects=True)	QuadTreeObjects(...)
RectQuadTree(..., track_objects=False)	RectQuadTree(...)
RectQuadTree(..., track_objects=True)	RectQuadTreeObjects(...)

This eliminates runtime branching and keeps the fastest class as the default.

Query Return Types: as_items Removed

Return types are now fixed per class. The as_items parameter no longer exists.

# QuadTree always returns tuples
for id_, x, y in qt.query(rect):
    ...

# QuadTreeObjects always returns PointItem objects
for item in qt_obj.query(rect):
    print(item.id_, item.x, item.y, item.obj)

Explicit NumPy Methods

Runtime type detection has been removed. NumPy arrays are no longer accepted by standard methods.

# v1.x (removed)
qt.insert_many(np_array)  # worked via runtime detection

# v2.0
qt.insert_many([(1, 2), (3, 4)])           # Python sequences
qt.insert_many_np(np_array)                 # NumPy arrays

ids, coords = qt.query_np(rect)             # NumPy output
ids, coords = qt.nearest_neighbors_np(pt, k=5)

Passing a NumPy array to a non-_np method now raises TypeError.

Bulk Insert Returns InsertResult

insert_many() now returns an InsertResult dataclass instead of an int.

result = qt.insert_many(points)

result.count      # number inserted
result.start_id   # first ID in batch
result.end_id     # last ID in batch
result.ids        # range(start_id, end_id + 1)

Deletion Signature Changed

Non-Objects classes now take coordinates as separate arguments.

# v1.x
qt.delete(id_, (x, y))
rqt.delete(id_, (min_x, min_y, max_x, max_y))

# v2.0
qt.delete(id_, x, y)
rqt.delete(id_, min_x, min_y, max_x, max_y)

Objects classes can delete by ID alone since they track coordinates internally.

Serialization Format Changed

The serialization format has been updated. v1 serialized data is not compatible with v2.

# v1.x (removed)
state = qt.to_dict()
qt2 = QuadTree.from_dict(state)
qt2 = QuadTree.from_bytes(data, dtype="f32")

# v2.0
data = qt.to_bytes()          # dtype encoded in payload
qt2 = QuadTree.from_bytes(data)

Object serialization is now explicit and opt-in for safety:

data = qt_obj.to_bytes(include_objects=True)
qt2 = QuadTreeObjects.from_bytes(data, allow_objects=True)

count_items() Removed

Use the standard len() function instead:

n = len(qt)

New Features

Custom IDs for Non-Objects Classes

Single inserts now support user-provided IDs for correlating with external data structures.

qt.insert((10, 20), id_=42)
qt.insert((30, 40), id_=1000)

Note: The quadtree does not validate ID uniqueness. Users are responsible for avoiding collisions.

__contains__ Support

if (10.0, 20.0) in qt:
    print("Point exists")

Iteration

for id_, x, y in qt:
    ...

for item in qt_obj:
    print(item.id_, item.x, item.y, item.obj)

query_ids() for Objects Classes

Fast path when you only need IDs from an Objects tree:

ids = qt_obj.query_ids(rect)  # list[int]

update_by_object() for Objects Classes

Update an item's position by finding it via its associated object:

qt_obj.update_by_object(obj, new_x, new_y)
rqt_obj.update_by_object(obj, new_min_x, new_min_y, new_max_x, new_max_y)

Location-Based Deletion for Objects Classes

qt_obj.delete_at(x, y)  # deletes lowest-ID match at location

Object Deletion by Identity

qt_obj.delete_by_object(obj)      # deletes all matches, returns count
qt_obj.delete_one_by_object(obj)  # deletes one match (lowest ID)

Migration Summary

Find	Replace
QuadTree(..., track_objects=True)	QuadTreeObjects(...)
RectQuadTree(..., track_objects=True)	RectQuadTreeObjects(...)
, track_objects=False	(remove)
, as_items=True	(remove, use Objects class)
.insert_many(np_array)	.insert_many_np(np_array)
.delete(id_, (x, y))	.delete(id_, x, y)
.count_items()	len(...)

See the full Migration Guide for detailed upgrade instructions.

1.5.2

• You can request the start ID when inserting many
• Formally establish that the auto-assigned IDs start at 0 and increment. However, after a deletion, the hole will be filled, causing an ID to be reused

Full Changelog: 1.5.1...1.5.2

1.5.1

Full Changelog: 1.5.0...1.5.1

1.5.0 - KNN for RectQuadTree

RectQuadTree: New Nearest Neighbor Methods

New Features

nearest_neighbor(xy, *, as_item=False) — Find the single closest rectangle to a query point.

nearest_neighbors(xy, k, *, as_items=False) — Find the k closest rectangles to a query point, returned in order of increasing distance.

Both methods use euclidean distance to the nearest edge of each rectangle, making them ideal for spatial proximity queries against axis-aligned bounding boxes.

Example

# Find the 3 closest rectangles to a point
results = rqt.nearest_neighbors((15.0, 15.0), k=3, as_items=True)
for item in results:
    print(f"Rectangle {item.id_} at {item.geom}")

Use Cases

These methods are particularly useful for game development scenarios involving rectangular geometry. You can quickly determine which wall, platform, or obstacle is closest to a player or NPC for collision detection, pathfinding, or proximity triggers.