Skip to main content

parquet_geospatial/
bounding.rs

1// SPDX-License-Identifier: Apache-2.0
2// SPDX-FileCopyrightText: See the NOTICE file distributed with this work for additional information regarding copyright ownership
3// SPDX-FileContributor: Licensed to the Apache Software Foundation (ASF) under one or more contributor license agreements
4
5use std::collections::HashSet;
6
7use arrow_schema::ArrowError;
8use geo_traits::{
9    CoordTrait, Dimensions, GeometryCollectionTrait, GeometryTrait, GeometryType, LineStringTrait,
10    MultiLineStringTrait, MultiPointTrait, MultiPolygonTrait, PointTrait, PolygonTrait,
11};
12use wkb::reader::Wkb;
13
14use crate::interval::{Interval, IntervalTrait, WraparoundInterval};
15
16/// Geometry bounder
17///
18/// Utility to accumulate statistics for geometries as they are written.
19/// This bounder is designed to output statistics accumulated according
20/// to the Parquet specification such that the output can be written to
21/// Parquet statistics with minimal modification.
22///
23/// See the [IntervalTrait] for an in-depth discussion of wraparound bounding
24/// (which adds some complexity to this implementation).
25#[derive(Debug)]
26pub struct GeometryBounder {
27    /// Union of all contiguous x intervals to the left of the wraparound midpoint
28    x_left: Interval,
29    /// Union of all contiguous x intervals that intersect the wraparound midpoint
30    x_mid: Interval,
31    /// Union of all contiguous x intervals to the right of the wraparound midpoint
32    x_right: Interval,
33    /// Union of all y intervals
34    y: Interval,
35    /// Union of all z intervals
36    z: Interval,
37    /// Union of all m intervals
38    m: Interval,
39    /// Unique geometry type codes encountered by the bounder
40    ///
41    /// The integer codes are identical to the ISO WKB geometry type codes and
42    /// are documented as part of the Parquet specification:
43    /// <https://github.com/apache/parquet-format/blob/master/Geospatial.md#geospatial-types>
44    geometry_types: HashSet<i32>,
45    wraparound_hint: Interval,
46}
47
48impl GeometryBounder {
49    /// Create a new, empty bounder that represents empty input
50    pub fn empty() -> Self {
51        Self {
52            x_left: Interval::empty(),
53            x_mid: Interval::empty(),
54            x_right: Interval::empty(),
55            y: Interval::empty(),
56            z: Interval::empty(),
57            m: Interval::empty(),
58            geometry_types: HashSet::<i32>::default(),
59            wraparound_hint: Interval::empty(),
60        }
61    }
62
63    /// Set the hint to use for generation of potential wraparound xmin/xmax output
64    ///
65    /// Usually this value should be set to (-180, 180), as wraparound is primarily
66    /// targeted at lon/lat coordinate systems where collections of features with
67    /// components at the very far left and very far right of the coordinate system
68    /// are actually very close to each other.
69    ///
70    /// It is safe to set this value even when the actual coordinate system of the
71    /// input is unknown: if the input has coordinate values that are outside the
72    /// range of the wraparound hint, wraparound xmin/xmax values will not be
73    /// generated. If the input has coordinate values that are well inside of the
74    /// range of the wraparound hint, the wraparound xmin/xmax value will be
75    /// substantially wider than the non-wraparound version and will not be returned.
76    pub fn with_wraparound_hint(self, wraparound_hint: impl Into<Interval>) -> Self {
77        Self {
78            wraparound_hint: wraparound_hint.into(),
79            ..self
80        }
81    }
82
83    /// Calculate the final xmin and xmax for geometries encountered by this bounder
84    ///
85    /// The interval returned may wraparound if a hint was set and the input
86    /// encountered by this bounder were exclusively at the far left and far right
87    /// of the input range. See [IntervalTrait] for an in-depth description of
88    /// wraparound intervals.
89    pub fn x(&self) -> WraparoundInterval {
90        let out_all = Interval::empty()
91            .merge_interval(&self.x_left)
92            .merge_interval(&self.x_mid)
93            .merge_interval(&self.x_right);
94
95        // Check if this even makes sense: if anything is covering the midpoint
96        // of the wraparound hint or the bounds don't make sense for the provided
97        // wraparound hint, just return the Cartesian bounds.
98        if !self.x_mid.is_empty() || !self.wraparound_hint.contains_interval(&out_all) {
99            return out_all.into();
100        }
101
102        // Check if our wraparound bounds are any better than our Cartesian bounds
103        // If the Cartesian bounds are tighter, return them.
104        let out_width = (self.x_left.hi() - self.wraparound_hint.lo())
105            + (self.wraparound_hint.hi() - self.x_right.lo());
106        if out_all.width() < out_width {
107            return out_all.into();
108        }
109
110        // Wraparound!
111        WraparoundInterval::new(self.x_right.lo(), self.x_left.hi())
112    }
113
114    /// Calculate the final ymin and ymax for geometries encountered by this bounder
115    pub fn y(&self) -> Interval {
116        self.y
117    }
118
119    /// Calculate the final zmin and zmax for geometries encountered by this bounder
120    pub fn z(&self) -> Interval {
121        self.z
122    }
123
124    /// Calculate the final mmin and mmax values for geometries encountered by this bounder
125    pub fn m(&self) -> Interval {
126        self.m
127    }
128
129    /// Calculate the final geometry type set
130    ///
131    /// Returns a copy of the unique geometry type/dimension combinations encountered
132    /// by this bounder. These identifiers are ISO WKB identifiers (e.g., 1001
133    /// for PointZ). The output is always returned sorted.
134    pub fn geometry_types(&self) -> Vec<i32> {
135        let mut out = self.geometry_types.iter().copied().collect::<Vec<_>>();
136        out.sort_unstable();
137        out
138    }
139
140    /// Update this bounder with one WKB-encoded geometry
141    ///
142    /// Parses and accumulates the bounds of one WKB-encoded geometry. This function
143    /// will error for invalid WKB input; however, clients may wish to ignore such
144    /// an error for the purposes of writing statistics.
145    pub fn update_wkb(&mut self, wkb: &[u8]) -> Result<(), ArrowError> {
146        let wkb = Wkb::try_new(wkb).map_err(|e| ArrowError::ExternalError(Box::new(e)))?;
147        self.update_geometry(&wkb)?;
148        Ok(())
149    }
150
151    fn update_geometry(&mut self, geom: &impl GeometryTrait<T = f64>) -> Result<(), ArrowError> {
152        let geometry_type = geometry_type(geom)?;
153        self.geometry_types.insert(geometry_type);
154
155        visit_intervals(geom, 'x', &mut |x| self.update_x(&x))?;
156        visit_intervals(geom, 'y', &mut |y| self.y.update_interval(&y))?;
157        visit_intervals(geom, 'z', &mut |z| self.z.update_interval(&z))?;
158        visit_intervals(geom, 'm', &mut |m| self.m.update_interval(&m))?;
159
160        Ok(())
161    }
162
163    fn update_x(&mut self, x: &Interval) {
164        if x.hi() < self.wraparound_hint.mid() {
165            // If the x interval is completely to the left of the midpoint, merge it
166            // with x_left
167            self.x_left.update_interval(x);
168        } else if x.lo() > self.wraparound_hint.mid() {
169            // If the x interval is completely to the right of the midpoint, merge it
170            // with x_right
171            self.x_right.update_interval(x);
172        } else {
173            // Otherwise, merge it with x_mid
174            self.x_mid.update_interval(x);
175        }
176    }
177}
178
179/// Visit contiguous intervals for a given dimension within a [GeometryTrait]
180///
181/// Here, contiguous intervals refers to intervals that must not be separated
182/// by wraparound bounding. Point components of a geometry are visited as
183/// degenerate intervals of a single value; linestring or polygon ring components
184/// are visited as single intervals.
185fn visit_intervals(
186    geom: &impl GeometryTrait<T = f64>,
187    dimension: char,
188    func: &mut impl FnMut(Interval),
189) -> Result<(), ArrowError> {
190    let Some(n) = dimension_index(geom.dim(), dimension) else {
191        return Ok(());
192    };
193
194    match geom.as_type() {
195        GeometryType::Point(pt) => {
196            if let Some(coord) = PointTrait::coord(pt) {
197                visit_point(coord, n, func);
198            }
199        }
200        GeometryType::LineString(ls) => {
201            visit_sequence(ls.coords(), n, func);
202        }
203        GeometryType::Polygon(pl) => {
204            if let Some(exterior) = pl.exterior() {
205                visit_sequence(exterior.coords(), n, func);
206            }
207
208            for interior in pl.interiors() {
209                visit_sequence(interior.coords(), n, func);
210            }
211        }
212        GeometryType::MultiPoint(multi_pt) => {
213            visit_collection(multi_pt.points(), dimension, func)?;
214        }
215        GeometryType::MultiLineString(multi_ls) => {
216            visit_collection(multi_ls.line_strings(), dimension, func)?;
217        }
218        GeometryType::MultiPolygon(multi_pl) => {
219            visit_collection(multi_pl.polygons(), dimension, func)?;
220        }
221        GeometryType::GeometryCollection(collection) => {
222            visit_collection(collection.geometries(), dimension, func)?;
223        }
224        _ => {
225            return Err(ArrowError::InvalidArgumentError(
226                "GeometryType not supported for dimension bounds".to_string(),
227            ));
228        }
229    }
230
231    Ok(())
232}
233
234/// Visit a point
235///
236/// Points can be separated by wraparound bounding even if they occur within
237/// the same feature, so we visit them as individual degenerate intervals.
238fn visit_point(coord: impl CoordTrait<T = f64>, n: usize, func: &mut impl FnMut(Interval)) {
239    let val = unsafe { coord.nth_unchecked(n) };
240    func((val, val).into());
241}
242
243/// Visit contiguous sequences
244///
245/// Sequences (e.g., linestrings or polygon rings) must always be considered
246/// together (i.e., are never separated by wraparound bounding).
247fn visit_sequence(
248    coords: impl IntoIterator<Item = impl CoordTrait<T = f64>>,
249    n: usize,
250    func: &mut impl FnMut(Interval),
251) {
252    let mut interval = Interval::empty();
253    for coord in coords {
254        interval.update_value(unsafe { coord.nth_unchecked(n) });
255    }
256
257    func(interval);
258}
259
260/// Visit intervals in a collection of geometries
261fn visit_collection(
262    collection: impl IntoIterator<Item = impl GeometryTrait<T = f64>>,
263    target: char,
264    func: &mut impl FnMut(Interval),
265) -> Result<(), ArrowError> {
266    for geom in collection {
267        visit_intervals(&geom, target, func)?;
268    }
269
270    Ok(())
271}
272
273/// Extract the geometry type code encountered by the bounder
274///
275/// The integer code is a ISO WKB geometry type codes is documented as part
276/// of the Parquet specification:
277/// <https://github.com/apache/parquet-format/blob/master/Geospatial.md#geospatial-types>
278///
279/// This can also be derived from bytes 2-5 (possibly endian-swapped according to byte 1)
280/// of the input WKB buffer but is slightly clearer recomputed.
281fn geometry_type(geom: &impl GeometryTrait<T = f64>) -> Result<i32, ArrowError> {
282    let dimension_type = match geom.dim() {
283        Dimensions::Xy => 0,
284        Dimensions::Xyz => 1000,
285        Dimensions::Xym => 2000,
286        Dimensions::Xyzm => 3000,
287        Dimensions::Unknown(_) => {
288            return Err(ArrowError::InvalidArgumentError(
289                "Unsupported dimensions".to_string(),
290            ));
291        }
292    };
293
294    let geometry_type = match geom.as_type() {
295        GeometryType::Point(_) => 1,
296        GeometryType::LineString(_) => 2,
297        GeometryType::Polygon(_) => 3,
298        GeometryType::MultiPoint(_) => 4,
299        GeometryType::MultiLineString(_) => 5,
300        GeometryType::MultiPolygon(_) => 6,
301        GeometryType::GeometryCollection(_) => 7,
302        _ => {
303            return Err(ArrowError::InvalidArgumentError(
304                "GeometryType not supported for dimension bounds".to_string(),
305            ));
306        }
307    };
308
309    Ok(dimension_type + geometry_type)
310}
311
312fn dimension_index(dim: Dimensions, target: char) -> Option<usize> {
313    match target {
314        'x' => return Some(0),
315        'y' => return Some(1),
316        _ => {}
317    }
318
319    match (dim, target) {
320        (Dimensions::Xyz, 'z') => Some(2),
321        (Dimensions::Xym, 'm') => Some(2),
322        (Dimensions::Xyzm, 'z') => Some(2),
323        (Dimensions::Xyzm, 'm') => Some(3),
324        (_, _) => None,
325    }
326}
327
328#[cfg(test)]
329mod test {
330
331    use std::str::FromStr;
332
333    use wkt::Wkt;
334
335    use super::*;
336
337    fn wkt_bounds(
338        wkt_values: impl IntoIterator<Item = impl AsRef<str>>,
339    ) -> Result<GeometryBounder, ArrowError> {
340        wkt_bounds_with_wraparound(wkt_values, Interval::empty())
341    }
342
343    fn wkt_bounds_with_wraparound(
344        wkt_values: impl IntoIterator<Item = impl AsRef<str>>,
345        wraparound: impl Into<Interval>,
346    ) -> Result<GeometryBounder, ArrowError> {
347        let mut bounder = GeometryBounder::empty().with_wraparound_hint(wraparound);
348        for wkt_value in wkt_values {
349            let wkt: Wkt = Wkt::from_str(wkt_value.as_ref())
350                .map_err(|e| ArrowError::InvalidArgumentError(e.to_string()))?;
351            bounder.update_geometry(&wkt)?;
352        }
353        Ok(bounder)
354    }
355
356    #[test]
357    fn test_wkb() {
358        let wkt: Wkt = Wkt::from_str("LINESTRING (0 1, 2 3)").unwrap();
359        let mut wkb = Vec::new();
360        wkb::writer::write_geometry(&mut wkb, &wkt, &Default::default()).unwrap();
361
362        let mut bounds = GeometryBounder::empty();
363        bounds.update_wkb(&wkb).unwrap();
364
365        assert_eq!(bounds.x(), (0, 2).into());
366        assert_eq!(bounds.y(), (1, 3).into());
367    }
368
369    #[test]
370    fn test_geometry_types() {
371        let empties = [
372            "POINT EMPTY",
373            "LINESTRING EMPTY",
374            "POLYGON EMPTY",
375            "MULTIPOINT EMPTY",
376            "MULTILINESTRING EMPTY",
377            "MULTIPOLYGON EMPTY",
378            "GEOMETRYCOLLECTION EMPTY",
379        ];
380
381        assert_eq!(
382            wkt_bounds(empties).unwrap().geometry_types(),
383            vec![1, 2, 3, 4, 5, 6, 7]
384        );
385
386        let empties_z = [
387            "POINT Z EMPTY",
388            "LINESTRING Z EMPTY",
389            "POLYGON Z EMPTY",
390            "MULTIPOINT Z EMPTY",
391            "MULTILINESTRING Z EMPTY",
392            "MULTIPOLYGON Z EMPTY",
393            "GEOMETRYCOLLECTION Z EMPTY",
394        ];
395
396        assert_eq!(
397            wkt_bounds(empties_z).unwrap().geometry_types(),
398            vec![1001, 1002, 1003, 1004, 1005, 1006, 1007]
399        );
400
401        let empties_m = [
402            "POINT M EMPTY",
403            "LINESTRING M EMPTY",
404            "POLYGON M EMPTY",
405            "MULTIPOINT M EMPTY",
406            "MULTILINESTRING M EMPTY",
407            "MULTIPOLYGON M EMPTY",
408            "GEOMETRYCOLLECTION M EMPTY",
409        ];
410
411        assert_eq!(
412            wkt_bounds(empties_m).unwrap().geometry_types(),
413            vec![2001, 2002, 2003, 2004, 2005, 2006, 2007]
414        );
415
416        let empties_zm = [
417            "POINT ZM EMPTY",
418            "LINESTRING ZM EMPTY",
419            "POLYGON ZM EMPTY",
420            "MULTIPOINT ZM EMPTY",
421            "MULTILINESTRING ZM EMPTY",
422            "MULTIPOLYGON ZM EMPTY",
423            "GEOMETRYCOLLECTION ZM EMPTY",
424        ];
425
426        assert_eq!(
427            wkt_bounds(empties_zm).unwrap().geometry_types(),
428            vec![3001, 3002, 3003, 3004, 3005, 3006, 3007]
429        );
430    }
431
432    #[test]
433    fn test_bounds_empty() {
434        let empties = [
435            "POINT EMPTY",
436            "LINESTRING EMPTY",
437            "POLYGON EMPTY",
438            "MULTIPOINT EMPTY",
439            "MULTILINESTRING EMPTY",
440            "MULTIPOLYGON EMPTY",
441            "GEOMETRYCOLLECTION EMPTY",
442        ];
443
444        let bounds = wkt_bounds(empties).unwrap();
445        assert!(bounds.x().is_empty());
446        assert!(bounds.y().is_empty());
447        assert!(bounds.z().is_empty());
448        assert!(bounds.m().is_empty());
449
450        // With wraparound, still empty
451        let bounds = wkt_bounds_with_wraparound(empties, (-180, 180)).unwrap();
452        assert!(bounds.x().is_empty());
453        assert!(bounds.y().is_empty());
454        assert!(bounds.z().is_empty());
455        assert!(bounds.m().is_empty());
456    }
457
458    #[test]
459    fn test_bounds_coord() {
460        let bounds = wkt_bounds(["POINT (0 1)", "POINT (2 3)"]).unwrap();
461        assert_eq!(bounds.x(), (0, 2).into());
462        assert_eq!(bounds.y(), (1, 3).into());
463        assert!(bounds.z().is_empty());
464        assert!(bounds.m().is_empty());
465
466        let bounds = wkt_bounds(["POINT Z (0 1 2)", "POINT Z (3 4 5)"]).unwrap();
467        assert_eq!(bounds.x(), (0, 3).into());
468        assert_eq!(bounds.y(), (1, 4).into());
469        assert_eq!(bounds.z(), (2, 5).into());
470        assert!(bounds.m().is_empty());
471
472        let bounds = wkt_bounds(["POINT M (0 1 2)", "POINT M (3 4 5)"]).unwrap();
473        assert_eq!(bounds.x(), (0, 3).into());
474        assert_eq!(bounds.y(), (1, 4).into());
475        assert!(bounds.z().is_empty());
476        assert_eq!(bounds.m(), (2, 5).into());
477
478        let bounds = wkt_bounds(["POINT ZM (0 1 2 3)", "POINT ZM (4 5 6 7)"]).unwrap();
479        assert_eq!(bounds.x(), (0, 4).into());
480        assert_eq!(bounds.y(), (1, 5).into());
481        assert_eq!(bounds.z(), (2, 6).into());
482        assert_eq!(bounds.m(), (3, 7).into());
483    }
484
485    #[test]
486    fn test_bounds_sequence() {
487        let bounds = wkt_bounds(["LINESTRING (0 1, 2 3)"]).unwrap();
488        assert_eq!(bounds.x(), (0, 2).into());
489        assert_eq!(bounds.y(), (1, 3).into());
490        assert!(bounds.z().is_empty());
491        assert!(bounds.m().is_empty());
492
493        let bounds = wkt_bounds(["LINESTRING Z (0 1 2, 3 4 5)"]).unwrap();
494        assert_eq!(bounds.x(), (0, 3).into());
495        assert_eq!(bounds.y(), (1, 4).into());
496        assert_eq!(bounds.z(), (2, 5).into());
497        assert!(bounds.m().is_empty());
498
499        let bounds = wkt_bounds(["LINESTRING M (0 1 2, 3 4 5)"]).unwrap();
500        assert_eq!(bounds.x(), (0, 3).into());
501        assert_eq!(bounds.y(), (1, 4).into());
502        assert!(bounds.z().is_empty());
503        assert_eq!(bounds.m(), (2, 5).into());
504
505        let bounds = wkt_bounds(["LINESTRING ZM (0 1 2 3, 4 5 6 7)"]).unwrap();
506        assert_eq!(bounds.x(), (0, 4).into());
507        assert_eq!(bounds.y(), (1, 5).into());
508        assert_eq!(bounds.z(), (2, 6).into());
509        assert_eq!(bounds.m(), (3, 7).into());
510    }
511
512    #[test]
513    fn test_bounds_geometry_type() {
514        let bounds = wkt_bounds(["POINT (0 1)", "POINT (2 3)"]).unwrap();
515        assert_eq!(bounds.x(), (0, 2).into());
516        assert_eq!(bounds.y(), (1, 3).into());
517
518        let bounds = wkt_bounds(["LINESTRING (0 1, 2 3)"]).unwrap();
519        assert_eq!(bounds.x(), (0, 2).into());
520        assert_eq!(bounds.y(), (1, 3).into());
521
522        // Normally interiors are supposed to be inside the exterior; however, we
523        // include a poorly formed polygon just to make sure they are considered
524        let bounds =
525            wkt_bounds(["POLYGON ((0 0, 0 1, 1 0, 0 0), (10 10, 10 11, 11 10, 10 10))"]).unwrap();
526        assert_eq!(bounds.x(), (0, 11).into());
527        assert_eq!(bounds.y(), (0, 11).into());
528
529        let bounds = wkt_bounds(["MULTIPOINT ((0 1), (2 3))"]).unwrap();
530        assert_eq!(bounds.x(), (0, 2).into());
531        assert_eq!(bounds.y(), (1, 3).into());
532
533        let bounds = wkt_bounds(["MULTILINESTRING ((0 1, 2 3))"]).unwrap();
534        assert_eq!(bounds.x(), (0, 2).into());
535        assert_eq!(bounds.y(), (1, 3).into());
536
537        let bounds = wkt_bounds(["MULTIPOLYGON (((0 0, 0 1, 1 0, 0 0)))"]).unwrap();
538        assert_eq!(bounds.x(), (0, 1).into());
539        assert_eq!(bounds.y(), (0, 1).into());
540
541        let bounds = wkt_bounds(["GEOMETRYCOLLECTION (POINT (0 1), POINT (2 3))"]).unwrap();
542        assert_eq!(bounds.x(), (0, 2).into());
543        assert_eq!(bounds.y(), (1, 3).into());
544    }
545
546    #[test]
547    fn test_bounds_wrap_basic() {
548        let geoms = ["POINT (-170 0)", "POINT (170 0)"];
549
550        // No wraparound because it was disabled
551        let bounds = wkt_bounds_with_wraparound(geoms, Interval::empty()).unwrap();
552        assert_eq!(bounds.x(), (-170, 170).into());
553
554        // Wraparound that can't happen because something is covering
555        // the midpoint.
556        let mut geoms_with_mid = geoms.to_vec();
557        geoms_with_mid.push("LINESTRING (-10 0, 10 0)");
558        let bounds = wkt_bounds_with_wraparound(geoms_with_mid, (-180, 180)).unwrap();
559        assert_eq!(bounds.x(), (-170, 170).into());
560
561        // Wraparound where the wrapped box is *not* better
562        let bounds = wkt_bounds_with_wraparound(geoms, (-1000, 1000)).unwrap();
563        assert_eq!(bounds.x(), (-170, 170).into());
564
565        // Wraparound where the wrapped box is inappropriate because it is
566        // outside the wrap hint
567        let bounds = wkt_bounds_with_wraparound(geoms, (-10, 10)).unwrap();
568        assert_eq!(bounds.x(), (-170, 170).into());
569
570        // Wraparound where the wrapped box *is* better
571        let bounds = wkt_bounds_with_wraparound(geoms, (-180, 180)).unwrap();
572        assert_eq!(bounds.x(), (170, -170).into());
573
574        // The Cartesian bounds are tighter than the wraparound bounds.
575        let geoms = [
576            "POINT (-10 0)",
577            "POINT (-2 0)",
578            "POINT (170 0)",
579            "POINT (175 0)",
580        ];
581        let bounds = wkt_bounds_with_wraparound(geoms, (-180, 180)).unwrap();
582        assert_eq!(bounds.x(), (-10, 175).into());
583    }
584
585    #[test]
586    fn test_bounds_wrap_multipart() {
587        let fiji = "MULTIPOLYGON (
588        ((-180 -15.51, -180 -19.78, -178.61 -21.14, -178.02 -18.22, -178.57 -16.04, -180 -15.51)),
589        ((180 -15.51, 177.98 -16.25, 176.67 -17.14, 177.83 -19.31, 180 -19.78, 180 -15.51))
590        )";
591
592        let bounds = wkt_bounds_with_wraparound([fiji], (-180, 180)).unwrap();
593        assert!(bounds.x().is_wraparound());
594        assert_eq!(bounds.x(), (176.67, -178.02).into());
595        assert_eq!(bounds.y(), (-21.14, -15.51).into());
596    }
597}