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

geometry_rtree/
lib.rs
