use super::{Point, Polygon};
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum BoolOp {
Intersection,
Union,
Difference,
}
#[derive(Debug, Clone)]
struct Node {
pt: Point,
prev: usize,
next: usize,
is_inter: bool,
entry: bool,
neighbor: usize,
pair: usize,
processed: bool,
}
#[derive(Debug, Clone)]
struct Ring {
nodes: Vec<Node>,
}
impl Ring {
fn step(&self, i: usize, forward: bool) -> usize {
if forward {
self.nodes[i].next
} else {
self.nodes[i].prev
}
}
}
struct RawIntersection {
ea: usize,
ta: f64,
eb: usize,
tb: f64,
pt: Point,
}
fn edge_intersection(p1: Point, p2: Point, q1: Point, q2: Point) -> Option<(f64, f64)> {
let rx = p2.x - p1.x;
let ry = p2.y - p1.y;
let sx = q2.x - q1.x;
let sy = q2.y - q1.y;
let denom = rx * sy - ry * sx;
if denom.abs() < 1e-14 {
return None;
}
let qpx = q1.x - p1.x;
let qpy = q1.y - p1.y;
let s = (qpx * sy - qpy * sx) / denom;
let t = (qpx * ry - qpy * rx) / denom;
if s > 0.0 && s < 1.0 && t > 0.0 && t < 1.0 {
Some((s, t))
} else {
None
}
}
fn compute_raw_intersections(pa: &[Point], pb: &[Point]) -> Vec<RawIntersection> {
let na = pa.len();
let nb = pb.len();
let mut out = Vec::new();
for i in 0..na {
for j in 0..nb {
if let Some((ta, tb)) =
edge_intersection(pa[i], pa[(i + 1) % na], pb[j], pb[(j + 1) % nb])
{
out.push(RawIntersection {
ea: i,
ta,
eb: j,
tb,
pt: Point::new(
pa[i].x + ta * (pa[(i + 1) % na].x - pa[i].x),
pa[i].y + ta * (pa[(i + 1) % na].y - pa[i].y),
),
});
}
}
}
out
}
fn build_ring(base: &[Point], inters: &[(usize, f64, usize)], raw: &[RawIntersection]) -> Ring {
let n = base.len();
let mut by_edge: std::collections::HashMap<usize, Vec<(f64, usize)>> =
std::collections::HashMap::new();
for &(e, t, id) in inters {
by_edge.entry(e).or_default().push((t, id));
}
for list in by_edge.values_mut() {
list.sort_by(|x, y| x.0.partial_cmp(&y.0).unwrap());
}
let mut nodes: Vec<Node> = Vec::new();
for i in 0..n {
let idx = nodes.len();
nodes.push(Node {
pt: base[i],
prev: idx.wrapping_sub(usize::MAX / 2), next: 0,
is_inter: false,
entry: false,
neighbor: usize::MAX,
pair: usize::MAX,
processed: false,
});
if let Some(list) = by_edge.get(&i) {
for &(_, id) in list {
let idx = nodes.len();
nodes.push(Node {
pt: raw[id].pt,
prev: idx - 1,
next: idx + 1,
is_inter: true,
entry: false,
neighbor: usize::MAX,
pair: id,
processed: false,
});
}
}
}
let last = nodes.len() - 1;
for i in 0..=last {
nodes[i].next = if i == last { 0 } else { i + 1 };
nodes[i].prev = if i == 0 { last } else { i - 1 };
}
Ring { nodes }
}
fn assign_entries(ring: &mut Ring, first_inside_other: bool) {
let mut inside = first_inside_other;
for i in 0..ring.nodes.len() {
if ring.nodes[i].is_inter {
ring.nodes[i].entry = !inside;
inside = !inside;
}
}
}
fn trace_loop(a: &mut Ring, b: &mut Ring, start: usize, op: BoolOp) -> Vec<Point> {
let mut pts = vec![a.nodes[start].pt];
let mut in_a = true;
let mut cur = start;
let max_iter = a.nodes.len() + b.nodes.len() + 4;
for _ in 0..max_iter {
let entry = {
let ring = if in_a { &*a } else { &*b };
ring.nodes[cur].entry
};
let forward = match (op, in_a) {
(BoolOp::Intersection, _) => entry,
(BoolOp::Union, _) => !entry,
(BoolOp::Difference, true) => !entry,
(BoolOp::Difference, false) => entry,
};
a_mark_pair(a, b, cur, in_a);
loop {
cur = {
let ring = if in_a { &*a } else { &*b };
ring.step(cur, forward)
};
let is_inter = {
let ring = if in_a { &*a } else { &*b };
ring.nodes[cur].is_inter
};
if is_inter || (cur == start && in_a) {
break;
}
pts.push({
let ring = if in_a { &*a } else { &*b };
ring.nodes[cur].pt
});
}
if cur == start && in_a {
break;
}
pts.push({
let ring = if in_a { &*a } else { &*b };
ring.nodes[cur].pt
});
a_mark_pair(a, b, cur, in_a);
let reached_neighbor = {
let ring = if in_a { &*a } else { &*b };
ring.nodes[cur].neighbor
};
debug_assert!(reached_neighbor != usize::MAX);
cur = reached_neighbor;
in_a = !in_a;
if in_a && cur == start {
break;
}
}
pts
}
fn a_mark_pair(a: &mut Ring, b: &mut Ring, cur: usize, in_a: bool) {
if in_a {
a.nodes[cur].processed = true;
let n = a.nodes[cur].neighbor;
if n != usize::MAX {
b.nodes[n].processed = true;
}
} else {
b.nodes[cur].processed = true;
let n = b.nodes[cur].neighbor;
if n != usize::MAX {
a.nodes[n].processed = true;
}
}
}
fn signed_area_pts(pts: &[Point]) -> f64 {
pts.iter()
.enumerate()
.map(|(k, p)| {
let q = &pts[(k + 1) % pts.len()];
p.x * q.y - q.x * p.y
})
.sum::<f64>()
/ 2.0
}
fn bbox_diag(pts: &[Point]) -> f64 {
let (mut mn_x, mut mn_y) = (f64::INFINITY, f64::INFINITY);
let (mut mx_x, mut mx_y) = (f64::NEG_INFINITY, f64::NEG_INFINITY);
for p in pts {
mn_x = mn_x.min(p.x);
mn_y = mn_y.min(p.y);
mx_x = mx_x.max(p.x);
mx_y = mx_y.max(p.y);
}
((mx_x - mn_x).powi(2) + (mx_y - mn_y).powi(2))
.sqrt()
.max(1e-12)
}
fn point_segment_dist(p: Point, a: Point, b: Point) -> f64 {
let abx = b.x - a.x;
let aby = b.y - a.y;
let l2 = abx * abx + aby * aby;
if l2 < 1e-24 {
return ((p.x - a.x).powi(2) + (p.y - a.y).powi(2)).sqrt();
}
let t = (((p.x - a.x) * abx + (p.y - a.y) * aby) / l2).clamp(0.0, 1.0);
let cx = a.x + t * abx;
let cy = a.y + t * aby;
((p.x - cx).powi(2) + (p.y - cy).powi(2)).sqrt()
}
fn has_vertex_on_boundary(a: &[Point], b: &Polygon, tol: f64) -> bool {
let n = b.vertices.len();
for p in a {
for i in 0..n {
if point_segment_dist(*p, b.vertices[i], b.vertices[(i + 1) % n]) <= tol {
return true;
}
}
}
false
}
fn polygon_boolean_internal(
a: &Polygon,
b: &Polygon,
op: BoolOp,
) -> Result<Vec<Polygon>, BooleanError> {
if a.vertices.len() == b.vertices.len()
&& a.vertices.iter().zip(&b.vertices).all(|(p, q)| p == q)
{
return Ok(match op {
BoolOp::Intersection | BoolOp::Union => vec![a.clone()],
BoolOp::Difference => vec![],
});
}
let diag = bbox_diag(&a.vertices).max(bbox_diag(&b.vertices));
let upper = 1e-6 * diag.min(1.0);
let lower = (1e-12 * diag).min(upper);
let eps = (1e-8 * diag).clamp(lower, upper);
let det_tol = 8.0 * eps;
let degenerate = has_vertex_on_boundary(&a.vertices, b, det_tol)
|| has_vertex_on_boundary(&b.vertices, a, det_tol);
if !degenerate {
return Ok(polygon_boolean_impl(a, b, op));
}
let directions: &[(f64, f64)] = &[
(1.0, 0.37), (-0.61, 1.0), (0.83, -0.83), ];
let area_a = a.area();
let area_b = b.area();
let denom = (area_a.abs() + area_b.abs()).max(1e-12);
let comp_op = match op {
BoolOp::Intersection => BoolOp::Union,
BoolOp::Union => BoolOp::Intersection,
BoolOp::Difference => BoolOp::Intersection,
};
for &(dx, dy) in directions {
let shifted: Vec<Point> = b
.vertices
.iter()
.map(|p| Point::new(p.x + eps * dx, p.y + eps * dy))
.collect();
let b_shifted = Polygon::new(shifted);
let result = polygon_boolean_impl(a, &b_shifted, op);
let result_comp = polygon_boolean_impl(a, &b_shifted, comp_op);
let area_result: f64 = result.iter().map(|p| p.area()).sum();
let area_comp: f64 = result_comp.iter().map(|p| p.area()).sum();
let rhs = match op {
BoolOp::Difference => area_a,
BoolOp::Intersection | BoolOp::Union => area_a + area_b,
};
let err = (area_result + area_comp - rhs).abs() / denom;
let mapped: Vec<Polygon> = result
.into_iter()
.map(|mut r| {
for v in &mut r.vertices {
v.x -= eps * dx;
v.y -= eps * dy;
}
r
})
.collect();
if err < 1e-9 {
return Ok(mapped);
}
}
Err(BooleanError::Validation {
op,
message: "boolean operation failed strict inclusion-exclusion identity after perturbation; no perturbation direction produced a geometrically consistent result".to_string(),
})
}
#[derive(Debug, Clone, PartialEq)]
pub enum BooleanError {
Validation { op: BoolOp, message: String },
}
impl std::fmt::Display for BooleanError {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
match self {
BooleanError::Validation { op, message } => {
write!(f, "boolean {:?} failed validation: {}", op, message)
}
}
}
}
impl std::error::Error for BooleanError {}
pub fn check_boolean_bounds(
result: &[Polygon],
a: &Polygon,
b: &Polygon,
op: BoolOp,
) -> Result<(), BooleanError> {
let area_a = a.area();
let area_b = b.area();
let area_res: f64 = result.iter().map(|p| p.area()).sum();
let rel = 1e-6;
let fail = |message: String| BooleanError::Validation { op, message };
match op {
BoolOp::Intersection => {
let min = area_a.min(area_b);
let tol = rel * min.abs().max(1e-12);
if area_res < -tol || area_res > min + tol {
return Err(fail(format!(
"intersection area {:.6} outside [0, min(|A|,|B|) = {:.6}]",
area_res, min
)));
}
}
BoolOp::Union => {
let max = area_a.max(area_b);
let lo = max;
let hi = area_a + area_b;
let tol = rel * hi.abs().max(1e-12);
if area_res < lo - tol || area_res > hi + tol {
return Err(fail(format!(
"union area {:.6} outside [max(|A|,|B|) = {:.6}, |A|+|B| = {:.6}]",
area_res, lo, hi
)));
}
}
BoolOp::Difference => {
let tol = rel * area_a.abs().max(1e-12);
if area_res < -tol || area_res > area_a + tol {
return Err(fail(format!(
"difference area {:.6} outside [0, |A| = {:.6}]",
area_res, area_a
)));
}
}
}
Ok(())
}
fn validate_boolean_sampling(
result: &[Polygon],
a: &Polygon,
b: &Polygon,
op: BoolOp,
) -> Result<(), BooleanError> {
if op == BoolOp::Difference {
let area_a = a.area();
let area_res: f64 = result.iter().map(|p| p.area()).sum();
if (area_res - area_a).abs() < 1e-9 {
return Ok(());
}
}
let diag = bbox_diag(&a.vertices).max(bbox_diag(&b.vertices));
if diag <= 0.0 {
return Ok(());
}
let upper = 1e-6 * diag.min(1.0);
let lower = (1e-12 * diag).min(upper);
let eps = (1e-8 * diag).clamp(lower, upper);
let bnd_tol = 16.0 * eps;
let (minx, maxx, miny, maxy) = {
let mut minx = f64::INFINITY;
let mut maxx = f64::NEG_INFINITY;
let mut miny = f64::INFINITY;
let mut maxy = f64::NEG_INFINITY;
for p in std::iter::once(a).chain(std::iter::once(b)).chain(result) {
for v in &p.vertices {
minx = minx.min(v.x);
maxx = maxx.max(v.x);
miny = miny.min(v.y);
maxy = maxy.max(v.y);
}
}
(minx, maxx, miny, maxy)
};
let boundary_edges: Vec<(Point, Point)> = std::iter::once(a)
.chain(std::iter::once(b))
.chain(result)
.flat_map(|p| {
p.vertices
.iter()
.enumerate()
.map(move |(i, v)| (*v, p.vertices[(i + 1) % p.vertices.len()]))
})
.collect();
const N: usize = 32;
let w = (maxx - minx).max(f64::MIN_POSITIVE);
let h = (maxy - miny).max(f64::MIN_POSITIVE);
let mut mismatches = 0usize;
let mut checked = 0usize;
for ix in 0..=N {
for iy in 0..=N {
let pt = Point::new(
minx + w * (ix as f64) / (N as f64),
miny + h * (iy as f64) / (N as f64),
);
let near_boundary = boundary_edges
.iter()
.any(|&(p, q)| point_segment_dist(pt, p, q) <= bnd_tol);
if near_boundary {
continue;
}
checked += 1;
let in_a = a.contains_point(pt);
let in_b = b.contains_point(pt);
let in_res = result.iter().any(|p| p.contains_point(pt));
let expected = match op {
BoolOp::Intersection => in_a && in_b,
BoolOp::Union => in_a || in_b,
BoolOp::Difference => in_a && !in_b,
};
if in_res != expected {
mismatches += 1;
}
}
}
if mismatches > 0 && checked > 0 {
return Err(BooleanError::Validation {
op,
message: format!(
"point-sampling mismatch: {mismatches}/{checked} of the checked samples disagree \
with the expected {:?} of A and B",
op
),
});
}
Ok(())
}
pub fn polygon_boolean_checked(
a: &Polygon,
b: &Polygon,
op: BoolOp,
) -> Result<Vec<Polygon>, BooleanError> {
let result = polygon_boolean_internal(a, b, op)?;
check_boolean_bounds(&result, a, b, op)?;
Ok(result)
}
pub fn polygon_boolean(a: &Polygon, b: &Polygon, op: BoolOp) -> Vec<Polygon> {
polygon_boolean_checked(a, b, op).expect("polygon boolean failed validation")
}
pub fn polygon_boolean_sampled_checked(
a: &Polygon,
b: &Polygon,
op: BoolOp,
) -> Result<Vec<Polygon>, BooleanError> {
let result = polygon_boolean_checked(a, b, op)?;
validate_boolean_sampling(&result, a, b, op)?;
Ok(result)
}
fn polygon_boolean_impl(a: &Polygon, b: &Polygon, op: BoolOp) -> Vec<Polygon> {
let a_in_b = a.vertices.iter().all(|v| b.contains_point(*v));
let b_in_a = b.vertices.iter().all(|v| a.contains_point(*v));
match op {
BoolOp::Intersection => {
if a_in_b {
return vec![a.clone()];
}
if b_in_a {
return vec![b.clone()];
}
}
BoolOp::Union => {
if a_in_b {
return vec![b.clone()];
}
if b_in_a {
return vec![a.clone()];
}
}
BoolOp::Difference => {
if a_in_b {
return vec![];
}
if b_in_a {
return vec![a.clone()];
}
}
}
boolean_generic(a, b, op)
}
fn boolean_generic(a: &Polygon, b: &Polygon, op: BoolOp) -> Vec<Polygon> {
let b_eff: Vec<Point> = if op == BoolOp::Difference {
b.vertices.iter().rev().copied().collect()
} else {
b.vertices.clone()
};
let raw = compute_raw_intersections(&a.vertices, &b_eff);
if raw.is_empty() {
return match op {
BoolOp::Intersection => vec![],
BoolOp::Union => vec![a.clone(), b.clone()],
BoolOp::Difference => vec![a.clone()],
};
}
let mut ring_a = build_ring(
&a.vertices,
&raw.iter()
.enumerate()
.map(|(id, r)| (r.ea, r.ta, id))
.collect::<Vec<_>>(),
&raw,
);
let mut ring_b = build_ring(
&b_eff,
&raw.iter()
.enumerate()
.map(|(id, r)| (r.eb, r.tb, id))
.collect::<Vec<_>>(),
&raw,
);
use std::collections::HashMap;
let mut pair_to_b: HashMap<usize, usize> = HashMap::new();
for (i, nd) in ring_b.nodes.iter().enumerate() {
if nd.is_inter {
pair_to_b.insert(nd.pair, i);
}
}
let mut pair_to_a: HashMap<usize, usize> = HashMap::new();
for (i, nd) in ring_a.nodes.iter().enumerate() {
if nd.is_inter {
pair_to_a.insert(nd.pair, i);
}
}
for (&pid, &ja) in &pair_to_a {
if let Some(&jb) = pair_to_b.get(&pid) {
ring_a.nodes[ja].neighbor = jb;
ring_b.nodes[jb].neighbor = ja;
}
}
assign_entries(&mut ring_a, b.contains_point(a.vertices[0]));
assign_entries(&mut ring_b, a.contains_point(b_eff[0]));
let mut results = Vec::new();
let starts: Vec<usize> = ring_a
.nodes
.iter()
.enumerate()
.filter(|(_, n)| n.is_inter)
.map(|(i, _)| i)
.collect();
for i in starts {
if !ring_a.nodes[i].processed {
let pts = trace_loop(&mut ring_a, &mut ring_b, i, op);
if pts.len() >= 3 && signed_area_pts(&pts).abs() > 1e-15 {
results.push(Polygon::new(pts));
}
}
}
results
}
fn material_inside(p: &Polygon, s: &crate::section::Section) -> Result<Vec<Polygon>, BooleanError> {
let mut acc = polygon_boolean_checked(p, &s.outer, BoolOp::Intersection)?;
for h in &s.holes {
let h_ccw = ccw(h);
let mut next = Vec::new();
for r in acc.iter() {
next.extend(polygon_boolean_checked(r, &h_ccw, BoolOp::Difference)?);
}
acc = next;
if acc.is_empty() {
break;
}
}
Ok(acc.into_iter().filter(|r| r.area().abs() > 1e-15).collect())
}
fn ccw(p: &Polygon) -> Polygon {
if p.signed_area() >= 0.0 {
p.clone()
} else {
Polygon::new(p.vertices.iter().rev().copied().collect())
}
}
fn hole_minus_material(
hole: &Polygon,
outer: &Polygon,
holes: &[Polygon],
) -> Result<Vec<Polygon>, BooleanError> {
let hole = ccw(hole);
let mut res = Vec::new();
res.extend(polygon_boolean_checked(&hole, outer, BoolOp::Difference)?);
for oh in holes {
res.extend(polygon_boolean_checked(
&hole,
&ccw(oh),
BoolOp::Intersection,
)?);
}
Ok(res)
}
pub fn union_voids(regions: &mut Vec<Polygon>) -> Result<(), BooleanError> {
let mut i = 0;
while i < regions.len() {
let mut j = i + 1;
let mut merged = false;
while j < regions.len() {
let u = polygon_boolean_checked(®ions[i], ®ions[j], BoolOp::Union)?;
if u.len() == 1 {
regions[i] = u.into_iter().next().unwrap();
regions.swap_remove(j);
merged = true;
break;
}
j += 1;
}
if !merged {
i += 1;
}
}
Ok(())
}
fn holes_for_piece(
p: &Polygon,
a: &crate::section::Section,
b: &crate::section::Section,
op: BoolOp,
kind: PieceKind,
) -> Result<Vec<Polygon>, BooleanError> {
let mut void_regions: Vec<Polygon> = Vec::new();
match op {
BoolOp::Union => {
for h in a.holes.iter() {
void_regions.extend(hole_minus_material(h, &b.outer, &b.holes)?);
}
for h in b.holes.iter() {
void_regions.extend(hole_minus_material(h, &a.outer, &a.holes)?);
}
}
BoolOp::Intersection => {
void_regions.extend(a.holes.iter().cloned());
void_regions.extend(b.holes.iter().cloned());
}
BoolOp::Difference => {
match kind {
PieceKind::Normal => {
for h in a.holes.iter() {
void_regions.extend(hole_minus_material(h, &b.outer, &b.holes)?);
}
void_regions.extend(material_inside(p, b)?);
}
PieceKind::InHole => {
for h in a.holes.iter() {
void_regions.extend(polygon_boolean_checked(h, p, BoolOp::Intersection)?);
}
}
}
}
}
let mut clipped = Vec::new();
for r in void_regions {
clipped.extend(polygon_boolean_checked(p, &ccw(&r), BoolOp::Intersection)?);
}
void_regions = clipped;
union_voids(&mut void_regions)?;
let scale = bbox_diag(&p.vertices);
let area_tol = 1e-9 * p.area().abs().max(1e-12) + 1e-8 * scale * scale;
let coord_tol = 1e-7 * scale;
let edge_pairs: Vec<(Point, Point)> = p
.vertices
.iter()
.enumerate()
.map(|(i, v)| (*v, p.vertices[(i + 1) % p.vertices.len()]))
.collect();
Ok(void_regions
.into_iter()
.filter(|r| {
if r.area().abs() <= area_tol {
return false;
}
r.vertices.iter().all(|&v| {
if p.contains_point(v) {
return true;
}
edge_pairs
.iter()
.any(|&(a, b)| point_segment_dist(v, a, b) <= coord_tol)
})
})
.collect())
}
fn section_boolean(
a: &crate::section::Section,
b: &crate::section::Section,
op: BoolOp,
) -> Result<Vec<crate::section::Section>, BooleanError> {
use crate::section::Section;
if op == BoolOp::Difference {
return section_difference_impl(a, b);
}
let pieces = polygon_boolean_checked(&a.outer, &b.outer, op)?;
let mut out = Vec::new();
for p in pieces {
let holes = holes_for_piece(&p, a, b, op, PieceKind::Normal)?;
let s = Section::new(p, holes);
if s.area() > 0.0 {
out.push(s);
}
}
Ok(out)
}
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
enum PieceKind {
Normal,
InHole,
}
fn section_difference_impl(
a: &crate::section::Section,
b: &crate::section::Section,
) -> Result<Vec<crate::section::Section>, BooleanError> {
use crate::section::Section;
let outer_diff = polygon_boolean_checked(&a.outer, &b.outer, BoolOp::Difference)?;
let mut hole_intersections = Vec::new();
for bh in &b.holes {
hole_intersections.extend(polygon_boolean_checked(&a.outer, bh, BoolOp::Intersection)?);
}
let mut pieces = Vec::new();
for p in outer_diff {
pieces.push((p, PieceKind::Normal));
}
for p in hole_intersections {
pieces.push((p, PieceKind::InHole));
}
let mut out = Vec::new();
for (p, kind) in pieces {
let holes = holes_for_piece(&p, a, b, BoolOp::Difference, kind)?;
let s = Section::new(p, holes);
if s.area() > 0.0 {
out.push(s);
}
}
Ok(out)
}
pub fn section_intersection(
a: &crate::section::Section,
b: &crate::section::Section,
) -> Result<Vec<crate::section::Section>, BooleanError> {
section_boolean(a, b, BoolOp::Intersection)
}
pub fn section_difference(
a: &crate::section::Section,
b: &crate::section::Section,
) -> Result<Vec<crate::section::Section>, BooleanError> {
section_boolean(a, b, BoolOp::Difference)
}
pub fn section_union(
a: &crate::section::Section,
b: &crate::section::Section,
) -> Result<Vec<crate::section::Section>, BooleanError> {
section_boolean(a, b, BoolOp::Union)
}
#[cfg(test)]
mod tests {
use super::*;
fn square(x0: f64, y0: f64, size: f64) -> Polygon {
Polygon::new(vec![
Point::new(x0, y0),
Point::new(x0 + size, y0),
Point::new(x0 + size, y0 + size),
Point::new(x0, y0 + size),
])
}
fn assert_holes_within_piece(piece: &Polygon, holes: &[Polygon]) {
let diag = bbox_diag(&piece.vertices);
let tol = 1e-7 * diag;
for h in holes {
for v in &h.vertices {
let on_boundary = piece.vertices.iter().enumerate().any(|(i, a)| {
let b = piece.vertices[(i + 1) % piece.vertices.len()];
point_segment_dist(*v, *a, b) <= tol
});
assert!(
piece.contains_point(*v) || on_boundary,
"hole must not extend outside the piece"
);
}
}
}
#[test]
fn intersection_of_overlapping_squares() {
let a = square(0.0, 0.0, 2.0);
let b = square(1.0, 1.0, 2.0);
let r = polygon_boolean(&a, &b, BoolOp::Intersection);
assert_eq!(r.len(), 1);
assert!((r[0].area() - 1.0).abs() < 1e-9);
}
#[test]
fn union_area_subtracts_overlap() {
let a = square(0.0, 0.0, 2.0);
let b = square(1.0, 1.0, 2.0);
let r = polygon_boolean(&a, &b, BoolOp::Union);
assert_eq!(r.len(), 1);
assert!((r[0].area() - 7.0).abs() < 1e-9);
}
#[test]
fn difference_removes_overlap() {
let a = square(0.0, 0.0, 2.0);
let b = square(1.0, 1.0, 2.0);
let r = polygon_boolean(&a, &b, BoolOp::Difference);
assert_eq!(r.len(), 1);
assert!((r[0].area() - 3.0).abs() < 1e-9);
}
#[test]
fn disjoint_polygons() {
let a = square(0.0, 0.0, 1.0);
let b = square(5.0, 5.0, 1.0);
assert!(polygon_boolean(&a, &b, BoolOp::Intersection).is_empty());
assert_eq!(polygon_boolean(&a, &b, BoolOp::Union).len(), 2);
let d = polygon_boolean(&a, &b, BoolOp::Difference);
assert_eq!(d.len(), 1);
assert!((d[0].area() - 1.0).abs() < 1e-12);
}
#[test]
fn contained_polygons() {
let outer = square(0.0, 0.0, 3.0);
let inner = square(1.0, 1.0, 1.0);
let i = polygon_boolean(&inner, &outer, BoolOp::Intersection);
assert_eq!(i.len(), 1);
assert!((i[0].area() - 1.0).abs() < 1e-12);
let u = polygon_boolean(&inner, &outer, BoolOp::Union);
assert_eq!(u.len(), 1);
assert!((u[0].area() - 9.0).abs() < 1e-12);
let d = polygon_boolean(&outer, &inner, BoolOp::Difference);
assert_eq!(d.len(), 1);
assert!((d[0].area() - 9.0).abs() < 1e-12);
}
#[test]
fn section_difference_creates_hole() {
use crate::section::Section;
let outer = square(0.0, 0.0, 4.0);
let a = Section::new(outer, vec![]);
let b = Section::new(square(1.0, 1.0, 2.0), vec![]);
let result = section_difference(&a, &b).unwrap();
assert_eq!(result.len(), 1);
assert_eq!(result[0].holes.len(), 1);
assert!((result[0].area() - (16.0 - 4.0)).abs() < 1e-9);
assert!((result[0].centroid().x - 2.0).abs() < 1e-12);
let props = crate::section_properties::SectionProperties::from_section(&result[0]);
let expected_ix = 4.0 * 4.0_f64.powi(3) / 12.0 - 2.0 * 2.0_f64.powi(3) / 12.0;
assert!((props.ix - expected_ix).abs() / expected_ix < 1e-10);
}
#[test]
fn section_difference_partial_overlap_no_hole() {
use crate::section::Section;
let a = Section::new(square(0.0, 0.0, 2.0), vec![]);
let b = Section::new(square(1.0, 1.0, 2.0), vec![]);
let result = section_difference(&a, &b).unwrap();
assert_eq!(result.len(), 1);
assert_eq!(result[0].holes.len(), 0);
assert!((result[0].area() - 3.0).abs() < 1e-9);
}
#[test]
fn section_difference_with_existing_holes() {
use crate::section::Section;
let a = Section::new(square(0.0, 0.0, 4.0), vec![square(0.5, 0.5, 1.0)]);
let b = Section::new(square(2.5, 2.5, 1.0), vec![]);
let result = section_difference(&a, &b).unwrap();
assert_eq!(result.len(), 1);
assert_eq!(result[0].holes.len(), 2);
assert!((result[0].area() - (16.0 - 1.0 - 1.0)).abs() < 1e-9);
}
#[test]
fn identical_polygons() {
let a = square(0.0, 0.0, 2.0);
assert_eq!(
polygon_boolean(&a, &a.clone(), BoolOp::Intersection)[0].area(),
4.0
);
assert_eq!(
polygon_boolean(&a, &a.clone(), BoolOp::Union)[0].area(),
4.0
);
assert!(polygon_boolean(&a, &a.clone(), BoolOp::Difference).is_empty());
}
#[test]
fn section_union_preserves_holes() {
use crate::section::Section;
let hole_a = square(0.2, 0.3, 0.3);
let a = Section::new(square(0.0, 0.0, 1.2), vec![hole_a]);
let hole_b = square(1.5, 0.3, 0.3);
let b = Section::new(square(1.0, 0.0, 1.2), vec![hole_b]);
let result = section_union(&a, &b).unwrap();
assert_eq!(result.len(), 1, "overlapping squares merge into one piece");
assert_eq!(result[0].holes.len(), 2, "union must preserve both holes");
let expected = (1.44 - 0.09) + (1.44 - 0.09) - 0.24;
assert!(
(result[0].area() - expected).abs() < 1e-6,
"union area {}",
result[0].area()
);
}
#[test]
fn section_union_drops_hole_filled_by_other() {
use crate::section::Section;
let hole = square(0.5, 0.5, 1.0);
let a = Section::new(square(0.0, 0.0, 2.0), vec![hole]);
let b = Section::new(square(0.5, 0.5, 1.0), vec![]);
let result = section_union(&a, &b).unwrap();
assert_eq!(result.len(), 1);
assert_eq!(
result[0].holes.len(),
0,
"filled hole must disappear: {:?}",
result[0].holes.len()
);
assert!(
(result[0].area() - 4.0).abs() < 1e-9,
"union area {}",
result[0].area()
);
}
#[test]
fn section_intersection_preserves_holes() {
use crate::section::Section;
let hole_a = square(0.5, 0.5, 0.5);
let a = Section::new(square(0.0, 0.0, 2.0), vec![hole_a]);
let hole_b = square(1.0, 1.0, 0.5);
let b = Section::new(square(0.0, 0.0, 2.0), vec![hole_b]);
let result = section_intersection(&a, &b).unwrap();
assert_eq!(result.len(), 1);
assert_eq!(result[0].holes.len(), 2, "intersection keeps both holes");
}
#[test]
fn section_intersection_clips_holes_to_piece() {
use crate::section::Section;
let hole_a = square(1.0, 1.0, 2.0); let a = Section::new(square(0.0, 0.0, 4.0), vec![hole_a]);
let b_outer = Polygon::new(vec![
Point::new(0.0, 0.0),
Point::new(1.5, 0.0),
Point::new(1.5, 4.0),
Point::new(0.0, 4.0),
]);
let hole_b = Polygon::new(vec![
Point::new(0.5, 1.0),
Point::new(1.0, 1.0),
Point::new(1.0, 3.0),
Point::new(0.5, 3.0),
]); let b = Section::new(b_outer, vec![hole_b]);
let result = section_intersection(&a, &b).unwrap();
assert_eq!(result.len(), 1);
let sec = &result[0];
assert!(
(sec.outer.area() - 6.0).abs() < 1e-6,
"piece area {}",
sec.outer.area()
);
let hole_area: f64 = sec.holes.iter().map(|h| h.area()).sum();
assert!(
(hole_area - 2.0).abs() < 1e-4,
"clipped holes total area {}",
hole_area
);
assert_holes_within_piece(&sec.outer, &sec.holes);
assert!(
(sec.area() - 4.0).abs() < 1e-4,
"section area {}",
sec.area()
);
}
#[test]
fn section_intersection_unions_overlapping_holes() {
use crate::section::Section;
let hole_a = square(1.0, 1.0, 2.0); let a = Section::new(square(0.0, 0.0, 4.0), vec![hole_a]);
let hole_b = square(2.0, 1.0, 2.0); let b = Section::new(square(0.0, 0.0, 4.0), vec![hole_b]);
let result = section_intersection(&a, &b).unwrap();
assert_eq!(result.len(), 1);
let sec = &result[0];
assert!(
(sec.outer.area() - 16.0).abs() < 1e-6,
"piece area {}",
sec.outer.area()
);
assert_eq!(
sec.holes.len(),
1,
"overlapping holes must merge: {}",
sec.holes.len()
);
let hole_area = sec.holes[0].area();
assert!(
(hole_area - 6.0).abs() < 1e-4,
"merged hole area {}",
hole_area
);
assert_holes_within_piece(&sec.outer, &sec.holes);
assert!(
(sec.area() - 10.0).abs() < 1e-4,
"section area {}",
sec.area()
);
}
#[test]
fn section_intersection_clips_hole_to_piece() {
use crate::section::Section;
let hole = square(1.0, 1.0, 8.0); let a = Section::new(square(0.0, 0.0, 10.0), vec![hole]);
let b_outer = Polygon::new(vec![
Point::new(0.0, 0.0),
Point::new(2.0, 0.0),
Point::new(2.0, 10.0),
Point::new(0.0, 10.0),
]);
let b = Section::new(b_outer, vec![]);
let result = section_intersection(&a, &b).unwrap();
assert_eq!(result.len(), 1);
let sec = &result[0];
assert!(
(sec.outer.area() - 20.0).abs() < 1e-6,
"piece area {}",
sec.outer.area()
);
let hole_area: f64 = sec.holes.iter().map(|h| h.area()).sum();
assert!(
(hole_area - 8.0).abs() < 1e-4,
"clipped hole area {}",
hole_area
);
assert_holes_within_piece(&sec.outer, &sec.holes);
assert!(
(sec.area() - 12.0).abs() < 1e-4,
"section area {}",
sec.area()
);
}
#[test]
fn section_difference_clips_hole_to_piece() {
use crate::section::Section;
let hole = square(1.0, 1.0, 8.0); let a = Section::new(square(0.0, 0.0, 10.0), vec![hole]);
let b_outer = Polygon::new(vec![
Point::new(0.0, 0.0),
Point::new(5.0, 0.0),
Point::new(5.0, 10.0),
Point::new(0.0, 10.0),
]);
let b = Section::new(b_outer, vec![]);
let result = section_difference(&a, &b).unwrap();
assert_eq!(result.len(), 1);
let sec = &result[0];
assert!(
(sec.outer.area() - 50.0).abs() < 1e-6,
"piece area {}",
sec.outer.area()
);
let hole_area: f64 = sec.holes.iter().map(|h| h.area()).sum();
assert!(
(hole_area - 32.0).abs() < 1e-4,
"clipped hole area {}",
hole_area
);
assert_holes_within_piece(&sec.outer, &sec.holes);
assert!(
(sec.area() - 18.0).abs() < 1e-4,
"section area {}",
sec.area()
);
}
#[test]
fn section_union_clips_hole_partially_filled() {
use crate::section::Section;
let hole = square(0.5, 0.5, 1.0); let a = Section::new(square(0.0, 0.0, 2.0), vec![hole]);
let b = Section::new(square(1.0, 0.5, 0.5), vec![]);
let result = section_union(&a, &b).unwrap();
assert_eq!(result.len(), 1);
let sec = &result[0];
let hole_area: f64 = sec.holes.iter().map(|h| h.area()).sum();
assert!(
(hole_area - 0.75).abs() < 1e-3,
"partially filled hole area: {}",
hole_area
);
assert!(
(sec.area() - 3.25).abs() < 1e-3,
"union area {}",
sec.area()
);
}
#[test]
fn shared_edge_squares_union_area() {
let a = square(0.0, 0.0, 1.0);
let b = square(1.0, 0.0, 1.0);
let u = polygon_boolean(&a, &b, BoolOp::Union);
let total: f64 = u.iter().map(|p| p.area()).sum();
assert!((total - 2.0).abs() < 1e-9);
assert!(polygon_boolean(&a, &b, BoolOp::Intersection).is_empty());
let d = polygon_boolean(&a, &b, BoolOp::Difference);
assert!((d[0].area() - 1.0).abs() < 1e-9);
}
#[test]
fn vertex_on_edge_case_satisfies_area_identity() {
let a = square(0.0, 0.0, 2.0);
let b = Polygon::new(vec![
Point::new(1.0, 0.0),
Point::new(3.0, 1.0),
Point::new(1.0, 2.0),
]);
let area_a = a.area();
let area_b = b.area();
let i = polygon_boolean(&a, &b, BoolOp::Intersection);
let inter: f64 = i.iter().map(|p| p.area()).sum();
let u = polygon_boolean(&a, &b, BoolOp::Union);
let uni: f64 = u.iter().map(|p| p.area()).sum();
let d = polygon_boolean(&a, &b, BoolOp::Difference);
let diff: f64 = d.iter().map(|p| p.area()).sum();
assert!(
(area_a + area_b - inter - uni).abs() < 1e-3,
"union identity: {} + {} - {} != {}",
area_a,
area_b,
inter,
uni
);
assert!((area_a - inter - diff).abs() < 1e-3, "difference identity");
assert!(inter > 0.0 && inter < area_b.min(area_a));
}
#[test]
fn perturbation_result_is_mapped_back_to_original_frame() {
let a = square(0.0, 0.0, 1.0);
let b = square(1.0, 1.0, 1.0);
let u = polygon_boolean(&a, &b, BoolOp::Union);
let total: f64 = u.iter().map(|p| p.area()).sum();
assert!((total - 2.0).abs() < 1e-9, "union area: {}", total);
let found = u
.iter()
.flat_map(|p| &p.vertices)
.any(|v| (v.x - 2.0).abs() < 1e-12 && (v.y - 2.0).abs() < 1e-12);
assert!(
found,
"B-originated vertex (2,2) not at its original position after \
perturbation; back-mapping missing?"
);
let found_corner = u
.iter()
.flat_map(|p| &p.vertices)
.any(|v| (v.x - 1.0).abs() < 1e-12 && (v.y - 1.0).abs() < 1e-12);
assert!(
found_corner,
"shared corner (1,1) not restored after perturbation"
);
}
#[test]
fn bounds_validation_rejects_bloated_union() {
let a = square(0.0, 0.0, 10.0); let b = square(0.0, 0.0, 10.0);
let bad_union = Polygon::new(vec![
Point::new(0.0, 0.0),
Point::new(30.0, 0.0),
Point::new(30.0, 10.0),
Point::new(0.0, 10.0),
]);
let bad_inter = Polygon::new(vec![
Point::new(0.0, 0.0),
Point::new(17.0, 0.0),
Point::new(17.0, 10.0),
Point::new(0.0, 10.0),
]);
assert!(
check_boolean_bounds(&[bad_union], &a, &b, BoolOp::Union).is_err(),
"union area 300 must be rejected (exceeds |A|+|B| = 200)"
);
assert!(
check_boolean_bounds(&[bad_inter.clone()], &a, &b, BoolOp::Intersection).is_err(),
"intersection area 170 must be rejected (exceeds min(|A|,|B|) = 100)"
);
let good = polygon_boolean_checked(&a, &b, BoolOp::Union).unwrap();
assert!(
check_boolean_bounds(&good, &a, &b, BoolOp::Union).is_ok(),
"correct union must pass bounds validation"
);
}
#[test]
fn checked_api_reports_ok_and_error_variants() {
let a = square(0.0, 0.0, 2.0);
let b = square(1.0, 1.0, 2.0);
let ok = polygon_boolean_checked(&a, &b, BoolOp::Intersection).unwrap();
assert!((ok[0].area() - 1.0).abs() < 1e-9);
let conv = polygon_boolean(&a, &b, BoolOp::Union);
assert!((conv[0].area() - 7.0).abs() < 1e-9);
let outer = square(0.0, 0.0, 3.0);
let inner = square(1.0, 1.0, 1.0);
let d = polygon_boolean_checked(&outer, &inner, BoolOp::Difference).unwrap();
assert_eq!(d.len(), 1);
assert!((d[0].area() - 9.0).abs() < 1e-12);
let err = BooleanError::Validation {
op: BoolOp::Union,
message: "test".to_string(),
};
assert!(err.to_string().contains("boolean Union failed validation"));
}
#[test]
fn section_operators_propagate_errors_as_result() {
use crate::section::Section;
let a = Section::new(square(0.0, 0.0, 4.0), vec![]);
let b = Section::new(square(1.0, 1.0, 2.0), vec![]);
match section_intersection(&a, &b) {
Ok(regions) => assert!(regions[0].area() > 0.0),
Err(e) => panic!("expected Ok, got Err: {e}"),
}
let union = section_union(&a, &b).expect("union must succeed");
assert_eq!(union.len(), 1);
let diff = section_difference(&a, &b).unwrap();
assert!((diff[0].area() - 16.0).abs() < 1e-6 || diff[0].holes.len() == 1);
}
#[test]
fn non_convex_l_shape_intersection() {
let l = Polygon::new(vec![
Point::new(0.0, 0.0),
Point::new(2.0, 0.0),
Point::new(2.0, 1.0),
Point::new(1.0, 1.0),
Point::new(1.0, 2.0),
Point::new(0.0, 2.0),
]);
let b = square(0.5, 0.5, 1.0); let r = polygon_boolean(&l, &b, BoolOp::Intersection);
assert_eq!(r.len(), 1);
assert!((r[0].area() - 0.75).abs() < 1e-9);
}
#[test]
fn deterministic_same_input_same_output() {
let a = square(0.0, 0.0, 2.0);
let b = Polygon::new(vec![
Point::new(1.0, 0.0),
Point::new(3.0, 1.0),
Point::new(1.0, 2.0),
]);
let r1 = polygon_boolean(&a, &b, BoolOp::Intersection);
let r2 = polygon_boolean(&a, &b, BoolOp::Intersection);
assert_eq!(r1.len(), r2.len());
for (p, q) in r1.iter().zip(&r2) {
assert_eq!(p.vertices.len(), q.vertices.len());
for (v, w) in p.vertices.iter().zip(&q.vertices) {
assert!((v.x - w.x).abs() < 1e-15 && (v.y - w.y).abs() < 1e-15);
}
}
}
#[test]
fn narrow_overlap_intersection() {
let a = square(0.0, 0.0, 1.0);
let b = Polygon::new(vec![
Point::new(0.999, 0.2),
Point::new(2.0, 0.2),
Point::new(2.0, 0.8),
Point::new(0.999, 0.8),
]);
let r = polygon_boolean(&a, &b, BoolOp::Intersection);
assert_eq!(r.len(), 1);
let expected_area = 0.001 * 0.6; assert!(
(r[0].area() - expected_area).abs() < 1e-9,
"narrow intersection area: got {}, expected {}",
r[0].area(),
expected_area
);
}
#[test]
fn near_vertex_on_edge_intersection() {
let a = square(0.0, 0.0, 2.0);
let b = Polygon::new(vec![
Point::new(1.0, 1e-10), Point::new(3.0, 1.0),
Point::new(1.0, 2.0),
]);
let r = polygon_boolean(&a, &b, BoolOp::Intersection);
assert!(!r.is_empty());
let area: f64 = r.iter().map(|p| p.area()).sum();
assert!(area > 0.0, "intersection must have positive area");
assert!(
(area - 1.5).abs() < 0.01,
"near-vertex intersection area: {}",
area
);
}
#[test]
fn shared_vertex_boolean() {
let a = square(0.0, 0.0, 1.0);
let b = square(1.0, 1.0, 1.0);
let i = polygon_boolean(&a, &b, BoolOp::Intersection);
assert!(
i.is_empty(),
"intersection of touching-at-vertex squares should be empty"
);
let u = polygon_boolean(&a, &b, BoolOp::Union);
let total: f64 = u.iter().map(|p| p.area()).sum();
assert!(
(total - 2.0).abs() < 1e-9,
"union area of touching squares: {}",
total
);
}
#[test]
fn u_shape_boolean() {
let u = Polygon::new(vec![
Point::new(0.0, 0.0),
Point::new(3.0, 0.0),
Point::new(3.0, 3.0),
Point::new(2.0, 3.0),
Point::new(2.0, 1.0),
Point::new(1.0, 1.0),
Point::new(1.0, 3.0),
Point::new(0.0, 3.0),
]);
let fill = square(0.5, 0.5, 2.0); let r = polygon_boolean(&u, &fill, BoolOp::Intersection);
let total: f64 = r.iter().map(|p| p.area()).sum();
assert!(
(total - 4.0).abs() < 1e-6,
"U-shape intersection: {}",
total
);
let left = Polygon::new(vec![
Point::new(0.0, 0.0),
Point::new(1.0, 0.0),
Point::new(1.0, 3.0),
Point::new(0.0, 3.0),
]);
let right = Polygon::new(vec![
Point::new(2.0, 0.0),
Point::new(3.0, 0.0),
Point::new(3.0, 3.0),
Point::new(2.0, 3.0),
]);
let r_left = polygon_boolean(&left, &fill, BoolOp::Intersection);
let r_right = polygon_boolean(&right, &fill, BoolOp::Intersection);
let area_left: f64 = r_left.iter().map(|p| p.area()).sum();
let area_right: f64 = r_right.iter().map(|p| p.area()).sum();
assert!(
(area_left - 1.0).abs() < 1e-6,
"left intersection: {}",
area_left
);
assert!(
(area_right - 1.0).abs() < 1e-6,
"right intersection: {}",
area_right
);
}
#[test]
fn collinear_edges_difference() {
let a = Polygon::new(vec![
Point::new(0.0, 0.0),
Point::new(2.0, 0.0),
Point::new(2.0, 1.0),
Point::new(0.0, 1.0),
]);
let b = Polygon::new(vec![
Point::new(0.5, 1.0),
Point::new(1.5, 1.0),
Point::new(1.5, 2.0),
Point::new(0.5, 2.0),
]);
let d = polygon_boolean(&a, &b, BoolOp::Difference);
let total: f64 = d.iter().map(|p| p.area()).sum();
assert!(
(total - 2.0).abs() < 1e-9,
"collinear difference: {}",
total
);
}
#[test]
fn touching_holes_stay_separate() {
use crate::section::Section;
let hole_a = Polygon::new(vec![
Point::new(0.5, 0.5),
Point::new(1.0, 0.5),
Point::new(1.0, 1.5),
Point::new(0.5, 1.5),
]); let a = Section::new(square(0.0, 0.0, 2.0), vec![hole_a]);
let hole_b = Polygon::new(vec![
Point::new(1.0, 0.5),
Point::new(1.5, 0.5),
Point::new(1.5, 1.5),
Point::new(1.0, 1.5),
]); let b = Section::new(square(0.0, 0.0, 2.0), vec![hole_b]);
let result = section_intersection(&a, &b).unwrap();
assert_eq!(result.len(), 1);
assert_eq!(
result[0].holes.len(),
2,
"touching holes must stay separate"
);
let hole_area: f64 = result[0].holes.iter().map(|h| h.area()).sum();
assert!(
(hole_area - 1.0).abs() < 1e-4,
"touching holes total area {}",
hole_area
);
assert!(
(result[0].area() - (4.0 - 1.0)).abs() < 1e-4,
"section area {}",
result[0].area()
);
}
#[test]
fn union_does_not_merge_touching_holes() {
use crate::section::Section;
let hole_a = Polygon::new(vec![
Point::new(0.5, 0.5),
Point::new(1.0, 0.5),
Point::new(1.0, 1.5),
Point::new(0.5, 1.5),
]);
let a = Section::new(square(0.0, 0.0, 2.0), vec![hole_a]);
let hole_b = Polygon::new(vec![
Point::new(1.0, 0.5),
Point::new(1.5, 0.5),
Point::new(1.5, 1.5),
Point::new(1.0, 1.5),
]);
let b = Section::new(square(0.0, 0.0, 2.0), vec![hole_b]);
let result = section_union(&a, &b).unwrap();
assert_eq!(result.len(), 1);
assert_eq!(
result[0].holes.len(),
0,
"union fills both touching holes, got {} holes",
result[0].holes.len()
);
assert!(
(result[0].area() - 4.0).abs() < 1e-4,
"union section area {}",
result[0].area()
);
}
#[test]
fn union_voids_keeps_touching_regions_separate() {
let rect = |x0: f64, x1: f64, y0: f64, y1: f64| {
Polygon::new(vec![
Point::new(x0, y0),
Point::new(x1, y0),
Point::new(x1, y1),
Point::new(x0, y1),
])
};
let a = rect(0.0, 1.0, 0.0, 1.0);
let b = rect(1.0, 2.0, 0.0, 1.0); let mut voids = vec![a, b];
union_voids(&mut voids).unwrap();
assert_eq!(voids.len(), 2, "touching holes must not be merged");
let total: f64 = voids.iter().map(|p| p.area()).sum();
assert!((total - 2.0).abs() < 1e-9, "touching total area {}", total);
}
#[test]
fn section_difference_clips_existing_hole_union() {
use crate::section::Section;
let a = Section::new(square(0.0, 0.0, 4.0), vec![square(1.0, 1.0, 2.0)]);
let b_outer = Polygon::new(vec![
Point::new(2.0, 0.0),
Point::new(4.0, 0.0),
Point::new(4.0, 4.0),
Point::new(2.0, 4.0),
]);
let b = Section::new(b_outer, vec![]);
let result = section_difference(&a, &b).unwrap();
assert_eq!(result.len(), 1);
let sec = &result[0];
assert!(
(sec.outer.area() - 8.0).abs() < 1e-6,
"piece area {}",
sec.outer.area()
);
let hole_area: f64 = sec.holes.iter().map(|h| h.area()).sum();
assert!(
(hole_area - 2.0).abs() < 1e-4,
"clipped existing hole area {}",
hole_area
);
assert_holes_within_piece(&sec.outer, &sec.holes);
assert!(
(sec.area() - 6.0).abs() < 1e-4,
"section area {}",
sec.area()
);
}
#[test]
fn nested_holes_are_rejected_by_validation() {
use crate::geometry::compound::CompoundGeometry;
use crate::section::Section;
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]);
let compound = CompoundGeometry::from_sections(&[s]);
assert!(
matches!(
compound.validate(),
Err(crate::geometry::compound::CompoundError::NestedHoles { .. })
),
"nested holes must be rejected by geometry validation"
);
let ok = Section::new(
square(0.0, 0.0, 4.0),
vec![square(0.5, 0.5, 0.5), square(3.0, 3.0, 0.5)],
);
let compound_ok = CompoundGeometry::from_sections(&[ok]);
assert!(
compound_ok.validate().is_ok(),
"non-nested holes must validate"
);
}
#[test]
fn section_difference_a_inside_b_hole_survives() {
use crate::section::Section;
let b = Section::new(square(0.0, 0.0, 10.0), vec![square(3.0, 3.0, 4.0)]);
let a = Section::new(square(4.0, 4.0, 2.0), vec![]);
let result = section_difference(&a, &b).unwrap();
assert_eq!(
result.len(),
1,
"A should survive completely inside B's hole"
);
let sec = &result[0];
assert!(
(sec.outer.area() - 4.0).abs() < 1e-6,
"piece area {}",
sec.outer.area()
);
assert_eq!(sec.holes.len(), 0, "A has no holes");
assert!(
(sec.area() - 4.0).abs() < 1e-6,
"section area {}",
sec.area()
);
}
#[test]
fn section_difference_a_inside_b_material_removed() {
use crate::section::Section;
let b = Section::new(square(0.0, 0.0, 10.0), vec![square(3.0, 3.0, 4.0)]);
let a = Section::new(square(1.0, 1.0, 2.0), vec![]);
let result = section_difference(&a, &b).unwrap();
assert_eq!(
result.len(),
0,
"A should be removed when inside B's material"
);
}
#[test]
fn section_difference_a_partial_b_hole_clipped() {
use crate::section::Section;
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();
assert_eq!(result.len(), 1, "one piece from A ∩ B.hole");
let sec = &result[0];
assert!(
(sec.outer.area() - 16.0).abs() < 1e-6,
"piece area {}",
sec.outer.area()
);
let hole_area: f64 = sec.holes.iter().map(|h| h.area()).sum();
assert!(
(hole_area - 4.0).abs() < 1e-4,
"clipped hole area {}",
hole_area
);
assert_holes_within_piece(&sec.outer, &sec.holes);
assert!(
(sec.area() - 12.0).abs() < 1e-4,
"section area {}",
sec.area()
);
}
}