geometry_rtree/
lib.rs

1//! An R-tree spatial index over the geometry kernel.
2//!
3//! Mirrors `boost/geometry/index/rtree.hpp` and the support headers
4//! under `boost/geometry/index/detail/`. Stores any [`Indexable`] value
5//! (a value with an axis-aligned bounding box) and answers Boost's box
6//! predicates plus logical/satisfies queries and k-nearest-neighbour
7//! search. It also provides insertion, condensing removal, count,
8//! iteration, clear, bulk packing, and opt-in serde persistence.
9//!
10//! The split strategy is a type parameter of [`Rtree`]. The default is
11//! [`AsymmetricRStarSplit`] with six-child branches and 12-value
12//! leaves for insertion, and four-child branches/four-value leaves for
13//! bulk packing; symmetric [`RStarSplit`], [`Quadratic`], and [`Linear`]
14//! configurations remain available. Bulk loading via [`FromIterator`] uses
15//! Sort-Tile-Recursive packing for a balanced tree in one pass.
16//! See [`split`] for parameter semantics, validity constraints, tuning
17//! guidance, and the benchmark evidence behind the default.
18//!
19//! Cartesian, 2D, `f64` for v1.
20//!
21//! ## Index polygons and query a point
22//!
23//! Implement [`Indexable`] for an application type by returning its
24//! axis-aligned bounds, then build an [`Rtree`] from an iterator. This example
25//! uses rectangular polygons, so a bounds intersection with a point is also an
26//! exact polygon intersection. For other polygon shapes, treat the result as a
27//! candidate set and apply an exact point-in-polygon test afterward.
28//!
29//! ```
30//! use geometry_rtree::{Bounds, Indexable, Predicate, Rtree};
31//!
32//! #[derive(Debug)]
33//! struct Parcel {
34//!     name: &'static str,
35//!     boundary: [[f64; 2]; 5],
36//!     bounds: Bounds,
37//! }
38//!
39//! impl Parcel {
40//!     fn rectangle(name: &'static str, min: [f64; 2], max: [f64; 2]) -> Self {
41//!         Self {
42//!             name,
43//!             boundary: [
44//!                 min,
45//!                 [min[0], max[1]],
46//!                 max,
47//!                 [max[0], min[1]],
48//!                 min,
49//!             ],
50//!             bounds: Bounds::new(min, max),
51//!         }
52//!     }
53//! }
54//!
55//! impl Indexable for Parcel {
56//!     fn bounds(&self) -> Bounds {
57//!         self.bounds
58//!     }
59//! }
60//!
61//! let parcels = [
62//!     Parcel::rectangle("park", [0.0, 0.0], [4.0, 3.0]),
63//!     Parcel::rectangle("school", [5.0, 0.0], [8.0, 2.0]),
64//!     Parcel::rectangle("lake", [1.0, 5.0], [3.0, 7.0]),
65//! ];
66//! let tree: Rtree<Parcel> = parcels.into_iter().collect();
67//!
68//! let point = Bounds::point([2.0, 1.0]);
69//! let hits = tree.query(Predicate::Intersects(point));
70//!
71//! assert_eq!(hits.len(), 1);
72//! assert_eq!(hits[0].name, "park");
73//! assert_eq!(hits[0].boundary[0], [0.0, 0.0]);
74//! ```
75//!
76//! Module layout:
77//!
78//! * [`bounds`] — the axis-aligned box arithmetic (area, enlargement,
79//!   union, distance) the tree keys on.
80//! * [`indexable`] — the [`Indexable`] trait.
81//! * [`node`] — the leaf / branch [`Node`](node::Node) enum.
82//! * [`split`] — the [`SplitParameters`] strategies.
83//! * [`predicate`] — built-in and composable query predicates.
84//! * [`rtree`](mod@rtree) — the [`Rtree`] and its mutation / query /
85//!   nearest / bulk-load operations.
86//! * [`query_iter`] — [`QueryIter`] and [`QueryWithIter`], the lazy
87//!   spatial-query walks.
88//! * [`nearest_iter`] — [`NearestIter`], the
89//!   unbounded nearest-first stream.
90//! * [`values`] — iteration over every stored value.
91//! * `serialization` (feature-gated) — serde value-sequence persistence.
92//! * `search_frontier` / `nearest_bound` (crate-internal) — the nearest
93//!   search's stack-first frontier and k-th-best rank buffer.
94//!
95//! [`Indexable`]: indexable::Indexable
96
97#![cfg_attr(not(feature = "std"), no_std)]
98#![forbid(unsafe_code)]
99
100extern crate alloc;
101
102mod nearest_bound;
103mod search_frontier;
104#[cfg(feature = "serde")]
105mod serialization;
106
107pub mod bounds;
108pub mod indexable;
109pub mod nearest_iter;
110pub mod node;
111pub mod predicate;
112pub mod query_iter;
113pub mod rtree;
114pub mod split;
115pub mod values;
116
117pub use bounds::Bounds;
118pub use indexable::Indexable;
119pub use nearest_iter::NearestIter;
120// feature-group: Spatial index
121pub use predicate::{
122    AndPredicate, NotPredicate, Predicate, QueryPredicate, Satisfies, and, not, satisfies,
123};
124pub use query_iter::{QueryIter, QueryWithIter};
125// feature-group: Spatial index
126// feature-desc: Bulk-loadable R-tree with nearest-neighbour and predicate queries
127// feature-keep: Rtree
128pub use rtree::Rtree;
129pub use split::{
130    AsymmetricQuadratic, AsymmetricRStarSplit, Linear, Quadratic, RStarSplit, SplitParameters,
131};
132pub use values::Values;
geometry_rtree/lib.rs

geometry_rtree/
lib.rs
