fastquadtree

Rust-optimized quadtree with a clean Python API

👉 Check out the Docs: https://elan456.github.io/fastquadtree/

Why use fastquadtree

• Just pip install: prebuilt wheels for Windows, macOS, and Linux (no Rust or compiler needed)
• The fastest quadtree Python package (>10x faster than pyqtree)
• Clean Python API with no external dependencies and modern typing hints
• Support for inserting bounding boxes or points
• Fast KNN and range queries
• Optional object tracking for id ↔ object mapping
• Mostly drop-in pygame sprite-group integration that adds automatic broadphase culling plus rect queries and k-NN over sprite rects
• Fast serialization to/from bytes
• Support for multiple data types (f32, f64, i32, i64) for coordinates
• 100% test coverage and CI on GitHub Actions
• Offers a drop-in pyqtree shim that is ~10x faster while keeping the same API

Install

pip install fastquadtree

from fastquadtree import QuadTree # Or any of the other classes mentioned below
from fastquadtree.pyqtree import Index  # Drop-in pyqtree shim (~10x faster while keeping the same API)

Which class should I use?

Quickstart

1. Point indexing (QuadTree)

from fastquadtree import QuadTree

qt = QuadTree((0.0, 0.0, 1000.0, 1000.0), capacity=16)

# Insert points with explicit IDs (or omit id_ for auto IDs)
qt.insert((100.0, 200.0), id_=1)
qt.insert((120.0, 260.0), id_=2)
qt.insert((700.0, 800.0), id_=3)

# Range query returns (id, x, y)
hits = qt.query((0.0, 0.0, 500.0, 500.0))
print(hits)  # [(1, 100.0, 200.0), (2, 120.0, 260.0)]

2. Object tracking (QuadTreeObjects)

from fastquadtree import QuadTreeObjects

qto = QuadTreeObjects((0.0, 0.0, 1000.0, 1000.0), capacity=16)

player = {"name": "player-1", "team": "blue"}
enemy = {"name": "enemy-9", "team": "red"}

qto.insert((100.0, 200.0), obj=player)
qto.insert((130.0, 220.0), obj=enemy)

# Query returns PointItem objects with id_, x, y, geom, and obj
for item in qto.query((0.0, 0.0, 300.0, 300.0)):
    print(item.id_, item.x, item.y, item.obj["name"]) # 0 100.0 200.0 player-1
                                                      # 1 130.0 220.0 enemy-9

# Remove entries by object identity
qto.delete_by_object(player)  # returns 1 (number of items deleted)

See the quickstart guide or the interactive demos for more details.

Benchmarks

fastquadtree outperforms all other quadtree Python packages, including the Rtree spatial index.

Library comparison

Summary (PyQtree baseline, sorted by total time)

• Points: 500,000, Queries: 500

See the benchmark section for details, including configurations, system info, and native vs shim benchmarks.

API

See the full API

QuadTree(bounds, capacity, max_depth=None, dtype="f32")

• bounds — tuple (min_x, min_y, max_x, max_y) defines the 2D area covered by the quadtree
• capacity — max number of points kept in a leaf before splitting
• max_depth — optional depth cap. If omitted, uses the engine default
• dtype — data type for coordinates, e.g., "f32", "f64", "i32", "i64"

Key Methods

• insert(xy, id_=None) -> int

• query(rect) -> list[tuple[int, float, float]]

• nearest_neighbor(xy) -> tuple[int, float, float] | None

• delete(id, x, y) -> bool

For object tracking, use QuadTreeObjects instead. See the docs for more methods.

Geometric conventions

• Rectangles are (min_x, min_y, max_x, max_y).
• Containment rule is closed on the min edge and open on the max edge (x >= min_x and x < max_x and y >= min_y and y < max_y). This only matters for points exactly on edges.

Performance tips

• Choose capacity so that leaves keep a small batch of points. Typical values are 8 to 64.
• If your data is very skewed, set a max_depth to prevent long chains.
• For fastest local runs, use maturin develop --release.
• Use QuadTree when you only need spatial indexing. Use QuadTreeObjects when you need to store Python objects with your points.
• Refer to the Native vs Shim Benchmark for overhead details.

Pygame Ball Pit Demo

A simple demo of moving objects with collision detection using fastquadtree. You can toggle between fastquadtree, pyqtree, and brute-force mode to see the performance difference. I typically see an FPS of ~70 with fastquadtree, ~25 with pyqtree, and <1 FPS with brute-force on my machine with 1500 balls.

See the runnables guide for setup instructions.

FAQ

Can I delete items from the quadtree? Yes! Use delete(id, x, y) to remove specific items. You must provide both the ID and exact location for precise deletion. This handles cases where multiple items exist at the same location. If you're using QuadTreeObjects, you can also use delete_by_object(obj) for convenient object-based deletion with O(1) lookup. The tree automatically merges nodes when item counts drop below capacity.

Can I store rectangles or circles? Yes, you can store rectangles using the RectQuadTree class. Circles can be approximated with bounding boxes. See the RectQuadTree docs for details.

Do I need NumPy installed? No, NumPy is a fully optional dependency. If you do have NumPy installed, you can use methods such as query_np and insert_many_np for better performance. Note that insert_many raises TypeError on NumPy input—you must use insert_many_np explicitly for NumPy arrays. The Rust core is able to handle NumPy arrays faster than Python lists, so there's a lot of time savings in utilizing the NumPy functions. See the Native vs Shim benchmark for details on how returing NumPy arrays can speed up queries.

# Using Python lists
qt.insert_many([(10, 20), (30, 40), (50, 60)])

# Using NumPy arrays (requires NumPy)
import numpy as np
points = np.array([[10, 20], [30, 40], [50, 60]])
qt.insert_many_np(points)  # Use insert_many_np for NumPy arrays

Does fastquadtree support multiprocessing? Yes, fastquadtree objects can be serialized to bytes using the to_bytes() method and deserialized back using from_bytes(). This allows you to share quadtree data across processes and even cache prebuilt trees to disk. When using QuadTreeObjects or RectQuadTreeObjects, you must pass include_objects=True to to_bytes() to serialize Python objects, and allow_objects=True to from_bytes() when loading. By default, objects are skipped for safety, as deserializing untrusted Python objects can be unsafe. Native decode uses a default preallocation limit of 67,108,864 bytes (64 MiB); if loading needs more than the configured bucket, from_bytes() fails with a ValueError unless you choose a larger allowed bucket or pass disable_preallocation_limit=True for trusted data. See the interactive v2 demo for an example of saving and loading a quadtree, and the QuadTreeObjects API docs for full details on the serialization methods.

Serialization uses the current fastquadtree binary format. Data serialized by bincode-backed fastquadtree releases, including v2.2 and earlier, is not loadable by newer wincode-backed releases.

License

MIT. See LICENSE.

Acknowledgments

• Python libraries compared: PyQtree, e-pyquadtree, Rtree, nontree, quads, Shapely
• Built with PyO3 and maturin