Rust-optimized quadtree with a clean Python API
👉 Check out the Docs: https://elan456.github.io/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
- 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
pip install fastquadtreefrom fastquadtree import QuadTree # Point handling
from fastquadtree import RectQuadTree # Bounding box handling
from fastquadtree import QuadTreeObjects # Point handling with object tracking
from fastquadtree import RectQuadTreeObjects # Bounding box handling with object tracking
from fastquadtree.pyqtree import Index # Drop-in pyqtree shim (~10x faster while keeping the same API)from fastquadtree import QuadTree
qt = QuadTree((0, 0, 1000, 1000), 16) # bounds and capacity
qt.insert((100, 200), id_=1) # insert point with ID 1
print(qt.query((0, 0, 500, 500))) # gets all points in that area: [(1, 100.0, 200.0)]See the quickstart guide or the interactive demos for more details.
fastquadtree outperforms all other quadtree Python packages, including the Rtree spatial index.
- Points: 500,000, Queries: 500
| Library | Build (s) | Query (s) | Total (s) | Speed vs PyQtree |
|---|---|---|---|---|
| fastquadtree (np)1 | 0.052 | 0.017 | 0.068 | 42.52× |
| fastquadtree2 | 0.054 | 0.231 | 0.285 | 10.20× |
| Shapely STRtree3 | 0.200 | 0.110 | 0.309 | 9.40× |
| fastquadtree (obj tracking)4 | 0.263 | 0.093 | 0.356 | 8.17× |
| nontree-QuadTree | 0.826 | 0.844 | 1.670 | 1.74× |
| Rtree | 1.805 | 0.546 | 2.351 | 1.24× |
| e-pyquadtree | 1.530 | 0.941 | 2.471 | 1.18× |
| quads | 1.907 | 0.759 | 2.667 | 1.09× |
| PyQtree | 2.495 | 0.414 | 2.909 | 1.00× |
See the benchmark section for details, including configurations, system info, and native vs shim benchmarks.
bounds— tuple(min_x, min_y, max_x, max_y)defines the 2D area covered by the quadtreecapacity— max number of points kept in a leaf before splittingmax_depth— optional depth cap. If omitted, the tree can keep splitting as neededdtype— data type for coordinates, e.g.,"f32","f64","i32","i64"
-
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.
- 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.
- Choose
capacityso that leaves keep a small batch of points. Typical values are 8 to 64. - If your data is very skewed, set a
max_depthto prevent long chains. - For fastest local runs, use
maturin develop --release. - Use
QuadTreewhen you only need spatial indexing. UseQuadTreeObjectswhen you need to store Python objects with your points. - Refer to the Native vs Shim Benchmark for overhead details.
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.
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 arraysDoes 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. 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.
MIT. See LICENSE.
- Python libraries compared: PyQtree, e-pyquadtree, Rtree, nontree, quads, Shapely
- Built with PyO3 and maturin