moonlight-triangulation

Part of Moonlight, the sheaf-theoretic computation layer beneath Melusine 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, incremental insertion and removal, and versioned binary serialization.

Operations

Choose the operation

Foreign bindings

The moonlight-triangulation-c foreign-library component exposes opaque immutable geometry meshes, batch insertion, finite-set operations, and dense vertex and triangle projections through one versioned C ABI. Python, TypeScript, and Rust bindings live beneath bindings/ and descend through that same ABI; none restates the triangulation engine or introduces a second mesh representation.

union a a is a; commutativity and associativity hold after explicit canonicalize; and a join adds no sites: the result carries |A| + |B| − |A ∩ B| of them. Structural Eq remains exact resident equality for caches and serialization rather than secretly rebuilding the mesh.

Persistent publication schedules

The algebraic result is independent of the execution schedule. These are the currently measured publication choices; canonicalize remains the explicit global observation when construction-independent numbering is required.

Benchmark highlights

Fresh source build on 2026-08-12. The comparison binaries passed exact canonical-output agreement before seven interleaved fresh-process timing rounds; brackets are the observed range. Lower is better.

Spade exposes no public triangulation set algebra corresponding to these operations. Their independently witnessed Moonlight publication costs are:

These are raw publication measurements. canonicalize remains a separate, explicit observation when construction-independent numbering is required.

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 () () ())

Constraints

• No Semigroup, no Monoid, no <>. A join the finite arena cannot represent is a Left; a partial class instance would lie about totality.
• union and unions glue overlapping annotations through JoinSemilattice. intersectionWith supplies the corresponding explicit overlap combiner. difference preserves the left annotation and symmetricDifference preserves the annotation of whichever exclusive site survives. Plain intersection remains the geometry-only specialization. Annotation-preserving restriction is derived rather than stored as a second operator: intersectionWith const left mask.
• refine composes after an operation. It is not a mode, a flag, or a second triangulation type.
• Mutation lives in ST behind Moonlight.Triangulation.Internal.Mutable and never escapes.
• serialize is absent from the facade by design; import Moonlight.Triangulation.Serialization to reach it. Its canonical decoder requires both a DecodingBudget and explicit TrustedPayloadDecoders; wire format 6 validates one structural count prefix before decoding defaults, payloads, or allocating a section, and preserves the vertex payload plane's optional fill. The budget covers the input envelope and every module-owned container. trustedBinaryPayloadDecoders records the separate caller decision that the selected executable Binary decoders have an acceptable internal resource policy. Version 5 is intentionally unsupported.
• Resident triangulation coordinates are binary64. Exact planar-region APIs use normalized rational ExactPoints; an admitted OverlayResult seals those authoritative coordinates beside one certified binary64 DCEL projection. vertexPoints and innerFaceVertexTriples still project the resident DCEL directly; callers do not reconstruct a sibling mesh DTO.
• One half-edge mesh underneath. Cdt is a mode index on it, not a second structure.

The Haskell facade carries the exact region, overlay, valuation, and morphology algebra. ExactCellSet preserves closed point, edge, and face selections; PlanarRegion is its full-dimensional polygonal publication. The C ABI and Python, TypeScript, and Rust bindings carry the immutable binary64 mesh surface.

Use

A triangulation is a value of its site set: construction returns Either with typed obstructions, union returns the same typed refusal when the finite arena cannot represent its result, and mesh quality is a composition over the result rather than a second operation. This program compiles against the facade alone; fromList is GHC.Exts, so nothing beyond base and moonlight-triangulation is in scope.

module Main where

import GHC.Exts (fromList)
import Moonlight.Triangulation

main :: IO ()
main = do
  let build :: [(Double, Double)] -> IO (DelaunayTriangulation ())
      build coords =
        either (fail . show) pure (delaunayGeometry (fromList [Point x y | (x, y) <- coords]))
  a <- build [(x, y) | x <- [0 .. 9], y <- [0 .. 9]]
  b <- build [(x + 6, y) | x <- [0 .. 9], y <- [0 .. 9]]

  -- valid Delaunay representative of the union of sites
  joined <- either (fail . show) pure (union a b)

  -- meet and differences return typed obstructions, never partial results
  met <- either (fail . show) pure (intersection a b)

  -- mesh quality is a composition, not a second operation
  parameters <- either (fail . show) pure (withMinimumAngle 14 defaultRefinementParameters)
  result <- either (fail . show) pure (refine (const ()) parameters joined)
  let healed = refinedTriangulation result

  print (numVertices joined, numVertices met, numVertices healed, refinementComplete result)

Output: (160,40,160,True) — the union carries 160 sites, the meet 40, and refinement inserts nothing because every triangle already clears the 14° bar; refinementComplete states that sufficiency. Where operands leave concavities, the same composition places Steiner sites exactly at the slivers it dissolves.

delaunayGeometry constructs the unit-annotated carrier directly. Payloads can instead enter with their coordinates through delaunay, or independently through delaunayFromCoordinates; annotation-preserving restriction is available through intersectionWith, difference, and symmetricDifference. Constraints enter through constrainedDelaunay; bulk incremental work names the machine-room module directly (Moonlight.Triangulation.BulkLoad for insertMany, Moonlight.Triangulation.Session for the owned editing transaction — withSession: thaw once, insert and remove freely, publish once).

Interior without hull-fill

A point set has no boundary, so delaunay necessarily meshes the convex hull: concavities and holes are spanned by faces that belong to the hull, not to any intended region. The region becomes real the moment its boundary is authored: constrainedDelaunay takes the sites plus constraint segments as input-index pairs, and interiority is then computable — facesAtEvenBarrierDepth runs a 0–1 BFS from the outer face and returns every face at even barrier depth, which is exactly the outside (depth 0) plus anything nested behind a second loop. The interior is the complement. refine consumes the same parity through refineExcludeOuterFaces, so Steiner sites respect the boundary too.

module Main where

import GHC.Exts (fromList)
import Moonlight.Triangulation

ring :: Double -> Int -> [(Double, Double)]
ring radius n =
  [ (radius * cos t, radius * sin t)
  | k <- [0 .. n - 1]
  , let t = 2 * pi * fromIntegral k / fromIntegral n
  ]

main :: IO ()
main = do
  let outer = ring 4 32
      inner = ring 2 16
      middle = ring 3 24
      pts = fromList [Point x y | (x, y) <- outer <> inner <> middle]
      loop base count = [(base + k, base + (k + 1) `mod` count) | k <- [0 .. count - 1]]
      constraints = fromList (loop 0 32 <> loop 32 16)
  annulus <- case constrainedDelaunay unitElementDefaults pts constraints of
    Left err -> fail (show err)
    Right result -> pure (buildTriangulation result)
  let outside =
        [ fromIntegral raw :: Int
        | FaceId raw <- facesAtEvenBarrierDepth annulus (isConstraintEdge annulus)
        ]
      interior =
        [ FaceId (fromIntegral k)
        | k <- [0 .. numFaces annulus - 1]
        , not (k `elem` outside)
        ]
  print (numFaces annulus, length interior)

Output: (111,97) — the annulus band is the 97 interior faces; the 14 excluded faces are the hole's hull-fill and the outer region. Rendering the interior list draws the ring with a genuine void: no crop, no edge-length heuristic, the engine's own verdict. faceVertices walks each interior face for display, and a nested loop flips parity again, so islands inside holes come back automatically.

Deriving the boundary

When no boundary is known, classify the Delaunay faces and let the DCEL descend them. faceComponents evaluates the caller's label once per bounded face and keeps disconnected regions distinct even when their labels compare equal. componentBoundary then returns one counter-clockwise outer loop and clockwise hole loops, dropping a boundary vertex only when the library's exact orientation predicate proves it collinear and the point lies on the closed neighbour segment. A point pinch is a typed BoundaryPinch, never an invented polygon.

For alpha-shape work the supplied label is simply alphaShapeContainsFace threshold mesh. mkRadiusSquared admits the finite non-negative threshold and exact dyadic comparison makes membership closed at equality. This is the face, or 2-simplex, filtration; it does not manufacture a second mesh or pretend to own palette, colour-space, or rendering policy.

module Main where

import GHC.Exts (fromList)
import Moonlight.Triangulation

ring :: Double -> Int -> [(Double, Double)]
ring radius n =
  [ (radius * cos t, radius * sin t)
  | k <- [0 .. n - 1]
  , let t = 2 * pi * fromIntegral k / fromIntegral n
  ]

main :: IO ()
main = do
  let pts = ring 4 32 <> ring 2 16 <> ring 3 24
  mesh <-
    either
      (fail . show)
      pure
      (delaunayGeometry (fromList [Point x y | (x, y) <- pts]))
  threshold <- either (fail . show) pure (mkRadiusSquared 0.4)
  let components = faceComponents mesh (alphaShapeContainsFace threshold mesh)
      kept = [(label, component) | (label, component) <- components, label]
  boundaries <-
    traverse
      (either (fail . show) pure . componentBoundary mesh . snd)
      kept
  print
    [ ( length (boundaryLoopVertices (regionBoundaryOuterLoop boundary))
      , length (regionBoundaryHoleLoops boundary)
      )
    | boundary <- boundaries
    ]

The numeric threshold remains application policy; the circumradius calculation, face adjacency, loop extraction, winding, holes, and exact simplification do not. The derived boundary walks through data sites, so it is as jagged as the sampling; an authored boundary stays smooth at any pitch and wins where the generator is known.

Exact overlay, valuations, and morphology

Author polygonal regions with rational coordinates, refine labelled layers once, and select every Boolean from that common arrangement. Closed selection retains zero- and one-dimensional intersections; polygon publication dissolves all arrangement edges internal to the selected faces.

Valuations read either carrier. Euler characteristic and area remain exact, while Euclidean length is a normalized radical expression with certified binary64 bounds. Minkowski addition, offset, erosion, opening, and closing then compose over the same admitted PlanarRegion.

module Main where

import Data.List.NonEmpty (NonEmpty (..))
import qualified Data.Map.Strict as Map
import Moonlight.Triangulation

admit :: Show obstruction => Either obstruction value -> IO value
admit = either (fail . show) pure

rectangleLoop :: Integer -> Integer -> Integer -> Integer -> IO ExactLoop
rectangleLoop minimumX minimumY maximumX maximumY =
  admit
    ( exactLoop
        ( exactPoint (fromInteger minimumX) (fromInteger minimumY)
            :| [ exactPoint (fromInteger maximumX) (fromInteger minimumY)
               , exactPoint (fromInteger maximumX) (fromInteger maximumY)
               , exactPoint (fromInteger minimumX) (fromInteger maximumY)
               ]
        )
    )

rectangleRegion :: Integer -> Integer -> Integer -> Integer -> IO PlanarRegion
rectangleRegion minimumX minimumY maximumX maximumY = do
  outer <- rectangleLoop minimumX minimumY maximumX maximumY
  component <- admit (polygonComponent outer [])
  admit (planarRegion [component])

insideLayer :: PlanarRegion -> IO (PlanarLayer Bool)
insideLayer region = admit (planarLayer False (Map.singleton True region))

cellSummary :: ExactCellSet -> IO (Int, Integer, Integer, CertifiedInterval)
cellSummary cells = do
  values <- admit (cellValuations cells)
  perimeter <- admit (cellSetPerimeter cells)
  let area = exactAreaValue (valuationArea values)
  pure
    ( eulerCharacteristicValue (valuationEuler values)
    , exactRationalNumerator area
    , exactRationalDenominator area
    , exactLengthBounds perimeter
    )

regionArea :: PlanarRegion -> IO (Integer, Integer)
regionArea region = do
  values <- admit (regionValuations region)
  let area = exactAreaValue (valuationArea values)
  pure (exactRationalNumerator area, exactRationalDenominator area)

main :: IO ()
main = do
  left <- rectangleRegion 0 0 4 4
  right <- rectangleRegion 2 1 6 3
  leftLayer <- insideLayer left
  rightLayer <- insideLayer right
  overlay <- admit (overlayLayers leftLayer rightLayer)

  unionCells <- admit (overlayClosedUnion id id overlay)
  intersectionCells <- admit (overlayClosedIntersection id id overlay)
  differenceCells <- admit (overlayRegularizedDifference id id overlay)
  traverse cellSummary [unionCells, intersectionCells, differenceCells]
    >>= print

  kernelLoop <- rectangleLoop (-1) (-1) 1 1
  kernel <- admit (convexPolygon (exactLoopPoints kernelLoop)) >>= admit . structuringElement
  (sumRegion, _) <- admit (minkowskiSum left right)
  (offsetRegion, _) <- admit (polygonOffset kernel left)
  (insetRegion, _) <- admit (polygonInset kernel left)
  (openedRegion, _) <- admit (openWith kernel left)
  (closedRegion, _) <- admit (closeWith kernel left)
  traverse regionArea [sumRegion, offsetRegion, insetRegion, openedRegion, closedRegion]
    >>= print

The Boolean summaries are union (χ = 1, area = 20, perimeter = 20), intersection (1, 4, 8), and regularized difference (1, 12, 20). The morphology areas are (48, 36, 4, 16, 16): Minkowski sum, one-unit square offset, inset, opening, and closing respectively.

The growing city

A triangulation is a value so that a large one can be extended without being rebuilt or locked: a city mesh a district is added to, and then another.

union rebuilds last. planPair classifies the pair first — an empty or repeated operand returns the other verbatim, separable operands merge along their seam, a subset inserts into its superset, skewed sizes insert the smaller into the larger.

insertionIsCheaper addition base = addition <= 64 || addition <= base `quot` 8

A district is small against a city, so it inserts through a local copy-on-write transaction. Publication scales with the insertion work and pages dirtied rather than copying and renumbering the whole city.

The mesh being read is never the mesh being written. A render or pathfinding thread queries the published value while the next is built: no lock, no defensive copy, no interval in which the world and the mesh disagree. Mutation offers only the choice between stalling in place and answering from a clone that does not yet know what was built, and both are visible from the frame.

The same fact makes a failed union a Left over an untouched operand, reverting an edit a selection, and a preview a second value rather than a copy.

Moonlight.Triangulation.Parallel reads the operation the other way: regions triangulated apart, folded up a balanced tournament, each node's sides concurrent.

Representation

Structure-of-arrays over paged, copy-on-write storage. Half-edge twins are index complements (e xor 1), so traversal is arithmetic rather than indirection. Local insertion transactions copy only the pages they touch; mutation is confined to ST behind Moonlight.Triangulation.Internal.Mutable and never escapes.

Predicates

Moonlight.Triangulation.Internal.Dyadic carries the exact layer: mantissas are decoded and aligned to a common exponent, with bounded predicates evaluated in machine words and larger cases over Integer. Floating approximations are trusted only inside proved error bounds and fall through to exact evaluation otherwise.

Public sublibraries

Depend on the sublibrary you actually use, not on the facade. The footprint is the interface: each row states what the token costs you, and a build that pulls more than the row says is a bug in this table or in the cabal.

Surface

• Moonlight.Triangulation — the apex facade.
• .BulkLoad — circle-sweep construction and incremental insertion.
• .Cdt — constraint recovery by conflict strip, with requeue on re-intersection.
• .PointLocation, .HintGenerator — walk location and Delaunay hierarchy hints.
• .IntersectionIterator, .FloodFillIterator — ordered line traversal, barrier fill, labelled face components, boundary loops, and alpha-face filtration.
• .Exact, .CellSet, .Region, .Valuation — exact rational geometry, closed cell selections, admitted polygonal regions, and intrinsic measures.
• .Overlay, .Minkowski — labelled common refinement, planar Booleans, polygonal convolution, offset, erosion, opening, and closing.
• .Voronoi, .Interpolation — dual cells and natural-neighbour interpolation.
• .Refinement — Ruppert-style angle and area refinement.
• .Validation — structural and Delaunay-property audits.
• .Serialization (sublibrary serialize) — versioned binary envelope.