# moonlight-triangulation
> Part of **Moonlight**, the sheaf-theoretic computation layer beneath
> [Melusine](https://bluerose.blue) and Pale Meridian.
`moonlight-triangulation` carries Delaunay and constrained Delaunay
triangulations as a lawful finite-set algebra under canonical observation: a
mesh represents its site set, a join returns a valid Delaunay representative,
and the result is a triangulation again — so the operations close, compose, and
fold. Operations return typed obstructions where the finite arena cannot
represent a result.
Delaunay triangulation, constrained Delaunay (CDT), exact rational planar
regions and labelled overlay, intrinsic valuations, polygonal Minkowski
morphology, the Voronoi dual, natural-neighbour interpolation, Ruppert
refinement, walk point location, convex hull, exact Shewchuk predicates,
and versioned binary serialization.
## Persistence rose
[Open the animation directly.](./docs/persistence-rose/moonlight-triangulation-persistence-rose.gif)
· [Open the static vector poster.](./docs/persistence-rose/moonlight-triangulation-persistence-rose.svg)
· [Read the exhibit guide.](./docs/persistence-rose/README.md)
## Operations
| Operation | Use when | Inputs | Result |
| --- | --- | --- | --- |
| `delaunayGeometry` | Coordinates own the input | `Vector Point` | Geometry-only mesh / `BuildError` |
| `delaunayFromCoordinates` | Payloads have a separate plane | Defaults, points, payloads, duplicate policy | `BuildResult` / `BuildError` |
| `siteRelation` | Supports need exact classification | Two meshes | `SiteRelation` |
| `union` / `unions` | Unconstrained supports must join | Two meshes / mesh list | Union mesh / `BuildError` |
| `intersection` / `intersectionWith` | Shared support is required | Two meshes; optional payload combiner | Common-site mesh / `BuildError` |
| `difference` / `symmetricDifference` | Left-only / exclusive support is required | Source and mask / two meshes | Result mesh / `BuildError` |
| `constrainedDelaunay` | Segments author topology | Defaults, positioned vertices, index pairs | `BuildResult` / `CdtError` |
| `unionConstrained` / `unionConstrainedWith` | Arbitrary constrained meshes must join | Two meshes; optional payload combiner | Constrained mesh / `ConstrainedUnionError` |
| `extendConstrainedWith` | One constrained mesh owns identity | Combiner, base, extension | `ConstrainedExtensionResult` / `ConstrainedUnionError` |
| `joinSeparatedConstrained` | Inputs are strictly x-separated | Face predicate, refinement parameters, two meshes | `ConstrainedSeamResult` / `ConstrainedUnionError` |
| `refine` | Quality applies globally | Vertex constructor, parameters, mesh | `RefinementResult` / `BuildError` |
| `refineWithinDomain` | Quality applies to admitted faces | Vertex constructor, parameters, face set, mesh | `RefinementDomainResult` / `BuildError` |
| `faceComponents` | Bounded faces must descend by label | Mesh, `FaceId -> label` | `[(label, FaceComponent)]` |
| `componentBoundary` | One component must publish as loops | Mesh, `FaceComponent` | `RegionBoundary` / `BoundaryObstruction` |
| `overlayLayers` | Layers need one exact arrangement | Two `PlanarLayer`s | `OverlayResult` / `OverlayError` |
| `overlayClosedUnion` / `overlayClosedIntersection` / `overlayRegularizedDifference` | Boolean output may retain lower cells | Two label predicates, `OverlayResult` | `ExactCellSet` / `OverlaySelectionError` |
| `overlaySelectedRegion` | Selected faces must publish as polygons | Label-pair predicate, `OverlayResult` | `PlanarRegion` / `RegionPublicationError` |
| `cellValuations` / `regionValuations` | Intrinsic measures are required | `ExactCellSet` / `PlanarRegion` | `PlanarValuations` / `ValuationError` |
| `minkowskiSum` / `polygonOffset` | Regions must add / expand | Two regions / element and region | Region plus receipt / `MinkowskiError` |
| `erodeBy` / `openWith` / `closeWith` | Regularized morphology is required | Structuring element, region | Region plus receipt / `MinkowskiError` |
| `alphaShapeContainsFace` | One face at one radius is enough | `RadiusSquared`, mesh, `FaceId` | `Bool` |
| `alphaFiltration` | Every critical radius matters | Delaunay mesh | `AlphaFiltration` / `AlphaFiltrationError` |
| `fromExactCellSet` | Exact cells need a generic complex view | `ExactCellSet` | `DCELComplex` |
| `filteredAlphaComplex` | Alpha births must enter persistence | `AlphaFiltration` | Filtered chain complex / `DCELError` |
| `canonicalize` | Numbering must ignore construction history | Mesh with unit edge/face payloads | Canonical mesh / `BuildError` |
[Interpret cell sets as incidence categories.](docs/category-observatory/README.md#cell-complex-and-category-interpretation)
· [Compute persistent alpha topology.](docs/persistence-rose/README.md#exact-alpha-filtration-and-persistent-topology)
## Foreign bindings
The C ABI and its Python, TypeScript, and Rust consumers are documented in the
[foreign-bindings guide](ffi/bindings/README.md). It owns construction, ABI
versioning, lifecycle, obstruction semantics, and consumer examples.
## Algebraic contract
`union` is idempotent; commutativity and associativity hold after
`canonicalize`. Structural `Eq` is resident equality; use `siteRelation` for
support comparison.
### Set-operation types
```haskell
union :: JoinSemilattice annotation
=> Triangulation 'Unconstrained annotation () () ()
-> Triangulation 'Unconstrained annotation () () ()
-> Either BuildError (Triangulation 'Unconstrained annotation () () ())
unions :: JoinSemilattice annotation
=> [Triangulation 'Unconstrained annotation () () ()]
-> Either BuildError (Triangulation 'Unconstrained annotation () () ())
siteRelation
:: Triangulation leftMode leftAnnotation leftDirected leftUndirected leftFace
-> Triangulation rightMode rightAnnotation rightDirected rightUndirected rightFace
-> SiteRelation
intersection
:: Triangulation 'Unconstrained () () () ()
-> Triangulation 'Unconstrained () () () ()
-> Either BuildError (Triangulation 'Unconstrained () () () ())
intersectionWith
:: (leftAnnotation -> rightAnnotation -> annotation)
-> Triangulation 'Unconstrained leftAnnotation () () ()
-> Triangulation 'Unconstrained rightAnnotation () () ()
-> Either BuildError (Triangulation 'Unconstrained annotation () () ())
difference
:: Triangulation 'Unconstrained leftAnnotation () () ()
-> Triangulation 'Unconstrained rightAnnotation () () ()
-> Either BuildError (Triangulation 'Unconstrained leftAnnotation () () ())
symmetricDifference
:: Triangulation 'Unconstrained annotation () () ()
-> Triangulation 'Unconstrained annotation () () ()
-> Either BuildError (Triangulation 'Unconstrained annotation () () ())
```
[Publication schedules and scale behavior.](docs/mesh-publication.md)
## Use
Use the main facade with explicit `Vector` inputs. Construction and set algebra
retain their typed obstruction in `Either`:
```cabal
build-depends:
base >= 4.19 && < 5,
moonlight-triangulation >= 1.4 && < 1.5,
vector >= 0.13 && < 0.14
```
[`SetAlgebra.hs`](docs/examples/Moonlight/Triangulation/Example/SetAlgebra.hs)
is the smallest compile-checked workflow. The
[example index](docs/examples/README.md) adds constrained interiors,
alpha-boundary descent, exact overlay and valuations, and polygonal morphology.
## Architecture
The resident DCEL is immutable structure-of-arrays over paged copy-on-write
storage; local mutation is sealed in `ST`. Half-edge twins are index
complements. Exact predicates use bounded machine-word evaluation and fall
through to aligned `Integer` arithmetic when required.
## Consumer libraries
The Cabal manifest owns component visibility and dependencies; this is its
consumer-facing projection. External packages normally use the main library
and add only the public sublibraries whose modules they import. The finite DCEL
and construction kernel remain private behind the main facade.
| Dependency | Imports | Purpose |
| --- | --- | --- |
| `moonlight-triangulation` | `Moonlight.Triangulation`, `.HintGenerator`, `.Overlay`, `.Minkowski` | Construction, observations, set algebra, CDT, refinement, alpha geometry, and exact planar operations. |
| `moonlight-triangulation:core` | `.Scalar`, `.LineSideInfo` | Low-level exact scalars and paged storage primitives. |
| `moonlight-triangulation:dual` | `.Voronoi`, `.Voronoi.Handles`, `.Interpolation` | Voronoi observations and natural-neighbour interpolation. |
| `moonlight-triangulation:parallel` | `.Parallel` | Bounded concurrent union; adds `async`. |
| `moonlight-triangulation:serialize` | `.Serialization` | Versioned binary envelopes; adds `binary`, `bytestring`, and `transformers`. |
| `moonlight-triangulation:cell-complex` (GHC 9.14+) | `.CellComplex` | Cell, chain, and filtered-alpha interpretations; adds Homology. |
[Build and validate package components locally.](docs/development.md)