Skip to main content

section_properties/geometry/
compound.rs

1use super::{Point, Polygon};
2use crate::section::Section;
3
4/// Axis selector for mirroring.
5#[derive(Debug, Clone, Copy, PartialEq, Eq)]
6pub enum Axis {
7    /// Reflect about the x-axis.
8    X,
9    /// Reflect about the y-axis.
10    Y,
11}
12
13/// A rigid or affine transformation applied to a [`Geometry`]'s vertices.
14///
15/// Mirrors `sectionproperties.pre.geometry.Transform`.
16#[derive(Debug, Clone, Copy, PartialEq)]
17pub enum Transform {
18    /// Translate by an offset (dx, dy).
19    Translate { dx: f64, dy: f64 },
20    /// Rotate counter-clockwise about the origin by `angle` radians.
21    Rotate { angle: f64 },
22    /// Uniform scale about the origin.
23    Scale { factor: f64 },
24    /// Reflect about the x-axis (y → -y).
25    MirrorX,
26    /// Reflect about the y-axis (x → -x).
27    MirrorY,
28}
29
30impl Transform {
31    /// Apply this transform to a point.
32    pub fn apply(&self, p: Point) -> Point {
33        match *self {
34            Transform::Translate { dx, dy } => Point::new(p.x + dx, p.y + dy),
35            Transform::Rotate { angle } => {
36                let (s, c) = angle.sin_cos();
37                Point::new(p.x * c - p.y * s, p.x * s + p.y * c)
38            }
39            Transform::Scale { factor } => Point::new(p.x * factor, p.y * factor),
40            Transform::MirrorX => Point::new(p.x, -p.y),
41            Transform::MirrorY => Point::new(-p.x, p.y),
42        }
43    }
44}
45
46/// A single connected region: an outer boundary plus optional holes,
47/// optionally followed by a list of transforms.
48///
49/// Mirrors `sectionproperties.pre.geometry.Geometry`.
50#[derive(Debug, Clone)]
51pub struct Geometry {
52    /// Outer boundary (normalised to CCW).
53    pub outer: Polygon,
54    /// Hole boundaries (each normalised to CW).
55    pub holes: Vec<Polygon>,
56    /// Geometric transforms applied in order (see [`Geometry`]).
57    pub transforms: Vec<Transform>,
58}
59
60impl Geometry {
61    /// Create a new geometry from an outer polygon and optional holes.
62    ///
63    /// The outer boundary is normalised to counter-clockwise orientation
64    /// and each hole to clockwise orientation, matching the convention used
65    /// by [`Section`](crate::section::Section).
66    pub fn new(mut outer: Polygon, mut holes: Vec<Polygon>) -> Self {
67        if outer.signed_area() < 0.0 {
68            outer.vertices.reverse();
69        }
70        for hole in &mut holes {
71            if hole.signed_area() > 0.0 {
72                hole.vertices.reverse();
73            }
74        }
75        Self {
76            outer,
77            holes,
78            transforms: Vec::new(),
79        }
80    }
81
82    /// Create a geometry from outer and hole point loops.
83    ///
84    /// Mirrors `Geometry.from_points(points, holes=...)`.
85    pub fn from_points(points: Vec<Point>, holes: Vec<Vec<Point>>) -> Self {
86        Self::new(
87            Polygon::new(points),
88            holes.into_iter().map(Polygon::new).collect(),
89        )
90    }
91
92    /// Convert a single-boundary [`Section`](crate::section::Section) into a geometry.
93    pub fn from_section(section: &crate::section::Section) -> Self {
94        Self::new(section.outer.clone(), section.holes.clone())
95    }
96
97    /// Rotate counter-clockwise about the origin by `angle_degrees` degrees.
98    ///
99    /// Mirrors `Geometry.rotate(angle_degrees, rot_point)`.
100    pub fn rotate(mut self, angle_degrees: f64) -> Self {
101        self.transforms.push(Transform::Rotate {
102            angle: angle_degrees.to_radians(),
103        });
104        self
105    }
106
107    /// Rotate about an explicit point.
108    pub fn rotate_about(mut self, angle_degrees: f64, point: Point) -> Self {
109        self.transforms.push(Transform::Translate {
110            dx: -point.x,
111            dy: -point.y,
112        });
113        self.transforms.push(Transform::Rotate {
114            angle: angle_degrees.to_radians(),
115        });
116        self.transforms.push(Transform::Translate {
117            dx: point.x,
118            dy: point.y,
119        });
120        self
121    }
122
123    /// Reflect about the x or y axis.
124    ///
125    /// Mirrors `Geometry.mirror(axis, mirror_point)`; here reflection is always
126    /// about the global axes.
127    pub fn mirror(mut self, axis: Axis) -> Self {
128        self.transforms.push(match axis {
129            Axis::X => Transform::MirrorX,
130            Axis::Y => Transform::MirrorY,
131        });
132        self
133    }
134
135    /// Translate by `(dx, dy)`.
136    ///
137    /// Mirrors `Geometry.shift(x_offset, y_offset)`.
138    pub fn shift(mut self, dx: f64, dy: f64) -> Self {
139        self.transforms.push(Transform::Translate { dx, dy });
140        self
141    }
142
143    /// Return a copy translated so that the centroid sits at the origin.
144    ///
145    /// Mirrors `Geometry.align_center()`.
146    pub fn align_center(&self) -> Self {
147        let c = self.centroid();
148        let mut g = self.clone();
149        g.transforms
150            .push(Transform::Translate { dx: -c.x, dy: -c.y });
151        g
152    }
153
154    /// Translate this geometry so its bounding box aligns with `other`.
155    ///
156    /// For each axis independently the nearest bounding-box edge is moved onto
157    /// the corresponding edge of `other`'s box, matching the behaviour of
158    /// `Geometry.align_to(other, pt=(0, 0))`.
159    pub fn align_to(&self, other: &Self) -> Self {
160        let (l1, r1, b1, t1) = self.bounds();
161        let (l2, r2, b2, t2) = other.bounds();
162
163        let dx = if (l1 - l2).abs() < (r1 - r2).abs() {
164            l2 - l1
165        } else {
166            r2 - r1
167        };
168        let dy = if (b1 - b2).abs() < (t1 - t2).abs() {
169            b2 - b1
170        } else {
171            t2 - t1
172        };
173
174        if dx == 0.0 && dy == 0.0 {
175            return self.clone();
176        }
177        let mut g = self.clone();
178        g.transforms.push(Transform::Translate { dx, dy });
179        g
180    }
181
182    /// Offset the geometry by `amount` using mitred corners.
183    ///
184    /// Positive amounts grow the geometry, negative amounts shrink it. The
185    /// outer boundary is offset by `+amount` and each hole by `-amount`.
186    /// Returns `None` if any boundary degenerates.
187    ///
188    /// Mirrors `Geometry.offset(amount)`.
189    pub fn offset(&self, amount: f64) -> Option<Self> {
190        let outer = self.apply_transforms().outer.offset(amount)?;
191        let mut holes = Vec::with_capacity(self.holes.len());
192        for h in &self.holes {
193            holes.push(h.offset(-amount)?);
194        }
195        Some(Self {
196            outer,
197            holes,
198            transforms: Vec::new(),
199        })
200    }
201
202    /// Split the geometry into two halves either side of the line through
203    /// points `a` and `b`.
204    ///
205    /// Mirrors `Geometry.split_section(point_a, point_b)`. Returns
206    /// `(below, above)`; each side is `None` when empty.
207    pub fn split_section(&self, a: Point, b: Point) -> (Option<Geometry>, Option<Geometry>) {
208        let g = self.apply_transforms();
209        let (below_outer, above_outer) = g.outer.split_by_line(a, b);
210
211        // Clip each hole and attach the matching half to its side.
212        let mut below_holes = Vec::new();
213        let mut above_holes = Vec::new();
214        for h in &g.holes {
215            let (hb, ha) = h.split_by_line(a, b);
216            if let Some(hb) = hb {
217                below_holes.push(hb);
218            }
219            if let Some(ha) = ha {
220                above_holes.push(ha);
221            }
222        }
223
224        let below = below_outer.map(|o| Geometry {
225            outer: o,
226            holes: below_holes,
227            transforms: Vec::new(),
228        });
229        let above = above_outer.map(|o| Geometry {
230            outer: o,
231            holes: above_holes,
232            transforms: Vec::new(),
233        });
234        (below, above)
235    }
236    /// Boolean union with `other`.
237    ///
238    /// Mirrors `Geometry | other` (shapely `union`). Returns a
239    /// `CompoundGeometry` that can represent multiple disconnected regions.
240    pub fn union(&self, other: &Self) -> Result<CompoundGeometry, super::boolean::BooleanError> {
241        self.boolean_op(other, super::boolean::BoolOp::Union)
242    }
243
244    /// Boolean intersection with `other`.
245    ///
246    /// Mirrors `Geometry & other` (shapely `intersection`). Returns a
247    /// `CompoundGeometry` that can represent multiple disconnected regions.
248    pub fn intersection(
249        &self,
250        other: &Self,
251    ) -> Result<CompoundGeometry, super::boolean::BooleanError> {
252        self.boolean_op(other, super::boolean::BoolOp::Intersection)
253    }
254
255    /// Boolean difference: this geometry minus `other`.
256    ///
257    /// Mirrors `Geometry - other` (shapely `difference`). Returns a
258    /// `CompoundGeometry` that can represent multiple disconnected regions.
259    pub fn subtract(&self, other: &Self) -> Result<CompoundGeometry, super::boolean::BooleanError> {
260        self.boolean_op(other, super::boolean::BoolOp::Difference)
261    }
262
263    fn boolean_op(
264        &self,
265        other: &Self,
266        op: super::boolean::BoolOp,
267    ) -> Result<CompoundGeometry, super::boolean::BooleanError> {
268        let a_trans = self.apply_transforms();
269        let b_trans = other.apply_transforms();
270        let a = Section::new(a_trans.outer, a_trans.holes);
271        let b = Section::new(b_trans.outer, b_trans.holes);
272
273        let results = match op {
274            super::boolean::BoolOp::Union => super::boolean::section_union(&a, &b)?,
275            super::boolean::BoolOp::Intersection => super::boolean::section_intersection(&a, &b)?,
276            super::boolean::BoolOp::Difference => super::boolean::section_difference(&a, &b)?,
277        };
278
279        let geometries = results
280            .into_iter()
281            .map(|sec| Geometry::new(sec.outer, sec.holes))
282            .collect();
283        Ok(CompoundGeometry::new(geometries))
284    }
285
286    /// Return a copy of this geometry with the transforms applied to all vertices.
287    ///
288    /// Transforms are applied in the order they appear in [`Geometry::transforms`].
289    pub fn apply_transforms(&self) -> Self {
290        if self.transforms.is_empty() {
291            return self.clone();
292        }
293        let map = |poly: &Polygon| -> Polygon {
294            Polygon::new(
295                poly.vertices
296                    .iter()
297                    .map(|&v| self.transforms.iter().fold(v, |p, t| t.apply(p)))
298                    .collect(),
299            )
300        };
301        Self {
302            outer: map(&self.outer),
303            holes: self.holes.iter().map(map).collect(),
304            transforms: Vec::new(),
305        }
306    }
307
308    /// Net area of the geometry (outer minus holes), after applying transforms.
309    pub fn area(&self) -> f64 {
310        let g = if self.transforms.is_empty() {
311            self
312        } else {
313            &self.apply_transforms()
314        };
315        let mut a = g.outer.area();
316        for h in &g.holes {
317            a -= h.area();
318        }
319        a
320    }
321
322    /// Centroid of the geometry using the composite area formula.
323    pub fn centroid(&self) -> Point {
324        let g = if self.transforms.is_empty() {
325            self
326        } else {
327            &self.apply_transforms()
328        };
329        let mut sum_x = 0.0;
330        let mut sum_y = 0.0;
331        let mut total = 0.0;
332
333        let outer_c = g.outer.centroid();
334        let outer_a = g.outer.area();
335        sum_x += outer_c.x * outer_a;
336        sum_y += outer_c.y * outer_a;
337        total += outer_a;
338
339        for h in &g.holes {
340            let a = h.area();
341            let c = h.centroid();
342            sum_x -= c.x * a;
343            sum_y -= c.y * a;
344            total -= a;
345        }
346
347        Point::new(sum_x / total, sum_y / total)
348    }
349
350    /// Bounding box of the geometry: (min_x, max_x, min_y, max_y).
351    pub fn bounds(&self) -> (f64, f64, f64, f64) {
352        let g = if self.transforms.is_empty() {
353            self
354        } else {
355            &self.apply_transforms()
356        };
357        let mut min_x = f64::INFINITY;
358        let mut max_x = f64::NEG_INFINITY;
359        let mut min_y = f64::INFINITY;
360        let mut max_y = f64::NEG_INFINITY;
361        for poly in std::iter::once(&g.outer).chain(g.holes.iter()) {
362            for v in &poly.vertices {
363                min_x = min_x.min(v.x);
364                max_x = max_x.max(v.x);
365                min_y = min_y.min(v.y);
366                max_y = max_y.max(v.y);
367            }
368        }
369        (min_x, max_x, min_y, max_y)
370    }
371
372    /// Perimeter of the geometry (outer + holes), after applying transforms.
373    pub fn perimeter(&self) -> f64 {
374        let g = if self.transforms.is_empty() {
375            self
376        } else {
377            &self.apply_transforms()
378        };
379        g.outer.perimeter() + g.holes.iter().map(|h| h.perimeter()).sum::<f64>()
380    }
381}
382
383/// A collection of independent regions, e.g. two parallel rectangles,
384/// an angle bolted to a plate, or a built-up girder.
385///
386/// Mirrors `sectionproperties.pre.geometry.CompoundGeometry`.
387///
388/// # Invariant
389/// Regions are assumed to be **material-disjoint**: no part of one region's
390/// material may overlap another region's material. Properties (`area`,
391/// inertia, ...) are computed by simple summation, which is only correct
392/// under this assumption.
393///
394/// Use [`CompoundGeometry::validate`] to check the invariant, and
395/// [`CompoundGeometry::dissolved_outer_only`] to merge overlapping inputs into a valid
396/// compound.
397#[derive(Debug, Clone)]
398pub struct CompoundGeometry {
399    /// The individual regions that make up the compound section.
400    pub geometries: Vec<Geometry>,
401}
402
403/// Errors from compound-geometry topology validation.
404#[derive(Debug, Clone, PartialEq)]
405pub enum CompoundError {
406    /// Material of region `a` overlaps material of region `b`.
407    OverlappingRegions { a: usize, b: usize },
408    /// Hole `hole` of `region` is not fully inside the region's outer
409    /// boundary.
410    HoleNotInsideOuter { region: usize, hole: usize },
411    /// Hole `b` of `region` is nested inside hole `a` (a hole-within-a-hole).
412    /// A single region cannot represent an island of material inside a void,
413    /// so nested holes are rejected.
414    NestedHoles { region: usize, a: usize, b: usize },
415}
416
417impl std::fmt::Display for CompoundError {
418    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
419        match self {
420            CompoundError::OverlappingRegions { a, b } => {
421                write!(f, "regions {a} and {b} have overlapping material")
422            }
423            CompoundError::HoleNotInsideOuter { region, hole } => {
424                write!(
425                    f,
426                    "hole {hole} of region {region} is not fully inside its outer boundary"
427                )
428            }
429            CompoundError::NestedHoles { region, a, b } => {
430                write!(
431                    f,
432                    "region {region} has hole {b} nested inside hole {a} (holes cannot nest)"
433                )
434            }
435        }
436    }
437}
438
439impl std::error::Error for CompoundError {}
440
441/// Bounding-box relation between two polygons for quick rejection.
442#[derive(Debug, Clone, Copy, PartialEq, Eq)]
443enum BBoxRelation {
444    /// No overlap, not even touching
445    Disjoint,
446    /// Touching at boundary but no area overlap
447    Touch,
448    /// Positive area overlap
449    Overlap,
450}
451
452/// Quick outer-boundary bounding-box relation test for two polygons.
453/// Returns Disjoint if separated, Touch if only boundaries touch, Overlap if interiors overlap.
454/// Note: This checks OUTER boundaries only, not material (outer minus holes).
455fn outer_bbox_relation(a: &Polygon, b: &Polygon) -> BBoxRelation {
456    let bbox = |pts: &[Point]| {
457        pts.iter().fold(
458            (
459                f64::INFINITY,
460                f64::NEG_INFINITY,
461                f64::INFINITY,
462                f64::NEG_INFINITY,
463            ),
464            |(l, r, b, t), p| (l.min(p.x), r.max(p.x), b.min(p.y), t.max(p.y)),
465        )
466    };
467    let (al, ar, ab, at) = bbox(&a.vertices);
468    let (bl, br, bb, bt) = bbox(&b.vertices);
469
470    // Check for disjoint (no overlap, not even touching)
471    if ar < bl || br < al || at < bb || bt < ab {
472        return BBoxRelation::Disjoint;
473    }
474
475    // Check for touch (boundaries touch but interiors don't overlap)
476    // This means at least one dimension has equality at the boundary
477    let x_touch = ar == bl || br == al;
478    let y_touch = at == bb || bt == ab;
479    if x_touch || y_touch {
480        return BBoxRelation::Touch;
481    }
482
483    // Otherwise there is positive area overlap
484    BBoxRelation::Overlap
485}
486
487impl CompoundGeometry {
488    /// Create a compound geometry from its constituent regions.
489    ///
490    /// # Invariant
491    /// The caller guarantees that region materials are **disjoint**.
492    /// Overlapping inputs silently double-count area/inertia in property
493    /// computations. Use [`CompoundGeometry::validate`] to check, or
494    /// [`CompoundGeometry::dissolved_outer_only`] to merge overlapping inputs.
495    pub fn new(geometries: Vec<Geometry>) -> Self {
496        Self { geometries }
497    }
498
499    /// Validating constructor: returns an error if any two regions have
500    /// overlapping material or a hole escapes its outer boundary.
501    pub fn new_validated(geometries: Vec<Geometry>) -> Result<Self, CompoundError> {
502        let compound = Self { geometries };
503        compound.validate()?;
504        Ok(compound)
505    }
506
507    /// Merge overlapping inputs into a valid (material-disjoint) compound by
508    /// dissolving overlaps with the boolean union. **Holes are dropped during
509    /// dissolution** (the merged outline is exact; re-derive holes afterwards
510    /// if required). This is a union of outer boundaries only.
511    ///
512    /// Prefer [`Self::dissolved_outer_only`] for explicit naming.
513    #[deprecated(
514        since = "0.1.0",
515        note = "Use dissolved_outer_only() for explicit naming; holes are dropped"
516    )]
517    pub fn dissolved(geometries: Vec<Geometry>) -> Self {
518        Self::dissolved_outer_only(geometries)
519    }
520
521    /// Merge overlapping inputs into a valid (material-disjoint) compound by
522    /// dissolving overlaps with the boolean union. **Holes are dropped** –
523    /// only outer boundaries are united. This is a union of outer boundaries
524    /// only; holes must be re-derived afterwards if required.
525    pub fn dissolved_outer_only(geometries: Vec<Geometry>) -> Self {
526        use super::boolean::{BoolOp, polygon_boolean};
527
528        let mut acc: Vec<Polygon> = geometries
529            .iter()
530            .map(|g| g.apply_transforms().outer)
531            .collect();
532
533        loop {
534            let mut merged: Option<(usize, usize, Vec<Polygon>)> = None;
535            'outer: for i in 0..acc.len() {
536                for j in (i + 1)..acc.len() {
537                    if matches!(
538                        outer_bbox_relation(&acc[i], &acc[j]),
539                        BBoxRelation::Disjoint
540                    ) {
541                        continue;
542                    }
543                    let u = polygon_boolean(&acc[i], &acc[j], BoolOp::Union);
544                    let u_area: f64 = u.iter().map(|p| p.area().abs()).sum();
545                    let sum_area = acc[i].area().abs() + acc[j].area().abs();
546                    if u_area < sum_area - 1e-9 {
547                        merged = Some((i, j, u));
548                        break 'outer;
549                    }
550                }
551            }
552            match merged {
553                Some((i, j, u)) => {
554                    let last = acc.len() - 1;
555                    acc[j] = acc[last].clone();
556                    acc.swap_remove(last);
557                    acc.splice(i..i + 1, u);
558                }
559                None => break,
560            }
561        }
562
563        let geometries = acc
564            .into_iter()
565            .map(|p| Geometry {
566                outer: p,
567                holes: Vec::new(),
568                transforms: Vec::new(),
569            })
570            .collect();
571        Self { geometries }
572    }
573
574    /// Check the material-disjoint invariant.
575    ///
576    /// * every hole must lie fully inside its own outer boundary,
577    /// * no two regions may claim the same material point (verified with
578    ///   deterministic edge–edge and containment checks).
579    pub fn validate(&self) -> Result<(), CompoundError> {
580        // Hole containment within its own outer boundary.
581        for (ri, g) in self.geometries.iter().enumerate() {
582            let g = g.apply_transforms();
583            for (hi, hole) in g.holes.iter().enumerate() {
584                // 1. All hole vertices must be inside outer.
585                let vertices_inside = hole.vertices.iter().all(|v| g.outer.contains_point(*v));
586                if !vertices_inside {
587                    return Err(CompoundError::HoleNotInsideOuter {
588                        region: ri,
589                        hole: hi,
590                    });
591                }
592                // 2. No hole edge may cross outer boundary edge.
593                for i in 0..hole.vertices.len() {
594                    let h1 = hole.vertices[i];
595                    let h2 = hole.vertices[(i + 1) % hole.vertices.len()];
596                    for j in 0..g.outer.vertices.len() {
597                        let o1 = g.outer.vertices[j];
598                        let o2 = g.outer.vertices[(j + 1) % g.outer.vertices.len()];
599                        if segments_interact(h1, h2, o1, o2) {
600                            return Err(CompoundError::HoleNotInsideOuter {
601                                region: ri,
602                                hole: hi,
603                            });
604                        }
605                    }
606                }
607            }
608
609            // 3. No hole may be nested inside another hole of the same region.
610            // A hole-within-a-hole is an island of material inside a void, which
611            // a single region (one outer + holes) cannot represent.
612            for a in 0..g.holes.len() {
613                for b in (a + 1)..g.holes.len() {
614                    let ha = &g.holes[a];
615                    let hb = &g.holes[b];
616                    let a_contains_b = hb.vertices.iter().all(|v| ha.contains_point(*v));
617                    let b_contains_a = ha.vertices.iter().all(|v| hb.contains_point(*v));
618                    if a_contains_b || b_contains_a {
619                        return Err(CompoundError::NestedHoles { region: ri, a, b });
620                    }
621                }
622            }
623        }
624
625        // Cross-region material overlap via deterministic checks.
626        //
627        // For each pair of regions, we verify the "material-disjoint"
628        // invariant by checking:
629        //  1. Edge–edge intersections between outer boundaries.
630        //  2. Vertex containment: any vertex of region A inside region B's
631        //     material (outer minus holes) or vice versa.
632        //  3. Full containment: one outer fully inside the other, with the
633        //     intersection not fully absorbed by holes.
634        let n = self.geometries.len();
635        if n < 2 {
636            return Ok(());
637        }
638
639        let applied: Vec<Geometry> = self
640            .geometries
641            .iter()
642            .map(|g| g.apply_transforms())
643            .collect();
644
645        for i in 0..n {
646            for j in (i + 1)..n {
647                let gi = &applied[i];
648                let gj = &applied[j];
649                if regions_overlap_deterministic(gi, gj) {
650                    return Err(CompoundError::OverlappingRegions { a: i, b: j });
651                }
652            }
653        }
654        Ok(())
655    }
656
657    /// Build a compound geometry from a slice of [`Section`](crate::section::Section).
658    pub fn from_sections(sections: &[crate::section::Section]) -> Self {
659        Self {
660            geometries: sections.iter().map(Geometry::from_section).collect(),
661        }
662    }
663
664    /// Boolean operation across compound geometries.
665    ///
666    /// Mirrors `CompoundGeometry.combine(other, operation)`:
667    /// - Union: all regions of both compounds unioned pairwise into one
668    ///   accumulated set (dissolves internal overlaps).
669    /// - Intersection: every region pair intersected, keeping non-empty
670    ///   results.
671    /// - Difference: each region of `self` reduced by every region of
672    ///   `other` in sequence.
673    pub fn boolean(
674        &self,
675        other: &Self,
676        op: super::boolean::BoolOp,
677    ) -> Result<Self, super::boolean::BooleanError> {
678        match op {
679            super::boolean::BoolOp::Intersection => {
680                // Intersection: pairwise intersection of all region pairs
681                // Use Geometry::boolean_op which properly uses section_intersection
682                // and preserves holes
683                let mut out = Vec::new();
684                for ga in &self.geometries {
685                    for gb in &other.geometries {
686                        let inter = ga.boolean_op(gb, op)?;
687                        out.extend(inter.geometries);
688                    }
689                }
690                Ok(Self { geometries: out })
691            }
692            super::boolean::BoolOp::Difference => {
693                // Start with all self regions
694                let mut current: Vec<Geometry> = self.geometries.clone();
695
696                // Subtract each other region from all current regions
697                for gb in &other.geometries {
698                    let mut next = Vec::new();
699                    for ga in &current {
700                        let diff = ga.boolean_op(gb, op)?;
701                        next.extend(diff.geometries);
702                    }
703                    current = next;
704                    if current.is_empty() {
705                        break;
706                    }
707                }
708                let geometries = current
709                    .into_iter()
710                    .map(|g| Geometry {
711                        outer: g.outer,
712                        holes: g.holes,
713                        transforms: Vec::new(),
714                    })
715                    .collect();
716                Ok(Self { geometries })
717            }
718            super::boolean::BoolOp::Union => {
719                // Collect every region from both compounds
720                let mut acc: Vec<Geometry> = self
721                    .geometries
722                    .iter()
723                    .chain(other.geometries.iter())
724                    .cloned()
725                    .collect();
726
727                // Merge overlapping regions iteratively
728                loop {
729                    let mut merged: Option<(usize, usize, Vec<Geometry>)> = None;
730                    'outer: for i in 0..acc.len() {
731                        for j in (i + 1)..acc.len() {
732                            if matches!(
733                                outer_bbox_relation(&acc[i].outer, &acc[j].outer),
734                                BBoxRelation::Disjoint
735                            ) {
736                                continue;
737                            }
738                            let union_result =
739                                acc[i].boolean_op(&acc[j], super::boolean::BoolOp::Union)?;
740                            // Only merge if the union actually produced a SINGLE region.
741                            // If it returns 2+ regions, the inputs were material-disjoint
742                            // (e.g. same outer bbox but holes isolate materials) and
743                            // merging would not reduce the set — it would cause an infinite loop.
744                            if union_result.geometries.len() == 1 {
745                                merged = Some((i, j, union_result.geometries));
746                                break 'outer;
747                            }
748                        }
749                    }
750                    match merged {
751                        Some((i, j, new_geometries)) => {
752                            let last = acc.len() - 1;
753                            acc[j] = acc[last].clone();
754                            acc.swap_remove(last);
755                            acc.splice(i..i + 1, new_geometries);
756                        }
757                        None => break,
758                    }
759                }
760
761                let geometries = acc;
762                Ok(Self { geometries })
763            }
764        }
765    }
766
767    /// Boolean union with `other`.
768    pub fn union(&self, other: &Self) -> Result<Self, super::boolean::BooleanError> {
769        self.boolean(other, super::boolean::BoolOp::Union)
770    }
771
772    /// Boolean intersection with `other`.
773    pub fn intersection(&self, other: &Self) -> Result<Self, super::boolean::BooleanError> {
774        self.boolean(other, super::boolean::BoolOp::Intersection)
775    }
776
777    /// Boolean difference: this compound minus `other`.
778    pub fn subtract(&self, other: &Self) -> Result<Self, super::boolean::BooleanError> {
779        self.boolean(other, super::boolean::BoolOp::Difference)
780    }
781    /// Total net area across all regions.
782    pub fn area(&self) -> f64 {
783        self.geometries.iter().map(|g| g.area()).sum()
784    }
785
786    /// Centroid of the compound section via the composite area formula.
787    pub fn centroid(&self) -> Point {
788        let mut sum_x = 0.0;
789        let mut sum_y = 0.0;
790        let mut total = 0.0;
791        for g in &self.geometries {
792            let a = g.area();
793            let c = g.centroid();
794            sum_x += c.x * a;
795            sum_y += c.y * a;
796            total += a;
797        }
798        assert!(
799            total.abs() > f64::EPSILON,
800            "CompoundGeometry has zero total area"
801        );
802        Point::new(sum_x / total, sum_y / total)
803    }
804
805    /// Bounding box of the compound geometry: (min_x, max_x, min_y, max_y).
806    pub fn bounds(&self) -> (f64, f64, f64, f64) {
807        let mut min_x = f64::INFINITY;
808        let mut max_x = f64::NEG_INFINITY;
809        let mut min_y = f64::INFINITY;
810        let mut max_y = f64::NEG_INFINITY;
811        for g in &self.geometries {
812            let (l, r, b, t) = g.bounds();
813            min_x = min_x.min(l);
814            max_x = max_x.max(r);
815            min_y = min_y.min(b);
816            max_y = max_y.max(t);
817        }
818        (min_x, max_x, min_y, max_y)
819    }
820
821    /// Total perimeter across all regions (outer + holes).
822    pub fn perimeter(&self) -> f64 {
823        self.geometries.iter().map(|g| g.perimeter()).sum()
824    }
825
826    /// Return all polygons (outer first, then holes) across every region,
827    /// with any transforms already applied.
828    pub fn polygons(&self) -> Vec<Polygon> {
829        let mut out = Vec::new();
830        for g in &self.geometries {
831            let g = g.apply_transforms();
832            out.push(g.outer);
833            out.extend(g.holes);
834        }
835        out
836    }
837}
838
839/// Convert a [`Section`](crate::section::Section) into a single-geometry compound.
840impl From<crate::section::Section> for CompoundGeometry {
841    fn from(section: crate::section::Section) -> Self {
842        Self::new(vec![Geometry::new(section.outer, section.holes)])
843    }
844}
845
846/// Deterministic check whether two regions share any material area.
847///
848/// A region's material is its outer boundary minus its holes.
849/// Two regions overlap if and only if there exists a point that lies in
850/// both materials.  This is checked by:
851///
852/// 1. **Edge–edge intersection** – if any outer-boundary edge of `a`
853///    crosses any outer-boundary edge of `b`, the interiors overlap.
854/// 2. **Vertex containment** – if a vertex of one outer lies inside the
855///    other region's material (outer minus holes), there is overlap.
856/// 3. **Full containment** – if all vertices of one outer lie inside the
857///    other outer, the intersection polygon is non-empty *and* not
858///    entirely absorbed by the union of all holes.
859fn intersection_point(a1: Point, a2: Point, b1: Point, b2: Point) -> Point {
860    // Line segment intersection using parametric form.
861    // a1 + t*(a2-a1) = b1 + u*(b2-b1)
862    let dx1 = a2.x - a1.x;
863    let dy1 = a2.y - a1.y;
864    let dx2 = b2.x - b1.x;
865    let dy2 = b2.y - b1.y;
866
867    let det = dx1 * dy2 - dy1 * dx2;
868    if det.abs() < 1e-12 {
869        // Parallel or collinear - compute midpoint of overlapping interval.
870        // Project all endpoints onto the line (a1->a2) and find overlap.
871        // Use parameter t along segment a1-a2.
872        let len2 = dx1 * dx1 + dy1 * dy1;
873        if len2 < 1e-24 {
874            // Degenerate segment - return a1
875            return a1;
876        }
877        // Project b1 and b2 onto a1-a2 line
878        let t_b1 = ((b1.x - a1.x) * dx1 + (b1.y - a1.y) * dy1) / len2;
879        let t_b2 = ((b2.x - a1.x) * dx1 + (b2.y - a1.y) * dy1) / len2;
880        // Segment a is [0, 1], segment b is [t_b1, t_b2] (may be reversed)
881        let b_lo = t_b1.min(t_b2);
882        let b_hi = t_b1.max(t_b2);
883        // Overlap interval
884        let lo = 0.0f64.max(b_lo);
885        let hi = 1.0f64.min(b_hi);
886        if lo <= hi {
887            // Overlap exists - return midpoint of overlap
888            let t_mid = (lo + hi) * 0.5;
889            return Point::new(a1.x + t_mid * dx1, a1.y + t_mid * dy1);
890        }
891        // No overlap - return midpoint of a (shouldn't happen if segments_interact returned true)
892        return Point::new((a1.x + a2.x) * 0.5, (a1.y + a2.y) * 0.5);
893    }
894
895    let t = ((b1.x - a1.x) * dy2 - (b1.y - a1.y) * dx2) / det;
896    // Clamp to segment
897    let t = t.clamp(0.0, 1.0);
898    Point::new(a1.x + t * dx1, a1.y + t * dy1)
899}
900
901fn regions_overlap_deterministic(a: &Geometry, b: &Geometry) -> bool {
902    let a_outer = &a.outer;
903    let b_outer = &b.outer;
904
905    // 1. Edge–edge intersection between the two outer boundaries.
906    //    Only counts if the intersection point is in the MATERIAL
907    //    of both regions (not inside any hole).
908    for i in 0..a_outer.vertices.len() {
909        let a1 = a_outer.vertices[i];
910        let a2 = a_outer.vertices[(i + 1) % a_outer.vertices.len()];
911        for j in 0..b_outer.vertices.len() {
912            let b1 = b_outer.vertices[j];
913            let b2 = b_outer.vertices[(j + 1) % b_outer.vertices.len()];
914            if segments_overlap(a1, a2, b1, b2) {
915                // Compute a representative point on the overlap.
916                // Use the midpoint of the overlapping segment or the
917                // intersection point itself.
918                let pt = intersection_point(a1, a2, b1, b2);
919                // Check if this point is in material of BOTH regions
920                let in_a_material =
921                    a_outer.contains_point(pt) && !a.holes.iter().any(|h| h.contains_point(pt));
922                let in_b_material =
923                    b_outer.contains_point(pt) && !b.holes.iter().any(|h| h.contains_point(pt));
924                if in_a_material && in_b_material {
925                    return true;
926                }
927            }
928        }
929    }
930
931    // 2. Vertex containment: any vertex of `a` inside `b`'s material?
932    for v in &a_outer.vertices {
933        if b_outer.contains_point(*v) && !b.holes.iter().any(|h| h.contains_point(*v)) {
934            return true;
935        }
936    }
937    // Any vertex of `b` inside `a`'s material?
938    for v in &b_outer.vertices {
939        if a_outer.contains_point(*v) && !a.holes.iter().any(|h| h.contains_point(*v)) {
940            return true;
941        }
942    }
943
944    // 3. Full containment: one outer fully contains the other, but no
945    //    vertex lies on the wrong side.  In this case the two outers
946    //    overlap as regions, but we must verify the overlap is not
947    //    entirely absorbed by holes.
948    let a_in_b = a_outer.vertices.iter().all(|v| b_outer.contains_point(*v));
949    let b_in_a = b_outer.vertices.iter().all(|v| a_outer.contains_point(*v));
950
951    if a_in_b || b_in_a {
952        // Compute the boolean intersection of the two outer polygons.
953        let inter =
954            super::boolean::polygon_boolean(a_outer, b_outer, super::boolean::BoolOp::Intersection);
955        if inter.is_empty() {
956            return false;
957        }
958        // Subtract every hole from both regions.  If anything survives, the
959        // regions overlap in material.
960        let mut remaining = inter;
961        for hole in a.holes.iter().chain(b.holes.iter()) {
962            let mut next = Vec::new();
963            for p in &remaining {
964                let diff =
965                    super::boolean::polygon_boolean(p, hole, super::boolean::BoolOp::Difference);
966                next.extend(diff);
967            }
968            remaining = next;
969            if remaining.is_empty() {
970                break;
971            }
972        }
973        return !remaining.is_empty();
974    }
975
976    false
977}
978
979/// Segment-segment relation for robust topology checks.
980#[derive(Debug, Clone, Copy, PartialEq)]
981enum SegmentRelation {
982    /// No intersection (disjoint, no shared points)
983    Disjoint,
984    /// Touching at a single endpoint (shared vertex)
985    Touch,
986    /// Proper interior intersection (crossing)
987    ProperCross,
988    /// Collinear and overlapping with positive-length intersection
989    CollinearOverlap,
990}
991
992/// Determine the topological relation between two segments A1→A2 and B1→B2.
993/// Uses orientation tests with epsilon for numerical robustness.
994fn segment_relation(a1: Point, a2: Point, b1: Point, b2: Point) -> SegmentRelation {
995    const EPS: f64 = 1e-12;
996
997    fn orient(p: Point, q: Point, r: Point) -> f64 {
998        (q.x - p.x) * (r.y - p.y) - (q.y - p.y) * (r.x - p.x)
999    }
1000
1001    fn on_segment(p: Point, q: Point, r: Point) -> bool {
1002        // q lies on segment pr (assuming collinear)
1003        q.x >= p.x.min(r.x) - EPS
1004            && q.x <= p.x.max(r.x) + EPS
1005            && q.y >= p.y.min(r.y) - EPS
1006            && q.y <= p.y.max(r.y) + EPS
1007    }
1008
1009    fn points_equal(p: Point, q: Point) -> bool {
1010        (p.x - q.x).abs() <= EPS && (p.y - q.y).abs() <= EPS
1011    }
1012
1013    let o1 = orient(a1, a2, b1);
1014    let o2 = orient(a1, a2, b2);
1015    let o3 = orient(b1, b2, a1);
1016    let o4 = orient(b1, b2, a2);
1017
1018    // General case: proper crossing (endpoints straddle each other's line)
1019    let o1_pos = o1 > EPS;
1020    let o1_neg = o1 < -EPS;
1021    let o2_pos = o2 > EPS;
1022    let o2_neg = o2 < -EPS;
1023    let o3_pos = o3 > EPS;
1024    let o3_neg = o3 < -EPS;
1025    let o4_pos = o4 > EPS;
1026    let o4_neg = o4 < -EPS;
1027
1028    if (o1_pos != o2_pos || o1_neg != o2_neg) && (o3_pos != o4_pos || o3_neg != o4_neg) {
1029        return SegmentRelation::ProperCross;
1030    }
1031
1032    // Special cases: check for collinear overlap
1033    // All orientations are near zero -> segments are collinear
1034    if o1.abs() <= EPS && o2.abs() <= EPS && o3.abs() <= EPS && o4.abs() <= EPS {
1035        // Check if projections on x or y overlap
1036        let a_min_x = a1.x.min(a2.x);
1037        let a_max_x = a1.x.max(a2.x);
1038        let b_min_x = b1.x.min(b2.x);
1039        let b_max_x = b1.x.max(b2.x);
1040        let a_min_y = a1.y.min(a2.y);
1041        let a_max_y = a1.y.max(a2.y);
1042        let b_min_y = b1.y.min(b2.y);
1043        let b_max_y = b1.y.max(b2.y);
1044
1045        let overlap_x = a_max_x >= b_min_x - EPS && b_max_x >= a_min_x - EPS;
1046        let overlap_y = a_max_y >= b_min_y - EPS && b_max_y >= a_min_y - EPS;
1047
1048        if overlap_x && overlap_y {
1049            // They overlap - now distinguish between Touch (point contact)
1050            // and CollinearOverlap (positive-length overlap)
1051            // For collinear segments, overlap length is the intersection of intervals
1052            // on the line. We can compute the overlap length parameter.
1053            // If the overlap is just a single point, it's Touch.
1054            let len_a2 = (a2.x - a1.x).powi(2) + (a2.y - a1.y).powi(2);
1055            let _len_b2 = (b2.x - b1.x).powi(2) + (b2.y - b1.y).powi(2);
1056
1057            // Project b1, b2 onto segment a's line (parameter t in [0,1])
1058            let t_b1 = if len_a2 > EPS {
1059                ((b1.x - a1.x) * (a2.x - a1.x) + (b1.y - a1.y) * (a2.y - a1.y)) / len_a2
1060            } else {
1061                0.0
1062            };
1063            let t_b2 = if len_a2 > EPS {
1064                ((b2.x - a1.x) * (a2.x - a1.x) + (b2.y - a1.y) * (a2.y - a1.y)) / len_a2
1065            } else {
1066                0.0
1067            };
1068
1069            let b_lo = t_b1.min(t_b2);
1070            let b_hi = t_b1.max(t_b2);
1071
1072            // Overlap interval on segment a's parameter space
1073            let lo = 0.0f64.max(b_lo);
1074            let hi = 1.0f64.min(b_hi);
1075
1076            if lo <= hi {
1077                let overlap_len = (hi - lo) * len_a2.sqrt();
1078                if overlap_len > EPS {
1079                    return SegmentRelation::CollinearOverlap;
1080                } else {
1081                    // Overlap is just a point
1082                    return SegmentRelation::Touch;
1083                }
1084            }
1085        }
1086        return SegmentRelation::Disjoint;
1087    }
1088
1089    // Check for endpoint touching (shared vertex) - this is Touch, not Disjoint
1090    // b1 on a
1091    if o1.abs() <= EPS && on_segment(a1, b1, a2) {
1092        return if points_equal(b1, a1) || points_equal(b1, a2) {
1093            SegmentRelation::Touch
1094        } else {
1095            SegmentRelation::Disjoint
1096        };
1097    }
1098    // b2 on a
1099    if o2.abs() <= EPS && on_segment(a1, b2, a2) {
1100        return if points_equal(b2, a1) || points_equal(b2, a2) {
1101            SegmentRelation::Touch
1102        } else {
1103            SegmentRelation::Disjoint
1104        };
1105    }
1106    // a1 on b
1107    if o3.abs() <= EPS && on_segment(b1, a1, b2) {
1108        return if points_equal(a1, b1) || points_equal(a1, b2) {
1109            SegmentRelation::Touch
1110        } else {
1111            SegmentRelation::Disjoint
1112        };
1113    }
1114    // a2 on b
1115    if o4.abs() <= EPS && on_segment(b1, a2, b2) {
1116        return if points_equal(a2, b1) || points_equal(a2, b2) {
1117            SegmentRelation::Touch
1118        } else {
1119            SegmentRelation::Disjoint
1120        };
1121    }
1122
1123    SegmentRelation::Disjoint
1124}
1125
1126/// Check if two segments have any topological interaction (crossing, touching, or collinear overlap).
1127/// Returns true for ProperCross, CollinearOverlap, and Touch.
1128pub fn segments_interact(a1: Point, a2: Point, b1: Point, b2: Point) -> bool {
1129    !matches!(segment_relation(a1, a2, b1, b2), SegmentRelation::Disjoint)
1130}
1131
1132/// Check if two segments have positive-length overlap or proper crossing (area overlap).
1133/// Returns true for ProperCross and CollinearOverlap only.
1134/// Returns false for Touch (endpoint contact) and Disjoint.
1135pub fn segments_overlap(a1: Point, a2: Point, b1: Point, b2: Point) -> bool {
1136    matches!(
1137        segment_relation(a1, a2, b1, b2),
1138        SegmentRelation::ProperCross | SegmentRelation::CollinearOverlap
1139    )
1140}
1141
1142#[cfg(test)]
1143mod tests {
1144    use super::{Point, SegmentRelation, segment_relation, segments_interact, segments_overlap};
1145
1146    #[test]
1147    fn segment_relation_proper_cross() {
1148        // Crossing segments
1149        let a1 = Point::new(0.0, 0.0);
1150        let a2 = Point::new(10.0, 10.0);
1151        let b1 = Point::new(0.0, 10.0);
1152        let b2 = Point::new(10.0, 0.0);
1153        assert_eq!(
1154            segment_relation(a1, a2, b1, b2),
1155            SegmentRelation::ProperCross
1156        );
1157        assert!(segments_overlap(a1, a2, b1, b2));
1158        assert!(segments_interact(a1, a2, b1, b2));
1159    }
1160
1161    #[test]
1162    fn segment_relation_touch_endpoint() {
1163        // Segments touching at endpoint
1164        let a1 = Point::new(0.0, 0.0);
1165        let a2 = Point::new(5.0, 0.0);
1166        let b1 = Point::new(5.0, 0.0);
1167        let b2 = Point::new(10.0, 0.0);
1168        assert_eq!(segment_relation(a1, a2, b1, b2), SegmentRelation::Touch);
1169        assert!(!segments_overlap(a1, a2, b1, b2));
1170        assert!(segments_interact(a1, a2, b1, b2));
1171    }
1172
1173    #[test]
1174    fn segment_relation_collinear_overlap() {
1175        // Collinear overlapping segments
1176        let a1 = Point::new(0.0, 0.0);
1177        let a2 = Point::new(10.0, 0.0);
1178        let b1 = Point::new(5.0, 0.0);
1179        let b2 = Point::new(15.0, 0.0);
1180        assert_eq!(
1181            segment_relation(a1, a2, b1, b2),
1182            SegmentRelation::CollinearOverlap
1183        );
1184        assert!(segments_overlap(a1, a2, b1, b2));
1185        assert!(segments_interact(a1, a2, b1, b2));
1186    }
1187
1188    #[test]
1189    fn segment_relation_collinear_touch() {
1190        // Collinear segments touching at endpoint
1191        let a1 = Point::new(0.0, 0.0);
1192        let a2 = Point::new(5.0, 0.0);
1193        let b1 = Point::new(5.0, 0.0);
1194        let b2 = Point::new(10.0, 0.0);
1195        // This is Touch, not CollinearOverlap, because overlap is just a point
1196        assert_eq!(segment_relation(a1, a2, b1, b2), SegmentRelation::Touch);
1197        assert!(!segments_overlap(a1, a2, b1, b2));
1198        assert!(segments_interact(a1, a2, b1, b2));
1199    }
1200
1201    #[test]
1202    fn segment_relation_disjoint() {
1203        // Disjoint segments
1204        let a1 = Point::new(0.0, 0.0);
1205        let a2 = Point::new(5.0, 0.0);
1206        let b1 = Point::new(6.0, 0.0);
1207        let b2 = Point::new(10.0, 0.0);
1208        assert_eq!(segment_relation(a1, a2, b1, b2), SegmentRelation::Disjoint);
1209        assert!(!segments_overlap(a1, a2, b1, b2));
1210        assert!(!segments_interact(a1, a2, b1, b2));
1211    }
1212
1213    #[test]
1214    fn segment_relation_cross_near_endpoint() {
1215        // Proper cross very near endpoint but still crossing
1216        let a1 = Point::new(0.0, 0.0);
1217        let a2 = Point::new(10.0, 10.0);
1218        let b1 = Point::new(0.0, 10.0);
1219        let b2 = Point::new(10.0, 0.0);
1220        assert_eq!(
1221            segment_relation(a1, a2, b1, b2),
1222            SegmentRelation::ProperCross
1223        );
1224        assert!(segments_overlap(a1, a2, b1, b2));
1225    }
1226}