geometry_algorithm/
disjoint.rs

1//! `disjoint(&a, &b)` — see
2//! `boost/geometry/algorithms/disjoint.hpp`.
3//!
4//! Defined as the negation of [`crate::intersects()`] for every pair
5//! the intersects kernel handles. Mirrors Boost's interface header
6//! that resolves one of the two through the other
7//! (`algorithms/detail/intersects/interface.hpp:64-78`).
8
9use geometry_coords::CoordinateScalar;
10use geometry_strategy::{CartesianIntersects, IntersectsStrategy};
11use geometry_trait::{Box as BoxTrait, Geometry, Point as PointTrait};
12
13/// `true` iff `a` and `b` share **no** point.
14///
15/// Mirrors `boost::geometry::disjoint(a, b)` from
16/// `boost/geometry/algorithms/disjoint.hpp`.
17#[inline]
18#[must_use]
19pub fn disjoint<A, B>(a: &A, b: &B) -> bool
20where
21    CartesianIntersects: IntersectsStrategy<A, B>,
22{
23    !CartesianIntersects.intersects(a, b)
24}
25
26/// `disjoint` for two axis-aligned boxes — a direct separating-axis
27/// test, skipping the general intersects machinery.
28///
29/// Two boxes are disjoint iff they are separated on **either** axis:
30/// one's maximum on an axis is below the other's minimum. Mirrors the
31/// box/box specialisation in
32/// `boost/geometry/strategies/cartesian/disjoint_box_box.hpp`, which
33/// short-circuits per axis rather than routing through `intersects`.
34///
35/// This is a CC5 fast path: `disjoint(Box, Box)` is one of the hottest
36/// pair-combinations (envelope pruning, rtree node tests), and the
37/// per-axis comparison is far cheaper than the generic areal intersects.
38///
39/// # Examples
40///
41/// ```
42/// use geometry_algorithm::disjoint_box_box;
43/// use geometry_cs::Cartesian;
44/// use geometry_model::{Box, Point2D};
45///
46/// type P = Point2D<f64, Cartesian>;
47/// let a = Box::from_corners(P::new(0.0, 0.0), P::new(2.0, 2.0));
48/// let far = Box::from_corners(P::new(5.0, 5.0), P::new(6.0, 6.0));
49/// let overlapping = Box::from_corners(P::new(1.0, 1.0), P::new(3.0, 3.0));
50/// assert!(disjoint_box_box(&a, &far));
51/// assert!(!disjoint_box_box(&a, &overlapping));
52/// ```
53#[inline]
54#[must_use]
55pub fn disjoint_box_box<A, B, T>(a: &A, b: &B) -> bool
56where
57    A: BoxTrait,
58    B: BoxTrait,
59    <A as Geometry>::Point: PointTrait<Scalar = T>,
60    <B as Geometry>::Point: PointTrait<Scalar = T>,
61    T: CoordinateScalar,
62{
63    (0..<A as Geometry>::Point::DIM).any(|d| separated_on_axis(a, b, d))
64}
65
66/// Are the two boxes separated along axis `d`? `get_indexed::<I, D>`:
67/// `I = 0` is the min corner, `I = 1` the max corner; one arm per
68/// dimension up to `MAX_DIM`.
69fn separated_on_axis<A, B, T>(a: &A, b: &B, d: usize) -> bool
70where
71    A: BoxTrait,
72    B: BoxTrait,
73    <A as Geometry>::Point: PointTrait<Scalar = T>,
74    <B as Geometry>::Point: PointTrait<Scalar = T>,
75    T: CoordinateScalar,
76{
77    let (a_min, a_max, b_min, b_max) = match d {
78        0 => (
79            a.get_indexed::<0, 0>(),
80            a.get_indexed::<1, 0>(),
81            b.get_indexed::<0, 0>(),
82            b.get_indexed::<1, 0>(),
83        ),
84        1 => (
85            a.get_indexed::<0, 1>(),
86            a.get_indexed::<1, 1>(),
87            b.get_indexed::<0, 1>(),
88            b.get_indexed::<1, 1>(),
89        ),
90        2 => (
91            a.get_indexed::<0, 2>(),
92            a.get_indexed::<1, 2>(),
93            b.get_indexed::<0, 2>(),
94            b.get_indexed::<1, 2>(),
95        ),
96        3 => (
97            a.get_indexed::<0, 3>(),
98            a.get_indexed::<1, 3>(),
99            b.get_indexed::<0, 3>(),
100            b.get_indexed::<1, 3>(),
101        ),
102        _ => panic!("disjoint_box_box: DIM exceeds MAX_DIM (4)"),
103    };
104    a_max < b_min || b_max < a_min
105}
106
107#[cfg(test)]
108mod tests {
109    use super::disjoint;
110    use crate::intersects::intersects;
111    use geometry_cs::Cartesian;
112    use geometry_model::{Linestring, Point2D, linestring};
113
114    type P = Point2D<f64, Cartesian>;
115    type LS = Linestring<P>;
116
117    #[test]
118    fn disjoint_matches_negated_intersects() {
119        let a: LS = linestring![(0.0, 0.0), (2.0, 0.0)];
120        let b: LS = linestring![(10.0, 10.0), (11.0, 11.0)];
121        assert!(disjoint(&a, &b));
122        assert!(!intersects(&a, &b));
123    }
124
125    #[test]
126    fn disjoint_false_when_intersecting() {
127        let a: LS = linestring![(0.0, 0.0), (2.0, 0.0)];
128        let b: LS = linestring![(1.0, -1.0), (1.0, 1.0)];
129        assert!(!disjoint(&a, &b));
130        assert!(intersects(&a, &b));
131    }
132
133    /// Polygon–polygon disjointness: separated squares are disjoint,
134    /// overlapping ones are not.
135    #[test]
136    fn polygon_pair_disjointness() {
137        use geometry_model::{Polygon, polygon};
138        let a: Polygon<P> = polygon![[(0.0, 0.0), (4.0, 0.0), (4.0, 4.0), (0.0, 4.0), (0.0, 0.0)]];
139        let apart: Polygon<P> = polygon![[
140            (10.0, 10.0),
141            (14.0, 10.0),
142            (14.0, 14.0),
143            (10.0, 14.0),
144            (10.0, 10.0)
145        ]];
146        let overlapping: Polygon<P> =
147            polygon![[(2.0, 2.0), (6.0, 2.0), (6.0, 6.0), (2.0, 6.0), (2.0, 2.0)]];
148        assert!(disjoint(&a, &apart));
149        assert!(!disjoint(&a, &overlapping));
150    }
151
152    #[test]
153    fn box_box_fast_path() {
154        use crate::disjoint::disjoint_box_box;
155        use geometry_model::Box;
156
157        let a = Box::from_corners(P::new(0.0, 0.0), P::new(2.0, 2.0));
158        // Separated on x.
159        let right = Box::from_corners(P::new(5.0, 0.0), P::new(6.0, 2.0));
160        assert!(disjoint_box_box(&a, &right));
161        // Separated on y.
162        let above = Box::from_corners(P::new(0.0, 5.0), P::new(2.0, 6.0));
163        assert!(disjoint_box_box(&a, &above));
164        // Overlapping.
165        let over = Box::from_corners(P::new(1.0, 1.0), P::new(3.0, 3.0));
166        assert!(!disjoint_box_box(&a, &over));
167        // Touching edges count as *not* disjoint (closed boxes).
168        let touch = Box::from_corners(P::new(2.0, 0.0), P::new(4.0, 2.0));
169        assert!(!disjoint_box_box(&a, &touch));
170    }
171
172    /// `disjoint_box_box.hpp` loops over every dimension: boxes that
173    /// coincide in `x`/`y` but are separated along `z` are disjoint.
174    #[test]
175    fn box_box_three_d_separated_along_z_is_disjoint() {
176        use crate::disjoint::disjoint_box_box;
177        use geometry_model::{Box, Point3D};
178        type P3 = Point3D<f64, Cartesian>;
179        let a = Box::from_corners(P3::new(0.0, 0.0, 0.0), P3::new(1.0, 1.0, 1.0));
180        let b = Box::from_corners(P3::new(0.0, 0.0, 5.0), P3::new(1.0, 1.0, 6.0));
181        let c = Box::from_corners(P3::new(0.5, 0.5, 0.5), P3::new(2.0, 2.0, 2.0));
182        assert!(disjoint_box_box(&a, &b));
183        assert!(disjoint_box_box(&b, &a));
184        assert!(!disjoint_box_box(&a, &c));
185    }
186
187    /// A 4-D box built corner-wise, since `Point::new` stops at three
188    /// arguments.
189    fn box4(min: [f64; 4], max: [f64; 4]) -> geometry_model::Box<geometry_model::Point<f64, 4>> {
190        use geometry_trait::set_ordinate;
191        let corner = |v: [f64; 4]| {
192            let mut p = geometry_model::Point::<f64, 4>::default();
193            for (d, value) in v.into_iter().enumerate() {
194                set_ordinate(&mut p, d, value);
195            }
196            p
197        };
198        geometry_model::Box::from_corners(corner(min), corner(max))
199    }
200
201    /// The axis loop runs to `Point::DIM`, so the last row of the
202    /// dispatch table is only reached by a box of the largest arity the
203    /// table supports. Two boxes that coincide in x, y and z and are
204    /// separated only in the fourth are the one input that tells a
205    /// present row from a missing one.
206    #[test]
207    fn box_box_four_d_separated_along_the_last_axis_is_disjoint() {
208        use crate::disjoint::disjoint_box_box;
209
210        let a = box4([0.0; 4], [1.0, 1.0, 1.0, 1.0]);
211        let past_w = box4([0.0, 0.0, 0.0, 5.0], [1.0, 1.0, 1.0, 6.0]);
212        let overlapping = box4([0.5; 4], [2.0; 4]);
213
214        assert!(disjoint_box_box(&a, &past_w));
215        assert!(disjoint_box_box(&past_w, &a));
216        assert!(!disjoint_box_box(&a, &overlapping));
217
218        // Touching on the fourth axis is not disjoint, matching x/y.
219        let touching_w = box4([0.0, 0.0, 0.0, 1.0], [1.0, 1.0, 1.0, 2.0]);
220        assert!(!disjoint_box_box(&a, &touching_w));
221    }
222
223    /// Past the last row the axis lookup must fail loudly. A silent
224    /// fall-through would compare the wrong axis and report a
225    /// separation that is not there.
226    #[test]
227    #[should_panic(expected = "disjoint_box_box: DIM exceeds MAX_DIM")]
228    fn separated_on_axis_panics_past_max_dim() {
229        let a = box4([0.0; 4], [1.0; 4]);
230        let b = box4([5.0; 4], [6.0; 4]);
231        let _ = super::separated_on_axis(&a, &b, 4);
232    }
233}
geometry_algorithm/disjoint.rs

geometry_algorithm/
disjoint.rs
