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
58#[cfg(test)]
59mod tests {
60    use super::Predicate;
61    use crate::bounds::Bounds;
62
63    #[test]
64    fn intersects_matches_overlap() {
65        let p = Predicate::Intersects(Bounds::new([0.0, 0.0], [2.0, 2.0]));
66        assert!(p.matches(&Bounds::new([1.0, 1.0], [3.0, 3.0])));
67        assert!(!p.matches(&Bounds::new([5.0, 5.0], [6.0, 6.0])));
68    }
69
70    #[test]
71    fn within_matches_contained() {
72        let p = Predicate::Within(Bounds::new([0.0, 0.0], [10.0, 10.0]));
73        assert!(p.matches(&Bounds::new([2.0, 2.0], [3.0, 3.0])));
74        assert!(!p.matches(&Bounds::new([2.0, 2.0], [12.0, 3.0])));
75    }
76
77    #[test]
78    fn contains_matches_covering() {
79        let p = Predicate::Contains(Bounds::new([4.0, 4.0], [5.0, 5.0]));
80        assert!(p.matches(&Bounds::new([0.0, 0.0], [10.0, 10.0])));
81        assert!(!p.matches(&Bounds::new([0.0, 0.0], [4.5, 4.5])));
82    }
83
84    #[test]
85    fn pruning_skips_disjoint_subtrees() {
86        let p = Predicate::Intersects(Bounds::new([0.0, 0.0], [1.0, 1.0]));
87        assert!(p.could_match(&Bounds::new([0.5, 0.5], [9.0, 9.0])));
88        assert!(!p.could_match(&Bounds::new([5.0, 5.0], [9.0, 9.0])));
89    }
90}
geometry_rtree/predicate.rs

geometry_rtree/
predicate.rs
