1use super::{Point, Polygon};
11
12#[derive(Debug, Clone, Copy, PartialEq, Eq)]
14pub enum BoolOp {
15 Intersection,
17 Union,
19 Difference,
21}
22
23#[derive(Debug, Clone)]
24struct Node {
25 pt: Point,
26 prev: usize,
27 next: usize,
28 is_inter: bool,
29 entry: bool,
31 neighbor: usize,
33 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
61fn 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
112fn 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), 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 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
166fn 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
178fn 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 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 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 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 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
275fn 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
290fn 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
304fn 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
318fn polygon_boolean_internal(
333 a: &Polygon,
334 b: &Polygon,
335 op: BoolOp,
336) -> Result<Vec<Polygon>, BooleanError> {
337 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 let diag = bbox_diag(&a.vertices).max(bbox_diag(&b.vertices));
358 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 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 let directions: &[(f64, f64)] = &[
382 (1.0, 0.37), (-0.61, 1.0), (0.83, -0.83), ];
386
387 let area_a = a.area();
388 let area_b = b.area();
389 let denom = (area_a.abs() + area_b.abs()).max(1e-12);
391
392 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 let result = polygon_boolean_impl(a, &b_shifted, op);
413 let result_comp = polygon_boolean_impl(a, &b_shifted, comp_op);
414
415 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 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 return Ok(mapped);
446 }
447 }
448
449 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#[derive(Debug, Clone, PartialEq)]
458pub enum BooleanError {
459 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
478pub 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 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 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
536fn validate_boolean_sampling(
570 result: &[Polygon],
571 a: &Polygon,
572 b: &Polygon,
573 op: BoolOp,
574) -> Result<(), BooleanError> {
575 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 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 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 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
668pub 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
693pub 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
701pub 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 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 return vec![a.clone()];
755 }
756 }
757 }
758
759 boolean_generic(a, b, op)
760}
761
762fn boolean_generic(a: &Polygon, b: &Polygon, op: BoolOp) -> Vec<Polygon> {
770 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 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
847fn material_inside(p: &Polygon, s: &crate::section::Section) -> Result<Vec<Polygon>, BooleanError> {
855 let mut acc = polygon_boolean_checked(p, &s.outer, BoolOp::Intersection)?;
857 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
872fn 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
883fn hole_minus_material(
888 hole: &Polygon,
889 outer: &Polygon,
890 holes: &[Polygon],
891) -> Result<Vec<Polygon>, BooleanError> {
892 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
906pub 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(®ions[i], ®ions[j], BoolOp::Union)?;
922 if u.len() == 1 {
923 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
938fn 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 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 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 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 for h in a.holes.iter() {
992 void_regions.extend(polygon_boolean_checked(h, p, BoolOp::Intersection)?);
993 }
994 }
995 }
996 }
997 }
998
999 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 union_voids(&mut void_regions)?;
1012
1013 let scale = bbox_diag(&p.vertices);
1023 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
1051fn 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#[derive(Clone, Copy, Debug, PartialEq, Eq)]
1086enum PieceKind {
1087 Normal,
1088 InHole,
1089}
1090
1091fn 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 let outer_diff = polygon_boolean_checked(&a.outer, &b.outer, BoolOp::Difference)?;
1103
1104 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 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
1130pub 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
1143pub 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
1156pub 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 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 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 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 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 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 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 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 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 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 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 let hole_a = square(1.0, 1.0, 2.0); 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 ]); 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 assert!(
1405 (sec.outer.area() - 6.0).abs() < 1e-6,
1406 "piece area {}",
1407 sec.outer.area()
1408 );
1409 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 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 let hole_a = square(1.0, 1.0, 2.0); 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); 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 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 assert_holes_within_piece(&sec.outer, &sec.holes);
1462 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 let hole = square(1.0, 1.0, 8.0); 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 assert!(
1491 (sec.outer.area() - 20.0).abs() < 1e-6,
1492 "piece area {}",
1493 sec.outer.area()
1494 );
1495 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 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 let hole = square(1.0, 1.0, 8.0); 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 assert!(
1532 (sec.outer.area() - 50.0).abs() < 1e-6,
1533 "piece area {}",
1534 sec.outer.area()
1535 );
1536 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 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 let hole = square(0.5, 0.5, 1.0); 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![]); 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 assert!(
1568 (hole_area - 0.75).abs() < 1e-3,
1569 "partially filled hole area: {}",
1570 hole_area
1571 );
1572 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 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 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 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 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 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 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 let a = square(0.0, 0.0, 10.0); let b = square(0.0, 0.0, 10.0); 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 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 let ok = polygon_boolean_checked(&a, &b, BoolOp::Intersection).unwrap();
1720 assert!((ok[0].area() - 1.0).abs() < 1e-9);
1721
1722 let conv = polygon_boolean(&a, &b, BoolOp::Union);
1724 assert!((conv[0].area() - 7.0).abs() < 1e-9);
1725
1726 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 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 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 let union = section_union(&a, &b).expect("union must succeed");
1758 assert_eq!(union.len(), 1);
1759
1760 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); 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 #[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 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 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; 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 let a = square(0.0, 0.0, 2.0);
1830 let b = Polygon::new(vec![
1831 Point::new(1.0, 1e-10), 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 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 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 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); let r = polygon_boolean(&u, &fill, BoolOp::Intersection);
1884 let total: f64 = r.iter().map(|p| p.area()).sum();
1885 assert!(
1888 (total - 4.0).abs() < 1e-6,
1889 "U-shape intersection: {}",
1890 total
1891 );
1892
1893 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 assert!(
1912 (area_left - 1.0).abs() < 1e-6,
1913 "left intersection: {}",
1914 area_left
1915 );
1916 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 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 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 ]); 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 ]); 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 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 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 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 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); 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 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 assert!(
2074 (sec.outer.area() - 8.0).abs() < 1e-6,
2075 "piece area {}",
2076 sec.outer.area()
2077 );
2078 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 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 let hole_outer = square(1.0, 1.0, 2.0); let hole_inner = square(1.5, 1.5, 1.0); 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 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 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 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 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![]); 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 let b = Section::new(square(0.0, 0.0, 10.0), vec![square(3.0, 3.0, 4.0)]); let a = Section::new(square(2.0, 2.0, 6.0), vec![square(3.0, 3.0, 2.0)]); 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 assert!(
2190 (sec.outer.area() - 16.0).abs() < 1e-6,
2191 "piece area {}",
2192 sec.outer.area()
2193 );
2194 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 assert!(
2204 (sec.area() - 12.0).abs() < 1e-4,
2205 "section area {}",
2206 sec.area()
2207 );
2208 }
2209}