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 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_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 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.

Trait Implementations

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> 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).