geometry_kernel/
canonicalize.rs

1use std::cmp::Ordering;
2
3use crate::precision::PrecisionModel;
4use crate::predicates::{is_ring_ccw, signed_ring_area};
5use crate::types::{Coord, LinearRing, MultiPolygon, Polygon};
6
7pub fn canonicalize_ring(
8    ring: &LinearRing,
9    desired_ccw: bool,
10    precision: PrecisionModel,
11) -> LinearRing {
12    let mut coords = dedup_open_coords(&ring.coords, precision);
13    if coords.len() < 3 {
14        return LinearRing { coords: Vec::new() };
15    }
16
17    let mut closed = coords.clone();
18    closed.push(coords[0]);
19    let mut normalized = LinearRing::new(closed);
20
21    if signed_ring_area(&normalized).abs() <= precision.epsilon() {
22        return LinearRing { coords: Vec::new() };
23    }
24
25    if is_ring_ccw(&normalized) != desired_ccw {
26        coords.reverse();
27    }
28
29    rotate_to_smallest_coord(&mut coords);
30    coords.push(coords[0]);
31    normalized = LinearRing::new(coords);
32    normalized
33}
34
35pub fn canonicalize_polygon(polygon: &Polygon, precision: PrecisionModel) -> Polygon {
36    let exterior = canonicalize_ring(&polygon.exterior, true, precision);
37    if exterior.coords.is_empty() {
38        return Polygon::empty();
39    }
40
41    let mut holes = polygon
42        .holes
43        .iter()
44        .map(|ring| canonicalize_ring(ring, false, precision))
45        .filter(|ring| !ring.coords.is_empty())
46        .collect::<Vec<_>>();
47
48    holes.sort_by(compare_rings);
49    Polygon::new(exterior, holes)
50}
51
52pub fn canonicalize_multi_polygon(
53    multi_polygon: &MultiPolygon,
54    precision: PrecisionModel,
55) -> MultiPolygon {
56    let mut polygons = multi_polygon
57        .polygons
58        .iter()
59        .map(|polygon| canonicalize_polygon(polygon, precision))
60        .filter(|polygon| !polygon.is_empty())
61        .collect::<Vec<_>>();
62
63    polygons.sort_by(|left, right| {
64        let area_cmp = signed_ring_area(&right.exterior)
65            .abs()
66            .partial_cmp(&signed_ring_area(&left.exterior).abs())
67            .unwrap_or(Ordering::Equal);
68        area_cmp.then_with(|| compare_rings(&left.exterior, &right.exterior))
69    });
70
71    MultiPolygon::new(polygons)
72}
73
74fn dedup_open_coords(coords: &[Coord], precision: PrecisionModel) -> Vec<Coord> {
75    let mut out = Vec::new();
76    for coord in coords {
77        let snapped = precision.snap_coord(*coord);
78        if out
79            .last()
80            .is_none_or(|last| !precision.same_coord(*last, snapped))
81        {
82            out.push(snapped);
83        }
84    }
85
86    while out.len() > 1 && precision.same_coord(out[0], *out.last().expect("checked len")) {
87        out.pop();
88    }
89
90    out
91}
92
93fn rotate_to_smallest_coord(coords: &mut [Coord]) {
94    if coords.is_empty() {
95        return;
96    }
97
98    let min_index = coords
99        .iter()
100        .enumerate()
101        .min_by(|(_, left), (_, right)| compare_coords(left, right))
102        .map(|(index, _)| index)
103        .unwrap_or(0);
104
105    coords.rotate_left(min_index);
106}
107
108fn compare_rings(left: &LinearRing, right: &LinearRing) -> Ordering {
109    left.coords
110        .iter()
111        .zip(right.coords.iter())
112        .map(|(left, right)| compare_coords(left, right))
113        .find(|ordering| *ordering != Ordering::Equal)
114        .unwrap_or_else(|| left.coords.len().cmp(&right.coords.len()))
115}
116
117fn compare_coords(left: &Coord, right: &Coord) -> Ordering {
118    left.x
119        .partial_cmp(&right.x)
120        .unwrap_or(Ordering::Equal)
121        .then_with(|| left.y.partial_cmp(&right.y).unwrap_or(Ordering::Equal))
122}
geometry_kernel/canonicalize.rs

geometry_kernel/
canonicalize.rs
