Triangulation.hs

-- | The public surface for Delaunay triangulations as values of finite
-- coordinate supports. Its exports are grouped by object, generation,
-- annotations, finite-set algebra, constraints, refinement, observations and
-- validation.
--
-- Geometry-only set laws are observed after erasing vertex annotations with
-- @mapVertices (const ())@ and applying 'canonicalize'. Successful construction
-- may retain schedule-dependent resident numbering, so structural 'Eq' compares
-- stored representations rather than silently normalizing them. Annotations may
-- change independently through 'mapVertices' and 'setVertexData'; they never
-- determine geometry.
--
-- The algebra is deliberately partial. Finite arena exhaustion is returned as
-- 'BuildError', while unrealizable constrained compositions return
-- 'ConstrainedUnionError'. These typed obstructions are why the surface exposes
-- explicit operations rather than total 'Semigroup' instances. Refinement then
-- composes over any admitted result without introducing a second mesh type.
module Moonlight.Triangulation
  ( -- * The object — a triangulation is a value of its site set
    Triangulation
  , DelaunayTriangulation
  , ConstrainedDelaunayTriangulation
  , ConstraintMode (..)
  , Point (..)
  , QueryPoint
  , queryPointValue
  , PointValidationError (..)
  , mkQueryPoint
  , HasPosition (..)
  , ElementDefaults (..)
  , unitElementDefaults
  , JoinSemilattice (..)
    -- | An identifier is admitted by the triangulation that issued it. The
    -- observations below index without a second bounds check, so the
    -- constructors are withheld here and the projections are not: an
    -- identifier can be read, compared and carried, and can only be obtained
    -- from a mesh. "Moonlight.Triangulation.Handles.HandleDefs" exports the
    -- constructors for a caller who is willing to own that obligation.
  , VertexId
  , unVertexId
  , FaceId
  , unFaceId
  , DirectedEdgeId
  , unDirectedEdgeId
  , UndirectedEdgeId
  , unUndirectedEdgeId
  , reverseEdge
  , asUndirected
  , normalizedDirected
  , reversedDirected
  , directedPair
  , isNormalized

    -- * Generation — @delaunay@; canonical observation factors through the site set
  , delaunay
  , BuildResult
  , buildTriangulation
  , buildInputVertices
  , BuildError (..)
  , CoordinateError (..)
  , NonFiniteValue (..)

    -- * The annotation functor — payloads annotate geometry, never author it;
    -- the mesh is the same mesh before and after
  , mapVertices
  , vertexData
  , setVertexData

    -- * Finite-set algebra and its normal form — support order is observable,
    -- intersection can combine heterogeneous annotations, and each
    -- construction returns its obstruction rather than an instance that lies
  , canonicalize
  , SiteRelation (..)
  , siteRelation
  , union
  , unions
  , intersection
  , intersectionWith
  , difference
  , symmetricDifference

    -- * The constraint layer — 'constrainedDelaunay' is the partial map from
    -- (sites, segments), defined exactly on realizable segment sets and
    -- naming the corridor that blocked it where it is not
  , constrainedDelaunay
  , fromDelaunay
  , constraintEdges
  , isConstraintEdge
  , CdtError (..)
  , CorridorObstruction (..)
  , CanonicalSegment
  , segmentStart
  , segmentEnd
  , ConstraintConflict
  , conflictFirstSegment
  , conflictSecondSegment
  , ConstrainedUnionError (..)
  , ConstrainedExtensionResult
  , constrainedExtensionTriangulation
  , constrainedExtensionConstraintOutcomes
  , constrainedExtensionConstraintStats
  , constrainedExtensionBuildStats
  , ConstrainedSeamSource (..)
  , ConstrainedSeamFaceEvidence
  , constrainedSeamSourceFace
  , constrainedSeamTargetFace
  , constrainedSeamFaceFirstPoint
  , constrainedSeamFaceSecondPoint
  , constrainedSeamFaceThirdPoint
  , ConstrainedSeamConstraintEvidence
  , constrainedSeamConstraintSegment
  , constrainedSeamConstraintRecovery
  , ConstrainedSeamResult
  , constrainedSeamResultTriangulation
  , constrainedSeamLeftFaceEvidence
  , constrainedSeamRightFaceEvidence
  , constrainedSeamNewFaces
  , constrainedSeamLeftConstraintEvidence
  , constrainedSeamRightConstraintEvidence
  , constrainedSeamConstraintStats
  , constrainedSeamBuildStats
  , constraintSegments
  , unionConstrainedWith
  , unionConstrained
  , joinSeparatedConstrainedWith
  , extendConstrainedWith

    -- * Refinement — budget-bounded, composed after any operation above rather
    -- than configured into it; 'refinementComplete' reports sufficiency, not
    -- effort
  , refine
  , refineWithinDomain
  , validateRefinementParameters
  , RefinementParameters (..)
  , defaultRefinementParameters
  , RefinementReceipt
  , RefinementDomainResult
  , RefinementResult
  , refinementDomainResult
  , refinementDomainReceipt
  , refinedTriangulation
  , refinementVisitedJoinFaces
  , refinementVisitedProtectedFaces
  , refinementCreatedFaces
  , refinementTouchedEdges
  , refinementRemovedEdges
  , refinementInterfaceBoundaryReads
  , refinementAttemptedBoundaryCrossings
  , refinementAddedVertices
  , refinementExcludedFaces
  , refinementComplete
  , withMinimumAngle
  , radiusEdgeRatioForAngle

    -- * Observations — pure functions of the value: incidence, location,
    -- interpolation and barrier parity, none of which build a second mesh
  , numVertices
  , vertices
  , vertexPoint
  , vertexPoints
  , numFaces
  , innerFaces
  , outerFace
  , faceDirectedEdges
  , faceVertices
  , innerFaceVertexTriples
  , vertexOutgoingEdges
  , numUndirectedEdges
  , undirectedEdges
  , undirectedEndpoints
  , origin
  , destination
  , incidentFace
  , isBoundaryEdge
  , nearestNeighbor
  , NearestStats (..)
  , interpolateNearest
  , interpolateBarycentric
  , LocationHint (..)
  , facesAtEvenBarrierDepth

    -- * Discharge — the invariants the constructors guarantee, checkable on a
    -- value built by any route; every violation is a value carrying its witness
  , validateTriangulation
  , InvariantViolation (..)
  ) where

import Moonlight.Triangulation.BulkLoad (delaunay)
import Moonlight.Triangulation.Dcel
  ( destination
  , faceDirectedEdges
  , faceVertices
  , innerFaceVertexTriples
  , incidentFace
  , isBoundaryEdge
  , isConstraintEdge
  , numFaces
  , numUndirectedEdges
  , numVertices
  , origin
  , outerFace
  , setVertexData
  , undirectedEndpoints
  , vertexData
  , vertexOutgoingEdges
  , vertexPoint
  , vertexPoints
  )
import Moonlight.Triangulation.FloodFillIterator (facesAtEvenBarrierDepth)
import Moonlight.Triangulation.Handles.HandleDefs
  ( DirectedEdgeId (..)
  , FaceId (..)
  , UndirectedEdgeId (..)
  , VertexId (..)
  , asUndirected
  , directedPair
  , isNormalized
  , normalizedDirected
  , reverseEdge
  , reversedDirected
  )
import Moonlight.Triangulation.Handles.Iterators.FixedIterators
  ( innerFaces
  , undirectedEdges
  , vertices
  )
import Moonlight.Triangulation.Internal.Canonical (canonicalize)
import Moonlight.Triangulation.Internal.Cdt.Build
  ( constrainedDelaunay
  , fromDelaunay
  )
import Moonlight.Triangulation.Internal.Cdt.Query (constraintEdges)
import Moonlight.Triangulation.Internal.Cdt.Types
  ( CanonicalSegment
  , CdtError (..)
  , ConstrainedUnionError (..)
  , ConstrainedExtensionResult
  , ConstrainedSeamConstraintEvidence
  , ConstrainedSeamFaceEvidence
  , ConstrainedSeamResult
  , ConstrainedSeamSource (..)
  , ConstraintConflict
  , CorridorObstruction (..)
  , constrainedExtensionBuildStats
  , constrainedExtensionConstraintOutcomes
  , constrainedExtensionConstraintStats
  , constrainedExtensionTriangulation
  , constrainedSeamBuildStats
  , constrainedSeamConstraintRecovery
  , constrainedSeamConstraintSegment
  , constrainedSeamConstraintStats
  , constrainedSeamFaceFirstPoint
  , constrainedSeamFaceSecondPoint
  , constrainedSeamFaceThirdPoint
  , constrainedSeamLeftConstraintEvidence
  , constrainedSeamLeftFaceEvidence
  , constrainedSeamNewFaces
  , constrainedSeamResultTriangulation
  , constrainedSeamRightConstraintEvidence
  , constrainedSeamRightFaceEvidence
  , constrainedSeamSourceFace
  , constrainedSeamTargetFace
  , conflictFirstSegment
  , conflictSecondSegment
  , segmentEnd
  , segmentStart
  )
import Moonlight.Triangulation.Internal.Cdt.Union
  ( constraintSegments
  , extendConstrainedWith
  , joinSeparatedConstrainedWith
  , unionConstrained
  , unionConstrainedWith
  )
import Moonlight.Triangulation.Internal.Representation
  ( BuildResult
  , ConstrainedDelaunayTriangulation
  , DelaunayTriangulation
  , RefinementDomainResult
  , RefinementReceipt
  , RefinementResult
  , Triangulation
  , buildInputVertices
  , buildTriangulation
  , refinementDomainReceipt
  , refinementDomainResult
  , refinedTriangulation
  , refinementInterfaceBoundaryReads
  , refinementAttemptedBoundaryCrossings
  , refinementAddedVertices
  , refinementComplete
  , refinementCreatedFaces
  , refinementExcludedFaces
  , refinementRemovedEdges
  , refinementTouchedEdges
  , refinementVisitedJoinFaces
  , refinementVisitedProtectedFaces
  )
import Moonlight.Triangulation.Internal.Types
  ( BuildError (..)
  , ConstraintMode (..)
  , CoordinateError (..)
  , ElementDefaults (..)
  , HasPosition (..)
  , InvariantViolation (..)
  , LocationHint (..)
  , NearestStats (..)
  , NonFiniteValue (..)
  , Point (..)
  , PointValidationError (..)
  , QueryPoint
  , RefinementParameters (..)
  , SiteRelation (..)
  , defaultRefinementParameters
  , queryPointValue
  , unitElementDefaults
  )
import Moonlight.Triangulation.Interpolation
  ( interpolateBarycentric
  , interpolateNearest
  , nearestNeighbor
  )
import Moonlight.Triangulation.Math (mkQueryPoint)
import Moonlight.Triangulation.Payload (mapVertices)
import Moonlight.Triangulation.JoinSemilattice (JoinSemilattice (..))
import Moonlight.Triangulation.Refinement
  ( radiusEdgeRatioForAngle
  , refine
  , refineWithinDomain
  , validateRefinementParameters
  , withMinimumAngle
  )
import Moonlight.Triangulation.SetAlgebra
  ( difference
  , intersection
  , intersectionWith
  , siteRelation
  , symmetricDifference
  , union
  , unions
  )
import Moonlight.Triangulation.Validation (validateTriangulation)