s2json_core/geometry/
bbox.rs

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

s2json_core/geometry/
bbox.rs
