# 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` |
| `insert` / `insertAt` / `insertMany` | An immutable mesh gains sites or payload replacements | Mesh plus payloads or explicit points | `InsertionResult` / `BuildResult` / `BuildError` |
| `withSession` | Many inserts and removals should publish once | Mesh, peak added-site count, composed `Session` | Result, mesh, and `BuildStats` / `BuildError` |
| `removeVertex` / `locateAndRemove` | A resident handle or exact position must be removed | Mesh plus `VertexId` / `Point` | `RemovalResult` / optional result / `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` |
| `addConstraintEdge(s)` / `removeConstraintEdge` | Constraints change on a resident mesh | Mesh plus vertex pair(s) / edge | Constraint receipt or mesh / `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` |
| `locatePoint` / `locatePointWithHint` | An admitted point needs an exact cell classification | Mesh, `QueryPoint`, optional hint | `Location`, optionally with `LocationStats` |
| `lineIntersections` | A segment needs its ordered mesh crossings | Mesh and admitted endpoints | `[Intersection]` |
| `verticesInCircle` / `verticesInRectangle` | A metric window selects resident sites | Mesh and circle / rectangle | Handles / typed metric error |
| `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 broad default library with explicit `Vector` inputs. It exposes the
facade and the safe leaf modules; 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.
For a smaller compile/dependency cone, depend on only the component modules you
import:
```cabal
build-depends:
moonlight-triangulation:dcel >= 1.4.1 && < 1.5,
moonlight-triangulation:build >= 1.4.1 && < 1.5
```
## 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. The default library reexports the complete safe
geometry surface. Use a public sublibrary directly when its smaller dependency
cone matters; the trusted implementation units remain private.
| Dependency | Imports | Purpose |
| --- | --- | --- |
| `moonlight-triangulation` | `Moonlight.Triangulation` and every safe `dcel`, `build`, and `dual` module | Broad construction, observation, set algebra, CDT, refinement, alpha, Voronoi, interpolation, and exact planar surface. |
| `moonlight-triangulation:core` | `.Scalar`, `.LineSideInfo` | Low-level exact scalars and paged storage primitives. |
| `moonlight-triangulation:dcel` | `.Types`, `.Dcel`, `.Handles.*`, `.PointLocation`, `.FloodFillIterator`, `.IntersectionIterator`, `.Alpha`, `.Exact`, `.Region`, `.Valuation` | Immutable mesh vocabulary, observations, typed spatial queries, exact geometry, and owning handles; no construction kernel. |
| `moonlight-triangulation:build` | `.BulkLoad`, `.Session`, `.Removal`, `.Cdt`, `.Refinement`, `.SetAlgebra` | Construction and persistent editing over the DCEL; no dual, serialization, concurrency, or Homology dependency. |
| `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)