axiolid_overlay/
lib.rs

1#![forbid(unsafe_code)]
2//! Validated, deterministic planar boolean overlay and offset.
3mod arc;
4mod arc_overlay;
5mod arrangement;
6mod circle;
7mod exact_arc;
8mod exact_overlay;
9mod minkowski;
10mod offset;
11mod rectangle;
12mod region;
13mod settle;
14mod visibility;
15
16pub use arc::{
17    arc_edge_radius, arc_ring_area, reverse_arc_ring, validate_arc_ring, ArcRing, ArcVertex,
18};
19pub use arc_overlay::{arc_overlay, ArcOverlayEvidence, ArcOverlayResult, ArcPolygon};
20pub use arrangement::{
21    ArcArrangement, ArrangementEdge, ArrangementRegion, EdgeSource, EdgeUse as ArrangementEdgeUse,
22};
23pub use circle::{
24    minimum_enclosing_circle, CircleError, CircleEvidence, EnclosingCircle, MinimumCircle,
25};
26pub use minkowski::{BoundSide, MinkowskiError, MorphologyBound};
27pub use offset::{
28    offset_polygons, polygon_area, ring_area, stroke_polyline, total_area, CapStyle, JoinStyle,
29    OffsetEvidence, OffsetResult,
30};
31pub use rectangle::{
32    minimum_area_rectangle, MinimumRectangle, OrientedRectangle, RectangleError, RectangleEvidence,
33};
34pub use region::{Region, RegionEvidence};
35pub use visibility::VisibilityError;
36
37use axiolid_core::{Frame2, Point2, Polygon2, Tolerance};
38
39#[derive(Debug, Clone, Copy, PartialEq, Eq)]
40pub enum FillRule {
41    EvenOdd,
42    NonZero,
43    Positive,
44    Negative,
45}
46#[derive(Debug, Clone, Copy, PartialEq, Eq)]
47pub enum OverlayOperation {
48    Intersection,
49    Union,
50    Difference,
51    Xor,
52}
53#[derive(Debug, Clone, PartialEq)]
54pub struct Ring {
55    pub points: Vec<Point2>,
56}
57
58/// A `Ring` is a closed boundary and so is [`Polygon2`]; converting between
59/// them moves the points and nothing else.
60///
61/// The two exist separately because they are reached from different places:
62/// `Polygon2` is a foundation value type usable without this crate, while
63/// `Ring` is what the overlay consumes. Making them the same type
64/// would drag the planar boolean vocabulary into `axiolid-core`.
65impl From<Polygon2> for Ring {
66    fn from(polygon: Polygon2) -> Self {
67        Self {
68            points: polygon.vertices,
69        }
70    }
71}
72
73impl From<Ring> for Polygon2 {
74    fn from(ring: Ring) -> Self {
75        Self::new(ring.points)
76    }
77}
78
79impl From<&Ring> for Polygon2 {
80    fn from(ring: &Ring) -> Self {
81        Self::new(ring.points.clone())
82    }
83}
84
85#[derive(Debug, Clone, PartialEq)]
86pub struct Polygon {
87    pub outer: Ring,
88    pub holes: Vec<Ring>,
89}
90
91impl Polygon {
92    /// The outer boundary as a [`Polygon2`], discarding any holes.
93    ///
94    /// Named `outline` rather than offered as a `From` impl because the
95    /// conversion is lossy and the loss is silent: an annulus and a filled
96    /// disc have the same outline, so a caller that reaches for this to
97    /// compute area gets the wrong answer with no error. `Polygon2` models a
98    /// simple polygon and cannot represent a hole, which is exactly why this
99    /// has to be an explicit request rather than an implicit coercion.
100    ///
101    /// Use [`polygon_area`] when the holes matter.
102    pub fn outline(&self) -> Polygon2 {
103        Polygon2::from(&self.outer)
104    }
105
106    /// Whether the polygon has inner boundaries that [`outline`] would drop.
107    ///
108    /// [`outline`]: Polygon::outline
109    pub fn has_holes(&self) -> bool {
110        !self.holes.is_empty()
111    }
112}
113#[derive(Debug, Clone, PartialEq)]
114pub struct OverlayInput {
115    pub frame: Frame2,
116    pub polygons: Vec<Polygon>,
117}
118#[derive(Debug, Clone, PartialEq, Eq)]
119pub enum OverlayError {
120    InvalidFrame,
121    NonFinitePoint,
122    RingTooShort,
123    RepeatedVertex,
124    ZeroArea,
125    /// Non-adjacent boundary segments meet or cross.
126    SelfIntersection,
127    HoleOutsideOuter,
128    /// An offset distance or stroke width was not finite, or a width was not
129    /// positive. A non-finite distance cannot produce a bounded region.
130    InvalidOffsetDistance,
131    /// A join or cap parameter was not a finite positive value.
132    ///
133    /// Separate from [`OverlayError::InvalidOffsetDistance`] because the fix is
134    /// different: the caller passed a malformed style, not a malformed measure.
135    InvalidOffsetStyle,
136    /// An arc edge's implied radius was not above tolerance.
137    ///
138    /// Distinct from [`OverlayError::RepeatedVertex`]: the chord can be long
139    /// enough while the bulge still implies a radius too small to be a real
140    /// boundary. Such an edge is a point, not an arc.
141    ZeroRadiusArc,
142}
143#[derive(Debug, Clone, Copy, PartialEq, Eq)]
144pub struct OverlayEvidence {
145    pub subject_rings: usize,
146    pub clip_rings: usize,
147    pub output_polygons: usize,
148    /// Number of inner boundary components across all result polygons.
149    pub output_holes: usize,
150}
151#[derive(Debug, Clone, PartialEq)]
152pub struct OverlayResult {
153    pub polygons: Vec<Polygon>,
154    pub evidence: OverlayEvidence,
155}
156fn signed(r: &Ring) -> f64 {
157    r.points
158        .iter()
159        .zip(r.points.iter().cycle().skip(1))
160        .take(r.points.len())
161        .map(|(a, b)| a.x * b.y - b.x * a.y)
162        .sum::<f64>()
163        * 0.5
164}
165fn cross(a: Point2, b: Point2, c: Point2) -> f64 {
166    (b - a).perp_dot(c - a)
167}
168
169fn segments_intersect(a: Point2, b: Point2, c: Point2, d: Point2, epsilon: f64) -> bool {
170    let ac = cross(a, b, c);
171    let ad = cross(a, b, d);
172    let ca = cross(c, d, a);
173    let cb = cross(c, d, b);
174    // Boundary contact is topology, not a repairable numerical nuisance. A
175    // touching endpoint must lie ON the other segment, not merely on the
176    // infinite line through it: two collinear edges of a U-shape or a comb
177    // share a line without touching.
178    (ac.abs() <= epsilon && within_extent(a, b, c, epsilon))
179        || (ad.abs() <= epsilon && within_extent(a, b, d, epsilon))
180        || (ca.abs() <= epsilon && within_extent(c, d, a, epsilon))
181        || (cb.abs() <= epsilon && within_extent(c, d, b, epsilon))
182        || ((ac > 0.0) != (ad > 0.0) && (ca > 0.0) != (cb > 0.0))
183}
184
185/// Whether `p` lies inside the axis-aligned box of segment `a`-`b`, widened
186/// by `epsilon`. Combined with collinearity this puts `p` on the segment.
187fn within_extent(a: Point2, b: Point2, p: Point2, epsilon: f64) -> bool {
188    p.x >= a.x.min(b.x) - epsilon
189        && p.x <= a.x.max(b.x) + epsilon
190        && p.y >= a.y.min(b.y) - epsilon
191        && p.y <= a.y.max(b.y) + epsilon
192}
193
194fn self_intersects(r: &Ring, t: Tolerance) -> bool {
195    let n = r.points.len();
196    for i in 0..n {
197        for j in i + 1..n {
198            if j == i + 1 || (i == 0 && j + 1 == n) {
199                continue;
200            }
201            if segments_intersect(
202                r.points[i],
203                r.points[(i + 1) % n],
204                r.points[j],
205                r.points[(j + 1) % n],
206                t.linear(),
207            ) {
208                return true;
209            }
210        }
211    }
212    false
213}
214
215pub(crate) fn validate_ring(r: &Ring, t: Tolerance) -> Result<(), OverlayError> {
216    if r.points.len() < 3 {
217        return Err(OverlayError::RingTooShort);
218    };
219    if !r.points.iter().all(|p| p.is_finite()) {
220        return Err(OverlayError::NonFinitePoint);
221    };
222    if r.points
223        .iter()
224        .zip(r.points.iter().cycle().skip(1))
225        .take(r.points.len())
226        .any(|(a, b)| (*a - *b).length() <= t.linear())
227    {
228        return Err(OverlayError::RepeatedVertex);
229    };
230    if self_intersects(r, t) {
231        return Err(OverlayError::SelfIntersection);
232    }
233    if signed(r).abs() <= t.linear().powi(2) {
234        return Err(OverlayError::ZeroArea);
235    };
236    Ok(())
237}
238fn validate(input: &OverlayInput, t: Tolerance) -> Result<(), OverlayError> {
239    let f = input.frame;
240    if !f.origin.is_finite()
241        || !f.x.is_finite()
242        || !f.y.is_finite()
243        || (f.x.length() - 1.).abs() > t.linear()
244        || (f.y.length() - 1.).abs() > t.linear()
245        || f.x.dot(f.y).abs() > t.linear()
246        || f.x.perp_dot(f.y) <= 0.
247    {
248        return Err(OverlayError::InvalidFrame);
249    }
250    for p in &input.polygons {
251        validate_ring(&p.outer, t)?;
252        for h in &p.holes {
253            validate_ring(h, t)?;
254            if hole_outside(&p.outer, h, t) {
255                return Err(OverlayError::HoleOutsideOuter);
256            }
257        }
258    }
259    Ok(())
260}
261/// Whether a hole leaves its outer ring: a vertex of it strictly outside.
262/// Vertices on the outer boundary decide nothing -- a hole may touch its
263/// outer ring at a vertex, which settled outputs do, and testing only the
264/// first vertex called such a hole outside whenever that was the touching
265/// one (axioval, #191).
266fn hole_outside(outer: &Ring, hole: &Ring, t: Tolerance) -> bool {
267    let n = outer.points.len();
268    let on_boundary = |q: Point2| {
269        (0..n).any(|i| {
270            let (a, b) = (outer.points[i], outer.points[(i + 1) % n]);
271            cross(a, b, q).abs() <= t.linear() && within_extent(a, b, q, t.linear())
272        })
273    };
274    hole.points
275        .iter()
276        .any(|&q| !on_boundary(q) && !contains(outer, q))
277}
278fn contains(r: &Ring, p: Point2) -> bool {
279    let mut inside = false;
280    for (a, b) in r
281        .points
282        .iter()
283        .zip(r.points.iter().cycle().skip(1))
284        .take(r.points.len())
285    {
286        if (a.y > p.y) != (b.y > p.y) && p.x < (b.x - a.x) * (p.y - a.y) / (b.y - a.y) + a.x {
287            inside = !inside
288        }
289    }
290    inside
291}
292pub(crate) fn canonical(mut r: Ring, want_positive: bool) -> Ring {
293    if (signed(&r) > 0.) != want_positive {
294        r.points.reverse()
295    };
296    let k = r
297        .points
298        .iter()
299        .enumerate()
300        .min_by(|a, b| {
301            a.1.x
302                .total_cmp(&b.1.x)
303                .then(a.1.y.total_cmp(&b.1.y))
304                .then(a.0.cmp(&b.0))
305        })
306        .map(|x| x.0)
307        .unwrap_or(0);
308    r.points.rotate_left(k);
309    r
310}
311/// Performs a neutral planar overlay. Output ordering is deterministic: polygons sort by outer-ring lexicographic start, rings are canonicalized CCW/CW.
312///
313/// Exact (#173): where boundaries cross and which side of each piece lies
314/// in the result are exact decisions; the tolerance only validates the
315/// operands and settles the output. An input vertex the operation does not
316/// move comes back bit-identical, and a crossing of two edges is the double
317/// nearest to the exact crossing point.
318pub fn overlay(
319    subject: &OverlayInput,
320    clip: &OverlayInput,
321    operation: OverlayOperation,
322    fill: FillRule,
323    tolerance: Tolerance,
324) -> Result<OverlayResult, OverlayError> {
325    validate(subject, tolerance)?;
326    validate(clip, tolerance)?;
327    if subject.frame != clip.frame {
328        return Err(OverlayError::InvalidFrame);
329    };
330    let rings = exact_overlay::boolean(&subject.polygons, &clip.polygons, operation, fill)?;
331    let polygons = settle::settle(canonical_polygons(rings), tolerance);
332    let evidence = OverlayEvidence {
333        subject_rings: subject.polygons.iter().map(|p| 1 + p.holes.len()).sum(),
334        clip_rings: clip.polygons.iter().map(|p| 1 + p.holes.len()).sum(),
335        output_polygons: polygons.len(),
336        output_holes: polygons.iter().map(|polygon| polygon.holes.len()).sum(),
337    };
338    Ok(OverlayResult { polygons, evidence })
339}
340
341/// Union a set of individually-valid rings that may overlap each other.
342///
343/// [`overlay`] rejects a self-intersecting *operand*, which is correct for a
344/// boolean between two shapes but wrong for a union of a triangle soup: a
345/// projected mesh routinely overlaps itself, and mutual overlap is exactly
346/// what a union is for. Each ring is still validated on its own, so malformed
347/// geometry is refused rather than absorbed.
348pub fn union_soup(rings: &[Ring], tolerance: Tolerance) -> Result<Vec<Polygon>, OverlayError> {
349    for ring in rings {
350        validate_ring(ring, tolerance)?;
351    }
352    if rings.is_empty() {
353        return Ok(Vec::new());
354    }
355    // All rings form one subject against an empty clip. The NonZero fill
356    // then resolves the mutual overlaps in a single pass, which is both
357    // correct and cheaper than folding pairwise.
358    let subject: Vec<Polygon> = rings
359        .iter()
360        .map(|ring| Polygon {
361            outer: ring.clone(),
362            holes: Vec::new(),
363        })
364        .collect();
365    let rings = exact_overlay::boolean(&subject, &[], OverlayOperation::Union, FillRule::NonZero)?;
366    // Settled like every other output, so the polygons are valid operands
367    // (#191).
368    Ok(settle::settle(canonical_polygons(rings), tolerance))
369}
370
371/// Canonical kernel polygons from a boolean's rings.
372///
373/// Shared by every operation so ring orientation, rotation and polygon
374/// ordering cannot drift between them.
375fn canonical_polygons(rings: Vec<(Ring, Vec<Ring>)>) -> Vec<Polygon> {
376    let mut polygons: Vec<Polygon> = rings
377        .into_iter()
378        .map(|(outer, holes)| Polygon {
379            outer: canonical(outer, true),
380            holes: holes.into_iter().map(|h| canonical(h, false)).collect(),
381        })
382        .collect();
383    polygons.sort_by(|a, b| {
384        a.outer.points[0]
385            .x
386            .total_cmp(&b.outer.points[0].x)
387            .then(a.outer.points[0].y.total_cmp(&b.outer.points[0].y))
388    });
389    polygons
390}
axiolid_overlay/lib.rs

axiolid_overlay/
lib.rs
