axiolid_overlay/

region.rs

//! A persistent planar region with set algebra, morphology and components.
//!
//! # Why a type rather than more free functions
//!
//! [`crate::overlay`] is stateless: it validates both operands on every
//! call and returns a fresh result. That is the right primitive, but a
//! consumer that builds free space, subtracts obstacles, erodes by a body
//! radius and then counts what is left has to thread raw polygon vectors
//! between calls and pay revalidation each time. Area and component count
//! are not reachable at all.
//!
//! A [`Region`] is validated once at construction. Every operation on it
//! consumes already-valid geometry and produces already-valid geometry, so
//! the invariant is established at the boundary rather than re-proven at
//! each step.
//!
//! # Emptiness is a reported fact, not an absence
//!
//! Every operation that can annihilate a region reports whether it did.
//! An erosion that removes the last of a corridor and an intersection of
//! two disjoint regions both yield no polygons, but they are different
//! facts, and a bare empty vector cannot tell a caller which happened.
//! [`RegionEvidence::emptied`] records that the operation consumed a
//! non-empty input, so "nothing was there" stays distinguishable from
//! "this operation destroyed it".
//!
//! # Boundary
//!
//! The kernel owns the region, the operations and the reported measures.
//! It does not own what the region represents, which radius is correct, or
//! whether a resulting area or component count is acceptable.

use axiolid_core::{Point2, Tolerance, Vec2};

use crate::minkowski::MorphologyBound;
use crate::offset::{offset_polygons, total_area, JoinStyle};
use crate::settle::Validated;
use crate::{canonical, OverlayError, Polygon, Ring};

/// What an operation did to produce a region.
#[derive(Debug, Clone, Copy, PartialEq, Eq, Default)]
pub struct RegionEvidence {
    /// Number of disjoint polygons in the result.
    pub polygons: usize,
    /// Number of inner boundary components across all polygons.
    pub holes: usize,
    /// The operation consumed a non-empty input and produced nothing.
    ///
    /// Distinguishes "eroded out of existence" or "disjoint operands" from
    /// "the input was already empty", which a bare empty result cannot.
    pub emptied: bool,
}

/// A validated planar region: a normalised set of polygons with holes,
/// whose holes lie apart inside their outer rings and whose polygons do
/// not overlap (#448).
///
/// Construction validates; operations preserve validity: a boolean or a
/// morphology returns the faces of an exact arrangement, apart and nested
/// by construction, and [`Region::translate`], which rounds each vertex on
/// its own, checks its result. Ring ordering is
/// canonical (outer counter-clockwise, holes clockwise, each rotated to its
/// lexicographically smallest vertex) and polygons are sorted, so equal
/// regions compare equal regardless of how they were built.
///
/// A region built by [`Region::new`] or by a boolean on regions carries
/// the proof that its rings are valid under that call's tolerance (#341),
/// and a boolean on it under the same tolerance does not validate them
/// again. The proof is not part of equality.
#[derive(Debug, Clone, Default)]
pub struct Region {
    polygons: Vec<Polygon>,
    evidence: RegionEvidence,
    /// For a disc morphology with a stated side, that side and the
    /// deviation from the exact result (#163).
    bound: Option<MorphologyBound>,
    /// For a fast disc morphology, the excess its filled notches add
    /// (#330).
    excess: Option<f64>,
    /// Every ring passes validation under this tolerance (#341): set by
    /// [`Region::new`] and by settled outputs only.
    validated: Option<Validated>,
}

impl PartialEq for Region {
    fn eq(&self, other: &Self) -> bool {
        // The proof says how the region was reached, not what it is.
        self.polygons == other.polygons
            && self.evidence == other.evidence
            && self.bound == other.bound
            && self.excess == other.excess
    }
}

/// Normalise a polygon set: canonical ring order, deterministic sorting.
///
/// Applied to every operation result so that two regions holding the same
/// point set are structurally equal, which is what makes idempotence and
/// round-trip assertions meaningful rather than incidental.
fn normalise(mut polygons: Vec<Polygon>) -> Vec<Polygon> {
    polygons = polygons
        .into_iter()
        .map(|polygon| Polygon {
            outer: canonical(polygon.outer, true),
            holes: polygon
                .holes
                .into_iter()
                .map(|hole| canonical(hole, false))
                .collect(),
        })
        .collect();
    for polygon in &mut polygons {
        polygon.holes.sort_by(|a, b| {
            a.points[0]
                .x
                .total_cmp(&b.points[0].x)
                .then(a.points[0].y.total_cmp(&b.points[0].y))
        });
    }
    polygons.sort_by(|a, b| {
        a.outer.points[0]
            .x
            .total_cmp(&b.outer.points[0].x)
            .then(a.outer.points[0].y.total_cmp(&b.outer.points[0].y))
    });
    polygons
}

impl Region {
    /// The empty region. Not a failure: the identity for union.
    #[must_use]
    pub fn empty() -> Self {
        Self::default()
    }

    /// Build a region from polygons, validating every ring and where the
    /// rings lie.
    ///
    /// Each ring is validated as [`crate::overlay`] validates an operand's,
    /// so the two cannot disagree about what a well-formed ring is. Then,
    /// decided exactly and with no tolerance, every hole must lie inside its
    /// own outer ring and in no other of its holes, and no point may lie in
    /// two polygons (#448). Rings may touch at points, and along a stretch
    /// they run with the polygons' insides on opposite sides, as settled outputs
    /// do. An `overlay` operand is not held to this: its rings may overlap,
    /// read by its fill rule.
    ///
    /// # Errors
    ///
    /// A ring's own refusal ([`OverlayError::RingTooShort`] and the
    /// others [`crate::overlay`] gives); [`OverlayError::HoleOutsideOuter`]
    /// for a hole crossing or leaving its outer ring;
    /// [`OverlayError::HolesOverlap`] for holes of one polygon that cross,
    /// nest or repeat; [`OverlayError::PolygonsOverlap`] for polygons that
    /// overlap. With several defects, one is named.
    pub fn new(polygons: Vec<Polygon>, tolerance: Tolerance) -> Result<Self, OverlayError> {
        let validated = Validated::check(&polygons, tolerance)?;
        crate::nesting::check(&polygons)?;
        let mut region = Self::from_valid(normalise(polygons), false);
        // Turning and rotating a ring, and ordering rings, change nothing
        // validation reads.
        region.validated = Some(validated);
        Ok(region)
    }

    /// Wrap already-valid geometry, recording whether the producing operation
    /// annihilated a non-empty input. No proof of validity is carried; see
    /// [`Self::with_validated`].
    fn from_valid(polygons: Vec<Polygon>, had_input: bool) -> Self {
        let evidence = RegionEvidence {
            polygons: polygons.len(),
            holes: polygons.iter().map(|p| p.holes.len()).sum(),
            emptied: had_input && polygons.is_empty(),
        };
        Self {
            polygons: normalise(polygons),
            evidence,
            bound: None,
            excess: None,
            validated: None,
        }
    }

    /// This region with the proof `validated` of its rings, from settling
    /// them or from the region it equals.
    pub(crate) fn with_validated(mut self, validated: Option<Validated>) -> Self {
        self.validated = validated;
        self
    }

    /// The proof this region's rings are valid, if it carries one.
    pub(crate) fn validated(&self) -> Option<Validated> {
        self.validated
    }

    /// [`Self::from_valid`] for the other modules of the crate.
    pub(crate) fn from_valid_polygons(polygons: Vec<Polygon>, had_input: bool) -> Self {
        Self::from_valid(polygons, had_input)
    }

    /// Record the side and deviation of a disc morphology.
    pub(crate) fn set_bound(&mut self, bound: MorphologyBound) {
        self.bound = Some(bound);
    }

    /// For a result of [`Self::dilate_inner`], [`Self::dilate_outer`],
    /// [`Self::erode_inner`] or [`Self::erode_outer`]: which side of the
    /// exact disc morphology it lies on and how far from it it can be.
    /// `None` for every other region, including [`Self::dilate`] and
    /// [`Self::erode`], whose side is not stated.
    #[must_use]
    pub const fn bound(&self) -> Option<MorphologyBound> {
        self.bound
    }

    /// Record the excess of a fast disc morphology.
    pub(crate) fn set_excess(&mut self, excess: f64) {
        self.excess = Some(excess);
    }

    /// For a result of [`Self::erode_inner_with`] and its siblings in
    /// [`crate::MorphologyMode::Fast`]: how much larger the filled notches
    /// made the sum, at most the mode's budget, zero where no notch was
    /// filled (#330). It is part of [`MorphologyBound::deviation`], which
    /// states the whole distance from the exact result. `None` for every
    /// other region, the exact mode's results included.
    #[must_use]
    pub const fn excess(&self) -> Option<f64> {
        self.excess
    }

    /// The region's polygons, in canonical order.
    #[must_use]
    pub fn polygons(&self) -> &[Polygon] {
        &self.polygons
    }

    /// What the producing operation did.
    #[must_use]
    pub const fn evidence(&self) -> RegionEvidence {
        self.evidence
    }

    /// True when the region covers no area.
    #[must_use]
    pub fn is_empty(&self) -> bool {
        self.polygons.is_empty()
    }

    /// Total covered area. Holes subtract.
    #[must_use]
    pub fn area(&self) -> f64 {
        total_area(&self.polygons)
    }

    /// Number of disjoint connected components.
    ///
    /// One polygon is one component: [`Self::new`] refuses polygons that
    /// overlap (#448) and every operation returns polygons that do not, so
    /// counting them is the component count rather than an approximation
    /// of it. Polygons touching at a point or along an edge count apart.
    #[must_use]
    pub fn component_count(&self) -> usize {
        self.polygons.len()
    }

    /// Every boundary ring, outer boundaries first then holes.
    #[must_use]
    pub fn boundary_rings(&self) -> Vec<Ring> {
        let mut rings: Vec<Ring> = self.polygons.iter().map(|p| p.outer.clone()).collect();
        for polygon in &self.polygons {
            rings.extend(polygon.holes.iter().cloned());
        }
        rings
    }

    /// Set union.
    pub fn union(&self, other: &Self, tolerance: Tolerance) -> Result<Self, OverlayError> {
        self.combine(other, crate::OverlayOperation::Union, tolerance)
    }

    /// Set intersection.
    pub fn intersection(&self, other: &Self, tolerance: Tolerance) -> Result<Self, OverlayError> {
        self.combine(other, crate::OverlayOperation::Intersection, tolerance)
    }

    /// Set difference: this region minus `other`.
    pub fn difference(&self, other: &Self, tolerance: Tolerance) -> Result<Self, OverlayError> {
        self.combine(other, crate::OverlayOperation::Difference, tolerance)
    }

    /// Apply a boolean operation through the validated overlay primitive.
    ///
    /// Empty operands are handled here rather than pushed into the backend:
    /// the identities are exact, and routing them through a general overlay
    /// would risk an incidental simplification pass changing geometry that
    /// set algebra says must be returned unchanged.
    fn combine(
        &self,
        other: &Self,
        operation: crate::OverlayOperation,
        tolerance: Tolerance,
    ) -> Result<Self, OverlayError> {
        let had_input = !self.is_empty() || !other.is_empty();
        match operation {
            crate::OverlayOperation::Union if other.is_empty() => {
                return Ok(Self::from_valid(self.polygons.clone(), had_input)
                    .with_validated(self.validated));
            }
            crate::OverlayOperation::Union if self.is_empty() => {
                return Ok(Self::from_valid(other.polygons.clone(), had_input)
                    .with_validated(other.validated));
            }
            crate::OverlayOperation::Intersection if self.is_empty() || other.is_empty() => {
                return Ok(Self::from_valid(Vec::new(), had_input));
            }
            crate::OverlayOperation::Difference if other.is_empty() => {
                return Ok(Self::from_valid(self.polygons.clone(), had_input)
                    .with_validated(self.validated));
            }
            crate::OverlayOperation::Difference if self.is_empty() => {
                return Ok(Self::from_valid(Vec::new(), had_input));
            }
            _ => {}
        }
        // The identity frame. A region carries no frame of its own: it is a
        // point set in whatever frame the caller established, and overlay
        // only requires both operands to agree.
        let frame = axiolid_core::Frame2 {
            origin: Point2::new(0.0, 0.0),
            x: Vec2::new(1.0, 0.0),
            y: Vec2::new(0.0, 1.0),
        };
        let subject = crate::OverlayInput {
            frame,
            polygons: self.polygons.clone(),
        };
        let clip = crate::OverlayInput {
            frame,
            polygons: other.polygons.clone(),
        };
        // Rings known valid under this tolerance are not validated again
        // (#341); the settled output carries its own proof.
        let known = |region: &Self| region.validated.is_some_and(|v| v.holds_for(tolerance));
        let (reported, validated) = crate::overlay_known(
            &subject,
            &clip,
            operation,
            crate::FillRule::NonZero,
            tolerance,
            crate::OverlayOptions::new(),
            &mut crate::budget::Charge::unlimited(),
            [known(self), known(other)],
        )
        .map_err(crate::budget::unbudgeted)?;
        Ok(Self::from_valid(reported.result.polygons, had_input).with_validated(validated))
    }

    /// Dilate by `radius`: the Minkowski sum with a disc, approximated by
    /// round joins on an unstated side of the exact result. Where a verdict
    /// must be proven, use [`Self::dilate_inner`] or [`Self::dilate_outer`].
    ///
    /// This is the disc-expansion form used for clearance envelopes. A zero
    /// radius is the identity.
    pub fn dilate(&self, radius: f64, tolerance: Tolerance) -> Result<Self, OverlayError> {
        self.morphology(radius, tolerance)
    }

    /// Erode by `radius`: the Minkowski erosion by a disc, approximated on
    /// an unstated side of the exact result. Where a verdict must be
    /// proven, use [`Self::erode_inner`] (a route found proves
    /// reachability) or [`Self::erode_outer`] (no route proves
    /// unreachability).
    ///
    /// A region thinner than `2 * radius` anywhere is cut there, which is
    /// how a corridor narrower than a body radius becomes impassable. If
    /// that removes everything the result is empty and
    /// [`RegionEvidence::emptied`] is set.
    pub fn erode(&self, radius: f64, tolerance: Tolerance) -> Result<Self, OverlayError> {
        if radius < 0.0 {
            return Err(OverlayError::InvalidOffsetDistance);
        }
        self.morphology(-radius, tolerance)
    }

    /// Shared offset path. Round joins approximate the disc, which is what
    /// makes this morphology rather than a polygonal offset.
    fn morphology(&self, distance: f64, tolerance: Tolerance) -> Result<Self, OverlayError> {
        if !distance.is_finite() {
            return Err(OverlayError::InvalidOffsetDistance);
        }
        if self.is_empty() || distance == 0.0 {
            return Ok(Self::from_valid(self.polygons.clone(), false));
        }
        // A disc is approximated by round joins; the parameter is the maximum
        // segment-length-to-radius ratio, so smaller is closer to a true disc.
        let join = JoinStyle::Round {
            max_segment_ratio: 0.1,
        };
        let result = offset_polygons(&self.polygons, distance, join, tolerance)?;
        Ok(Self::from_valid(result.polygons, true))
    }

    /// Translate by `offset`. Rigid: area and component count are preserved.
    ///
    /// # Errors
    ///
    /// [`OverlayError::NonFinitePoint`] for a non-finite offset. Each vertex
    /// moves by its own rounding, which can turn a contact into a crossing,
    /// so the result is checked as [`Region::new`] checks its rings: the
    /// refusals of `Region::new` for rings crossing into each other (#448).
    /// That arranges a region of more than one ring, as `Region::new` does:
    /// 0.34 s for a floor of 100,000 corners with 200 holes.
    pub fn translate(&self, offset: Vec2) -> Result<Self, OverlayError> {
        let polygons = self.shifted(offset)?;
        crate::nesting::check(&polygons)?;
        Ok(Self::from_valid(polygons, !self.is_empty()))
    }

    /// The region moved by `offset`, each vertex by its own rounding, not
    /// checked: a copy that only feeds `union`, which reads overlapping
    /// operands by their fill rule (#448).
    fn shifted(&self, offset: Vec2) -> Result<Vec<Polygon>, OverlayError> {
        if !offset.is_finite() {
            return Err(OverlayError::NonFinitePoint);
        }
        let shift = |ring: &Ring| Ring {
            points: ring
                .points
                .iter()
                .map(|p| Point2::new(p.x + offset.x, p.y + offset.y))
                .collect(),
        };
        Ok(self
            .polygons
            .iter()
            .map(|polygon| Polygon {
                outer: shift(&polygon.outer),
                holes: polygon.holes.iter().map(shift).collect(),
            })
            .collect())
    }

    /// Sweep along `direction`: the union of the region with every
    /// translate of itself along the vector.
    ///
    /// Equivalent to the Minkowski sum with the segment `[0, direction]`.
    /// Built as the union of the region and its translate plus the hull
    /// swept between them, which for a polygon set is exactly the union of
    /// the two end positions with the stroke of each boundary edge; using
    /// the union of endpoints alone would miss the swept middle whenever
    /// the translation exceeds the region's own extent.
    pub fn sweep(&self, direction: Vec2, tolerance: Tolerance) -> Result<Self, OverlayError> {
        if !direction.is_finite() {
            return Err(OverlayError::NonFinitePoint);
        }
        if self.is_empty() || direction.length() == 0.0 {
            return Ok(Self::from_valid(self.polygons.clone(), false));
        }
        // Not checked: the copy only feeds `union`, which reads overlapping
        // operands by fill rule, so a rounding that makes the copy's rings
        // cross still gives the sound sweep.
        let moved = Self::from_valid(self.shifted(direction)?, true);
        let mut swept = self.union(&moved, tolerance)?;
        // Fill the corridor between the two positions: each boundary edge
        // sweeps a parallelogram, and their union with the endpoints is the
        // Minkowski sum. Built from quads so no offset approximation enters.
        for ring in self.boundary_rings() {
            let count = ring.points.len();
            for index in 0..count {
                let a = ring.points[index];
                let b = ring.points[(index + 1) % count];
                let quad = Polygon {
                    outer: Ring {
                        points: vec![
                            a,
                            b,
                            Point2::new(b.x + direction.x, b.y + direction.y),
                            Point2::new(a.x + direction.x, a.y + direction.y),
                        ],
                    },
                    holes: Vec::new(),
                };
                // A degenerate quad (edge parallel to the sweep) contributes
                // nothing and is skipped rather than rejected.
                if let Ok(band) = Self::new(vec![quad], tolerance) {
                    swept = swept.union(&band, tolerance)?;
                }
            }
        }
        Ok(swept)
    }
}