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.
35///
36/// `orient2d` escalates to exact arithmetic, so it always certifies; this
37/// helper documents that invariant instead of scattering `expect` calls.
38fn sign_of(a: Point2, b: Point2, c: Point2) -> Sign {
39    orient2d(a, b, c)
40        .sign()
41        .expect("orient2d escalates to exact arithmetic and always certifies")
42}
43
44/// Whether `p` lies in or on the boundary of counter-clockwise triangle
45/// `a,b,c`, using certified signs.
46///
47/// A non-corner vertex on an ear boundary blocks that ear. Otherwise the clip
48/// can leave a negatively wound remainder whose signed area merely cancels the
49/// outside area it emitted.
50fn blocks_ear(a: Point2, b: Point2, c: Point2, p: Point2) -> bool {
51    let s1 = sign_of(a, b, p);
52    let s2 = sign_of(b, c, p);
53    let s3 = sign_of(c, a, p);
54    s1 != Sign::Negative && s2 != Sign::Negative && s3 != Sign::Negative
55}
56
57/// Whether vertex `i` of `ring` is a clippable ear of a CCW polygon.
58fn is_ear(ring: &[Point2], indices: &[usize], at: usize) -> bool {
59    let n = indices.len();
60    let (ia, ib, ic) = (
61        indices[(at + n - 1) % n],
62        indices[at],
63        indices[(at + 1) % n],
64    );
65    let (a, b, c) = (ring[ia], ring[ib], ring[ic]);
66
67    // Reflex or collinear vertices are never ears. Collinear is excluded
68    // because a zero-area ear adds a degenerate triangle to the output.
69    if sign_of(a, b, c) != Sign::Positive {
70        return false;
71    }
72
73    // No other vertex may fall inside the candidate ear.
74    //
75    // Bridged rings contain DUPLICATE vertices by construction: a bridge visits
76    // the same two points twice. Comparing by index alone would treat a
77    // duplicate of an ear corner as an intruder and reject every ear, so
78    // coincident positions are skipped as well.
79    !indices
80        .iter()
81        .filter(|&&idx| idx != ia && idx != ib && idx != ic)
82        .map(|&idx| ring[idx])
83        .filter(|q| *q != a && *q != b && *q != c)
84        .any(|q| blocks_ear(a, b, c, q))
85}
86
87/// Triangulate a simple CCW polygon by ear clipping.
88///
89/// Returns index triples into `ring`. Fails rather than emitting a partial fan:
90/// a caller that receives triangles must be able to trust they cover the input.
91pub fn triangulate_simple(ring: &[Point2]) -> GeomResult<Vec<[u32; 3]>> {
92    if ring.len() < 3 {
93        return Err(GeomError::Degenerate(format!(
94            "ring has {} vertices, need at least 3",
95            ring.len()
96        )));
97    }
98    let mut indices: Vec<usize> = (0..ring.len()).collect();
99    let mut out = Vec::with_capacity(ring.len().saturating_sub(2));
100
101    // Each successful clip removes one vertex, so the loop is bounded. The
102    // `guard` counts consecutive failures: a full pass with no ear found means
103    // the polygon is not simple, which is a data fault, not a retry case.
104    let mut at = 0usize;
105    let mut guard = 0usize;
106    while indices.len() > 3 {
107        if guard > indices.len() {
108            return Err(GeomError::Degenerate(
109                "no ear found; polygon is self-intersecting or degenerate".to_owned(),
110            ));
111        }
112        if is_ear(ring, &indices, at % indices.len()) {
113            let n = indices.len();
114            let cur = at % n;
115            out.push([
116                indices[(cur + n - 1) % n] as u32,
117                indices[cur] as u32,
118                indices[(cur + 1) % n] as u32,
119            ]);
120            indices.remove(cur);
121            at = cur;
122            guard = 0;
123        } else {
124            at += 1;
125            guard += 1;
126        }
127    }
128    // The final triangle must still enclose area; a collinear remainder means
129    // the whole ring was degenerate and no valid fan exists.
130    let (a, b, c) = (ring[indices[0]], ring[indices[1]], ring[indices[2]]);
131    if sign_of(a, b, c) != Sign::Positive {
132        return Err(GeomError::Degenerate(
133            "final triangle is not positively wound; polygon is self-intersecting or degenerate"
134                .to_owned(),
135        ));
136    }
137    out.push([indices[0] as u32, indices[1] as u32, indices[2] as u32]);
138    Ok(out)
139}
axiolid_reference/polygon.rs

axiolid_reference/
polygon.rs
