polyclip/
validate.rs

1//! Validity and canonical-form checks.
2
3use crate::arrangement::{Arrangement, InEdge};
4use crate::geom::{Point, PointF, Polygon};
5use crate::node::node_exact;
6use crate::predicates::{crossing_f64, orient};
7use crate::query::{Location, locate_in_ring, ring_area2};
8use core::fmt;
9
10/// Identifies a ring: `polygon` index in the set (0 for a single polygon) and `ring` index
11/// within the polygon (0 = outer, `1 + i` = hole `i`).
12#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
13pub struct RingId {
14    /// Polygon index.
15    pub polygon: usize,
16    /// Ring index (0 = outer ring).
17    pub ring: usize,
18}
19
20/// Why a polygon (set) is invalid.
21#[derive(Clone, Debug, PartialEq)]
22#[non_exhaustive]
23pub enum ValidityError {
24    /// A coordinate is outside `±MAX_COORD`.
25    CoordinateOutOfRange(Point),
26    /// A ring has fewer than three vertices.
27    TooFewVertices(RingId),
28    /// Two consecutive vertices are equal (a zero-length edge).
29    DuplicateVertex(RingId, Point),
30    /// A ring has zero area.
31    ZeroArea(RingId),
32    /// Two edges cross at a point interior to both.
33    SelfIntersection(PointF),
34    /// A ring touches itself (passes twice through a point).
35    SelfTouch(RingId, Point),
36    /// Two edges overlap along a segment.
37    OverlappingEdges(Point, Point),
38    /// A hole is not inside its outer ring, holes overlap, or polygons overlap. The point is
39    /// an endpoint of an edge bordering the offending region.
40    InvalidNesting(Point),
41    /// The rings touch in a way that splits the polygon's interior into several pieces.
42    DisconnectedInterior(Point),
43    /// Orientation does not match the canonical convention (outer CCW, holes CW).
44    WrongOrientation(RingId),
45    /// Not in canonical form (start vertex, collinear vertex or ordering).
46    NotCanonical(&'static str),
47}
48
49impl fmt::Display for ValidityError {
50    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
51        use ValidityError::*;
52        match self {
53            CoordinateOutOfRange(p) => write!(f, "coordinate out of range at ({}, {})", p.x, p.y),
54            TooFewVertices(r) => {
55                write!(f, "ring {}/{} has fewer than 3 vertices", r.polygon, r.ring)
56            }
57            DuplicateVertex(r, p) => write!(
58                f,
59                "ring {}/{} repeats vertex ({}, {})",
60                r.polygon, r.ring, p.x, p.y
61            ),
62            ZeroArea(r) => write!(f, "ring {}/{} has zero area", r.polygon, r.ring),
63            SelfIntersection(p) => write!(f, "self-intersection at ({}, {})", p.x, p.y),
64            SelfTouch(r, p) => write!(
65                f,
66                "ring {}/{} touches itself at ({}, {})",
67                r.polygon, r.ring, p.x, p.y
68            ),
69            OverlappingEdges(a, b) => write!(
70                f,
71                "overlapping edges along ({}, {})-({}, {})",
72                a.x, a.y, b.x, b.y
73            ),
74            InvalidNesting(p) => write!(f, "invalid nesting near ({}, {})", p.x, p.y),
75            DisconnectedInterior(p) => write!(f, "interior disconnected at ({}, {})", p.x, p.y),
76            WrongOrientation(r) => write!(
77                f,
78                "ring {}/{} has non-canonical orientation",
79                r.polygon, r.ring
80            ),
81            NotCanonical(s) => write!(f, "not canonical: {s}"),
82        }
83    }
84}
85
86impl std::error::Error for ValidityError {}
87
88/// Checks that a polygon is valid: every ring simple with at least three vertices and
89/// non-zero area, holes strictly inside the outer ring and with disjoint interiors, rings
90/// touching only at isolated points without disconnecting the interior. Orientation is not
91/// checked (see [`check_canonical`]).
92pub fn validate(poly: &Polygon) -> Result<(), ValidityError> {
93    validate_set(core::slice::from_ref(poly))
94}
95
96/// Checks a polygon set: every polygon valid (see [`validate`]) and polygon interiors
97/// pairwise disjoint (touching at isolated points is allowed, sharing edges is not).
98pub fn validate_set(polys: &[Polygon]) -> Result<(), ValidityError> {
99    // Per-ring checks, and edges with each ring oriented by its role.
100    let mut edges: Vec<InEdge> = Vec::new();
101    let mut ring_of_edge: Vec<(usize, usize)> = Vec::new();
102    for (pi, poly) in polys.iter().enumerate() {
103        for (ri, ring) in poly.rings().enumerate() {
104            let id = RingId {
105                polygon: pi,
106                ring: ri,
107            };
108            let pts = &ring.0;
109            if let Some(&p) = pts.iter().find(|p| !p.in_range()) {
110                return Err(ValidityError::CoordinateOutOfRange(p));
111            }
112            if pts.len() < 3 {
113                return Err(ValidityError::TooFewVertices(id));
114            }
115            for i in 0..pts.len() {
116                if pts[i] == pts[(i + 1) % pts.len()] {
117                    return Err(ValidityError::DuplicateVertex(id, pts[i]));
118                }
119            }
120            let a = ring_area2(pts);
121            if a == 0 {
122                return Err(ValidityError::ZeroArea(id));
123            }
124            // Orient outer rings CCW and holes CW for the winding check.
125            let flip = (ri == 0) != (a > 0);
126            let n = pts.len();
127            for i in 0..n {
128                let (p, q) = (pts[i], pts[(i + 1) % n]);
129                let (p, q) = if flip { (q, p) } else { (p, q) };
130                edges.push(InEdge {
131                    a: p,
132                    b: q,
133                    tag: ((pi as u64) << 32) | ri as u64,
134                    operand: 0,
135                });
136                ring_of_edge.push((pi, ri));
137            }
138        }
139    }
140    let segs: Vec<(Point, Point)> = edges.iter().map(|e| (e.a, e.b)).collect();
141    let frags = match node_exact(&segs) {
142        Ok(f) => f,
143        Err(c) => {
144            let (a, b) = (segs[c.i as usize], segs[c.j as usize]);
145            let (x, y) = crossing_f64(a.0, a.1, b.0, b.1);
146            return Err(ValidityError::SelfIntersection(PointF::new(x, y)));
147        }
148    };
149    drop(segs);
150    // Overlapping edges.
151    let fr: Vec<(Point, Point)> = frags
152        .iter()
153        .map(|f| if f.a < f.b { (f.a, f.b) } else { (f.b, f.a) })
154        .collect();
155    let fr = crate::par::bucket_sort_by_x(fr, |e| e.0.x, |a, b| a.cmp(b));
156    for w in fr.windows(2) {
157        if w[0] == w[1] {
158            return Err(ValidityError::OverlappingEdges(w[0].0, w[0].1));
159        }
160    }
161    drop(fr);
162    // Self-touch (a ring through a point more than once) and the touch graph.
163    // Rings numbered in (polygon, ring) order, so sorting by number sorts by ring.
164    let mut ring_ids: Vec<(usize, usize)> = ring_of_edge.clone();
165    ring_ids.dedup();
166    let mut gid_of_edge: Vec<u32> = Vec::with_capacity(ring_of_edge.len());
167    let mut g = 0u32;
168    for (k, r) in ring_of_edge.iter().enumerate() {
169        if k > 0 && ring_of_edge[k - 1] != *r {
170            g += 1;
171        }
172        gid_of_edge.push(g);
173    }
174    let mut vr: Vec<(Point, u32)> = Vec::with_capacity(frags.len() * 2);
175    for f in &frags {
176        let r = gid_of_edge[f.src as usize];
177        vr.push((f.a, r));
178        vr.push((f.b, r));
179    }
180    let vr = crate::par::bucket_sort_by_x(vr, |e| e.0.x, |a, b| a.cmp(b));
181    let vr: Vec<(Point, (usize, usize))> = vr
182        .into_iter()
183        .map(|(p, g)| (p, ring_ids[g as usize]))
184        .collect();
185    // Union-find over rings and touch points (per polygon): a cycle means the touching
186    // rings cut the interior into pieces.
187    let mut uf = UnionFind::new(0);
188    let mut ring_node: std::collections::HashMap<(usize, usize), usize> =
189        std::collections::HashMap::new();
190    let mut rings_here: Vec<(usize, usize)> = Vec::new();
191    let mut i = 0;
192    while i < vr.len() {
193        let p = vr[i].0;
194        let mut j = i;
195        rings_here.clear();
196        while j < vr.len() && vr[j].0 == p {
197            let r = vr[j].1;
198            let mut k = j;
199            while k < vr.len() && vr[k].0 == p && vr[k].1 == r {
200                k += 1;
201            }
202            // A simple ring passes through each of its vertices exactly once (two edges).
203            if k - j > 2 {
204                return Err(ValidityError::SelfTouch(
205                    RingId {
206                        polygon: r.0,
207                        ring: r.1,
208                    },
209                    p,
210                ));
211            }
212            rings_here.push(r);
213            j = k;
214        }
215        let mut a = 0;
216        while a < rings_here.len() {
217            let mut b = a;
218            while b < rings_here.len() && rings_here[b].0 == rings_here[a].0 {
219                b += 1;
220            }
221            if b - a >= 2 {
222                let pn = uf.add();
223                for r in &rings_here[a..b] {
224                    let rn = *ring_node.entry(*r).or_insert_with(|| uf.add());
225                    if !uf.union(pn, rn) {
226                        return Err(ValidityError::DisconnectedInterior(p));
227                    }
228                }
229            }
230            a = b;
231        }
232        i = j;
233    }
234    drop(vr);
235    let arr = Arrangement::from_frags(&edges, frags);
236    // Winding numbers must be 0 or 1 everywhere.
237    for (k, e) in arr.edges.iter().enumerate() {
238        let wb = arr.below[k][0];
239        let wa = wb + e.delta[0];
240        if !(0..=1).contains(&wb) || !(0..=1).contains(&wa) {
241            return Err(ValidityError::InvalidNesting(e.lo));
242        }
243    }
244    // Each hole inside its own outer ring.
245    for poly in polys {
246        for h in &poly.holes {
247            if !hole_inside(&poly.outer.0, &h.0) {
248                return Err(ValidityError::InvalidNesting(h.0[0]));
249            }
250        }
251    }
252    Ok(())
253}
254
255/// `true` when the (valid, non-crossing) hole lies inside the outer ring: some hole vertex or
256/// edge midpoint off the outer boundary is strictly inside.
257fn hole_inside(outer: &[Point], hole: &[Point]) -> bool {
258    for &p in hole {
259        match locate_in_ring(outer, p) {
260            Location::Inside => return true,
261            Location::Outside => return false,
262            Location::OnBoundary => {}
263        }
264    }
265    // All vertices on the outer boundary: test edge midpoints in doubled coordinates.
266    let dbl: Vec<Point> = outer.iter().map(|p| Point::new(2 * p.x, 2 * p.y)).collect();
267    let n = hole.len();
268    for i in 0..n {
269        let (a, b) = (hole[i], hole[(i + 1) % n]);
270        let m = Point::new(a.x + b.x, a.y + b.y);
271        match locate_in_ring(&dbl, m) {
272            Location::Inside => return true,
273            Location::Outside => return false,
274            Location::OnBoundary => {}
275        }
276    }
277    false
278}
279
280struct UnionFind {
281    parent: Vec<usize>,
282}
283
284impl UnionFind {
285    fn new(n: usize) -> Self {
286        UnionFind {
287            parent: (0..n).collect(),
288        }
289    }
290    fn add(&mut self) -> usize {
291        self.parent.push(self.parent.len());
292        self.parent.len() - 1
293    }
294    fn find(&mut self, mut x: usize) -> usize {
295        while self.parent[x] != x {
296            self.parent[x] = self.parent[self.parent[x]];
297            x = self.parent[x];
298        }
299        x
300    }
301    /// Returns `false` when already connected.
302    fn union(&mut self, a: usize, b: usize) -> bool {
303        let (ra, rb) = (self.find(a), self.find(b));
304        if ra == rb {
305            return false;
306        }
307        self.parent[ra] = rb;
308        true
309    }
310}
311
312/// Checks that a polygon set is valid **and** in the canonical form produced by this crate:
313/// outer rings counter-clockwise and holes clockwise, every ring starting at its
314/// lexicographically smallest vertex, holes sorted, polygons sorted by outer ring, and (when
315/// `collinear_removed`) no vertex collinear with its neighbours unless it is shared with
316/// another ring.
317pub fn check_canonical(polys: &[Polygon], collinear_removed: bool) -> Result<(), ValidityError> {
318    validate_set(polys)?;
319    let mut shared: Vec<Point> = Vec::new();
320    if collinear_removed {
321        let all: Vec<Point> = polys
322            .iter()
323            .flat_map(|p| p.rings().flat_map(|r| r.0.iter().copied()))
324            .collect();
325        let all = crate::par::bucket_sort_by_x(all, |p| p.x, |a, b| a.cmp(b));
326        for w in all.windows(2) {
327            if w[0] == w[1] && shared.last() != Some(&w[0]) {
328                shared.push(w[0]);
329            }
330        }
331    }
332    for (pi, poly) in polys.iter().enumerate() {
333        for (ri, ring) in poly.rings().enumerate() {
334            let id = RingId {
335                polygon: pi,
336                ring: ri,
337            };
338            if (ring_area2(&ring.0) > 0) != (ri == 0) {
339                return Err(ValidityError::WrongOrientation(id));
340            }
341            let min = ring.0.iter().min().copied();
342            if ring.0.first().copied() != min {
343                return Err(ValidityError::NotCanonical(
344                    "ring does not start at its minimum vertex",
345                ));
346            }
347            if collinear_removed {
348                let n = ring.0.len();
349                for i in 0..n {
350                    let (a, v, b) = (ring.0[(i + n - 1) % n], ring.0[i], ring.0[(i + 1) % n]);
351                    if orient(a, v, b) == 0 && shared.binary_search(&v).is_err() {
352                        return Err(ValidityError::NotCanonical("collinear vertex"));
353                    }
354                }
355            }
356        }
357        if poly.holes.windows(2).any(|w| w[0].0 >= w[1].0) {
358            return Err(ValidityError::NotCanonical("holes not sorted"));
359        }
360    }
361    if polys.windows(2).any(|w| w[0].outer.0 >= w[1].outer.0) {
362        return Err(ValidityError::NotCanonical("polygons not sorted"));
363    }
364    Ok(())
365}
polyclip/validate.rs

polyclip/
validate.rs
