axiolid-overlay

Deterministic validated planar overlay contract.

Latest release	0.4.1 (2026-11-14)
crates.io	axiolid-overlay
Facade	axiolid feature overlay
Layer	algorithms (algorithm.planar)
API documentation	rustdoc · docs.rs
Source	crates/algorithms/planar/overlay/

Overview

Validated, deterministic planar booleans (intersection, union, difference, xor) and offsets over regions with holes, plus the planar operations built on them: arc-aware booleans and arrangements, polyline strokes, Minkowski morphology bounds, minimum enclosing circles and rectangles, visibility, and exact intersection of many segments by a sweep. Inputs are validated and refused with a typed error rather than repaired. It answers a query and keeps no structure; editable subdivisions with persistent identity live in axiolid-arrangement.

Design notes

• Straight-edged booleans (Region, overlay, union_soup) and arc-aware ones (arc_overlay, ArcArrangement) share one exact core in src/exact_arc.rs (ADR 0070, #173): every topological decision is an exact sign, and output is rounded once, so an input vertex comes back bit-identical. i_overlay remains only for offsets. The core's maintenance rules and verification commands are in that module's docs.
• An arc polygon is checked exactly for self-contact, shared boundary and hole nesting by check_arc_polygon, with no tolerance in any contact or nesting decision (src/arc_check.rs, #352, ADR 0095). scripts/probe_arc_check_mutants.py lists the faults its tests must catch. check_arc_polygon_with can also report edges that miss each other by less than a distance (ArcCheckOptions::with_clearance, src/arc_clearance.rs, #388), decided exactly; its faults are listed by scripts/probe_arc_clearance_mutants.py.
• Operand validation and output settling share one exact notion of when two boundary edges meet (src/contact.rs, #272): an end on the other edge within the tolerance, or a proper crossing, so every output is a valid operand wherever it lies. scripts/probe_edge_contact_mutants.py lists the faults its tests must catch.
• A soup of convex parts fanned into triangles reduces to the parts' outlines even where the parts overlap and share vertices: the chain is reduced group by group when one walk through it closes a crossing cycle. Edges given more than once, and edges meeting at a shared vertex, are not paired again for every copy, so a soup whose grown parts line up costs about what its outlines cost (#338). overlay_within and union_soup_within take ExecutionOptions: with a memory budget the subdivision is charged before it allocates and refused with OverlayRefusal::BudgetExceeded before it would hold more (src/budget.rs, ADR 0088). scripts/probe_grown_soup_mutants.py lists the faults its tests must catch.
• Ring validation asks the crate's box tree for the edge pairs that can meet within the tolerance, decided by the same exact test in the same order, so a ring of 100,000 corners validates in about n log n. A Region carries the proof that its rings are valid under its tolerance, set only by Region::new and by settled outputs, and booleans on regions under that tolerance do not validate them again (#341). scripts/probe_ring_validation_mutants.py lists the faults its tests must catch.
• Region::new also refuses rings that cross into each other (src/nesting.rs, ADR 0104, #448): a hole outside its outer ring (HoleOutsideOuter), two holes of a polygon that overlap (HolesOverlap), two polygons that overlap (PolygonsOverlap). The decision is exact and tolerance-free, on one arrangement of all rings; rings may touch at points or share a stretch with the polygons' insides on opposite sides, as settled outputs do. Operations do not re-check their outputs. scripts/probe_region_nesting_mutants.py lists the faults its tests must catch.
• free_faces returns the bounded faces of the plane that obstacle polygons and barriers leave free, each ring edge with the inputs it lies on, and FreeFaces::locate says which face a point is in (src/free_faces.rs, #490, ADR 0109). A gap narrower than the closing width is closed by a reported bridge, never by moving an input, and a free region narrower than the width is a closed gap, listed apart. It runs on axiolid-exact-arrangement, so every decision is an exact sign and the rings are snap-rounded as the visible faces are (ADR 0100). scripts/probe_free_faces_mutants.py lists the faults its tests must catch.
• A degenerate input ring refuses the operation by default. overlay_with and union_soup_with with OverlayOptions::dropping_degenerate_rings leave out a ring that is too short, has a repeated vertex, or has zero area under the exact ZeroArea rule, and report each one with its place, reason and area (src/degenerate.rs, #256). A self-intersecting ring is never dropped. scripts/probe_degenerate_drop_mutants.py lists the faults its tests must catch.
• segment_intersections (src/segment_sweep.rs, #146) is a Bentley-Ottmann sweep over many segments with its own exact rational points; its reporting rule and degeneracy handling are in that module's docs, and scripts/probe_segment_sweep_mutants.py lists the faults its tests must catch.
• Minkowski sums and erosions take one hull per boundary edge. Exactly collinear corners are merged first, and a chord proved exactly to lie in the summed set trims the hulls it spans to what its own hull does not hold, so a wall of many short edges costs about its teeth, not their square, and the union stays the same set (src/cover.rs, #323). A chord whose hull or any trimmed hull would be a ring of zero area is not used, so trimming never adds a ring the arrangement refuses (#331). scripts/probe_minkowski_cover_mutants.py and scripts/probe_minkowski_degenerate_mutants.py list the faults its tests must catch.
• The disc morphology has two modes (MorphologyMode, ADR 0087, #330). Exact, the default and the behaviour of erode_inner and its siblings, is bit for bit the route above; a CAD kernel takes it. Its cost still grows with the square of the corners where teeth stand closer than their tips' slivers are wide. Fast, through erode_inner_with and its siblings, first fills the summed set's notches with chords proved to lie outside it, each used only when the excess it adds is within the caller's budget, and keeps the inner or outer side: the excess goes into MorphologyBound's deviation and is reported by Region::excess. A wall of teeth then costs about its corners; a rule engine takes it (src/fill.rs). It fills needles deeper than the disc too, each bounded by its own slab (#428). scripts/probe_fast_morphology_mutants.py lists the faults its tests must catch.

Depends on

• axiolid-contracts
• axiolid-core
• axiolid-exact
• axiolid-exact-arrangement
• axiolid-guarantees

Changes

Latest release, 0.4.1 (2026-11-14):

Added

• free_faces, free_faces_within, FreeFaces (with locate), FreeSpaceInput, FreeFace, FreeRing, Bridge, PieceSource, FaceLocation, FreeFaceEvidence, FreeFacesError and BarrierDefect (#490, ADR 0109): the bounded faces of the plane that obstacle polygons and open-segment barriers leave free, with the inputs each ring edge lies on. Gaps narrower than a closing width are closed by reported bridges, never by moving an input; a free region narrower than the width is a closed gap, returned apart. Rings are snap-rounded and certified as the visible faces are. Depends on axiolid-exact-arrangement now.

Full history: crates/algorithms/planar/overlay/CHANGELOG.md