axiolid_overlay/
arc_overlay.rs

1//! Arc-aware planar boolean (ADR 0050; exact since ADR 0070).
2//!
3//! The polygon path ([`crate::overlay`], [`crate::Region`]) runs on the same
4//! exact core since #173. This path handles boundaries that carry arcs.
5//!
6//! # Exact, not tolerant
7//!
8//! Every topological decision is an exact sign over the given `f64` input
9//! (see `exact_arc`): where boundaries cross, in which order, what lies
10//! inside what, how the result links into rings, which ring is a hole of
11//! which. None of them uses the tolerance, so a scene gives the same answer
12//! in millimetres and in metres. Crossing points of two curves are in
13//! general irrational; they are rounded to `f64` once, in the output
14//! (correctly rounded where they are rational, as segment crossings are).
15//!
16//! The tolerance still validates operands ([`validate_arc_ring`]), the
17//! same contract the polygon path applies.
18
19use axiolid_core::Tolerance;
20use axiolid_guarantees::Sign;
21
22use crate::arc::{arc_orientation, validate_arc_ring, ArcRing};
23use crate::exact_arc;
24use crate::{OverlayError, OverlayOperation};
25
26/// An arc-aware region: one outer boundary and its holes.
27#[derive(Debug, Clone, PartialEq)]
28pub struct ArcPolygon {
29    /// Outer boundary, counter-clockwise.
30    pub outer: ArcRing,
31    /// Inner boundaries, each clockwise.
32    pub holes: Vec<ArcRing>,
33}
34
35/// Evidence that the arc path did what it claims.
36///
37/// `arc_edges` is the load-bearing number: a tessellating backend
38/// would return zero here while still producing a plausible area.
39#[derive(Debug, Clone, Copy, PartialEq, Eq)]
40pub struct ArcOverlayEvidence {
41    /// Outer boundaries in the result.
42    pub regions: usize,
43    /// Hole boundaries across all regions.
44    pub holes: usize,
45    /// Curved edges preserved as arcs, never tessellated.
46    pub arc_edges: usize,
47    /// Straight edges in the result.
48    pub line_edges: usize,
49}
50
51/// The result of an arc-aware boolean.
52#[derive(Debug, Clone, PartialEq)]
53pub struct ArcOverlayResult {
54    pub regions: Vec<ArcPolygon>,
55    pub evidence: ArcOverlayEvidence,
56}
57
58/// Count arc and straight edges in a ring.
59fn count_edges(ring: &ArcRing) -> (usize, usize) {
60    let arcs = ring
61        .vertices
62        .iter()
63        .filter(|vertex| vertex.bulge != 0.0)
64        .count();
65    (arcs, ring.vertices.len() - arcs)
66}
67
68/// Orient a ring so its signed area matches the wanted sign.
69///
70/// Outer boundaries are counter-clockwise and holes clockwise, so a
71/// consumer can rely on winding without recomputing areas. Operands are
72/// normalised on the way in (the exact core assumes the region lies left of
73/// its boundary) and results on the way out.
74fn oriented(ring: ArcRing, want_positive: bool) -> ArcRing {
75    if (arc_orientation(&ring) == Sign::Positive) == want_positive {
76        ring
77    } else {
78        crate::arc::reverse_arc_ring(&ring)
79    }
80}
81
82/// Collapse edges no longer than `tolerance` after output rounding.
83///
84/// Exact topology keeps pieces of any length. A crossing that lies within
85/// rounding of a vertex (a circle drawn through a corner, with coordinates
86/// like 0.3 that binary cannot hold) leaves a piece far shorter than any
87/// meaningful length, and once both ends are rounded to `f64` it can become
88/// a repeated vertex. Such an edge is dropped: its end vertex goes, and the
89/// following edge's bulge moves to its start, which lies within
90/// `tolerance` of the dropped vertex. A ring left without a valid shape
91/// (fewer vertices than a boundary needs, or no area) was a sliver below
92/// the tolerance and is removed.
93///
94/// This is the only place the tolerance acts on a result, and it acts on
95/// presentation only: which pieces exist and how they link were decided
96/// exactly beforehand.
97pub(crate) fn presented(mut ring: ArcRing, tolerance: Tolerance) -> Option<ArcRing> {
98    loop {
99        let count = ring.vertices.len();
100        if count < 2 {
101            return None;
102        }
103        let short = (0..count).find(|&i| {
104            let (a, b) = (ring.vertices[i].point, ring.vertices[(i + 1) % count].point);
105            (b - a).length() <= tolerance.linear()
106        });
107        let Some(i) = short else {
108            break;
109        };
110        let j = (i + 1) % count;
111        ring.vertices[i].bulge = ring.vertices[j].bulge;
112        ring.vertices.remove(j);
113    }
114    match validate_arc_ring(&ring, tolerance) {
115        Err(OverlayError::RingTooShort | OverlayError::ZeroArea) => None,
116        _ => Some(ring),
117    }
118}
119
120/// Boolean of two arc-capable regions.
121///
122/// Both operands are validated by the same contract the polygon path
123/// uses, so malformed input is refused by reason before any work happens.
124///
125/// Returns regions with outer boundaries counter-clockwise and holes
126/// clockwise. An empty result is not an error: an intersection of
127/// disjoint shapes is legitimately empty.
128///
129/// # Errors
130///
131/// Any [`validate_arc_ring`] refusal, and
132/// [`OverlayError::SelfIntersection`] when an operand's boundary crosses
133/// itself, which the exact linking detects.
134pub fn arc_overlay(
135    subject: &ArcRing,
136    clip: &ArcRing,
137    operation: OverlayOperation,
138    tolerance: Tolerance,
139) -> Result<ArcOverlayResult, OverlayError> {
140    validate_arc_ring(subject, tolerance)?;
141    validate_arc_ring(clip, tolerance)?;
142    let subject = oriented(subject.clone(), true);
143    let clip = oriented(clip.clone(), true);
144
145    let regions: Vec<ArcPolygon> = exact_arc::boolean(&subject, &clip, operation)?
146        .into_iter()
147        .filter_map(|(outer, holes)| {
148            Some(ArcPolygon {
149                outer: oriented(presented(outer, tolerance)?, true),
150                holes: holes
151                    .into_iter()
152                    .filter_map(|h| presented(h, tolerance))
153                    .map(|h| oriented(h, false))
154                    .collect(),
155            })
156        })
157        .collect();
158
159    let mut arc_edges = 0;
160    let mut line_edges = 0;
161    let mut holes = 0;
162    for region in &regions {
163        holes += region.holes.len();
164        for ring in std::iter::once(&region.outer).chain(&region.holes) {
165            let (arcs, lines) = count_edges(ring);
166            arc_edges += arcs;
167            line_edges += lines;
168        }
169    }
170
171    Ok(ArcOverlayResult {
172        evidence: ArcOverlayEvidence {
173            regions: regions.len(),
174            holes,
175            arc_edges,
176            line_edges,
177        },
178        regions,
179    })
180}
axiolid_overlay/arc_overlay.rs

axiolid_overlay/
arc_overlay.rs
