Crate geometry_rtree 

An R-tree spatial index over the geometry kernel.

Mirrors boost/geometry/index/rtree.hpp and the support headers under boost/geometry/index/detail/. Stores any Indexable value (a value with an axis-aligned bounding box) and answers Boost’s box predicates plus logical/satisfies queries and k-nearest-neighbour search. It also provides insertion, condensing removal, count, iteration, clear, bulk packing, and opt-in serde persistence.

The split strategy is a type parameter of Rtree. The default is AsymmetricRStarSplit with six-child branches and 12-value leaves for insertion, and four-child branches/four-value leaves for bulk packing; symmetric RStarSplit, Quadratic, and Linear configurations remain available. Bulk loading via FromIterator uses Sort-Tile-Recursive packing for a balanced tree in one pass. See split for parameter semantics, validity constraints, tuning guidance, and the benchmark evidence behind the default.

Cartesian, 2D, f64 for v1.

Index polygons and query a point

Implement Indexable for an application type by returning its axis-aligned bounds, then build an Rtree from an iterator. This example uses rectangular polygons, so a bounds intersection with a point is also an exact polygon intersection. For other polygon shapes, treat the result as a candidate set and apply an exact point-in-polygon test afterward.

use geometry_rtree::{Bounds, Indexable, Predicate, Rtree};

#[derive(Debug)]
struct Parcel {
    name: &'static str,
    boundary: [[f64; 2]; 5],
    bounds: Bounds,
}

impl Parcel {
    fn rectangle(name: &'static str, min: [f64; 2], max: [f64; 2]) -> Self {
        Self {
            name,
            boundary: [
                min,
                [min[0], max[1]],
                max,
                [max[0], min[1]],
                min,
            ],
            bounds: Bounds::new(min, max),
        }
    }
}

impl Indexable for Parcel {
    fn bounds(&self) -> Bounds {
        self.bounds
    }
}

let parcels = [
    Parcel::rectangle("park", [0.0, 0.0], [4.0, 3.0]),
    Parcel::rectangle("school", [5.0, 0.0], [8.0, 2.0]),
    Parcel::rectangle("lake", [1.0, 5.0], [3.0, 7.0]),
];
let tree: Rtree<Parcel> = parcels.into_iter().collect();

let point = Bounds::point([2.0, 1.0]);
let hits = tree.query(Predicate::Intersects(point));

assert_eq!(hits.len(), 1);
assert_eq!(hits[0].name, "park");
assert_eq!(hits[0].boundary[0], [0.0, 0.0]);

Module layout:

• bounds — the axis-aligned box arithmetic (area, enlargement, union, distance) the tree keys on.
• indexable — the Indexable trait.
• node — the leaf / branch Node enum.
• split — the SplitParameters strategies.
• predicate — built-in and composable query predicates.
• rtree — the Rtree and its mutation / query / nearest / bulk-load operations.
• query_iter — QueryIter and QueryWithIter, the lazy spatial-query walks.
• nearest_iter — NearestIter, the unbounded nearest-first stream.
• values — iteration over every stored value.
• serialization (feature-gated) — serde value-sequence persistence.
• search_frontier / nearest_bound (crate-internal) — the nearest search’s stack-first frontier and k-th-best rank buffer.

Re-exports

pub use bounds::Bounds;

pub use indexable::Indexable;

pub use nearest_iter::NearestIter;

pub use predicate::AndPredicate;

pub use predicate::NotPredicate;

pub use predicate::Predicate;

pub use predicate::QueryPredicate;

pub use predicate::Satisfies;

pub use predicate::and;

pub use predicate::not;

pub use predicate::satisfies;

pub use query_iter::QueryIter;

pub use query_iter::QueryWithIter;

pub use rtree::Rtree;

pub use split::AsymmetricQuadratic;

pub use split::AsymmetricRStarSplit;

pub use split::Linear;

pub use split::Quadratic;

pub use split::RStarSplit;

pub use split::SplitParameters;

pub use values::Values;

Modules

bounds

The axis-aligned bounding box used for tree keys.

indexable

The Indexable trait — what can be stored in an Rtree.

nearest_iter

Unbounded nearest-first streaming — the search behind Rtree::nearest_iter.

node

Tree nodes: leaves hold values, branches hold child subtrees.

predicate

Spatial query predicates.

query_iter

Lazy spatial-query iteration.

rtree

The Rtree itself — insert, spatial query, nearest-neighbour, and Sort-Tile-Recursive bulk load.

split

Node-split strategies — the type parameter that governs tree shape.

values

Iteration over all values stored in an R-tree.