1use 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#[derive(Debug)]
26pub struct GeometryBounder {
27 x_left: Interval,
29 x_mid: Interval,
31 x_right: Interval,
33 y: Interval,
35 z: Interval,
37 m: Interval,
39 geometry_types: HashSet<i32>,
45 wraparound_hint: Interval,
46}
47
48impl GeometryBounder {
49 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 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 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 if !self.x_mid.is_empty() || !self.wraparound_hint.contains_interval(&out_all) {
99 return out_all.into();
100 }
101
102 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 WraparoundInterval::new(self.x_right.lo(), self.x_left.hi())
112 }
113
114 pub fn y(&self) -> Interval {
116 self.y
117 }
118
119 pub fn z(&self) -> Interval {
121 self.z
122 }
123
124 pub fn m(&self) -> Interval {
126 self.m
127 }
128
129 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 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 self.x_left.update_interval(x);
168 } else if x.lo() > self.wraparound_hint.mid() {
169 self.x_right.update_interval(x);
172 } else {
173 self.x_mid.update_interval(x);
175 }
176 }
177}
178
179fn 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
234fn 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
243fn 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
260fn 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
273fn 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 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 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 let bounds = wkt_bounds_with_wraparound(geoms, Interval::empty()).unwrap();
552 assert_eq!(bounds.x(), (-170, 170).into());
553
554 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 let bounds = wkt_bounds_with_wraparound(geoms, (-1000, 1000)).unwrap();
563 assert_eq!(bounds.x(), (-170, 170).into());
564
565 let bounds = wkt_bounds_with_wraparound(geoms, (-10, 10)).unwrap();
568 assert_eq!(bounds.x(), (-170, 170).into());
569
570 let bounds = wkt_bounds_with_wraparound(geoms, (-180, 180)).unwrap();
572 assert_eq!(bounds.x(), (170, -170).into());
573
574 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}