Struct Rtree 

pub struct Rtree<T: Indexable, Params: SplitParameters = AsymmetricRStarSplit<6, 2, 12, 4, 4, 4>> { /* private fields */ }

A spatial index over Indexable values, parameterised by a split strategy.

Mirrors boost::geometry::index::rtree<Value, Parameters> (index/rtree.hpp). The default uses six-child branches and 12-value leaves for insertion, with four-child branches and four-value leaves for bulk packing, via AsymmetricRStarSplit; pass a symmetric RStarSplit, Quadratic, or Linear as Params for a different trade-off. Most users should retain the default; the split module explains the parameter order, validity constraints, tuning process, and benchmark evidence.

Examples

use geometry_cs::Cartesian;
use geometry_model::Point2D;
use geometry_rtree::Rtree;

type P = Point2D<f64, Cartesian>;
let mut tree: Rtree<P> = Rtree::new();
tree.insert(P::new(1.0, 1.0));
tree.insert(P::new(5.0, 5.0));
assert_eq!(tree.len(), 2);

Implementations

impl<T: Indexable, Params: SplitParameters> Rtree<T, Params>

pub fn new() -> Self

An empty tree.

pub fn len(&self) -> usize

Number of values in the tree.

pub fn is_empty(&self) -> bool

Whether the tree holds no values.

pub fn height(&self) -> usize

The height of the tree (a single-leaf tree is height 1).

This is cached and returned in constant time.

pub fn bounds(&self) -> Option<Bounds>

The bounding box covering every value, or None for an empty tree.

pub fn iter(&self) -> Values<'_, T>

Iterate over every stored value in depth-first tree order.

pub fn clear(&mut self)

Remove every value while retaining this tree’s split strategy.

pub fn insert(&mut self, value: T)

Insert one value.

Descends by least-enlargement to a leaf, inserts, and splits and propagates upward if a node overflows. Mirrors visitors/insert.hpp.

pub fn query(&self, predicate: Predicate) -> Vec<&T>

Every value whose bounds satisfy predicate.

query_iter collected — the lazy walk is the crate’s single query implementation. Mirrors visitors/spatial_query.hpp.

pub fn query_with<P: QueryPredicate<T>>(&self, predicate: P) -> Vec<&T>

Every value accepted by a logical or user-defined predicate.

This is the extensible companion to query.

pub fn query_iter(&self, predicate: Predicate) -> QueryIter<'_, T>

Lazily iterate the values whose bounds satisfy predicate.

The pruning walk of visitors/spatial_query.hpp as a lazy iterator: stopping early performs no traversal past the value stopped at, and folding stores no output. query is this walk collected.

Examples

Fold without collecting:

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

let tree: Rtree<(Bounds, u32)> = (0..100u32)
    .map(|i| (Bounds::point([f64::from(i), 0.0]), i))
    .collect();
let window = Predicate::Intersects(Bounds::new([10.0, -1.0], [19.0, 1.0]));
let id_sum: u32 = tree.query_iter(window).map(|(_, id)| id).sum();
assert_eq!(id_sum, (10..=19).sum());

pub fn query_iter_with<P: QueryPredicate<T>>( &self, predicate: P, ) -> QueryWithIter<'_, T, P>

Lazily iterate values accepted by a logical or user-defined predicate.

Built-in spatial predicates should use query_iter, whose concrete iterator keeps that common path compact.

pub fn nearest_iter(&self, query: [f64; 2]) -> NearestIter<'_, T>

Lazily iterate ALL values, nearest to query first — an unbounded ordered stream over the entire tree.

The consumer supplies its own bound via take; with no k up front nothing can be pruned, so a caller who knows k and wants maximum pruning calls nearest instead. Distances are compared SQUARED, the same ordering nearest uses.

Examples

Nearest-one:

use geometry_rtree::{Bounds, Rtree};

let tree: Rtree<(Bounds, u32)> = (0..100u32)
    .map(|i| (Bounds::point([f64::from(i), 0.0]), i))
    .collect();
let (_, nearest_id) = tree.nearest_iter([41.7, 0.0]).next().unwrap();
assert_eq!(*nearest_id, 42);

Over-fetch and re-rank: take more than needed by box distance, re-rank by a finer key, keep the best:

use geometry_rtree::{Bounds, Rtree};

let tree: Rtree<(Bounds, u32)> = (0..100u32)
    .map(|i| (Bounds::point([f64::from(i), 0.0]), i))
    .collect();
let mut candidates: Vec<&(Bounds, u32)> =
    tree.nearest_iter([50.2, 0.0]).take(8).collect();
candidates.sort_by_key(|(_, id)| *id);
candidates.truncate(2);
let ids: Vec<u32> = candidates.iter().map(|(_, id)| *id).collect();
assert_eq!(ids, [47, 48]);

pub fn nearest_iter_with_inline_capacities<const NODE_INLINE_CAPACITY: usize, const VALUE_INLINE_CAPACITY: usize>( &self, query: [f64; 2], ) -> NearestIter<'_, T, NODE_INLINE_CAPACITY, VALUE_INLINE_CAPACITY>

Lazily iterate all values nearest-first with caller-selected inline capacities for the node and value frontiers.

Entries beyond either capacity spill that frontier to an allocated binary heap. Smaller capacities reduce the iterator’s stack footprint and initialization cost; larger capacities avoid spills on wider searches. Prefer nearest_iter unless measurements for the caller’s tree and query distribution justify a different pair.

pub fn nearest(&self, query: [f64; 2], k: usize) -> Vec<&T>

The k values nearest to the query point, closest first.

Best-first search over node bounding boxes by SQUARED minimum possible distance (same ordering as true distance, no square roots). A stack-first frontier (SearchFrontier) holds unexpanded NODES only, popped nearest-first; candidate values never enter it. Each candidate instead goes through a bounded max-heap (NearestBound) whose entries pair each distance with its value. Collecting the final values reuses that heap’s allocation in place, so the whole search performs one min(k, len)-sized heap allocation unless the frontier spills.

Termination: a child’s box is contained in its parent’s, so frontier pops ascend in minimum possible distance. When a popped node’s distance reaches the k-th-best value distance, every value in every unvisited subtree is at least that far away and the held ranks are final; equality only ties distances already held. Mirrors visitors/distance_query.hpp.

This bounded implementation stays dedicated: its best-k pruning needs k up front, which the unbounded nearest_iter stream cannot have.

pub fn count(&self, value: &T) -> usize

where T: PartialEq,

Count values equal to value.

Mirrors boost::geometry::index::rtree::count. Equality is evaluated with T::eq; the indexable bounds are not used as a substitute for value equality.

pub fn remove(&mut self, value: &T) -> usize

where T: PartialEq,

Remove one value equal to value, returning 1 when found and 0 otherwise.

Underfull nodes are detached and their remaining values are reinserted, then a one-child root is collapsed. This is the value-level analogue of Boost’s visitors/remove.hpp condense walk and preserves every configured minimum-fill invariant.

pub fn remove_all<'a, I>(&mut self, values: I) -> usize

where T: PartialEq + 'a, I: IntoIterator<Item = &'a T>,

Remove one occurrence of each supplied value and return the number removed.

This is the Rust iterator counterpart of Boost’s range-removal overload.

Trait Implementations

impl<T: Indexable + Clone, Params: SplitParameters> Clone for Rtree<T, Params>

fn clone(&self) -> Self

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<T: Debug + Indexable, Params: Debug + SplitParameters> Debug for Rtree<T, Params>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<T: Indexable, Params: SplitParameters> Default for Rtree<T, Params>

fn default() -> Self

Returns the “default value” for a type.

impl<T: Indexable, Params: SplitParameters> Extend<T> for Rtree<T, Params>

fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I)

Extends a collection with the contents of an iterator.

fn extend_one(&mut self, item: A)

🔬This is a nightly-only experimental API. (extend_one)

Extends a collection with exactly one element.

fn extend_reserve(&mut self, additional: usize)

🔬This is a nightly-only experimental API. (extend_one)

Reserves capacity in a collection for the given number of additional elements.

impl<T: Indexable, Params: SplitParameters> FromIterator<T> for Rtree<T, Params>

fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self

Bulk-load with top-down Sort-Tile-Recursive packing: recursively partition cached centroids into balanced x/y tiles until they fit the configured bulk leaf capacity. Produces a balanced tree, the analogue of Boost’s pack_create (index/detail/rtree/pack_create.hpp).

impl<'a, T: Indexable, Params: SplitParameters> IntoIterator for &'a Rtree<T, Params>

type Item = &'a T

The type of the elements being iterated over.

type IntoIter = Values<'a, T>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.