nodedb_types/
bbox.rs

1//! Axis-aligned bounding box for 2D geometries (WGS-84).
2//!
3//! Handles the anti-meridian (±180° date line) correctly: when a geometry
4//! crosses the date line, `min_lng > max_lng`. All intersection and
5//! containment logic accounts for this split case.
6
7use crate::geometry::Geometry;
8use serde::{Deserialize, Serialize};
9use zerompk::{FromMessagePack, ToMessagePack};
10
11/// An axis-aligned bounding box in WGS-84 coordinates.
12///
13/// **Anti-meridian convention:** When `min_lng > max_lng`, the bbox wraps
14/// across the ±180° date line. For example, a geometry spanning 170°E to
15/// 170°W has `min_lng = 170.0, max_lng = -170.0`.
16#[derive(
17    Debug,
18    Clone,
19    Copy,
20    PartialEq,
21    Serialize,
22    Deserialize,
23    ToMessagePack,
24    FromMessagePack,
25    rkyv::Archive,
26    rkyv::Serialize,
27    rkyv::Deserialize,
28)]
29pub struct BoundingBox {
30    pub min_lng: f64,
31    pub min_lat: f64,
32    pub max_lng: f64,
33    pub max_lat: f64,
34}
35
36impl BoundingBox {
37    pub fn new(min_lng: f64, min_lat: f64, max_lng: f64, max_lat: f64) -> Self {
38        Self {
39            min_lng,
40            min_lat,
41            max_lng,
42            max_lat,
43        }
44    }
45
46    pub fn from_point(lng: f64, lat: f64) -> Self {
47        Self {
48            min_lng: lng,
49            min_lat: lat,
50            max_lng: lng,
51            max_lat: lat,
52        }
53    }
54
55    pub fn crosses_antimeridian(&self) -> bool {
56        self.min_lng > self.max_lng
57    }
58
59    /// Area in approximate square degrees (for R-tree heuristics).
60    pub fn area(&self) -> f64 {
61        let lat_span = self.max_lat - self.min_lat;
62        let lng_span = if self.crosses_antimeridian() {
63            (180.0 - self.min_lng) + (self.max_lng + 180.0)
64        } else {
65            self.max_lng - self.min_lng
66        };
67        lat_span * lng_span
68    }
69
70    /// Half-perimeter (R*-tree margin heuristic).
71    pub fn margin(&self) -> f64 {
72        let lat_span = self.max_lat - self.min_lat;
73        let lng_span = if self.crosses_antimeridian() {
74            (180.0 - self.min_lng) + (self.max_lng + 180.0)
75        } else {
76            self.max_lng - self.min_lng
77        };
78        lat_span + lng_span
79    }
80
81    pub fn contains_point(&self, lng: f64, lat: f64) -> bool {
82        if lat < self.min_lat || lat > self.max_lat {
83            return false;
84        }
85        if self.crosses_antimeridian() {
86            lng >= self.min_lng || lng <= self.max_lng
87        } else {
88            lng >= self.min_lng && lng <= self.max_lng
89        }
90    }
91
92    pub fn contains_bbox(&self, other: &BoundingBox) -> bool {
93        if other.min_lat < self.min_lat || other.max_lat > self.max_lat {
94            return false;
95        }
96        match (self.crosses_antimeridian(), other.crosses_antimeridian()) {
97            (false, false) => other.min_lng >= self.min_lng && other.max_lng <= self.max_lng,
98            (true, false) => other.min_lng >= self.min_lng || other.max_lng <= self.max_lng,
99            (false, true) => false,
100            (true, true) => other.min_lng >= self.min_lng && other.max_lng <= self.max_lng,
101        }
102    }
103
104    pub fn intersects(&self, other: &BoundingBox) -> bool {
105        if self.max_lat < other.min_lat || self.min_lat > other.max_lat {
106            return false;
107        }
108        match (self.crosses_antimeridian(), other.crosses_antimeridian()) {
109            (false, false) => self.min_lng <= other.max_lng && self.max_lng >= other.min_lng,
110            (true, false) => other.max_lng >= self.min_lng || other.min_lng <= self.max_lng,
111            (false, true) => self.max_lng >= other.min_lng || self.min_lng <= other.max_lng,
112            (true, true) => true,
113        }
114    }
115
116    pub fn union(&self, other: &BoundingBox) -> BoundingBox {
117        let min_lat = self.min_lat.min(other.min_lat);
118        let max_lat = self.max_lat.max(other.max_lat);
119        let (min_lng, max_lng) =
120            union_longitude(self.min_lng, self.max_lng, other.min_lng, other.max_lng);
121        BoundingBox {
122            min_lng,
123            min_lat,
124            max_lng,
125            max_lat,
126        }
127    }
128
129    pub fn extend_point(&mut self, lng: f64, lat: f64) {
130        self.min_lat = self.min_lat.min(lat);
131        self.max_lat = self.max_lat.max(lat);
132        if self.crosses_antimeridian() {
133            let in_east = lng >= self.min_lng;
134            let in_west = lng <= self.max_lng;
135            if !in_east && !in_west {
136                if self.min_lng - lng < lng - self.max_lng {
137                    self.min_lng = lng;
138                } else {
139                    self.max_lng = lng;
140                }
141            }
142        } else {
143            self.min_lng = self.min_lng.min(lng);
144            self.max_lng = self.max_lng.max(lng);
145        }
146    }
147
148    /// Expand by meters (equirectangular approximation, <0.5% error ±70°).
149    pub fn expand_meters(&self, meters: f64) -> BoundingBox {
150        let dlat = meters / 110_540.0;
151        let center_lat = (self.min_lat + self.max_lat) / 2.0;
152        let dlng = meters / (111_320.0 * center_lat.to_radians().cos());
153        BoundingBox {
154            min_lng: self.min_lng - dlng,
155            min_lat: self.min_lat - dlat,
156            max_lng: self.max_lng + dlng,
157            max_lat: self.max_lat + dlat,
158        }
159    }
160
161    pub fn overlap_area(&self, other: &BoundingBox) -> f64 {
162        if !self.intersects(other) {
163            return 0.0;
164        }
165        let lat_overlap = self.max_lat.min(other.max_lat) - self.min_lat.max(other.min_lat);
166        if lat_overlap <= 0.0 {
167            return 0.0;
168        }
169        let lng_overlap =
170            lng_overlap_span(self.min_lng, self.max_lng, other.min_lng, other.max_lng);
171        lat_overlap * lng_overlap
172    }
173
174    pub fn enlargement(&self, other: &BoundingBox) -> f64 {
175        self.union(other).area() - self.area()
176    }
177}
178
179fn lng_overlap_span(a_min: f64, a_max: f64, b_min: f64, b_max: f64) -> f64 {
180    let a_wraps = a_min > a_max;
181    let b_wraps = b_min > b_max;
182    match (a_wraps, b_wraps) {
183        (false, false) => (a_max.min(b_max) - a_min.max(b_min)).max(0.0),
184        (true, false) => {
185            let east = (180.0_f64.min(b_max) - a_min.max(b_min)).max(0.0);
186            let west = (a_max.min(b_max) - (-180.0_f64).max(b_min)).max(0.0);
187            east + west
188        }
189        (false, true) => lng_overlap_span(b_min, b_max, a_min, a_max),
190        (true, true) => {
191            let east = (180.0 - a_min.max(b_min)).max(0.0);
192            let west = (a_max.min(b_max) + 180.0).max(0.0);
193            east + west
194        }
195    }
196}
197
198fn union_longitude(a_min: f64, a_max: f64, b_min: f64, b_max: f64) -> (f64, f64) {
199    let a_wraps = a_min > a_max;
200    let b_wraps = b_min > b_max;
201    match (a_wraps, b_wraps) {
202        (false, false) => {
203            let simple_min = a_min.min(b_min);
204            let simple_max = a_max.max(b_max);
205            let simple_span = simple_max - simple_min;
206            let gap = (b_min - a_max).max(0.0).min((a_min - b_max).max(0.0));
207            if gap <= 0.0 {
208                return (simple_min, simple_max);
209            }
210            let wrap_min = a_min.max(b_min);
211            let wrap_max = a_max.min(b_max);
212            let wrap_span = (180.0 - wrap_min) + (wrap_max + 180.0);
213            if wrap_span < simple_span {
214                (wrap_min, wrap_max)
215            } else {
216                (simple_min, simple_max)
217            }
218        }
219        (true, false) => {
220            if b_min >= a_min || b_max <= a_max {
221                (a_min, a_max)
222            } else {
223                let extend_east = a_min - b_min;
224                let extend_west = b_max - a_max;
225                if extend_east <= extend_west {
226                    (b_min, a_max)
227                } else {
228                    (a_min, b_max)
229                }
230            }
231        }
232        (false, true) => union_longitude(b_min, b_max, a_min, a_max),
233        (true, true) => (a_min.min(b_min), a_max.max(b_max)),
234    }
235}
236
237/// Compute bounding box for any Geometry.
238pub fn geometry_bbox(geom: &Geometry) -> BoundingBox {
239    match geom {
240        Geometry::Point { coordinates } => BoundingBox::from_point(coordinates[0], coordinates[1]),
241        Geometry::LineString { coordinates } => bbox_from_coords(coordinates),
242        Geometry::Polygon { coordinates } => {
243            let all: Vec<[f64; 2]> = coordinates.iter().flat_map(|r| r.iter().copied()).collect();
244            bbox_from_coords(&all)
245        }
246        Geometry::MultiPoint { coordinates } => bbox_from_coords(coordinates),
247        Geometry::MultiLineString { coordinates } => {
248            let all: Vec<[f64; 2]> = coordinates
249                .iter()
250                .flat_map(|ls| ls.iter().copied())
251                .collect();
252            bbox_from_coords(&all)
253        }
254        Geometry::MultiPolygon { coordinates } => {
255            let all: Vec<[f64; 2]> = coordinates
256                .iter()
257                .flat_map(|poly| poly.iter().flat_map(|ring| ring.iter().copied()))
258                .collect();
259            bbox_from_coords(&all)
260        }
261        Geometry::GeometryCollection { geometries } => {
262            if geometries.is_empty() {
263                return BoundingBox::new(0.0, 0.0, 0.0, 0.0);
264            }
265            let mut result = geometry_bbox(&geometries[0]);
266            for geom in &geometries[1..] {
267                result = result.union(&geometry_bbox(geom));
268            }
269            result
270        }
271    }
272}
273
274fn bbox_from_coords(coords: &[[f64; 2]]) -> BoundingBox {
275    if coords.is_empty() {
276        return BoundingBox::new(0.0, 0.0, 0.0, 0.0);
277    }
278    let mut min_lng = coords[0][0];
279    let mut min_lat = coords[0][1];
280    let mut max_lng = coords[0][0];
281    let mut max_lat = coords[0][1];
282    for c in &coords[1..] {
283        min_lng = min_lng.min(c[0]);
284        min_lat = min_lat.min(c[1]);
285        max_lng = max_lng.max(c[0]);
286        max_lat = max_lat.max(c[1]);
287    }
288    BoundingBox {
289        min_lng,
290        min_lat,
291        max_lng,
292        max_lat,
293    }
294}
295
296#[cfg(test)]
297mod tests {
298    use super::*;
299
300    #[test]
301    fn point_bbox() {
302        let bb = geometry_bbox(&Geometry::point(10.0, 20.0));
303        assert_eq!(bb.min_lng, 10.0);
304        assert_eq!(bb.max_lng, 10.0);
305        assert_eq!(bb.area(), 0.0);
306    }
307
308    #[test]
309    fn polygon_bbox() {
310        let poly = Geometry::polygon(vec![vec![
311            [-10.0, -5.0],
312            [10.0, -5.0],
313            [10.0, 5.0],
314            [-10.0, 5.0],
315            [-10.0, -5.0],
316        ]]);
317        let bb = geometry_bbox(&poly);
318        assert_eq!(bb.min_lng, -10.0);
319        assert_eq!(bb.max_lng, 10.0);
320    }
321
322    #[test]
323    fn contains_point_normal() {
324        let bb = BoundingBox::new(0.0, 0.0, 10.0, 10.0);
325        assert!(bb.contains_point(5.0, 5.0));
326        assert!(!bb.contains_point(11.0, 5.0));
327    }
328
329    #[test]
330    fn contains_point_antimeridian() {
331        let bb = BoundingBox::new(170.0, -10.0, -170.0, 10.0);
332        assert!(bb.crosses_antimeridian());
333        assert!(bb.contains_point(175.0, 0.0));
334        assert!(bb.contains_point(-175.0, 0.0));
335        assert!(!bb.contains_point(0.0, 0.0));
336    }
337
338    #[test]
339    fn intersects_normal() {
340        let a = BoundingBox::new(0.0, 0.0, 10.0, 10.0);
341        let b = BoundingBox::new(5.0, 5.0, 15.0, 15.0);
342        assert!(a.intersects(&b));
343        let c = BoundingBox::new(20.0, 20.0, 30.0, 30.0);
344        assert!(!a.intersects(&c));
345    }
346
347    #[test]
348    fn intersects_antimeridian() {
349        let a = BoundingBox::new(170.0, -5.0, -170.0, 5.0);
350        let b = BoundingBox::new(175.0, 0.0, -175.0, 3.0);
351        assert!(a.intersects(&b));
352        let c = BoundingBox::new(0.0, 0.0, 10.0, 10.0);
353        assert!(!a.intersects(&c));
354    }
355
356    #[test]
357    fn union_normal() {
358        let a = BoundingBox::new(0.0, 0.0, 5.0, 5.0);
359        let b = BoundingBox::new(3.0, 3.0, 10.0, 10.0);
360        let u = a.union(&b);
361        assert_eq!(u.min_lng, 0.0);
362        assert_eq!(u.max_lng, 10.0);
363    }
364
365    #[test]
366    fn overlap_area_partial() {
367        let a = BoundingBox::new(0.0, 0.0, 10.0, 10.0);
368        let b = BoundingBox::new(5.0, 5.0, 15.0, 15.0);
369        assert!((a.overlap_area(&b) - 25.0).abs() < 1e-10);
370    }
371
372    #[test]
373    fn expand_meters_basic() {
374        let bb = BoundingBox::from_point(0.0, 0.0);
375        let expanded = bb.expand_meters(1000.0);
376        assert!((expanded.min_lat - (-0.00905)).abs() < 0.001);
377    }
378
379    #[test]
380    fn geometry_collection_bbox() {
381        let gc = Geometry::GeometryCollection {
382            geometries: vec![Geometry::point(0.0, 0.0), Geometry::point(10.0, 10.0)],
383        };
384        let bb = geometry_bbox(&gc);
385        assert_eq!(bb.min_lng, 0.0);
386        assert_eq!(bb.max_lng, 10.0);
387    }
388}
nodedb_types/bbox.rs

nodedb_types/
bbox.rs
