Skip to main content

section_properties/geometry/
boolean.rs

1//! Boolean operations on polygons (union, intersection, difference).
2//!
3//! Implements the Greiner–Hormann clipping algorithm, which plays the same
4//! role shapely plays for Python `sectionproperties`. Handles non-convex
5//! simple polygons; degenerate cases (a vertex lying exactly on another
6//! polygon's edge) are avoided by convention.
7//!
8//! `difference(a, b)` is realised as `intersection(a, b.reversed())`.
9
10use super::{Point, Polygon};
11
12/// Boolean operation selector.
13#[derive(Debug, Clone, Copy, PartialEq, Eq)]
14pub enum BoolOp {
15    /// Region covered by both polygons.
16    Intersection,
17    /// Region covered by either polygon.
18    Union,
19    /// Region covered by `a` but not `b`.
20    Difference,
21}
22
23#[derive(Debug, Clone)]
24struct Node {
25    pt: Point,
26    prev: usize,
27    next: usize,
28    is_inter: bool,
29    /// Walking forward along this ring, do we enter the other polygon?
30    entry: bool,
31    /// Index of the paired node in the other ring.
32    neighbor: usize,
33    /// Shared intersection id (pairing key).
34    pair: usize,
35    processed: bool,
36}
37
38#[derive(Debug, Clone)]
39struct Ring {
40    nodes: Vec<Node>,
41}
42
43impl Ring {
44    fn step(&self, i: usize, forward: bool) -> usize {
45        if forward {
46            self.nodes[i].next
47        } else {
48            self.nodes[i].prev
49        }
50    }
51}
52
53struct RawIntersection {
54    ea: usize,
55    ta: f64,
56    eb: usize,
57    tb: f64,
58    pt: Point,
59}
60
61/// Proper interior edge-edge intersection parameters (`None` if parallel or
62/// non-crossing).
63fn edge_intersection(p1: Point, p2: Point, q1: Point, q2: Point) -> Option<(f64, f64)> {
64    let rx = p2.x - p1.x;
65    let ry = p2.y - p1.y;
66    let sx = q2.x - q1.x;
67    let sy = q2.y - q1.y;
68
69    let denom = rx * sy - ry * sx;
70    if denom.abs() < 1e-14 {
71        return None;
72    }
73
74    let qpx = q1.x - p1.x;
75    let qpy = q1.y - p1.y;
76    let s = (qpx * sy - qpy * sx) / denom;
77    let t = (qpx * ry - qpy * rx) / denom;
78
79    if s > 0.0 && s < 1.0 && t > 0.0 && t < 1.0 {
80        Some((s, t))
81    } else {
82        None
83    }
84}
85
86fn compute_raw_intersections(pa: &[Point], pb: &[Point]) -> Vec<RawIntersection> {
87    let na = pa.len();
88    let nb = pb.len();
89    let mut out = Vec::new();
90
91    for i in 0..na {
92        for j in 0..nb {
93            if let Some((ta, tb)) =
94                edge_intersection(pa[i], pa[(i + 1) % na], pb[j], pb[(j + 1) % nb])
95            {
96                out.push(RawIntersection {
97                    ea: i,
98                    ta,
99                    eb: j,
100                    tb,
101                    pt: Point::new(
102                        pa[i].x + ta * (pa[(i + 1) % na].x - pa[i].x),
103                        pa[i].y + ta * (pa[(i + 1) % na].y - pa[i].y),
104                    ),
105                });
106            }
107        }
108    }
109    out
110}
111
112/// Build a ring from base vertices plus spliced intersection nodes.
113/// `inters`: (edge_index, param, shared_id) sorted later per-edge.
114fn build_ring(base: &[Point], inters: &[(usize, f64, usize)], raw: &[RawIntersection]) -> Ring {
115    let n = base.len();
116    let mut by_edge: std::collections::HashMap<usize, Vec<(f64, usize)>> =
117        std::collections::HashMap::new();
118    for &(e, t, id) in inters {
119        by_edge.entry(e).or_default().push((t, id));
120    }
121    for list in by_edge.values_mut() {
122        list.sort_by(|x, y| x.0.partial_cmp(&y.0).unwrap());
123    }
124
125    let mut nodes: Vec<Node> = Vec::new();
126    for i in 0..n {
127        let idx = nodes.len();
128        nodes.push(Node {
129            pt: base[i],
130            prev: idx.wrapping_sub(usize::MAX / 2), // fixed below
131            next: 0,
132            is_inter: false,
133            entry: false,
134            neighbor: usize::MAX,
135            pair: usize::MAX,
136            processed: false,
137        });
138
139        if let Some(list) = by_edge.get(&i) {
140            for &(_, id) in list {
141                let idx = nodes.len();
142                nodes.push(Node {
143                    pt: raw[id].pt,
144                    prev: idx - 1,
145                    next: idx + 1,
146                    is_inter: true,
147                    entry: false,
148                    neighbor: usize::MAX,
149                    pair: id,
150                    processed: false,
151                });
152            }
153        }
154    }
155
156    // Close ring links.
157    let last = nodes.len() - 1;
158    for i in 0..=last {
159        nodes[i].next = if i == last { 0 } else { i + 1 };
160        nodes[i].prev = if i == 0 { last } else { i - 1 };
161    }
162
163    Ring { nodes }
164}
165
166/// Assign entry flags by walking forward from the first vertex, whose
167/// inside/outside status w.r.t. the other polygon is given.
168fn assign_entries(ring: &mut Ring, first_inside_other: bool) {
169    let mut inside = first_inside_other;
170    for i in 0..ring.nodes.len() {
171        if ring.nodes[i].is_inter {
172            ring.nodes[i].entry = !inside;
173            inside = !inside;
174        }
175    }
176}
177
178/// Trace one output loop starting at an unprocessed intersection node.
179fn trace_loop(a: &mut Ring, b: &mut Ring, start: usize, op: BoolOp) -> Vec<Point> {
180    let mut pts = vec![a.nodes[start].pt];
181    let mut in_a = true;
182    let mut cur = start;
183    let max_iter = a.nodes.len() + b.nodes.len() + 4;
184
185    for _ in 0..max_iter {
186        // Direction rule (Foster):
187        // intersection: forward if entering; union: forward if exiting.
188        // difference is handled upstream as intersection with reversed B.
189        let entry = {
190            let ring = if in_a { &*a } else { &*b };
191            ring.nodes[cur].entry
192        };
193        let forward = match (op, in_a) {
194            (BoolOp::Intersection, _) => entry,
195            (BoolOp::Union, _) => !entry,
196            (BoolOp::Difference, true) => !entry,
197            (BoolOp::Difference, false) => entry,
198        };
199
200        a_mark_pair(a, b, cur, in_a);
201
202        // Walk emitting ordinary vertices until the next intersection.
203        loop {
204            cur = {
205                let ring = if in_a { &*a } else { &*b };
206                ring.step(cur, forward)
207            };
208            let is_inter = {
209                let ring = if in_a { &*a } else { &*b };
210                ring.nodes[cur].is_inter
211            };
212            if is_inter || (cur == start && in_a) {
213                break;
214            }
215            pts.push({
216                let ring = if in_a { &*a } else { &*b };
217                ring.nodes[cur].pt
218            });
219        }
220
221        if cur == start && in_a {
222            break;
223        }
224
225        // Emit the reached intersection, consume it, and jump across rings.
226        pts.push({
227            let ring = if in_a { &*a } else { &*b };
228            ring.nodes[cur].pt
229        });
230        a_mark_pair(a, b, cur, in_a);
231        let reached_neighbor = {
232            let ring = if in_a { &*a } else { &*b };
233            ring.nodes[cur].neighbor
234        };
235        debug_assert!(reached_neighbor != usize::MAX);
236        cur = reached_neighbor;
237        in_a = !in_a;
238
239        // Closure: arriving back at the start node (only meaningful once we
240        // are back in ring A).
241        if in_a && cur == start {
242            break;
243        }
244    }
245
246    pts
247}
248fn a_mark_pair(a: &mut Ring, b: &mut Ring, cur: usize, in_a: bool) {
249    if in_a {
250        a.nodes[cur].processed = true;
251        let n = a.nodes[cur].neighbor;
252        if n != usize::MAX {
253            b.nodes[n].processed = true;
254        }
255    } else {
256        b.nodes[cur].processed = true;
257        let n = b.nodes[cur].neighbor;
258        if n != usize::MAX {
259            a.nodes[n].processed = true;
260        }
261    }
262}
263
264fn signed_area_pts(pts: &[Point]) -> f64 {
265    pts.iter()
266        .enumerate()
267        .map(|(k, p)| {
268            let q = &pts[(k + 1) % pts.len()];
269            p.x * q.y - q.x * p.y
270        })
271        .sum::<f64>()
272        / 2.0
273}
274
275/// Approximate scale of a polygon (bounding-box diagonal).
276fn bbox_diag(pts: &[Point]) -> f64 {
277    let (mut mn_x, mut mn_y) = (f64::INFINITY, f64::INFINITY);
278    let (mut mx_x, mut mx_y) = (f64::NEG_INFINITY, f64::NEG_INFINITY);
279    for p in pts {
280        mn_x = mn_x.min(p.x);
281        mn_y = mn_y.min(p.y);
282        mx_x = mx_x.max(p.x);
283        mx_y = mx_y.max(p.y);
284    }
285    ((mx_x - mn_x).powi(2) + (mx_y - mn_y).powi(2))
286        .sqrt()
287        .max(1e-12)
288}
289
290/// Distance from point `p` to segment `a`-`b`.
291fn point_segment_dist(p: Point, a: Point, b: Point) -> f64 {
292    let abx = b.x - a.x;
293    let aby = b.y - a.y;
294    let l2 = abx * abx + aby * aby;
295    if l2 < 1e-24 {
296        return ((p.x - a.x).powi(2) + (p.y - a.y).powi(2)).sqrt();
297    }
298    let t = (((p.x - a.x) * abx + (p.y - a.y) * aby) / l2).clamp(0.0, 1.0);
299    let cx = a.x + t * abx;
300    let cy = a.y + t * aby;
301    ((p.x - cx).powi(2) + (p.y - cy).powi(2)).sqrt()
302}
303
304/// True if any vertex of `a` lies (nearly) on the boundary of `b` or vice
305/// versa -- the class of degeneracies Greiner-Hormann cannot handle directly.
306fn has_vertex_on_boundary(a: &[Point], b: &Polygon, tol: f64) -> bool {
307    let n = b.vertices.len();
308    for p in a {
309        for i in 0..n {
310            if point_segment_dist(*p, b.vertices[i], b.vertices[(i + 1) % n]) <= tol {
311                return true;
312            }
313        }
314    }
315    false
316}
317
318/// Run the boolean operation on the outer boundaries of two polygons.
319///
320/// Returns the resulting polygons; an empty vector means an empty result.
321///
322/// # Deterministic behaviour
323///
324/// When a vertex of either polygon lies on the other's boundary (degenerate
325/// for Greiner–Hormann), the function applies **systematic deterministic
326/// perturbation** in fixed directions rather than random jitter. This
327/// guarantees that identical inputs always produce identical outputs.
328///
329/// The result is validated against the area inclusion-exclusion identity:
330/// `|A| + |B| = |A∩B| + |A∪B|`, which is a strict mathematical invariant.
331/// Compute boolean operation on two polygons.
332fn polygon_boolean_internal(
333    a: &Polygon,
334    b: &Polygon,
335    op: BoolOp,
336) -> Result<Vec<Polygon>, BooleanError> {
337    // Identical boundaries: exact fast path.
338    if a.vertices.len() == b.vertices.len()
339        && a.vertices.iter().zip(&b.vertices).all(|(p, q)| p == q)
340    {
341        return Ok(match op {
342            BoolOp::Intersection | BoolOp::Union => vec![a.clone()],
343            BoolOp::Difference => vec![],
344        });
345    }
346
347    // Robustness: when a vertex of either polygon sits (nearly) on the other
348    // polygon's boundary (or edges are collinear-overlapping), the generic
349    // Greiner–Hormann algorithm cannot resolve the degeneracy. `b` is shifted
350    // by a fixed deterministic offset to remove the degeneracy; the result is
351    // then mapped back onto the original coordinates.
352    //
353    // The degeneracy-detection tolerance must match the perturbation scale:
354    // detecting a vertex only works if the shift is large enough to move it off
355    // the other polygon's boundary. We therefore derive `eps` first and scale
356    // the detection window by a small multiple of it.
357    let diag = bbox_diag(&a.vertices).max(bbox_diag(&b.vertices));
358    // Use scale-adaptive epsilon: large enough to resolve vertex-on-edge
359    // degeneracies, small enough to avoid coordinate distortion.
360    // eps = 1e-8 * diag, clamped to [1e-12 * diag, 1e-6 * min(diag, 1.0)].
361    // For diag=1e6 mm (1 km): eps = 1e-2 mm (clamped to 1e-6 * 1.0 = 1 µm)
362    // For diag=1e-3 mm (1 µm): eps = 1e-11 mm → clamped to 1e-15 mm (near f64 precision)
363    // This ensures the perturbation is never larger than 1 micron for large models,
364    // avoiding the issue where 0.5 mm gaps were incorrectly merged.
365    let upper = 1e-6 * diag.min(1.0);
366    let lower = (1e-12 * diag).min(upper);
367    let eps = (1e-8 * diag).clamp(lower, upper);
368    // Detection window slightly larger than the shift so that any vertex we
369    // detect as degenerate is actually moved clear of the boundary.
370    let det_tol = 8.0 * eps;
371    let degenerate = has_vertex_on_boundary(&a.vertices, b, det_tol)
372        || has_vertex_on_boundary(&b.vertices, a, det_tol);
373
374    if !degenerate {
375        return Ok(polygon_boolean_impl(a, b, op));
376    }
377
378    // Deterministic perturbation: try systematic shifts in fixed directions.
379    // Directions chosen to avoid common edge orientations (horizontal, vertical,
380    // 45-degree).
381    let directions: &[(f64, f64)] = &[
382        (1.0, 0.37),   // ~20° from horizontal
383        (-0.61, 1.0),  // ~122° from horizontal
384        (0.83, -0.83), // ~-45° from horizontal
385    ];
386
387    let area_a = a.area();
388    let area_b = b.area();
389    // Normaliser for the relative inclusion-exclusion error.
390    let denom = (area_a.abs() + area_b.abs()).max(1e-12);
391
392    // The inverse of `op`: |op(a,b)| + |complement(a,b)| = |a| + |b| always.
393    let comp_op = match op {
394        BoolOp::Intersection => BoolOp::Union,
395        BoolOp::Union => BoolOp::Intersection,
396        BoolOp::Difference => BoolOp::Intersection,
397    };
398
399    for &(dx, dy) in directions {
400        let shifted: Vec<Point> = b
401            .vertices
402            .iter()
403            .map(|p| Point::new(p.x + eps * dx, p.y + eps * dy))
404            .collect();
405        let b_shifted = Polygon::new(shifted);
406
407        // Compute the main op and its complement **in the same shifted frame**,
408        // using the non-perturbing impl. The shift removes the original
409        // degeneracy, so `polygon_boolean_impl` (bare GH + nesting fast paths)
410        // is exact on `(a, b_shifted)` and does not recurse back into this
411        // perturbation logic.
412        let result = polygon_boolean_impl(a, &b_shifted, op);
413        let result_comp = polygon_boolean_impl(a, &b_shifted, comp_op);
414
415        // Area is translation-invariant, so summing the shifted-frame results
416        // and comparing against the per-op inclusion-exclusion reference gives
417        // the strict identity (both |a| and |b| are translation-invariant, and
418        // |b_shifted| == |b|):
419        //   Intersection/Union: |op| + |complement| = |a| + |b|
420        //   Difference:         |A\B| + |A∩B|      = |a|
421        let area_result: f64 = result.iter().map(|p| p.area()).sum();
422        let area_comp: f64 = result_comp.iter().map(|p| p.area()).sum();
423        let rhs = match op {
424            BoolOp::Difference => area_a,
425            BoolOp::Intersection | BoolOp::Union => area_a + area_b,
426        };
427        let err = (area_result + area_comp - rhs).abs() / denom;
428
429        // Map the perturbed result back onto the original coordinates so that
430        // higher-order quantities (centroid, moments, principal axes) do not
431        // inherit the artificial `eps * direction` offset.
432        let mapped: Vec<Polygon> = result
433            .into_iter()
434            .map(|mut r| {
435                for v in &mut r.vertices {
436                    v.x -= eps * dx;
437                    v.y -= eps * dy;
438                }
439                r
440            })
441            .collect();
442
443        if err < 1e-9 {
444            // Strict inclusion-exclusion satisfied: accept.
445            return Ok(mapped);
446        }
447    }
448
449    // No direction satisfied the strict identity.
450    Err(BooleanError::Validation {
451        op,
452        message: "boolean operation failed strict inclusion-exclusion identity after perturbation; no perturbation direction produced a geometrically consistent result".to_string(),
453    })
454}
455
456/// Errors from polygon / section boolean operations.
457#[derive(Debug, Clone, PartialEq)]
458pub enum BooleanError {
459    /// The computed result violates a geometric invariant (area bounds or
460    /// point-in/polygon sampling) and must not be used downstream. Returning
461    /// this instead of a `Vec<Polygon>` prevents a silently-wrong boolean from
462    /// propagating corrupt areas, centroids, moments and FEM meshes.
463    Validation { op: BoolOp, message: String },
464}
465
466impl std::fmt::Display for BooleanError {
467    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
468        match self {
469            BooleanError::Validation { op, message } => {
470                write!(f, "boolean {:?} failed validation: {}", op, message)
471            }
472        }
473    }
474}
475
476impl std::error::Error for BooleanError {}
477
478/// Cheap per-op area-bounds reconciliation.
479///
480/// Catches gross topological errors that the inclusion-exclusion identity
481/// alone cannot. Example: a blundering algorithm may return `|A∩B|=30` and
482/// `|A∪B|=170` for two area-100 polygons. The identity `30+170=100+100` holds,
483/// yet the union clearly violates `|A∪B| >= max(|A|,|B|) = 100`.
484pub fn check_boolean_bounds(
485    result: &[Polygon],
486    a: &Polygon,
487    b: &Polygon,
488    op: BoolOp,
489) -> Result<(), BooleanError> {
490    let area_a = a.area();
491    let area_b = b.area();
492    let area_res: f64 = result.iter().map(|p| p.area()).sum();
493    // Sliver allowance: perturbation-induced slivers are ~eps*scale in area
494    // (~1e-8 relative), so a 1e-6 relative tolerance is far larger than any
495    // legitimate sliver yet far smaller than a genuine topological blunder.
496    let rel = 1e-6;
497    let fail = |message: String| BooleanError::Validation { op, message };
498    match op {
499        BoolOp::Intersection => {
500            let min = area_a.min(area_b);
501            let tol = rel * min.abs().max(1e-12);
502            if area_res < -tol || area_res > min + tol {
503                return Err(fail(format!(
504                    "intersection area {:.6} outside [0, min(|A|,|B|) = {:.6}]",
505                    area_res, min
506                )));
507            }
508        }
509        BoolOp::Union => {
510            let max = area_a.max(area_b);
511            // |A∪B| must lie within [max(|A|,|B|), |A|+|B|]. Violating either
512            // bound means the result cannot be a true union of A and B.
513            let lo = max;
514            let hi = area_a + area_b;
515            let tol = rel * hi.abs().max(1e-12);
516            if area_res < lo - tol || area_res > hi + tol {
517                return Err(fail(format!(
518                    "union area {:.6} outside [max(|A|,|B|) = {:.6}, |A|+|B| = {:.6}]",
519                    area_res, lo, hi
520                )));
521            }
522        }
523        BoolOp::Difference => {
524            let tol = rel * area_a.abs().max(1e-12);
525            if area_res < -tol || area_res > area_a + tol {
526                return Err(fail(format!(
527                    "difference area {:.6} outside [0, |A| = {:.6}]",
528                    area_res, area_a
529                )));
530            }
531        }
532    }
533    Ok(())
534}
535
536/// Deterministic point-in/polygon sampling validation.
537///
538/// Much stronger than area checks: verifies the result's set membership against
539/// the expected boolean (`op(A,B)`) at a grid of sample points covering the
540/// combined bounding box. Points on (or within a perturbation tolerance of) any
541/// boundary are skipped because membership there is inherently ambiguous; on
542/// the clean interior samples any mismatch is a genuine topology error.
543///
544/// # Why this is OPT-IN / advisory (not a default gate)
545///
546/// It can raise **false positives on legitimately-correct geometry** for two
547/// fundamental reasons:
548///
549/// 1. `Polygon::contains_point` (ray casting) and the GH boolean kernel use
550///    **incompatible interior/winding interpretations** on concave polygons.
551///    Measured example: for the U-shape `(0,0)(3,0)(3,3)(2,3)(2,1)(1,1)(1,3)(0,3)`
552///    the ray-caster reports a notch point `(1.5,2.0)` as *exterior* while the
553///    kernel treats the region as interior, so `u ∩ fill` returns area = 4 (the
554///    full fill) yet the sampler's `contains_point(result, notch-pt)` is `true`.
555///    Any sampler built on `contains_point` will therefore disagree with the
556///    kernel on such inputs.
557/// 2. Polygon-level `Difference` of a nested operand returns the outer region
558///    *without cutting the hole* (a documented module convention — the hole is
559///    only realised at `Section` level). Sampling naively expects the hole to
560///    be present and flags the (correct, convention-compliant) result.
561///
562/// To reduce false positives, this function now **skips sampling validation**
563/// for `Difference` when `result.area() ≈ |A|` (i.e. no hole was actually cut),
564/// since that is the documented convention-compliant outcome.
565///
566/// Consequently it is exposed separately as `polygon_boolean_sampled_checked`
567/// and is intended for callers who know their inputs are convex and
568/// non-nested, where it adds a strong extra correctness signal.
569fn validate_boolean_sampling(
570    result: &[Polygon],
571    a: &Polygon,
572    b: &Polygon,
573    op: BoolOp,
574) -> Result<(), BooleanError> {
575    // Fast skip: for nested Difference where result == outer (no hole cut),
576    // this is the documented convention. Sampling would flag it falsely.
577    if op == BoolOp::Difference {
578        let area_a = a.area();
579        let area_res: f64 = result.iter().map(|p| p.area()).sum();
580        if (area_res - area_a).abs() < 1e-9 {
581            return Ok(());
582        }
583    }
584
585    let diag = bbox_diag(&a.vertices).max(bbox_diag(&b.vertices));
586    if diag <= 0.0 {
587        return Ok(());
588    }
589    let upper = 1e-6 * diag.min(1.0);
590    let lower = (1e-12 * diag).min(upper);
591    let eps = (1e-8 * diag).clamp(lower, upper);
592    let bnd_tol = 16.0 * eps;
593
594    // Combined bounding box of a, b and the result so the grid covers everything.
595    let (minx, maxx, miny, maxy) = {
596        let mut minx = f64::INFINITY;
597        let mut maxx = f64::NEG_INFINITY;
598        let mut miny = f64::INFINITY;
599        let mut maxy = f64::NEG_INFINITY;
600        for p in std::iter::once(a).chain(std::iter::once(b)).chain(result) {
601            for v in &p.vertices {
602                minx = minx.min(v.x);
603                maxx = maxx.max(v.x);
604                miny = miny.min(v.y);
605                maxy = maxy.max(v.y);
606            }
607        }
608        (minx, maxx, miny, maxy)
609    };
610
611    // All boundary edges (a, b and every result polygon) for the skip test.
612    let boundary_edges: Vec<(Point, Point)> = std::iter::once(a)
613        .chain(std::iter::once(b))
614        .chain(result)
615        .flat_map(|p| {
616            p.vertices
617                .iter()
618                .enumerate()
619                .map(move |(i, v)| (*v, p.vertices[(i + 1) % p.vertices.len()]))
620        })
621        .collect();
622
623    const N: usize = 32;
624    let w = (maxx - minx).max(f64::MIN_POSITIVE);
625    let h = (maxy - miny).max(f64::MIN_POSITIVE);
626    let mut mismatches = 0usize;
627    let mut checked = 0usize;
628    for ix in 0..=N {
629        for iy in 0..=N {
630            let pt = Point::new(
631                minx + w * (ix as f64) / (N as f64),
632                miny + h * (iy as f64) / (N as f64),
633            );
634            // Skip ambiguously-placed samples near any boundary.
635            let near_boundary = boundary_edges
636                .iter()
637                .any(|&(p, q)| point_segment_dist(pt, p, q) <= bnd_tol);
638            if near_boundary {
639                continue;
640            }
641            checked += 1;
642            let in_a = a.contains_point(pt);
643            let in_b = b.contains_point(pt);
644            let in_res = result.iter().any(|p| p.contains_point(pt));
645            let expected = match op {
646                BoolOp::Intersection => in_a && in_b,
647                BoolOp::Union => in_a || in_b,
648                BoolOp::Difference => in_a && !in_b,
649            };
650            if in_res != expected {
651                mismatches += 1;
652            }
653        }
654    }
655    if mismatches > 0 && checked > 0 {
656        return Err(BooleanError::Validation {
657            op,
658            message: format!(
659                "point-sampling mismatch: {mismatches}/{checked} of the checked samples disagree \
660                     with the expected {:?} of A and B",
661                op
662            ),
663        });
664    }
665    Ok(())
666}
667
668/// Checked boolean operation that verifies the result before returning it.
669///
670/// Runs a cheap, reliable area-bounds reconciliation against per-op invariants
671/// (`intersection <= min`, `union >= max`, `difference in [0, |A|]`), which
672/// catches gross topological errors that the inclusion-exclusion identity alone
673/// cannot. Returns `Err(BooleanError)` instead of a possibly-wrong polygon set,
674/// so a corrupt boolean can never silently propagate into section properties or
675/// FEM.
676///
677/// Note: stronger point-in/polygon *sampling* validation is available via
678/// [`polygon_boolean_sampled_checked`], but is not part of this default gate
679/// because it is incompatible with this module's polygon-level conventions
680/// (nested `Difference` returns the hole-not-cut outer, and `contains_point`
681/// ray-casting can disagree with the kernel's interior interpretation on some
682/// concave inputs).
683pub fn polygon_boolean_checked(
684    a: &Polygon,
685    b: &Polygon,
686    op: BoolOp,
687) -> Result<Vec<Polygon>, BooleanError> {
688    let result = polygon_boolean_internal(a, b, op)?;
689    check_boolean_bounds(&result, a, b, op)?;
690    Ok(result)
691}
692
693/// Convenience wrapper over [`polygon_boolean_checked`] that infallibly returns
694/// the result, panicking if the area-bounds validation fails. Prefer the
695/// checked variant when the error must be recoverable rather than aborting the
696/// process.
697pub fn polygon_boolean(a: &Polygon, b: &Polygon, op: BoolOp) -> Vec<Polygon> {
698    polygon_boolean_checked(a, b, op).expect("polygon boolean failed validation")
699}
700
701/// Explicitly request the point-in/polygon *sampling* validation in addition to
702/// the area-bounds reconciliation.
703///
704/// # Caveats
705/// This is an advisory, stronger check and is **not** suitable as an automatic
706/// gate for the whole pipeline because it can report false mismatches on
707/// legitimate inputs:
708/// - Polygon-level `Difference` of nested polygons returns the outer without
709///   materialising the hole (a documented convention), which disagrees with
710///   point-set `Difference`.
711/// - `Polygon::contains_point` (ray-casting) can disagree with the kernel's
712///   interior interpretation on some concave polygons.
713/// Use it for explicit verification of inputs you expect to be well-behaved
714/// (e.g. convex, non-nested) and treat a mismatch as a strong signal worth
715/// investigating, not a definitive proof of error for the cases above.
716pub fn polygon_boolean_sampled_checked(
717    a: &Polygon,
718    b: &Polygon,
719    op: BoolOp,
720) -> Result<Vec<Polygon>, BooleanError> {
721    let result = polygon_boolean_checked(a, b, op)?;
722    validate_boolean_sampling(&result, a, b, op)?;
723    Ok(result)
724}
725
726fn polygon_boolean_impl(a: &Polygon, b: &Polygon, op: BoolOp) -> Vec<Polygon> {
727    // Fast paths for nesting / disjoint configurations.
728    let a_in_b = a.vertices.iter().all(|v| b.contains_point(*v));
729    let b_in_a = b.vertices.iter().all(|v| a.contains_point(*v));
730
731    match op {
732        BoolOp::Intersection => {
733            if a_in_b {
734                return vec![a.clone()];
735            }
736            if b_in_a {
737                return vec![b.clone()];
738            }
739        }
740        BoolOp::Union => {
741            if a_in_b {
742                return vec![b.clone()];
743            }
744            if b_in_a {
745                return vec![a.clone()];
746            }
747        }
748        BoolOp::Difference => {
749            if a_in_b {
750                return vec![];
751            }
752            if b_in_a {
753                // Hole case: only expressible at Section level with holes.
754                return vec![a.clone()];
755            }
756        }
757    }
758
759    boolean_generic(a, b, op)
760}
761
762/// Greiner–Hormann boolean on two **simple polygons** that always runs the
763/// generic crossing algorithm, without the nesting/disjoint fast paths.
764///
765/// The fast paths in [`polygon_boolean_impl`] defer holes to the Section
766/// level (e.g. `A \ B` with B nested inside A returns `[A]`); this variant is
767/// used when the result must be expressed as explicit polygons (building
768/// material regions and punching holes).
769fn boolean_generic(a: &Polygon, b: &Polygon, op: BoolOp) -> Vec<Polygon> {
770    // For difference, reverse B so intersection semantics apply
771    // (A - B == A intersect reversed-B).
772    let b_eff: Vec<Point> = if op == BoolOp::Difference {
773        b.vertices.iter().rev().copied().collect()
774    } else {
775        b.vertices.clone()
776    };
777
778    let raw = compute_raw_intersections(&a.vertices, &b_eff);
779    if raw.is_empty() {
780        return match op {
781            BoolOp::Intersection => vec![],
782            BoolOp::Union => vec![a.clone(), b.clone()],
783            BoolOp::Difference => vec![a.clone()],
784        };
785    }
786
787    let mut ring_a = build_ring(
788        &a.vertices,
789        &raw.iter()
790            .enumerate()
791            .map(|(id, r)| (r.ea, r.ta, id))
792            .collect::<Vec<_>>(),
793        &raw,
794    );
795    let mut ring_b = build_ring(
796        &b_eff,
797        &raw.iter()
798            .enumerate()
799            .map(|(id, r)| (r.eb, r.tb, id))
800            .collect::<Vec<_>>(),
801        &raw,
802    );
803
804    // Pair up intersection nodes across rings by shared id.
805    use std::collections::HashMap;
806    let mut pair_to_b: HashMap<usize, usize> = HashMap::new();
807    for (i, nd) in ring_b.nodes.iter().enumerate() {
808        if nd.is_inter {
809            pair_to_b.insert(nd.pair, i);
810        }
811    }
812    let mut pair_to_a: HashMap<usize, usize> = HashMap::new();
813    for (i, nd) in ring_a.nodes.iter().enumerate() {
814        if nd.is_inter {
815            pair_to_a.insert(nd.pair, i);
816        }
817    }
818    for (&pid, &ja) in &pair_to_a {
819        if let Some(&jb) = pair_to_b.get(&pid) {
820            ring_a.nodes[ja].neighbor = jb;
821            ring_b.nodes[jb].neighbor = ja;
822        }
823    }
824
825    assign_entries(&mut ring_a, b.contains_point(a.vertices[0]));
826    assign_entries(&mut ring_b, a.contains_point(b_eff[0]));
827
828    let mut results = Vec::new();
829    let starts: Vec<usize> = ring_a
830        .nodes
831        .iter()
832        .enumerate()
833        .filter(|(_, n)| n.is_inter)
834        .map(|(i, _)| i)
835        .collect();
836    for i in starts {
837        if !ring_a.nodes[i].processed {
838            let pts = trace_loop(&mut ring_a, &mut ring_b, i, op);
839            if pts.len() >= 3 && signed_area_pts(&pts).abs() > 1e-15 {
840                results.push(Polygon::new(pts));
841            }
842        }
843    }
844    results
845}
846
847/// Compute the material of `s` that lies inside `p`, expressed as a list of
848/// polygons `p ∩ material(s)`.
849///
850/// Because `material(s) = outer \ holes`, this is `p ∩ outer` with each hole
851/// cut out. Each operation used here (`intersection` and `difference`) acts on
852/// simple polygons and, crucially, never needs to represent a polygon-with-a-
853/// nested-hole, so the results are always plain regions.
854fn material_inside(p: &Polygon, s: &crate::section::Section) -> Result<Vec<Polygon>, BooleanError> {
855    // p ∩ outer
856    let mut acc = polygon_boolean_checked(p, &s.outer, BoolOp::Intersection)?;
857    // subtract every hole (in CCW orientation, as the boolean expects)
858    for h in &s.holes {
859        let h_ccw = ccw(h);
860        let mut next = Vec::new();
861        for r in acc.iter() {
862            next.extend(polygon_boolean_checked(r, &h_ccw, BoolOp::Difference)?);
863        }
864        acc = next;
865        if acc.is_empty() {
866            break;
867        }
868    }
869    Ok(acc.into_iter().filter(|r| r.area().abs() > 1e-15).collect())
870}
871
872/// Return a counter-clockwise (positive-area) copy of a polygon. Holes are
873/// stored clockwise by [`Section`](crate::section::Section), but the boolean
874/// routines operate on CCW outer polygons.
875fn ccw(p: &Polygon) -> Polygon {
876    if p.signed_area() >= 0.0 {
877        p.clone()
878    } else {
879        Polygon::new(p.vertices.iter().rev().copied().collect())
880    }
881}
882
883/// The part of `hole` that is **not** covered by the material of the section
884/// represented by `(outer, holes)`; i.e. `hole \ material`. These regions are
885/// the "void" left by a hole of one section that is not filled by the other
886/// section's material.
887fn hole_minus_material(
888    hole: &Polygon,
889    outer: &Polygon,
890    holes: &[Polygon],
891) -> Result<Vec<Polygon>, BooleanError> {
892    // hole \ material = (hole \ outer) ∪ (hole ∩ each hole)
893    let hole = ccw(hole);
894    let mut res = Vec::new();
895    res.extend(polygon_boolean_checked(&hole, outer, BoolOp::Difference)?);
896    for oh in holes {
897        res.extend(polygon_boolean_checked(
898            &hole,
899            &ccw(oh),
900            BoolOp::Intersection,
901        )?);
902    }
903    Ok(res)
904}
905
906/// Merge a collection of void polygons (already clipped to a piece) into a
907/// minimal set of pairwise-disjoint simple polygons.
908///
909/// Two holes belonging to different sections may overlap after clipping (e.g.
910/// A.hole and B.hole on an Intersection). If they were attached as-is,
911/// `Section::area()` would subtract the overlapping region twice. Unioning
912/// overlapping members folds them into one polygon so every region is counted
913/// exactly once. Members that merely touch (share an edge) are already
914/// disjoint for area purposes and are left separate.
915pub fn union_voids(regions: &mut Vec<Polygon>) -> Result<(), BooleanError> {
916    let mut i = 0;
917    while i < regions.len() {
918        let mut j = i + 1;
919        let mut merged = false;
920        while j < regions.len() {
921            let u = polygon_boolean_checked(&regions[i], &regions[j], BoolOp::Union)?;
922            if u.len() == 1 {
923                // The two regions overlap (or are nested) and fold into one.
924                regions[i] = u.into_iter().next().unwrap();
925                regions.swap_remove(j);
926                merged = true;
927                break;
928            }
929            j += 1;
930        }
931        if !merged {
932            i += 1;
933        }
934    }
935    Ok(())
936}
937
938/// Compute the holes that survive inside the outer-boundary piece `p` when
939/// `a` and `b` are combined by `op`. The voids are regions inside `p` where
940/// the result has no material, expressed as plain simple polygons.
941///
942/// - **Union**: material exists where *either* section has material, so a hole
943///   of one section remains a hole only where the other section does not fill
944///   it (`hole \ material(other)`).
945/// - **Intersection**: material exists where *both* sections have material, so
946///   every hole of either section that lies inside the piece is a void.
947/// - **Difference**: material is `material(A) \ material(B)`, so the voids are
948///   A's holes (inside the piece) plus any of B's material inside the piece.
949///   For pieces from `A.outer ∩ B.holes` (B's hole regions), B has no material
950///   there, so voids are only A's holes clipped to the piece.
951///
952/// Candidate voids are clipped to `p`, unioned so that overlapping holes are
953/// not double-counted, and tiny/sliver regions dropped.
954fn holes_for_piece(
955    p: &Polygon,
956    a: &crate::section::Section,
957    b: &crate::section::Section,
958    op: BoolOp,
959    kind: PieceKind,
960) -> Result<Vec<Polygon>, BooleanError> {
961    let mut void_regions: Vec<Polygon> = Vec::new();
962
963    match op {
964        BoolOp::Union => {
965            // A's holes that B does not fill, plus B's holes that A does not fill.
966            for h in a.holes.iter() {
967                void_regions.extend(hole_minus_material(h, &b.outer, &b.holes)?);
968            }
969            for h in b.holes.iter() {
970                void_regions.extend(hole_minus_material(h, &a.outer, &a.holes)?);
971            }
972        }
973        BoolOp::Intersection => {
974            // Every hole of either section inside the piece is a void.
975            void_regions.extend(a.holes.iter().cloned());
976            void_regions.extend(b.holes.iter().cloned());
977        }
978        BoolOp::Difference => {
979            match kind {
980                PieceKind::Normal => {
981                    // Standard outer difference: A.outer \ B.outer
982                    // Voids = A's holes (minus B's material) + B's material inside piece
983                    for h in a.holes.iter() {
984                        void_regions.extend(hole_minus_material(h, &b.outer, &b.holes)?);
985                    }
986                    void_regions.extend(material_inside(p, b)?);
987                }
988                PieceKind::InHole => {
989                    // A's material inside B's hole: B has no material here
990                    // Voids = only A's holes clipped to piece (no B material subtraction)
991                    for h in a.holes.iter() {
992                        void_regions.extend(polygon_boolean_checked(h, p, BoolOp::Intersection)?);
993                    }
994                }
995            }
996        }
997    }
998
999    // Clip every candidate void to the piece boundary so that no hole ever
1000    // extends outside `p`. A hole of one section that spans the intersection or
1001    // difference cut line is trimmed to `hole ∩ p`, not kept whole.
1002    let mut clipped = Vec::new();
1003    for r in void_regions {
1004        clipped.extend(polygon_boolean_checked(p, &ccw(&r), BoolOp::Intersection)?);
1005    }
1006    void_regions = clipped;
1007
1008    // Merge overlapping voids so overlapping holes are not double-counted by
1009    // Section::area(). Members that only touch remain separate (already
1010    // disjoint for area purposes).
1011    union_voids(&mut void_regions)?;
1012
1013    // Keep only regions inside `p` that carry meaningful area. Any tiny region
1014    // that touches `p`'s boundary is an exterior sliver, not a hole, so it is
1015    // dropped. Vertices may overhang `p`'s boundary by a tiny amount due to the
1016    // boolean perturbation, so allow a small coordinate tolerance rather than a
1017    // strict point-in-polygon test (which would break legitimate boundary holes).
1018    //
1019    // The perturbation can also fabricate phantom voids (area ~eps * scale
1020    // with eps=1e-8*diag) where two holes merely touch, so the area threshold
1021    // must exceed that scale to drop them while keeping genuine holes.
1022    let scale = bbox_diag(&p.vertices);
1023    // Relative tolerance (1e-9 * piece_area) plus absolute tolerance based on
1024    // perturbation-induced phantom void area (~eps * scale with eps=1e-8*diag).
1025    let area_tol = 1e-9 * p.area().abs().max(1e-12) + 1e-8 * scale * scale;
1026    let coord_tol = 1e-7 * scale;
1027    let edge_pairs: Vec<(Point, Point)> = p
1028        .vertices
1029        .iter()
1030        .enumerate()
1031        .map(|(i, v)| (*v, p.vertices[(i + 1) % p.vertices.len()]))
1032        .collect();
1033    Ok(void_regions
1034        .into_iter()
1035        .filter(|r| {
1036            if r.area().abs() <= area_tol {
1037                return false;
1038            }
1039            r.vertices.iter().all(|&v| {
1040                if p.contains_point(v) {
1041                    return true;
1042                }
1043                edge_pairs
1044                    .iter()
1045                    .any(|&(a, b)| point_segment_dist(v, a, b) <= coord_tol)
1046            })
1047        })
1048        .collect())
1049}
1050
1051/// Core boolean on two full sections (outer boundary + holes) that unifies
1052/// hole handling across all three operations.
1053///
1054/// The outer boundaries are combined with [`polygon_boolean`], then each
1055/// resulting region has its surviving holes re-attached with
1056/// [`holes_for_piece`].
1057///
1058/// Returns one [`Section`] per disjoint result region.
1059fn section_boolean(
1060    a: &crate::section::Section,
1061    b: &crate::section::Section,
1062    op: BoolOp,
1063) -> Result<Vec<crate::section::Section>, BooleanError> {
1064    use crate::section::Section;
1065
1066    if op == BoolOp::Difference {
1067        return section_difference_impl(a, b);
1068    }
1069
1070    let pieces = polygon_boolean_checked(&a.outer, &b.outer, op)?;
1071    let mut out = Vec::new();
1072    for p in pieces {
1073        let holes = holes_for_piece(&p, a, b, op, PieceKind::Normal)?;
1074        let s = Section::new(p, holes);
1075        if s.area() > 0.0 {
1076            out.push(s);
1077        }
1078    }
1079    Ok(out)
1080}
1081
1082/// Difference pieces have two kinds:
1083/// - `Normal`: from `A.outer \ B.outer` (standard outer difference)
1084/// - `InHole`: from `A.outer ∩ B.holes[i]` (A's material inside B's holes)
1085#[derive(Clone, Copy, Debug, PartialEq, Eq)]
1086enum PieceKind {
1087    Normal,
1088    InHole,
1089}
1090
1091/// Difference of two sections with proper hole handling.
1092///
1093/// Material = material(A) \ material(B) = (A.outer \ A.holes) \ (B.outer \ B.holes)
1094/// = (A.outer \ B.outer) ∪ (A.outer ∩ B.holes) minus holes appropriately.
1095fn section_difference_impl(
1096    a: &crate::section::Section,
1097    b: &crate::section::Section,
1098) -> Result<Vec<crate::section::Section>, BooleanError> {
1099    use crate::section::Section;
1100
1101    // 1. Standard outer difference: A.outer \ B.outer
1102    let outer_diff = polygon_boolean_checked(&a.outer, &b.outer, BoolOp::Difference)?;
1103
1104    // 2. Parts of A that fall inside B's holes (B has no material there, so A survives)
1105    let mut hole_intersections = Vec::new();
1106    for bh in &b.holes {
1107        hole_intersections.extend(polygon_boolean_checked(&a.outer, bh, BoolOp::Intersection)?);
1108    }
1109
1110    // Combine all pieces with their kind
1111    let mut pieces = Vec::new();
1112    for p in outer_diff {
1113        pieces.push((p, PieceKind::Normal));
1114    }
1115    for p in hole_intersections {
1116        pieces.push((p, PieceKind::InHole));
1117    }
1118
1119    let mut out = Vec::new();
1120    for (p, kind) in pieces {
1121        let holes = holes_for_piece(&p, a, b, BoolOp::Difference, kind)?;
1122        let s = Section::new(p, holes);
1123        if s.area() > 0.0 {
1124            out.push(s);
1125        }
1126    }
1127    Ok(out)
1128}
1129
1130/// Boolean intersection between two full sections (outer boundary + holes).
1131///
1132/// Mirrors shapely `geometry & other` as used by Python `sectionproperties`.
1133///
1134/// Returns one [`Section`](crate::section::Section) per disjoint result region, or
1135/// [`BooleanError`] if the underlying polygon booleans fail validation.
1136pub fn section_intersection(
1137    a: &crate::section::Section,
1138    b: &crate::section::Section,
1139) -> Result<Vec<crate::section::Section>, BooleanError> {
1140    section_boolean(a, b, BoolOp::Intersection)
1141}
1142
1143/// Boolean difference between two full sections (outer boundary + holes).
1144///
1145/// Mirrors shapely `geometry - other` as used by Python `sectionproperties`.
1146///
1147/// Returns one [`Section`](crate::section::Section) per disjoint result region, or
1148/// [`BooleanError`] if the underlying polygon booleans fail validation.
1149pub fn section_difference(
1150    a: &crate::section::Section,
1151    b: &crate::section::Section,
1152) -> Result<Vec<crate::section::Section>, BooleanError> {
1153    section_boolean(a, b, BoolOp::Difference)
1154}
1155
1156/// Boolean union between two full sections (outer boundary + holes).
1157///
1158/// Mirrors shapely `geometry | other` as used by Python `sectionproperties`.
1159///
1160/// Returns one [`Section`](crate::section::Section) per disjoint result region, or
1161/// [`BooleanError`] if the underlying polygon booleans fail validation.
1162pub fn section_union(
1163    a: &crate::section::Section,
1164    b: &crate::section::Section,
1165) -> Result<Vec<crate::section::Section>, BooleanError> {
1166    section_boolean(a, b, BoolOp::Union)
1167}
1168
1169#[cfg(test)]
1170mod tests {
1171    use super::*;
1172
1173    fn square(x0: f64, y0: f64, size: f64) -> Polygon {
1174        Polygon::new(vec![
1175            Point::new(x0, y0),
1176            Point::new(x0 + size, y0),
1177            Point::new(x0 + size, y0 + size),
1178            Point::new(x0, y0 + size),
1179        ])
1180    }
1181
1182    /// Assert that every hole vertex is strictly inside `piece`, or within a
1183    /// tiny coordinate tolerance of its boundary (to absorb the boolean
1184    /// perturbation that may push an on-boundary vertex an epsilon outside).
1185    fn assert_holes_within_piece(piece: &Polygon, holes: &[Polygon]) {
1186        let diag = bbox_diag(&piece.vertices);
1187        let tol = 1e-7 * diag;
1188        for h in holes {
1189            for v in &h.vertices {
1190                let on_boundary = piece.vertices.iter().enumerate().any(|(i, a)| {
1191                    let b = piece.vertices[(i + 1) % piece.vertices.len()];
1192                    point_segment_dist(*v, *a, b) <= tol
1193                });
1194                assert!(
1195                    piece.contains_point(*v) || on_boundary,
1196                    "hole must not extend outside the piece"
1197                );
1198            }
1199        }
1200    }
1201
1202    #[test]
1203    fn intersection_of_overlapping_squares() {
1204        let a = square(0.0, 0.0, 2.0);
1205        let b = square(1.0, 1.0, 2.0);
1206        let r = polygon_boolean(&a, &b, BoolOp::Intersection);
1207        assert_eq!(r.len(), 1);
1208        assert!((r[0].area() - 1.0).abs() < 1e-9);
1209    }
1210
1211    #[test]
1212    fn union_area_subtracts_overlap() {
1213        let a = square(0.0, 0.0, 2.0);
1214        let b = square(1.0, 1.0, 2.0);
1215        let r = polygon_boolean(&a, &b, BoolOp::Union);
1216        assert_eq!(r.len(), 1);
1217        assert!((r[0].area() - 7.0).abs() < 1e-9);
1218    }
1219
1220    #[test]
1221    fn difference_removes_overlap() {
1222        let a = square(0.0, 0.0, 2.0);
1223        let b = square(1.0, 1.0, 2.0);
1224        let r = polygon_boolean(&a, &b, BoolOp::Difference);
1225        assert_eq!(r.len(), 1);
1226        assert!((r[0].area() - 3.0).abs() < 1e-9);
1227    }
1228
1229    #[test]
1230    fn disjoint_polygons() {
1231        let a = square(0.0, 0.0, 1.0);
1232        let b = square(5.0, 5.0, 1.0);
1233        assert!(polygon_boolean(&a, &b, BoolOp::Intersection).is_empty());
1234        assert_eq!(polygon_boolean(&a, &b, BoolOp::Union).len(), 2);
1235        let d = polygon_boolean(&a, &b, BoolOp::Difference);
1236        assert_eq!(d.len(), 1);
1237        assert!((d[0].area() - 1.0).abs() < 1e-12);
1238    }
1239
1240    #[test]
1241    fn contained_polygons() {
1242        let outer = square(0.0, 0.0, 3.0);
1243        let inner = square(1.0, 1.0, 1.0);
1244
1245        let i = polygon_boolean(&inner, &outer, BoolOp::Intersection);
1246        assert_eq!(i.len(), 1);
1247        assert!((i[0].area() - 1.0).abs() < 1e-12);
1248
1249        let u = polygon_boolean(&inner, &outer, BoolOp::Union);
1250        assert_eq!(u.len(), 1);
1251        assert!((u[0].area() - 9.0).abs() < 1e-12);
1252
1253        let d = polygon_boolean(&outer, &inner, BoolOp::Difference);
1254        // boundary-level: hole case returns the full outer polygon
1255        assert_eq!(d.len(), 1);
1256        assert!((d[0].area() - 9.0).abs() < 1e-12);
1257    }
1258
1259    #[test]
1260    fn section_difference_creates_hole() {
1261        use crate::section::Section;
1262        let outer = square(0.0, 0.0, 4.0);
1263        let a = Section::new(outer, vec![]);
1264        let b = Section::new(square(1.0, 1.0, 2.0), vec![]);
1265
1266        let result = section_difference(&a, &b).unwrap();
1267        assert_eq!(result.len(), 1);
1268        assert_eq!(result[0].holes.len(), 1);
1269        assert!((result[0].area() - (16.0 - 4.0)).abs() < 1e-9);
1270        assert!((result[0].centroid().x - 2.0).abs() < 1e-12);
1271
1272        // Properties must account for the hole.
1273        let props = crate::section_properties::SectionProperties::from_section(&result[0]);
1274        let expected_ix = 4.0 * 4.0_f64.powi(3) / 12.0 - 2.0 * 2.0_f64.powi(3) / 12.0;
1275        assert!((props.ix - expected_ix).abs() / expected_ix < 1e-10);
1276    }
1277
1278    #[test]
1279    fn section_difference_partial_overlap_no_hole() {
1280        use crate::section::Section;
1281        let a = Section::new(square(0.0, 0.0, 2.0), vec![]);
1282        let b = Section::new(square(1.0, 1.0, 2.0), vec![]);
1283        let result = section_difference(&a, &b).unwrap();
1284        assert_eq!(result.len(), 1);
1285        assert_eq!(result[0].holes.len(), 0);
1286        assert!((result[0].area() - 3.0).abs() < 1e-9);
1287    }
1288
1289    #[test]
1290    fn section_difference_with_existing_holes() {
1291        use crate::section::Section;
1292        // Square with existing hole, minus an offset square.
1293        let a = Section::new(square(0.0, 0.0, 4.0), vec![square(0.5, 0.5, 1.0)]);
1294        let b = Section::new(square(2.5, 2.5, 1.0), vec![]);
1295        let result = section_difference(&a, &b).unwrap();
1296        assert_eq!(result.len(), 1);
1297        // Interior subtraction becomes a second hole.
1298        assert_eq!(result[0].holes.len(), 2);
1299        assert!((result[0].area() - (16.0 - 1.0 - 1.0)).abs() < 1e-9);
1300    }
1301    #[test]
1302    fn identical_polygons() {
1303        let a = square(0.0, 0.0, 2.0);
1304        assert_eq!(
1305            polygon_boolean(&a, &a.clone(), BoolOp::Intersection)[0].area(),
1306            4.0
1307        );
1308        assert_eq!(
1309            polygon_boolean(&a, &a.clone(), BoolOp::Union)[0].area(),
1310            4.0
1311        );
1312        assert!(polygon_boolean(&a, &a.clone(), BoolOp::Difference).is_empty());
1313    }
1314
1315    #[test]
1316    fn section_union_preserves_holes() {
1317        use crate::section::Section;
1318        // Two overlapping squares, each with a hole in its non-overlapped
1319        // region. The union merges into one piece and keeps both holes.
1320        let hole_a = square(0.2, 0.3, 0.3);
1321        let a = Section::new(square(0.0, 0.0, 1.2), vec![hole_a]);
1322        let hole_b = square(1.5, 0.3, 0.3);
1323        let b = Section::new(square(1.0, 0.0, 1.2), vec![hole_b]);
1324
1325        let result = section_union(&a, &b).unwrap();
1326        assert_eq!(result.len(), 1, "overlapping squares merge into one piece");
1327        assert_eq!(result[0].holes.len(), 2, "union must preserve both holes");
1328        // Material a (1.44-0.09) + material b (1.44-0.09) - overlap [1.0,1.2]x[0,1.2] (0.24).
1329        let expected = (1.44 - 0.09) + (1.44 - 0.09) - 0.24;
1330        assert!(
1331            (result[0].area() - expected).abs() < 1e-6,
1332            "union area {}",
1333            result[0].area()
1334        );
1335    }
1336
1337    #[test]
1338    fn section_union_drops_hole_filled_by_other() {
1339        use crate::section::Section;
1340        // A with a hole; B is a solid square exactly filling that hole.
1341        // Union must fill the hole (B's material occupies it).
1342        let hole = square(0.5, 0.5, 1.0);
1343        let a = Section::new(square(0.0, 0.0, 2.0), vec![hole]);
1344        let b = Section::new(square(0.5, 0.5, 1.0), vec![]);
1345
1346        let result = section_union(&a, &b).unwrap();
1347        assert_eq!(result.len(), 1);
1348        // The hole is filled by B -> union is the full 2x2 square, no border hole.
1349        assert_eq!(
1350            result[0].holes.len(),
1351            0,
1352            "filled hole must disappear: {:?}",
1353            result[0].holes.len()
1354        );
1355        assert!(
1356            (result[0].area() - 4.0).abs() < 1e-9,
1357            "union area {}",
1358            result[0].area()
1359        );
1360    }
1361
1362    #[test]
1363    fn section_intersection_preserves_holes() {
1364        use crate::section::Section;
1365        // Two fully overlapping squares, each with its own hole. Intersection
1366        // is material where BOTH have material, so both holes are voids.
1367        let hole_a = square(0.5, 0.5, 0.5);
1368        let a = Section::new(square(0.0, 0.0, 2.0), vec![hole_a]);
1369        let hole_b = square(1.0, 1.0, 0.5);
1370        let b = Section::new(square(0.0, 0.0, 2.0), vec![hole_b]);
1371
1372        let result = section_intersection(&a, &b).unwrap();
1373        assert_eq!(result.len(), 1);
1374        assert_eq!(result[0].holes.len(), 2, "intersection keeps both holes");
1375    }
1376
1377    #[test]
1378    fn section_intersection_clips_holes_to_piece() {
1379        use crate::section::Section;
1380        // A = 4x4 with a 2x2 hole ([1,3]^2). B = 1.5x4 strip along the left
1381        // edge with its own 0.5x2 hole. The intersection piece is only
1382        // [0,1.5]x[0,4], so neither full hole fits: each must be clipped to
1383        // hole ∩ piece.
1384        let hole_a = square(1.0, 1.0, 2.0); // [1,3]^2
1385        let a = Section::new(square(0.0, 0.0, 4.0), vec![hole_a]);
1386        let b_outer = Polygon::new(vec![
1387            Point::new(0.0, 0.0),
1388            Point::new(1.5, 0.0),
1389            Point::new(1.5, 4.0),
1390            Point::new(0.0, 4.0),
1391        ]);
1392        let hole_b = Polygon::new(vec![
1393            Point::new(0.5, 1.0),
1394            Point::new(1.0, 1.0),
1395            Point::new(1.0, 3.0),
1396            Point::new(0.5, 3.0),
1397        ]); // [0.5,1.0]x[1.0,3.0], area 1
1398        let b = Section::new(b_outer, vec![hole_b]);
1399
1400        let result = section_intersection(&a, &b).unwrap();
1401        assert_eq!(result.len(), 1);
1402        let sec = &result[0];
1403        // Piece = [0,1.5]x[0,4], area 6.
1404        assert!(
1405            (sec.outer.area() - 6.0).abs() < 1e-6,
1406            "piece area {}",
1407            sec.outer.area()
1408        );
1409        // A's hole clipped to [1,1.5]x[1,3] (0.5x2) and B's hole [0.5,1.0]x[1,3]
1410        // (already inside the piece). Total void = 1 + 1 = 2.
1411        let hole_area: f64 = sec.holes.iter().map(|h| h.area()).sum();
1412        assert!(
1413            (hole_area - 2.0).abs() < 1e-4,
1414            "clipped holes total area {}",
1415            hole_area
1416        );
1417        assert_holes_within_piece(&sec.outer, &sec.holes);
1418        // Net material = 6 - 2 = 4.
1419        assert!(
1420            (sec.area() - 4.0).abs() < 1e-4,
1421            "section area {}",
1422            sec.area()
1423        );
1424    }
1425
1426    #[test]
1427    fn section_intersection_unions_overlapping_holes() {
1428        use crate::section::Section;
1429        // A = 4x4 with hole [1,3]x[1,3]. B = 4x4 (same outer) with hole
1430        // [2,4]x[1,3]. The two holes overlap in [2,3]x[1,3]. The intersection
1431        // piece is the full 4x4 and both holes are voids, but the overlap must
1432        // not be subtracted twice: the final hole set is their union
1433        // ([1,4]x[1,3], area 6), not 4 + 4 = 8.
1434        let hole_a = square(1.0, 1.0, 2.0); // [1,3]^2, area 4
1435        let a = Section::new(square(0.0, 0.0, 4.0), vec![hole_a]);
1436        let hole_b = square(2.0, 1.0, 2.0); // [2,4]x[1,3], area 4
1437        let b = Section::new(square(0.0, 0.0, 4.0), vec![hole_b]);
1438
1439        let result = section_intersection(&a, &b).unwrap();
1440        assert_eq!(result.len(), 1);
1441        let sec = &result[0];
1442        assert!(
1443            (sec.outer.area() - 16.0).abs() < 1e-6,
1444            "piece area {}",
1445            sec.outer.area()
1446        );
1447        // Overlapping holes must fold into a single void of area 6.
1448        assert_eq!(
1449            sec.holes.len(),
1450            1,
1451            "overlapping holes must merge: {}",
1452            sec.holes.len()
1453        );
1454        let hole_area = sec.holes[0].area();
1455        assert!(
1456            (hole_area - 6.0).abs() < 1e-4,
1457            "merged hole area {}",
1458            hole_area
1459        );
1460        // The merged hole must lie within the piece (allowing perturbation tol).
1461        assert_holes_within_piece(&sec.outer, &sec.holes);
1462        // Net material = 16 - 6 = 10 (overlap counted once).
1463        assert!(
1464            (sec.area() - 10.0).abs() < 1e-4,
1465            "section area {}",
1466            sec.area()
1467        );
1468    }
1469
1470    #[test]
1471    fn section_intersection_clips_hole_to_piece() {
1472        use crate::section::Section;
1473        // A = 10x10 with an 8x8 hole ([1,9]^2). B = 2x10 strip along the left
1474        // edge ([0,2]x[0,10]). The intersection piece is only 2 wide, so the
1475        // full 8x8 hole cannot fit inside it -- it must be clipped.
1476        let hole = square(1.0, 1.0, 8.0); // [1,9]^2
1477        let a = Section::new(square(0.0, 0.0, 10.0), vec![hole]);
1478        let b_outer = Polygon::new(vec![
1479            Point::new(0.0, 0.0),
1480            Point::new(2.0, 0.0),
1481            Point::new(2.0, 10.0),
1482            Point::new(0.0, 10.0),
1483        ]);
1484        let b = Section::new(b_outer, vec![]);
1485
1486        let result = section_intersection(&a, &b).unwrap();
1487        assert_eq!(result.len(), 1);
1488        let sec = &result[0];
1489        // Piece = [0,2]x[0,10], area 20.
1490        assert!(
1491            (sec.outer.area() - 20.0).abs() < 1e-6,
1492            "piece area {}",
1493            sec.outer.area()
1494        );
1495        // Hole clipped to [1,2]x[1,9], area 8, and it must lie inside the piece.
1496        let hole_area: f64 = sec.holes.iter().map(|h| h.area()).sum();
1497        assert!(
1498            (hole_area - 8.0).abs() < 1e-4,
1499            "clipped hole area {}",
1500            hole_area
1501        );
1502        assert_holes_within_piece(&sec.outer, &sec.holes);
1503        // Net material = 20 - 8 = 12 (and not negative).
1504        assert!(
1505            (sec.area() - 12.0).abs() < 1e-4,
1506            "section area {}",
1507            sec.area()
1508        );
1509    }
1510
1511    #[test]
1512    fn section_difference_clips_hole_to_piece() {
1513        use crate::section::Section;
1514        // A = 10x10 with an 8x8 hole ([1,9]^2). B = 5x10 strip along the left
1515        // edge ([0,5]x[0,10]). The difference piece is [5,10]x[0,10], so only
1516        // the part of A's hole inside it ([5,9]x[1,9]) survives, clipped.
1517        let hole = square(1.0, 1.0, 8.0); // [1,9]^2
1518        let a = Section::new(square(0.0, 0.0, 10.0), vec![hole]);
1519        let b_outer = Polygon::new(vec![
1520            Point::new(0.0, 0.0),
1521            Point::new(5.0, 0.0),
1522            Point::new(5.0, 10.0),
1523            Point::new(0.0, 10.0),
1524        ]);
1525        let b = Section::new(b_outer, vec![]);
1526
1527        let result = section_difference(&a, &b).unwrap();
1528        assert_eq!(result.len(), 1);
1529        let sec = &result[0];
1530        // Piece = [5,10]x[0,10], area 50.
1531        assert!(
1532            (sec.outer.area() - 50.0).abs() < 1e-6,
1533            "piece area {}",
1534            sec.outer.area()
1535        );
1536        // Hole clipped to [5,9]x[1,9], area 32, inside the piece.
1537        let hole_area: f64 = sec.holes.iter().map(|h| h.area()).sum();
1538        assert!(
1539            (hole_area - 32.0).abs() < 1e-4,
1540            "clipped hole area {}",
1541            hole_area
1542        );
1543        assert_holes_within_piece(&sec.outer, &sec.holes);
1544        // Net material = 50 - 32 = 18.
1545        assert!(
1546            (sec.area() - 18.0).abs() < 1e-4,
1547            "section area {}",
1548            sec.area()
1549        );
1550    }
1551
1552    #[test]
1553    fn section_union_clips_hole_partially_filled() {
1554        use crate::section::Section;
1555        // A = 2x2 with a centred 1x1 hole. B = solid rectangle filling the
1556        // bottom-right quarter of that hole. The union keeps the hole minus the
1557        // filled part (area 0.75) and drops the corner covered by B.
1558        let hole = square(0.5, 0.5, 1.0); // [0.5,1.5]^2
1559        let a = Section::new(square(0.0, 0.0, 2.0), vec![hole]);
1560        let b = Section::new(square(1.0, 0.5, 0.5), vec![]); // [1.0,1.5]x[0.5,1.0]
1561
1562        let result = section_union(&a, &b).unwrap();
1563        assert_eq!(result.len(), 1);
1564        let sec = &result[0];
1565        let hole_area: f64 = sec.holes.iter().map(|h| h.area()).sum();
1566        // Surviving void = hole (area 1) minus B's filled part (area 0.25) = 0.75.
1567        assert!(
1568            (hole_area - 0.75).abs() < 1e-3,
1569            "partially filled hole area: {}",
1570            hole_area
1571        );
1572        // Union outer is the full 2x2; material = 4 - 0.75 = 3.25.
1573        assert!(
1574            (sec.area() - 3.25).abs() < 1e-3,
1575            "union area {}",
1576            sec.area()
1577        );
1578    }
1579
1580    #[test]
1581    fn shared_edge_squares_union_area() {
1582        // Two unit squares sharing the edge x = 1 exactly.
1583        let a = square(0.0, 0.0, 1.0);
1584        let b = square(1.0, 0.0, 1.0);
1585        let u = polygon_boolean(&a, &b, BoolOp::Union);
1586        let total: f64 = u.iter().map(|p| p.area()).sum();
1587        assert!((total - 2.0).abs() < 1e-9);
1588        assert!(polygon_boolean(&a, &b, BoolOp::Intersection).is_empty());
1589        let d = polygon_boolean(&a, &b, BoolOp::Difference);
1590        assert!((d[0].area() - 1.0).abs() < 1e-9);
1591    }
1592
1593    #[test]
1594    fn vertex_on_edge_case_satisfies_area_identity() {
1595        // Triangle apex (1,0) lies exactly on A's bottom edge.
1596        let a = square(0.0, 0.0, 2.0);
1597        let b = Polygon::new(vec![
1598            Point::new(1.0, 0.0),
1599            Point::new(3.0, 1.0),
1600            Point::new(1.0, 2.0),
1601        ]);
1602        let area_a = a.area();
1603        let area_b = b.area();
1604
1605        let i = polygon_boolean(&a, &b, BoolOp::Intersection);
1606        let inter: f64 = i.iter().map(|p| p.area()).sum();
1607        let u = polygon_boolean(&a, &b, BoolOp::Union);
1608        let uni: f64 = u.iter().map(|p| p.area()).sum();
1609        let d = polygon_boolean(&a, &b, BoolOp::Difference);
1610        let diff: f64 = d.iter().map(|p| p.area()).sum();
1611
1612        // Inclusion-exclusion identity must hold (within jitter tolerance).
1613        assert!(
1614            (area_a + area_b - inter - uni).abs() < 1e-3,
1615            "union identity: {} + {} - {} != {}",
1616            area_a,
1617            area_b,
1618            inter,
1619            uni
1620        );
1621        assert!((area_a - inter - diff).abs() < 1e-3, "difference identity");
1622        assert!(inter > 0.0 && inter < area_b.min(area_a));
1623    }
1624
1625    #[test]
1626    fn perturbation_result_is_mapped_back_to_original_frame() {
1627        // Regression for P0b: when the boolean engine perturbs `b` to resolve a
1628        // vertex-on-boundary degeneracy, the returned geometry must be mapped
1629        // back onto the *original* coordinate frame (vertices reduced by
1630        // `-eps * direction`). Otherwise B-originated vertices retain the
1631        // artificial `~eps` offset, which corrupts higher-order section
1632        // properties (centroid, moments, principal axes).
1633        //
1634        // Two unit squares that share exactly one corner: A=[0,1]^2, B=[1,2]^2
1635        // touch at (1,1). The corner (1,1) lies on A's boundary, so the
1636        // perturbation path is taken. A and B share no edges and do not cross,
1637        // so the union has NO computed crossing points — every vertex is an
1638        // original polygon vertex and must be restored to its exact position.
1639        let a = square(0.0, 0.0, 1.0);
1640        let b = square(1.0, 1.0, 1.0);
1641
1642        let u = polygon_boolean(&a, &b, BoolOp::Union);
1643        let total: f64 = u.iter().map(|p| p.area()).sum();
1644        assert!((total - 2.0).abs() < 1e-9, "union area: {}", total);
1645
1646        // B's far corner (2,2) is a pure B vertex. Without map-back it would
1647        // sit at (2 + eps*dx, 2 + eps*dy); with map-back it is restored to
1648        // exactly (2,2) up to floating-point roundoff.
1649        let found = u
1650            .iter()
1651            .flat_map(|p| &p.vertices)
1652            .any(|v| (v.x - 2.0).abs() < 1e-12 && (v.y - 2.0).abs() < 1e-12);
1653        assert!(
1654            found,
1655            "B-originated vertex (2,2) not at its original position after \
1656             perturbation; back-mapping missing?"
1657        );
1658
1659        // The shared-corner point must also be exactly restored (it is emitted
1660        // as an A vertex and, if not merged, as a duplicate B vertex).
1661        let found_corner = u
1662            .iter()
1663            .flat_map(|p| &p.vertices)
1664            .any(|v| (v.x - 1.0).abs() < 1e-12 && (v.y - 1.0).abs() < 1e-12);
1665        assert!(
1666            found_corner,
1667            "shared corner (1,1) not restored after perturbation"
1668        );
1669    }
1670
1671    #[test]
1672    fn bounds_validation_rejects_bloated_union() {
1673        // Regression for the "identity alone is not sufficient" case: two
1674        // area-100 polygons could yield |A∩B|=30 and |A∪B|=170 with
1675        // 30+170=100+100 (identity passes) even though the union clearly
1676        // violates |A∪B| >= max(|A|,|B|). The area-bounds gate must reject it.
1677        let a = square(0.0, 0.0, 10.0); // area 100
1678        let b = square(0.0, 0.0, 10.0); // area 100
1679
1680        // Fabricated, obviously-wrong results (area far outside the feasible
1681        // range for two area-100 polygons):
1682        // - union as a 30×10 rectangle (area 300) > |A|+|B| = 200
1683        // - intersection as a 17×10 rectangle (area 170) > min(|A|,|B|) = 100
1684        let bad_union = Polygon::new(vec![
1685            Point::new(0.0, 0.0),
1686            Point::new(30.0, 0.0),
1687            Point::new(30.0, 10.0),
1688            Point::new(0.0, 10.0),
1689        ]);
1690        let bad_inter = Polygon::new(vec![
1691            Point::new(0.0, 0.0),
1692            Point::new(17.0, 0.0),
1693            Point::new(17.0, 10.0),
1694            Point::new(0.0, 10.0),
1695        ]);
1696        assert!(
1697            check_boolean_bounds(&[bad_union], &a, &b, BoolOp::Union).is_err(),
1698            "union area 300 must be rejected (exceeds |A|+|B| = 200)"
1699        );
1700        assert!(
1701            check_boolean_bounds(&[bad_inter.clone()], &a, &b, BoolOp::Intersection).is_err(),
1702            "intersection area 170 must be rejected (exceeds min(|A|,|B|) = 100)"
1703        );
1704
1705        // A legitimate result passes.
1706        let good = polygon_boolean_checked(&a, &b, BoolOp::Union).unwrap();
1707        assert!(
1708            check_boolean_bounds(&good, &a, &b, BoolOp::Union).is_ok(),
1709            "correct union must pass bounds validation"
1710        );
1711    }
1712
1713    #[test]
1714    fn checked_api_reports_ok_and_error_variants() {
1715        let a = square(0.0, 0.0, 2.0);
1716        let b = square(1.0, 1.0, 2.0);
1717
1718        // Normal case: Ok with the expected area.
1719        let ok = polygon_boolean_checked(&a, &b, BoolOp::Intersection).unwrap();
1720        assert!((ok[0].area() - 1.0).abs() < 1e-9);
1721
1722        // The convenience wrapper yields the same value.
1723        let conv = polygon_boolean(&a, &b, BoolOp::Union);
1724        assert!((conv[0].area() - 7.0).abs() < 1e-9);
1725
1726        // Difference of nested inputs returns the (hole-not-cut) outer, which
1727        // passes the area bounds (|res| == |A|), demonstrating the documented
1728        // polygon-level convention is accepted by the bounds gate.
1729        let outer = square(0.0, 0.0, 3.0);
1730        let inner = square(1.0, 1.0, 1.0);
1731        let d = polygon_boolean_checked(&outer, &inner, BoolOp::Difference).unwrap();
1732        assert_eq!(d.len(), 1);
1733        assert!((d[0].area() - 9.0).abs() < 1e-12);
1734
1735        // Error type is constructible and Displayable (used in panic messages).
1736        let err = BooleanError::Validation {
1737            op: BoolOp::Union,
1738            message: "test".to_string(),
1739        };
1740        assert!(err.to_string().contains("boolean Union failed validation"));
1741    }
1742
1743    #[test]
1744    fn section_operators_propagate_errors_as_result() {
1745        use crate::section::Section;
1746
1747        let a = Section::new(square(0.0, 0.0, 4.0), vec![]);
1748        let b = Section::new(square(1.0, 1.0, 2.0), vec![]);
1749
1750        // The Result-wrapped API: match to confirm it is Ok on valid input.
1751        match section_intersection(&a, &b) {
1752            Ok(regions) => assert!(regions[0].area() > 0.0),
1753            Err(e) => panic!("expected Ok, got Err: {e}"),
1754        }
1755
1756        // Union is recoverable via ?-style propagation in the same way.
1757        let union = section_union(&a, &b).expect("union must succeed");
1758        assert_eq!(union.len(), 1);
1759
1760        // A geometry error does not panic at the section boundary; it is a
1761        // typed Result a caller can respond to. (No valid input here triggers
1762        // one, so we only assert the type flows through: unwrap succeeds.)
1763        let diff = section_difference(&a, &b).unwrap();
1764        assert!((diff[0].area() - 16.0).abs() < 1e-6 || diff[0].holes.len() == 1);
1765    }
1766
1767    #[test]
1768    fn non_convex_l_shape_intersection() {
1769        let l = Polygon::new(vec![
1770            Point::new(0.0, 0.0),
1771            Point::new(2.0, 0.0),
1772            Point::new(2.0, 1.0),
1773            Point::new(1.0, 1.0),
1774            Point::new(1.0, 2.0),
1775            Point::new(0.0, 2.0),
1776        ]);
1777        let b = square(0.5, 0.5, 1.0); // [0.5,1.5]^2
1778        let r = polygon_boolean(&l, &b, BoolOp::Intersection);
1779        assert_eq!(r.len(), 1);
1780        assert!((r[0].area() - 0.75).abs() < 1e-9);
1781    }
1782
1783    // ---- Determinism & edge-case tests ----
1784
1785    #[test]
1786    fn deterministic_same_input_same_output() {
1787        let a = square(0.0, 0.0, 2.0);
1788        let b = Polygon::new(vec![
1789            Point::new(1.0, 0.0),
1790            Point::new(3.0, 1.0),
1791            Point::new(1.0, 2.0),
1792        ]);
1793        // Run twice; results must be byte-identical.
1794        let r1 = polygon_boolean(&a, &b, BoolOp::Intersection);
1795        let r2 = polygon_boolean(&a, &b, BoolOp::Intersection);
1796        assert_eq!(r1.len(), r2.len());
1797        for (p, q) in r1.iter().zip(&r2) {
1798            assert_eq!(p.vertices.len(), q.vertices.len());
1799            for (v, w) in p.vertices.iter().zip(&q.vertices) {
1800                assert!((v.x - w.x).abs() < 1e-15 && (v.y - w.y).abs() < 1e-15);
1801            }
1802        }
1803    }
1804
1805    #[test]
1806    fn narrow_overlap_intersection() {
1807        // Two rectangles with a very thin (0.001 wide) overlap.
1808        let a = square(0.0, 0.0, 1.0);
1809        let b = Polygon::new(vec![
1810            Point::new(0.999, 0.2),
1811            Point::new(2.0, 0.2),
1812            Point::new(2.0, 0.8),
1813            Point::new(0.999, 0.8),
1814        ]);
1815        let r = polygon_boolean(&a, &b, BoolOp::Intersection);
1816        assert_eq!(r.len(), 1);
1817        let expected_area = 0.001 * 0.6; // 1mm × 0.6m
1818        assert!(
1819            (r[0].area() - expected_area).abs() < 1e-9,
1820            "narrow intersection area: got {}, expected {}",
1821            r[0].area(),
1822            expected_area
1823        );
1824    }
1825
1826    #[test]
1827    fn near_vertex_on_edge_intersection() {
1828        // Vertex of B is very close to (but not exactly on) an edge of A.
1829        let a = square(0.0, 0.0, 2.0);
1830        let b = Polygon::new(vec![
1831            Point::new(1.0, 1e-10), // Nearly on A's bottom edge (y=0)
1832            Point::new(3.0, 1.0),
1833            Point::new(1.0, 2.0),
1834        ]);
1835        let r = polygon_boolean(&a, &b, BoolOp::Intersection);
1836        assert!(!r.is_empty());
1837        let area: f64 = r.iter().map(|p| p.area()).sum();
1838        assert!(area > 0.0, "intersection must have positive area");
1839        // Triangle area=2. Cut beyond x=2 removes a small triangle (area ~0.5).
1840        // Expected intersection ~1.5.
1841        assert!(
1842            (area - 1.5).abs() < 0.01,
1843            "near-vertex intersection area: {}",
1844            area
1845        );
1846    }
1847
1848    #[test]
1849    fn shared_vertex_boolean() {
1850        // Two squares sharing exactly one vertex.
1851        let a = square(0.0, 0.0, 1.0);
1852        let b = square(1.0, 1.0, 1.0);
1853        let i = polygon_boolean(&a, &b, BoolOp::Intersection);
1854        assert!(
1855            i.is_empty(),
1856            "intersection of touching-at-vertex squares should be empty"
1857        );
1858        let u = polygon_boolean(&a, &b, BoolOp::Union);
1859        let total: f64 = u.iter().map(|p| p.area()).sum();
1860        assert!(
1861            (total - 2.0).abs() < 1e-9,
1862            "union area of touching squares: {}",
1863            total
1864        );
1865    }
1866
1867    #[test]
1868    fn u_shape_boolean() {
1869        // U-shape intersected with a rectangle.
1870        // Note: the U-shape polygon (concave, non-holed) has the "cavity"
1871        // as interior by ray-casting — it's a single connected region.
1872        let u = Polygon::new(vec![
1873            Point::new(0.0, 0.0),
1874            Point::new(3.0, 0.0),
1875            Point::new(3.0, 3.0),
1876            Point::new(2.0, 3.0),
1877            Point::new(2.0, 1.0),
1878            Point::new(1.0, 1.0),
1879            Point::new(1.0, 3.0),
1880            Point::new(0.0, 3.0),
1881        ]);
1882        let fill = square(0.5, 0.5, 2.0); // [0.5,2.5]×[0.5,2.5]
1883        let r = polygon_boolean(&u, &fill, BoolOp::Intersection);
1884        let total: f64 = r.iter().map(|p| p.area()).sum();
1885        // fill is fully inside U (cavity is interior for a simple polygon),
1886        // so intersection = fill area = 4.
1887        assert!(
1888            (total - 4.0).abs() < 1e-6,
1889            "U-shape intersection: {}",
1890            total
1891        );
1892
1893        // Now test with a truly disconnected region: two disjoint parts.
1894        let left = Polygon::new(vec![
1895            Point::new(0.0, 0.0),
1896            Point::new(1.0, 0.0),
1897            Point::new(1.0, 3.0),
1898            Point::new(0.0, 3.0),
1899        ]);
1900        let right = Polygon::new(vec![
1901            Point::new(2.0, 0.0),
1902            Point::new(3.0, 0.0),
1903            Point::new(3.0, 3.0),
1904            Point::new(2.0, 3.0),
1905        ]);
1906        let r_left = polygon_boolean(&left, &fill, BoolOp::Intersection);
1907        let r_right = polygon_boolean(&right, &fill, BoolOp::Intersection);
1908        let area_left: f64 = r_left.iter().map(|p| p.area()).sum();
1909        let area_right: f64 = r_right.iter().map(|p| p.area()).sum();
1910        // left ∩ fill = [0.5,1]×[0.5,2.5] = 0.5×2 = 1.0
1911        assert!(
1912            (area_left - 1.0).abs() < 1e-6,
1913            "left intersection: {}",
1914            area_left
1915        );
1916        // right ∩ fill = [2,2.5]×[0.5,2.5] = 0.5×2 = 1.0
1917        assert!(
1918            (area_right - 1.0).abs() < 1e-6,
1919            "right intersection: {}",
1920            area_right
1921        );
1922    }
1923
1924    #[test]
1925    fn collinear_edges_difference() {
1926        // Two rectangles sharing a collinear edge at y=1.
1927        let a = Polygon::new(vec![
1928            Point::new(0.0, 0.0),
1929            Point::new(2.0, 0.0),
1930            Point::new(2.0, 1.0),
1931            Point::new(0.0, 1.0),
1932        ]);
1933        let b = Polygon::new(vec![
1934            Point::new(0.5, 1.0),
1935            Point::new(1.5, 1.0),
1936            Point::new(1.5, 2.0),
1937            Point::new(0.5, 2.0),
1938        ]);
1939        let d = polygon_boolean(&a, &b, BoolOp::Difference);
1940        let total: f64 = d.iter().map(|p| p.area()).sum();
1941        assert!(
1942            (total - 2.0).abs() < 1e-9,
1943            "collinear difference: {}",
1944            total
1945        );
1946    }
1947
1948    #[test]
1949    fn touching_holes_stay_separate() {
1950        use crate::section::Section;
1951        // Two sections with the same 2x2 outer, each with a hole; the holes
1952        // share the edge x=1.0 but do not overlap. The intersection piece is
1953        // the full 2x2 and both holes are voids that merely touch -- they must
1954        // NOT be merged into one hole (that would lose topology).
1955        let hole_a = Polygon::new(vec![
1956            Point::new(0.5, 0.5),
1957            Point::new(1.0, 0.5),
1958            Point::new(1.0, 1.5),
1959            Point::new(0.5, 1.5),
1960        ]); // [0.5,1.0]x[0.5,1.5]
1961        let a = Section::new(square(0.0, 0.0, 2.0), vec![hole_a]);
1962        let hole_b = Polygon::new(vec![
1963            Point::new(1.0, 0.5),
1964            Point::new(1.5, 0.5),
1965            Point::new(1.5, 1.5),
1966            Point::new(1.0, 1.5),
1967        ]); // [1.0,1.5]x[0.5,1.5]
1968        let b = Section::new(square(0.0, 0.0, 2.0), vec![hole_b]);
1969
1970        let result = section_intersection(&a, &b).unwrap();
1971        assert_eq!(result.len(), 1);
1972        assert_eq!(
1973            result[0].holes.len(),
1974            2,
1975            "touching holes must stay separate"
1976        );
1977        let hole_area: f64 = result[0].holes.iter().map(|h| h.area()).sum();
1978        // Two 0.5 wide x 1 tall holes = 1.0 total void; they must not be
1979        // double-counted (which would give 1.0) nor merged+larger.
1980        assert!(
1981            (hole_area - 1.0).abs() < 1e-4,
1982            "touching holes total area {}",
1983            hole_area
1984        );
1985        assert!(
1986            (result[0].area() - (4.0 - 1.0)).abs() < 1e-4,
1987            "section area {}",
1988            result[0].area()
1989        );
1990    }
1991
1992    #[test]
1993    fn union_does_not_merge_touching_holes() {
1994        use crate::section::Section;
1995        // Same touching holes, but via UNION. In a union neither hole is filled
1996        // by the other section, so both survive and merely touch.
1997        let hole_a = Polygon::new(vec![
1998            Point::new(0.5, 0.5),
1999            Point::new(1.0, 0.5),
2000            Point::new(1.0, 1.5),
2001            Point::new(0.5, 1.5),
2002        ]);
2003        let a = Section::new(square(0.0, 0.0, 2.0), vec![hole_a]);
2004        let hole_b = Polygon::new(vec![
2005            Point::new(1.0, 0.5),
2006            Point::new(1.5, 0.5),
2007            Point::new(1.5, 1.5),
2008            Point::new(1.0, 1.5),
2009        ]);
2010        let b = Section::new(square(0.0, 0.0, 2.0), vec![hole_b]);
2011
2012        let result = section_union(&a, &b).unwrap();
2013        assert_eq!(result.len(), 1);
2014        // Both holes are filled by the other section's material in a union, so
2015        // the touching holes do NOT survive -- union material is the full outer.
2016        assert_eq!(
2017            result[0].holes.len(),
2018            0,
2019            "union fills both touching holes, got {} holes",
2020            result[0].holes.len()
2021        );
2022        assert!(
2023            (result[0].area() - 4.0).abs() < 1e-4,
2024            "union section area {}",
2025            result[0].area()
2026        );
2027    }
2028
2029    #[test]
2030    fn union_voids_keeps_touching_regions_separate() {
2031        // Direct unit test of the union_voids() heuristic: two polygons that
2032        // merely touch (share an edge) must NOT be merged into one by the
2033        // `u.len() == 1` check, because touching polygons have zero overlap and
2034        // are already disjoint for area purposes.
2035        let rect = |x0: f64, x1: f64, y0: f64, y1: f64| {
2036            Polygon::new(vec![
2037                Point::new(x0, y0),
2038                Point::new(x1, y0),
2039                Point::new(x1, y1),
2040                Point::new(x0, y1),
2041            ])
2042        };
2043        let a = rect(0.0, 1.0, 0.0, 1.0);
2044        let b = rect(1.0, 2.0, 0.0, 1.0); // touches a at x=1
2045        let mut voids = vec![a, b];
2046        union_voids(&mut voids).unwrap();
2047        assert_eq!(voids.len(), 2, "touching holes must not be merged");
2048        let total: f64 = voids.iter().map(|p| p.area()).sum();
2049        assert!((total - 2.0).abs() < 1e-9, "touching total area {}", total);
2050    }
2051
2052    #[test]
2053    fn section_difference_clips_existing_hole_union() {
2054        use crate::section::Section;
2055        // A = 4x4 with a 2x2 hole ([1,3]^2). B = right-half band [2,4]x[0,4]
2056        // that slices through both A's hole and A's outer. The difference piece
2057        // is the left half [0,2]x[0,4]; A's existing hole is clipped to the
2058        // part inside the piece and the result must be the correct union of the
2059        // clipped hole with any B material (here none remains inside the piece).
2060        let a = Section::new(square(0.0, 0.0, 4.0), vec![square(1.0, 1.0, 2.0)]);
2061        let b_outer = Polygon::new(vec![
2062            Point::new(2.0, 0.0),
2063            Point::new(4.0, 0.0),
2064            Point::new(4.0, 4.0),
2065            Point::new(2.0, 4.0),
2066        ]);
2067        let b = Section::new(b_outer, vec![]);
2068
2069        let result = section_difference(&a, &b).unwrap();
2070        assert_eq!(result.len(), 1);
2071        let sec = &result[0];
2072        // Piece = [0,2]x[0,4], area 8.
2073        assert!(
2074            (sec.outer.area() - 8.0).abs() < 1e-6,
2075            "piece area {}",
2076            sec.outer.area()
2077        );
2078        // Existing hole clipped to [1,2]x[1,3], area 2.
2079        let hole_area: f64 = sec.holes.iter().map(|h| h.area()).sum();
2080        assert!(
2081            (hole_area - 2.0).abs() < 1e-4,
2082            "clipped existing hole area {}",
2083            hole_area
2084        );
2085        assert_holes_within_piece(&sec.outer, &sec.holes);
2086        // Net material = 8 - 2 = 6.
2087        assert!(
2088            (sec.area() - 6.0).abs() < 1e-4,
2089            "section area {}",
2090            sec.area()
2091        );
2092    }
2093
2094    #[test]
2095    fn nested_holes_are_rejected_by_validation() {
2096        use crate::geometry::compound::CompoundGeometry;
2097        use crate::section::Section;
2098        // A single Section cannot represent a hole-within-a-hole (an island of
2099        // material inside a void). Validation must reject it, since
2100        // Section::area() would otherwise double-subtract the nested region.
2101        let hole_outer = square(1.0, 1.0, 2.0); // [1,3]^2
2102        let hole_inner = square(1.5, 1.5, 1.0); // [1.5,2.5]^2, nested inside
2103        let s = Section::new(square(0.0, 0.0, 4.0), vec![hole_outer, hole_inner]);
2104        let compound = CompoundGeometry::from_sections(&[s]);
2105        assert!(
2106            matches!(
2107                compound.validate(),
2108                Err(crate::geometry::compound::CompoundError::NestedHoles { .. })
2109            ),
2110            "nested holes must be rejected by geometry validation"
2111        );
2112
2113        // A control: two non-nested, non-overlapping holes are valid.
2114        let ok = Section::new(
2115            square(0.0, 0.0, 4.0),
2116            vec![square(0.5, 0.5, 0.5), square(3.0, 3.0, 0.5)],
2117        );
2118        let compound_ok = CompoundGeometry::from_sections(&[ok]);
2119        assert!(
2120            compound_ok.validate().is_ok(),
2121            "non-nested holes must validate"
2122        );
2123    }
2124
2125    #[test]
2126    fn section_difference_a_inside_b_hole_survives() {
2127        use crate::section::Section;
2128        // B = 10x10 with a 4x4 hole in the center
2129        // A = 2x2 completely inside B's hole
2130        // B has no material where A is, so A should survive completely in A - B
2131        let b = Section::new(square(0.0, 0.0, 10.0), vec![square(3.0, 3.0, 4.0)]);
2132        let a = Section::new(square(4.0, 4.0, 2.0), vec![]);
2133
2134        let result = section_difference(&a, &b).unwrap();
2135        assert_eq!(
2136            result.len(),
2137            1,
2138            "A should survive completely inside B's hole"
2139        );
2140        let sec = &result[0];
2141        // A is 2x2 = 4 area, no holes
2142        assert!(
2143            (sec.outer.area() - 4.0).abs() < 1e-6,
2144            "piece area {}",
2145            sec.outer.area()
2146        );
2147        assert_eq!(sec.holes.len(), 0, "A has no holes");
2148        assert!(
2149            (sec.area() - 4.0).abs() < 1e-6,
2150            "section area {}",
2151            sec.area()
2152        );
2153    }
2154
2155    #[test]
2156    fn section_difference_a_inside_b_material_removed() {
2157        use crate::section::Section;
2158        // B = 10x10 with a 4x4 hole in the center [3,7]^2
2159        // A = 2x2 completely inside B's MATERIAL (not hole), e.g. at [1,3]^2
2160        // B has material where A is, so A should be completely removed in A - B
2161        let b = Section::new(square(0.0, 0.0, 10.0), vec![square(3.0, 3.0, 4.0)]);
2162        let a = Section::new(square(1.0, 1.0, 2.0), vec![]); // [1,3]^2, inside B's material
2163
2164        let result = section_difference(&a, &b).unwrap();
2165        assert_eq!(
2166            result.len(),
2167            0,
2168            "A should be removed when inside B's material"
2169        );
2170    }
2171
2172    #[test]
2173    fn section_difference_a_partial_b_hole_clipped() {
2174        use crate::section::Section;
2175        // B = 10x10 with a 4x4 hole [3,7]^2
2176        // A = 6x6 [2,8]^2 with a 2x2 hole [3,5]^2
2177        // A extends beyond B's hole on the right side.
2178        // The Difference piece = A \ B.outer = [2,8]x[2,8] \ [0,10]^2 = empty (since A inside B.outer)
2179        // Plus A ∩ B.hole = [3,7]x[3,7] ∩ [2,8]^2 = [3,7]x[3,7] (the part of A inside B's hole)
2180        // That piece has A's hole [3,5]^2 clipped to it → [3,5]^2 survives (inside B's hole, B has no material)
2181        // B material = none inside B's hole.
2182        let b = Section::new(square(0.0, 0.0, 10.0), vec![square(3.0, 3.0, 4.0)]); // hole [3,7]^2
2183        let a = Section::new(square(2.0, 2.0, 6.0), vec![square(3.0, 3.0, 2.0)]); // [2,8]^2 with hole [3,5]^2
2184
2185        let result = section_difference(&a, &b).unwrap();
2186        assert_eq!(result.len(), 1, "one piece from A ∩ B.hole");
2187        let sec = &result[0];
2188        // Piece = A ∩ B.hole = [3,7]x[3,7], area 16
2189        assert!(
2190            (sec.outer.area() - 16.0).abs() < 1e-6,
2191            "piece area {}",
2192            sec.outer.area()
2193        );
2194        // A's hole [3,5]^2 is inside the piece, so survives fully
2195        let hole_area: f64 = sec.holes.iter().map(|h| h.area()).sum();
2196        assert!(
2197            (hole_area - 4.0).abs() < 1e-4,
2198            "clipped hole area {}",
2199            hole_area
2200        );
2201        assert_holes_within_piece(&sec.outer, &sec.holes);
2202        // Net material = 16 - 4 = 12
2203        assert!(
2204            (sec.area() - 12.0).abs() < 1e-4,
2205            "section area {}",
2206            sec.area()
2207        );
2208    }
2209}