rstar

rstar is a Rust implementation of the R*-tree, a self-balancing spatial data structure for indexing points and geometries in two or more dimensions. It answers nearest-neighbor, range, and intersection queries efficiently, making it a core building block for the GeoRust ecosystem and any application that needs fast spatial lookups.

It supports bulk loading for building trees quickly from large datasets, works with custom point types and objects through simple traits, and can run in no_std environments. Optional serde and mint integrations make it easy to persist trees and interoperate with other geometry libraries.

What You Get

• A generic R*-tree over custom point and geometry types via the RTreeObject trait
• Nearest-neighbor queries and ordered nearest-neighbor iteration
• Range and intersection queries against bounding envelopes
• Bulk loading to build balanced trees efficiently from large batches
• Optional serde persistence, mint interop, and no_std support

Common Use Cases

• Finding the nearest points of interest to a location
• Querying which geometries fall within a bounding box
• Detecting intersections between spatial objects in simulations or maps

Under The Hood

Architecture - rstar is the primary crate in a Cargo workspace (alongside rstar-demo and rstar-benches). Its src/ separates the geometric abstractions (point.rs, aabb.rs, envelope.rs, object.rs, primitives/) from the tree machinery (rtree.rs, node.rs, params.rs) and the query/insertion logic under algorithm/. Users plug in their own types through the Point and RTreeObject traits, and tree behavior is tunable via RTreeParams.

Tech Stack - Written in Rust (edition 2021, rust-version 1.85). It is no_std-friendly: heapless and smallvec provide stack-friendly storage, num-traits (with libm) supplies generic numerics, and serde and mint are optional integration features. Dev dependencies include rand for randomized tests and a separate benches crate uses criterion.

Code Quality - The codebase is trait-generic and heavily tested, with a dedicated test_utilities.rs, categories declared for crates.io (data-structures, algorithms, science::geo), and an actively-developed maintenance badge. With 42 contributors and long history under GeoRust, it follows the ecosystem’s rigorous review conventions and keeps a dedicated benchmark crate to guard performance.

API Design - The public API is compact: implement RTreeObject (and PointDistance for nearest-neighbor) for your type, then use RTree::bulk_load or insert, and query via nearest_neighbor, locate_in_envelope, locate_at_point, and related methods. Trait-based extensibility keeps the surface small while supporting arbitrary geometries, and docs.rs documentation is thorough with examples, though the generic trait bounds add some initial learning curve.