1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
//! 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 spatial
//! queries — intersects / within / contains — and k-nearest-neighbour
//! search, pruning the tree with each node's bounding box.
//!
//! 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`](node::Node) enum.
//! * [`split`] — the [`SplitParameters`] strategies.
//! * [`predicate`] — the query [`Predicate`]s.
//! * [`rtree`](mod@rtree) — the [`Rtree`] and its insert / query /
//! nearest / bulk load.
//! * [`query_iter`] — [`QueryIter`], the lazy
//! spatial-query walk.
//! * [`nearest_iter`] — [`NearestIter`], the
//! unbounded nearest-first stream.
//! * `search_frontier` / `nearest_bound` (crate-internal) — the nearest
//! search's stack-first frontier and k-th-best rank buffer.
//!
//! [`Indexable`]: indexable::Indexable
extern crate alloc;
pub use Bounds;
pub use Indexable;
pub use NearestIter;
pub use Predicate;
pub use QueryIter;
pub use Rtree;
pub use ;