geometry_rtree/
predicate.rs

1//! Spatial query predicates.
2//!
3//! Mirrors `boost/geometry/index/predicates.hpp`. A predicate is tested
4//! against candidate values during a query walk; the tree prunes any
5//! subtree whose bounds cannot satisfy the predicate.
6//!
7//! v1 ships the box-level predicates the pruning walk needs directly —
8//! [`Predicate::Intersects`], [`Predicate::Within`],
9//! [`Predicate::Contains`]. The interior/boundary DE-9IM predicates
10//! (`covered_by`, `overlaps`) layer on top once the value type carries a
11//! full geometry rather than only its bounds.
12
13use crate::bounds::Bounds;
14
15/// A spatial query against the index, expressed on bounding boxes.
16///
17/// Mirrors the `index::detail::predicates` family
18/// (`index/predicates.hpp`). Each variant carries the query box.
19#[derive(Debug, Clone, Copy, PartialEq)]
20pub enum Predicate {
21    /// Values whose bounds intersect the query box. Boost's
22    /// `index::intersects`.
23    Intersects(Bounds),
24    /// Values whose bounds are fully inside the query box. Boost's
25    /// `index::within`.
26    Within(Bounds),
27    /// Values whose bounds fully contain the query box. Boost's
28    /// `index::contains`.
29    Contains(Bounds),
30}
31
32impl Predicate {
33    /// Whether a leaf value with box `value` satisfies this predicate.
34    #[must_use]
35    pub fn matches(&self, value: &Bounds) -> bool {
36        match self {
37            Predicate::Intersects(q) => q.intersects(value),
38            Predicate::Within(q) => q.contains(value),
39            Predicate::Contains(q) => value.contains(q),
40        }
41    }
42
43    /// Whether a subtree with box `node` could contain any matching
44    /// value — the pruning test. A subtree is skipped when this is
45    /// `false`.
46    #[must_use]
47    pub fn could_match(&self, node: &Bounds) -> bool {
48        match self {
49            // Intersect / within candidates must overlap the query box.
50            Predicate::Intersects(q) | Predicate::Within(q) => q.intersects(node),
51            // A value containing the query box must itself have a box
52            // overlapping the query, and the subtree must cover it.
53            Predicate::Contains(q) => node.intersects(q),
54        }
55    }
56
57    /// Whether EVERY value in a subtree with box `node` is a guaranteed
58    /// match — the containment fast path. A covered subtree is dumped
59    /// without per-node or per-value tests.
60    ///
61    /// Sound because a value's box ⊆ its node's box: for `Intersects`
62    /// and `Within`, `q.contains(node)` implies every value below
63    /// matches. `Contains` needs value ⊇ q, which node ⊆ q says nothing
64    /// about, so it never takes the fast path.
65    #[must_use]
66    pub(crate) fn covers_all(&self, node: &Bounds) -> bool {
67        match self {
68            Predicate::Intersects(q) | Predicate::Within(q) => q.contains(node),
69            Predicate::Contains(_) => false,
70        }
71    }
72}
73
74#[cfg(test)]
75mod tests {
76    use super::Predicate;
77    use crate::bounds::Bounds;
78
79    #[test]
80    fn intersects_matches_overlap() {
81        let p = Predicate::Intersects(Bounds::new([0.0, 0.0], [2.0, 2.0]));
82        assert!(p.matches(&Bounds::new([1.0, 1.0], [3.0, 3.0])));
83        assert!(!p.matches(&Bounds::new([5.0, 5.0], [6.0, 6.0])));
84    }
85
86    #[test]
87    fn within_matches_contained() {
88        let p = Predicate::Within(Bounds::new([0.0, 0.0], [10.0, 10.0]));
89        assert!(p.matches(&Bounds::new([2.0, 2.0], [3.0, 3.0])));
90        assert!(!p.matches(&Bounds::new([2.0, 2.0], [12.0, 3.0])));
91    }
92
93    #[test]
94    fn contains_matches_covering() {
95        let p = Predicate::Contains(Bounds::new([4.0, 4.0], [5.0, 5.0]));
96        assert!(p.matches(&Bounds::new([0.0, 0.0], [10.0, 10.0])));
97        assert!(!p.matches(&Bounds::new([0.0, 0.0], [4.5, 4.5])));
98    }
99
100    #[test]
101    fn pruning_skips_disjoint_subtrees() {
102        let p = Predicate::Intersects(Bounds::new([0.0, 0.0], [1.0, 1.0]));
103        assert!(p.could_match(&Bounds::new([0.5, 0.5], [9.0, 9.0])));
104        assert!(!p.could_match(&Bounds::new([5.0, 5.0], [9.0, 9.0])));
105    }
106
107    const QUERY: Bounds = Bounds::new([0.0, 0.0], [10.0, 10.0]);
108    const CONTAINED: Bounds = Bounds::new([2.0, 2.0], [3.0, 3.0]);
109    const OVERLAPPING: Bounds = Bounds::new([5.0, 5.0], [15.0, 15.0]);
110    const DISJOINT: Bounds = Bounds::new([20.0, 20.0], [30.0, 30.0]);
111
112    #[test]
113    fn covers_all_intersects() {
114        let p = Predicate::Intersects(QUERY);
115        assert!(p.covers_all(&CONTAINED));
116        assert!(p.covers_all(&QUERY));
117        assert!(!p.covers_all(&OVERLAPPING));
118        assert!(!p.covers_all(&DISJOINT));
119    }
120
121    #[test]
122    fn covers_all_within() {
123        let p = Predicate::Within(QUERY);
124        assert!(p.covers_all(&CONTAINED));
125        assert!(p.covers_all(&QUERY));
126        assert!(!p.covers_all(&OVERLAPPING));
127        assert!(!p.covers_all(&DISJOINT));
128    }
129
130    #[test]
131    fn covers_all_contains_never() {
132        let p = Predicate::Contains(QUERY);
133        assert!(!p.covers_all(&CONTAINED));
134        assert!(!p.covers_all(&QUERY));
135        assert!(!p.covers_all(&OVERLAPPING));
136        assert!(!p.covers_all(&DISJOINT));
137    }
138}
geometry_rtree/predicate.rs

geometry_rtree/
predicate.rs
