s2json_core/geometry/
bbox.rs

1use crate::*;
2use alloc::fmt;
3use core::cmp::Ordering;
4use serde::{
5    Deserialize, Deserializer, Serialize, Serializer,
6    de::{self, SeqAccess, Visitor},
7    ser::SerializeTuple,
8};
9
10trait Bounded {
11    fn min_value() -> Self;
12    fn max_value() -> Self;
13}
14macro_rules! impl_bounded {
15    ($($t:ty),*) => {
16        $(
17            impl Bounded for $t {
18                fn min_value() -> Self {
19                    <$t>::MIN
20                }
21                fn max_value() -> Self {
22                    <$t>::MAX
23                }
24            }
25        )*
26    };
27}
28
29// Implement for common numeric types
30impl_bounded!(i8, i16, i32, i64, i128, u8, u16, u32, u64, u128, isize, usize, f32, f64);
31
32/// A BBOX is defined in lon-lat space and helps with zooming motion to
33/// see the entire line or polygon
34/// The order is (left, bottom, right, top)
35/// If WM, then the projection is lon-lat
36/// If S2, then the projection is s-t
37#[derive(Copy, Clone, Debug, PartialEq, PartialOrd)]
38pub struct BBox<T = f64> {
39    /// left most longitude (WM) or S (S2)
40    pub left: T,
41    /// bottom most latitude (WM) or T (S2)
42    pub bottom: T,
43    /// right most longitude (WM) or T (S2)
44    pub right: T,
45    /// top most latitude (WM) or S (S2)
46    pub top: T,
47}
48impl<T> From<BBox<T>> for MValue
49where
50    T: Into<ValueType>,
51{
52    fn from(bbox: BBox<T>) -> MValue {
53        MValue::from([
54            ("left".into(), bbox.left.into()),
55            ("bottom".into(), bbox.bottom.into()),
56            ("right".into(), bbox.right.into()),
57            ("top".into(), bbox.top.into()),
58        ])
59    }
60}
61impl<T> From<&BBox<T>> for MValue
62where
63    T: Copy + Into<ValueType>,
64{
65    fn from(bbox: &BBox<T>) -> MValue {
66        MValue::from([
67            ("left".into(), bbox.left.into()),
68            ("bottom".into(), bbox.bottom.into()),
69            ("right".into(), bbox.right.into()),
70            ("top".into(), bbox.top.into()),
71        ])
72    }
73}
74impl<T> From<MValue> for BBox<T>
75where
76    T: From<ValueType>,
77{
78    fn from(mvalue: MValue) -> Self {
79        BBox {
80            left: mvalue.get("left").unwrap().clone().into(),
81            bottom: mvalue.get("bottom").unwrap().clone().into(),
82            right: mvalue.get("right").unwrap().clone().into(),
83            top: mvalue.get("top").unwrap().clone().into(),
84        }
85    }
86}
87impl<T> From<&MValue> for BBox<T>
88where
89    T: From<ValueType>,
90{
91    fn from(mvalue: &MValue) -> Self {
92        BBox {
93            left: mvalue.get("left").unwrap().clone().into(),
94            bottom: mvalue.get("bottom").unwrap().clone().into(),
95            right: mvalue.get("right").unwrap().clone().into(),
96            top: mvalue.get("top").unwrap().clone().into(),
97        }
98    }
99}
100impl<T> MValueCompatible for BBox<T>
101where
102    ValueType: From<T>,
103    T: From<ValueType> + Default + Bounded + Copy,
104{
105}
106impl<T> Default for BBox<T>
107where
108    T: Default + Bounded + Copy,
109{
110    fn default() -> Self {
111        BBox::new(T::max_value(), T::max_value(), T::min_value(), T::min_value())
112    }
113}
114impl<T> BBox<T> {
115    /// Creates a new BBox
116    pub fn new(left: T, bottom: T, right: T, top: T) -> Self
117    where
118        T: Copy,
119    {
120        BBox { left, bottom, right, top }
121    }
122
123    /// Checks if a point is within the BBox
124    pub fn point_overlap<P: GetXY>(&self, point: &P) -> bool
125    where
126        T: Into<f64> + Copy, // Ensures that comparison operators work for type T
127    {
128        point.x() >= self.left.into()
129            && point.x() <= self.right.into()
130            && point.y() >= self.bottom.into()
131            && point.y() <= self.top.into()
132    }
133
134    /// Merges another bounding box with this one
135    pub fn merge(&self, other: &Self) -> Self
136    where
137        T: PartialOrd + Copy,
138    {
139        let mut new_bbox = *self;
140        new_bbox.left = if new_bbox.left < other.left { new_bbox.left } else { other.left };
141        new_bbox.bottom =
142            if new_bbox.bottom < other.bottom { new_bbox.bottom } else { other.bottom };
143        new_bbox.right = if new_bbox.right > other.right { new_bbox.right } else { other.right };
144        new_bbox.top = if new_bbox.top > other.top { new_bbox.top } else { other.top };
145
146        new_bbox
147    }
148
149    /// Merges in place another bounding box with this one
150    pub fn merge_in_place(&mut self, other: &Self)
151    where
152        T: PartialOrd + Copy,
153    {
154        self.left = if self.left < other.left { self.left } else { other.left };
155        self.bottom = if self.bottom < other.bottom { self.bottom } else { other.bottom };
156        self.right = if self.right > other.right { self.right } else { other.right };
157        self.top = if self.top > other.top { self.top } else { other.top };
158    }
159
160    /// Checks if another bounding box overlaps with this one and returns the overlap
161    pub fn overlap(&self, other: &BBox<T>) -> Option<BBox<T>>
162    where
163        T: PartialOrd + Copy,
164    {
165        if self.left > other.right
166            || self.right < other.left
167            || self.bottom > other.top
168            || self.top < other.bottom
169        {
170            None
171        } else {
172            let left = if self.left > other.left { self.left } else { other.left };
173            let bottom = if self.bottom > other.bottom { self.bottom } else { other.bottom };
174            let right = if self.right < other.right { self.right } else { other.right };
175            let top = if self.top < other.top { self.top } else { other.top };
176
177            Some(BBox { left, bottom, right, top })
178        }
179    }
180
181    /// Clips the bounding box along an axis
182    pub fn clip(&self, axis: Axis, k1: T, k2: T) -> BBox<T>
183    where
184        T: PartialOrd + Copy,
185    {
186        let mut new_bbox = *self;
187        if axis == Axis::X {
188            new_bbox.left = if new_bbox.left > k1 { new_bbox.left } else { k1 };
189            new_bbox.right = if new_bbox.right < k2 { new_bbox.right } else { k2 };
190        } else {
191            new_bbox.bottom = if new_bbox.bottom > k1 { new_bbox.bottom } else { k1 };
192            new_bbox.top = if new_bbox.top < k2 { new_bbox.top } else { k2 };
193        }
194
195        new_bbox
196    }
197
198    /// Checks if this bounding box is inside another
199    pub fn inside(&self, other: &BBox<T>) -> bool
200    where
201        T: PartialOrd + Copy,
202    {
203        self.left >= other.left
204            && self.right <= other.right
205            && self.bottom >= other.bottom
206            && self.top <= other.top
207    }
208}
209impl BBox<f64> {
210    /// Creates a new BBox from a point
211    pub fn from_point<P: GetXY>(point: &P) -> Self {
212        BBox::new(point.x(), point.y(), point.x(), point.y())
213    }
214
215    /// Creates a new BBox from a linestring
216    pub fn from_linestring<P: GetXY>(line: &[P]) -> Self {
217        let mut bbox = BBox::from_point(&line[0]);
218        for point in line {
219            bbox.extend_from_point(point);
220        }
221        bbox
222    }
223
224    /// Creates a new BBox from a multi-linestring
225    pub fn from_multi_linestring<P: GetXY>(lines: &[Vec<P>]) -> Self {
226        let mut bbox = BBox::from_point(&lines[0][0]);
227        for line in lines {
228            for point in line {
229                bbox.extend_from_point(point);
230            }
231        }
232        bbox
233    }
234
235    /// Creates a new BBox from a polygon
236    pub fn from_polygon<P: GetXY>(polygon: &[Vec<P>]) -> Self {
237        BBox::<f64>::from_multi_linestring(polygon)
238    }
239
240    /// Creates a new BBox from a multi-polygon
241    pub fn from_multi_polygon<P: GetXY>(polygons: &[Vec<Vec<P>>]) -> Self {
242        let mut bbox = BBox::from_point(&polygons[0][0][0]);
243        for polygon in polygons {
244            for line in polygon {
245                for point in line {
246                    bbox.extend_from_point(point);
247                }
248            }
249        }
250        bbox
251    }
252
253    /// Extends the bounding box with a point
254    pub fn extend_from_point<P: GetXY>(&mut self, point: &P) {
255        self.merge_in_place(&BBox::from_point(point));
256    }
257
258    /// Creates a new BBox from zoom-uv coordinates
259    pub fn from_uv_zoom(u: f64, v: f64, zoom: u8) -> Self {
260        let division_factor = 2. / (1 << zoom) as f64;
261
262        BBox {
263            left: division_factor * u - 1.0,
264            bottom: division_factor * v - 1.0,
265            right: division_factor * (u + 1.0) - 1.0,
266            top: division_factor * (v + 1.0) - 1.0,
267        }
268    }
269
270    /// Creates a new BBox from zoom-st coordinates
271    pub fn from_st_zoom(s: f64, t: f64, zoom: u8) -> Self {
272        let division_factor = (2. / (1 << zoom) as f64) * 0.5;
273
274        BBox {
275            left: division_factor * s,
276            bottom: division_factor * t,
277            right: division_factor * (s + 1.),
278            top: division_factor * (t + 1.),
279        }
280    }
281}
282impl<T> Serialize for BBox<T>
283where
284    T: Serialize + Copy,
285{
286    fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
287    where
288        S: Serializer,
289    {
290        let mut seq = serializer.serialize_tuple(4)?;
291        seq.serialize_element(&self.left)?;
292        seq.serialize_element(&self.bottom)?;
293        seq.serialize_element(&self.right)?;
294        seq.serialize_element(&self.top)?;
295        seq.end()
296    }
297}
298impl<T: Copy> From<BBox3D<T>> for BBox<T> {
299    fn from(bbox: BBox3D<T>) -> Self {
300        BBox::new(bbox.left, bbox.bottom, bbox.right, bbox.top)
301    }
302}
303impl<'de, T> Deserialize<'de> for BBox<T>
304where
305    T: Deserialize<'de> + Copy,
306{
307    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
308    where
309        D: Deserializer<'de>,
310    {
311        struct BBoxVisitor<T> {
312            marker: core::marker::PhantomData<T>,
313        }
314
315        impl<'de, T> Visitor<'de> for BBoxVisitor<T>
316        where
317            T: Deserialize<'de> + Copy,
318        {
319            type Value = BBox<T>;
320
321            fn expecting(&self, formatter: &mut fmt::Formatter) -> fmt::Result {
322                formatter.write_str("a sequence of four numbers")
323            }
324
325            fn visit_seq<V>(self, mut seq: V) -> Result<BBox<T>, V::Error>
326            where
327                V: SeqAccess<'de>,
328            {
329                let left =
330                    seq.next_element()?.ok_or_else(|| de::Error::invalid_length(0, &self))?;
331                let bottom =
332                    seq.next_element()?.ok_or_else(|| de::Error::invalid_length(1, &self))?;
333                let right =
334                    seq.next_element()?.ok_or_else(|| de::Error::invalid_length(2, &self))?;
335                let top = seq.next_element()?.ok_or_else(|| de::Error::invalid_length(3, &self))?;
336                Ok(BBox { left, bottom, right, top })
337            }
338        }
339
340        deserializer.deserialize_tuple(4, BBoxVisitor { marker: core::marker::PhantomData })
341    }
342}
343
344/// A BBOX is defined in lon-lat space and helps with zooming motion to
345/// see the entire 3D line or polygon
346#[derive(Copy, Clone, Debug, PartialEq, PartialOrd)]
347pub struct BBox3D<T = f64> {
348    /// left most longitude (WM) or S (S2)
349    pub left: T,
350    /// bottom most latitude (WM) or T (S2)
351    pub bottom: T,
352    /// right most longitude (WM) or T (S2)
353    pub right: T,
354    /// top most latitude (WM) or S (S2)
355    pub top: T,
356    /// near most height (WM) or T (S2)
357    /// generic height is relative to the surface of the earth in meters
358    pub near: T,
359    /// far most height (WM) or T (S2)
360    /// generic height is relative to the surface of the earth in meters
361    pub far: T,
362}
363impl<T> BBox3D<T> {
364    /// Creates a new BBox3D
365    pub fn new(left: T, bottom: T, right: T, top: T, near: T, far: T) -> Self
366    where
367        T: Copy,
368    {
369        BBox3D { left, bottom, right, top, near, far }
370    }
371
372    /// Checks if a point is within the BBox
373    pub fn point_overlap<P: GetXY + GetZ>(&self, point: &P) -> bool
374    where
375        T: Into<f64> + Copy, // Ensures that comparison operators work for type T
376    {
377        let z = point.z().unwrap_or_default();
378        point.x() >= self.left.into()
379            && point.x() <= self.right.into()
380            && point.y() >= self.bottom.into()
381            && point.y() <= self.top.into()
382            && z >= self.near.into()
383            && z <= self.far.into()
384    }
385
386    /// Merges another bounding box with this one
387    pub fn merge(&self, other: &BBox3D<T>) -> BBox3D<T>
388    where
389        T: PartialOrd + Copy,
390    {
391        let mut new_bbox = *self;
392        new_bbox.left = if new_bbox.left < other.left { new_bbox.left } else { other.left };
393        new_bbox.bottom =
394            if new_bbox.bottom < other.bottom { new_bbox.bottom } else { other.bottom };
395        new_bbox.right = if new_bbox.right > other.right { new_bbox.right } else { other.right };
396        new_bbox.top = if new_bbox.top > other.top { new_bbox.top } else { other.top };
397        new_bbox.near = if new_bbox.near < other.near { new_bbox.near } else { other.near };
398        new_bbox.far = if new_bbox.far > other.far { new_bbox.far } else { other.far };
399
400        new_bbox
401    }
402
403    /// Merges in place another bounding box with this one
404    pub fn merge_in_place(&mut self, other: &Self)
405    where
406        T: PartialOrd + Copy,
407    {
408        self.left = if self.left < other.left { self.left } else { other.left };
409        self.bottom = if self.bottom < other.bottom { self.bottom } else { other.bottom };
410        self.right = if self.right > other.right { self.right } else { other.right };
411        self.top = if self.top > other.top { self.top } else { other.top };
412        self.near = if self.near < other.near { self.near } else { other.near };
413        self.far = if self.far > other.far { self.far } else { other.far };
414    }
415
416    /// Checks if another bounding box overlaps with this one and returns the overlap
417    pub fn overlap(&self, other: &BBox3D<T>) -> Option<BBox3D<T>>
418    where
419        T: PartialOrd + Copy,
420    {
421        if self.left > other.right
422            || self.right < other.left
423            || self.bottom > other.top
424            || self.top < other.bottom
425            || self.near > other.far
426            || self.far < other.near
427        {
428            None
429        } else {
430            let left = if self.left > other.left { self.left } else { other.left };
431            let bottom = if self.bottom > other.bottom { self.bottom } else { other.bottom };
432            let right = if self.right < other.right { self.right } else { other.right };
433            let top = if self.top < other.top { self.top } else { other.top };
434
435            let near = if self.near > other.near { self.near } else { other.near };
436            let far = if self.far < other.far { self.far } else { other.far };
437
438            Some(BBox3D { left, bottom, right, top, near, far })
439        }
440    }
441
442    /// Clips the bounding box along an axis
443    pub fn clip(&self, axis: Axis, k1: T, k2: T) -> BBox3D<T>
444    where
445        T: PartialOrd + Copy,
446    {
447        let mut new_bbox = *self;
448        if axis == Axis::X {
449            new_bbox.left = if new_bbox.left > k1 { new_bbox.left } else { k1 };
450            new_bbox.right = if new_bbox.right < k2 { new_bbox.right } else { k2 };
451        } else {
452            new_bbox.bottom = if new_bbox.bottom > k1 { new_bbox.bottom } else { k1 };
453            new_bbox.top = if new_bbox.top < k2 { new_bbox.top } else { k2 };
454        }
455
456        new_bbox
457    }
458
459    /// Creates a new BBox3D from a BBox
460    pub fn from_bbox(bbox: &BBox<T>) -> Self
461    where
462        T: Copy + Default,
463    {
464        BBox3D::new(bbox.left, bbox.bottom, bbox.right, bbox.top, T::default(), T::default())
465    }
466
467    /// Checks if this bounding box is inside another
468    pub fn inside(&self, other: &BBox3D<T>) -> bool
469    where
470        T: PartialOrd + Copy,
471    {
472        self.left >= other.left
473            && self.right <= other.right
474            && self.bottom >= other.bottom
475            && self.top <= other.top
476            && self.near >= other.near
477            && self.far <= other.far
478    }
479}
480impl<T> Serialize for BBox3D<T>
481where
482    T: Serialize + Copy,
483{
484    fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
485    where
486        S: Serializer,
487    {
488        let mut seq = serializer.serialize_tuple(6)?;
489        seq.serialize_element(&self.left)?;
490        seq.serialize_element(&self.bottom)?;
491        seq.serialize_element(&self.right)?;
492        seq.serialize_element(&self.top)?;
493        seq.serialize_element(&self.near)?;
494        seq.serialize_element(&self.far)?;
495        seq.end()
496    }
497}
498impl<T> Default for BBox3D<T>
499where
500    T: Default + Bounded + Copy,
501{
502    fn default() -> Self {
503        BBox3D::new(
504            T::max_value(),
505            T::max_value(),
506            T::min_value(),
507            T::min_value(),
508            T::max_value(),
509            T::min_value(),
510        )
511    }
512}
513impl BBox3D<f64> {
514    /// Creates a new BBox3D from a point
515    pub fn from_point<P: GetXY + GetZ>(point: &P) -> Self {
516        BBox3D::new(
517            point.x(),
518            point.y(),
519            point.x(),
520            point.y(),
521            point.z().unwrap_or(f64::MAX),
522            point.z().unwrap_or(f64::MIN),
523        )
524    }
525
526    /// Creates a new BBox from a linestring
527    pub fn from_linestring<P: GetXY + GetZ>(line: &[P]) -> Self {
528        let mut bbox = BBox3D::from_point(&line[0]);
529        for point in line {
530            bbox.extend_from_point(point);
531        }
532        bbox
533    }
534
535    /// Creates a new BBox from a multi-linestring
536    pub fn from_multi_linestring<P: GetXY + GetZ>(lines: &[Vec<P>]) -> Self {
537        let mut bbox = BBox3D::from_point(&lines[0][0]);
538        for line in lines {
539            for point in line {
540                bbox.extend_from_point(point);
541            }
542        }
543        bbox
544    }
545
546    /// Creates a new BBox from a polygon
547    pub fn from_polygon<P: GetXY + GetZ>(polygon: &[Vec<P>]) -> Self {
548        BBox3D::<f64>::from_multi_linestring(polygon)
549    }
550
551    /// Creates a new BBox from a multi-polygon
552    pub fn from_multi_polygon<P: GetXY + GetZ>(polygons: &[Vec<Vec<P>>]) -> Self {
553        let mut bbox = BBox3D::from_point(&polygons[0][0][0]);
554        for polygon in polygons {
555            for line in polygon {
556                for point in line {
557                    bbox.extend_from_point(point);
558                }
559            }
560        }
561        bbox
562    }
563
564    /// Extends the bounding box with a point
565    pub fn extend_from_point<P: GetXY + GetZ>(&mut self, point: &P) {
566        self.merge_in_place(&BBox3D::from_point(point));
567    }
568
569    /// Creates a new BBox3D from zoom-uv coordinates
570    pub fn from_uv_zoom(u: f64, v: f64, zoom: u8) -> Self {
571        let division_factor = 2. / (1 << zoom) as f64;
572
573        BBox3D {
574            left: division_factor * u - 1.0,
575            bottom: division_factor * v - 1.0,
576            right: division_factor * (u + 1.0) - 1.0,
577            top: division_factor * (v + 1.0) - 1.0,
578            near: f64::MAX,
579            far: f64::MIN,
580        }
581    }
582
583    /// Creates a new BBox from zoom-st coordinates
584    pub fn from_st_zoom(s: f64, t: f64, zoom: u8) -> Self {
585        let division_factor = (2. / (1 << zoom) as f64) * 0.5;
586
587        BBox3D {
588            left: division_factor * s,
589            bottom: division_factor * t,
590            right: division_factor * (s + 1.),
591            top: division_factor * (t + 1.),
592            near: f64::MAX,
593            far: f64::MIN,
594        }
595    }
596}
597impl<T: Default + Copy> From<BBox<T>> for BBox3D<T> {
598    fn from(bbox: BBox<T>) -> Self {
599        BBox3D::from_bbox(&bbox)
600    }
601}
602impl<'de, T> Deserialize<'de> for BBox3D<T>
603where
604    T: Deserialize<'de> + Copy,
605{
606    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
607    where
608        D: Deserializer<'de>,
609    {
610        struct BBox3DVisitor<T> {
611            marker: core::marker::PhantomData<T>,
612        }
613
614        impl<'de, T> Visitor<'de> for BBox3DVisitor<T>
615        where
616            T: Deserialize<'de> + Copy,
617        {
618            type Value = BBox3D<T>;
619
620            fn expecting(&self, formatter: &mut fmt::Formatter) -> fmt::Result {
621                formatter.write_str("a sequence of six numbers")
622            }
623
624            fn visit_seq<V>(self, mut seq: V) -> Result<BBox3D<T>, V::Error>
625            where
626                V: SeqAccess<'de>,
627            {
628                let left =
629                    seq.next_element()?.ok_or_else(|| de::Error::invalid_length(0, &self))?;
630                let bottom =
631                    seq.next_element()?.ok_or_else(|| de::Error::invalid_length(1, &self))?;
632                let right =
633                    seq.next_element()?.ok_or_else(|| de::Error::invalid_length(2, &self))?;
634                let top = seq.next_element()?.ok_or_else(|| de::Error::invalid_length(3, &self))?;
635                let near =
636                    seq.next_element()?.ok_or_else(|| de::Error::invalid_length(4, &self))?;
637                let far = seq.next_element()?.ok_or_else(|| de::Error::invalid_length(5, &self))?;
638                Ok(BBox3D { left, bottom, right, top, near, far })
639            }
640        }
641
642        deserializer.deserialize_tuple(6, BBox3DVisitor { marker: core::marker::PhantomData })
643    }
644}
645
646/// BBox or BBox3D
647#[derive(Serialize, Deserialize, Copy, Clone, Debug, PartialEq)]
648pub enum BBOX {
649    /// 2D bounding box
650    BBox(BBox),
651    /// 3D bounding box
652    BBox3D(BBox3D),
653}
654impl Default for BBOX {
655    fn default() -> Self {
656        BBOX::BBox(BBox::default())
657    }
658}
659impl Eq for BBOX {}
660impl PartialOrd for BBOX {
661    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
662        Some(self.cmp(other))
663    }
664}
665impl Ord for BBOX {
666    fn cmp(&self, other: &Self) -> Ordering {
667        match (self, other) {
668            (BBOX::BBox(a), BBOX::BBox(b)) => a.partial_cmp(b).unwrap_or(Ordering::Equal),
669            (BBOX::BBox3D(a), BBOX::BBox3D(b)) => a.partial_cmp(b).unwrap_or(Ordering::Equal),
670            // Ensure that BBox and BBox3D are ordered correctly
671            (BBOX::BBox(_), BBOX::BBox3D(_)) => Ordering::Less,
672            (BBOX::BBox3D(_), BBOX::BBox(_)) => Ordering::Greater,
673        }
674    }
675}
s2json_core/geometry/bbox.rs

s2json_core/geometry/
bbox.rs
