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

axiolid_overlay/
arc_overlay.rs
