axiolid_reference/
polygon.rs

1//! Simple-polygon triangulation by ear clipping, with hole support.
2//!
3//! Orientation is decided by the certified `orient2d` predicate rather than a
4//! raw sign test, so a near-degenerate vertex cannot silently flip a triangle.
5
6use axiolid_contracts::{GeomError, GeomResult, Sign};
7use axiolid_core::{Point2, Scalar};
8
9use crate::orient2d;
10
11/// Twice the signed area of a closed ring. Positive means counter-clockwise.
12pub fn signed_area2(ring: &[Point2]) -> Scalar {
13    let mut acc = 0.0;
14    for i in 0..ring.len() {
15        let a = ring[i];
16        let b = ring[(i + 1) % ring.len()];
17        acc += a.x * b.y - b.x * a.y;
18    }
19    acc
20}
21
22/// Orientation of a ring, or `None` when it encloses no certifiable area.
23pub fn ring_orientation(ring: &[Point2]) -> Option<Sign> {
24    if ring.len() < 3 {
25        return None;
26    }
27    match signed_area2(ring) {
28        a if a > 0.0 => Some(Sign::Positive),
29        a if a < 0.0 => Some(Sign::Negative),
30        _ => None,
31    }
32}
33
34/// Certified orientation sign of a finite triple.
35///
36/// `orient2d` is exact for every finite input and only a non-finite
37/// coordinate leaves it uncertain, so [`triangulate_simple`] refuses such a
38/// ring before any triple reaches this helper.
39fn sign_of(a: Point2, b: Point2, c: Point2) -> Sign {
40    orient2d(a, b, c)
41        .sign()
42        .expect("orient2d is certain for finite coordinates, which the caller checked")
43}
44
45/// Whether `p` lies in or on the boundary of counter-clockwise triangle
46/// `a,b,c`, using certified signs.
47///
48/// A non-corner vertex on an ear boundary blocks that ear. Otherwise the clip
49/// can leave a negatively wound remainder whose signed area merely cancels the
50/// outside area it emitted.
51fn blocks_ear(a: Point2, b: Point2, c: Point2, p: Point2) -> bool {
52    let s1 = sign_of(a, b, p);
53    let s2 = sign_of(b, c, p);
54    let s3 = sign_of(c, a, p);
55    s1 != Sign::Negative && s2 != Sign::Negative && s3 != Sign::Negative
56}
57
58/// Whether vertex `i` of `ring` is a clippable ear of a CCW polygon.
59fn is_ear(ring: &[Point2], indices: &[usize], at: usize) -> bool {
60    let n = indices.len();
61    let (ia, ib, ic) = (
62        indices[(at + n - 1) % n],
63        indices[at],
64        indices[(at + 1) % n],
65    );
66    let (a, b, c) = (ring[ia], ring[ib], ring[ic]);
67
68    // Reflex or collinear vertices are never ears. Collinear is excluded
69    // because a zero-area ear adds a degenerate triangle to the output.
70    if sign_of(a, b, c) != Sign::Positive {
71        return false;
72    }
73
74    // No other vertex may fall inside the candidate ear.
75    //
76    // Bridged rings contain DUPLICATE vertices by construction: a bridge visits
77    // the same two points twice. Comparing by index alone would treat a
78    // duplicate of an ear corner as an intruder and reject every ear, so
79    // coincident positions are skipped as well.
80    !indices
81        .iter()
82        .filter(|&&idx| idx != ia && idx != ib && idx != ic)
83        .map(|&idx| ring[idx])
84        .filter(|q| *q != a && *q != b && *q != c)
85        .any(|q| blocks_ear(a, b, c, q))
86}
87
88/// Triangulate a simple CCW polygon by ear clipping.
89///
90/// Returns index triples into `ring`. Fails rather than emitting a partial fan:
91/// a caller that receives triangles must be able to trust they cover the input.
92///
93/// # Errors
94///
95/// [`GeomError::InvalidInput`] for a NaN or infinite coordinate, which no
96/// orientation predicate can decide; [`GeomError::Degenerate`] for a ring that
97/// is too short, self-intersecting or without area.
98pub fn triangulate_simple(ring: &[Point2]) -> GeomResult<Vec<[u32; 3]>> {
99    if ring.iter().any(|p| !(p.x.is_finite() && p.y.is_finite())) {
100        return Err(GeomError::InvalidInput(
101            "ring has a non-finite coordinate".to_owned(),
102        ));
103    }
104    if ring.len() < 3 {
105        return Err(GeomError::Degenerate(format!(
106            "ring has {} vertices, need at least 3",
107            ring.len()
108        )));
109    }
110    let mut indices: Vec<usize> = (0..ring.len()).collect();
111    let mut out = Vec::with_capacity(ring.len().saturating_sub(2));
112
113    // Each successful clip removes one vertex, so the loop is bounded. The
114    // `guard` counts consecutive failures: a full pass with no ear found means
115    // the polygon is not simple, which is a data fault, not a retry case.
116    let mut at = 0usize;
117    let mut guard = 0usize;
118    while indices.len() > 3 {
119        if guard > indices.len() {
120            return Err(GeomError::Degenerate(
121                "no ear found; polygon is self-intersecting or degenerate".to_owned(),
122            ));
123        }
124        if is_ear(ring, &indices, at % indices.len()) {
125            let n = indices.len();
126            let cur = at % n;
127            out.push([
128                indices[(cur + n - 1) % n] as u32,
129                indices[cur] as u32,
130                indices[(cur + 1) % n] as u32,
131            ]);
132            indices.remove(cur);
133            at = cur;
134            guard = 0;
135        } else {
136            at += 1;
137            guard += 1;
138        }
139    }
140    // The final triangle must still enclose area; a collinear remainder means
141    // the whole ring was degenerate and no valid fan exists.
142    let (a, b, c) = (ring[indices[0]], ring[indices[1]], ring[indices[2]]);
143    if sign_of(a, b, c) != Sign::Positive {
144        return Err(GeomError::Degenerate(
145            "final triangle is not positively wound; polygon is self-intersecting or degenerate"
146                .to_owned(),
147        ));
148    }
149    out.push([indices[0] as u32, indices[1] as u32, indices[2] as u32]);
150    Ok(out)
151}
axiolid_reference/polygon.rs

axiolid_reference/
polygon.rs
