-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/


-- | Collection of algorithms in Computational Geometry.
--   
--   Collection of algorithms in Computational Geometry.
@package computational-geometry
@version 0.1.0


module Geometry.SetOperations.Types

-- | Four basic set operations:
--   
data SetOperation
Union :: SetOperation
Intersection :: SetOperation
Difference :: SetOperation
SymmetricDifference :: SetOperation


module Data.EqZero

-- | Convenient universal zero equality predicate that warps to zero within
--   some epsilon for floating point numbers.
class EqZero a
eqZero :: EqZero a => a -> Bool

-- | Greater or equal to zero predicate.
geqZero :: (EqZero n, Ord n, Num n) => n -> Bool
instance Data.EqZero.EqZero GHC.Types.Float
instance Data.EqZero.EqZero GHC.Types.Double
instance Data.EqZero.EqZero Foreign.C.Types.CFloat
instance Data.EqZero.EqZero Foreign.C.Types.CDouble
instance Data.EqZero.EqZero GHC.Real.Rational


-- | General representation of a plane. Plane in the General Form is
--   Hession Normal Form scaled by an arbitrary non-zero scalar.
module Geometry.Plane.General

-- | Internally Plane is represented as a pair (sN, sO) where N is a normal
--   vector of a plane O is the distance of that plane from the origin and
--   s is an arbitrary non-zero scalar.
data Plane v n
Plane :: !(v n) -> !n -> Plane v n
[planeVector] :: Plane v n -> !(v n)
[planeLast] :: Plane v n -> !n
type Plane2 = Plane V2
type Plane3 = Plane V3
type Plane2D = Plane V2 Double
type Plane3D = Plane V3 Double
class MakePlane v n

-- | Make plane from vector of points. Returns Nothing if vectors between
--   points are linearly dependent
makePlane :: MakePlane v n => v (Point v n) -> Maybe (Plane v n)

-- | Assumes that points form a valid plane (i.e. vectors between all
--   points are linearly independent).
unsafeMakePlane :: MakePlane v n => v (Point v n) -> Plane v n

-- | Flip plane orientation.
flipPlane :: (Functor v, Num n) => Plane v n -> Plane v n

-- | Test whether two vectors are collinear.
collinear :: (Foldable v, Num n, EqZero n) => v n -> v n -> Bool
data PlanesRelation
Parallel :: Incidence -> Orientation -> PlanesRelation
Crossing :: PlanesRelation
data Incidence
CoIncident :: Incidence
NonIncident :: Incidence
data Orientation
CoOriented :: Orientation
AntiOriented :: Orientation

-- | Relate two planes on Parallelism, Incidence and Orientation.
planesRelation :: (Foldable v, Num n, Ord n, EqZero n) => Plane v n -> Plane v n -> PlanesRelation
isParallel :: (Foldable v, Num n, Ord n, EqZero n) => Plane v n -> Plane v n -> Bool
instance GHC.Show.Show Geometry.Plane.General.PlanesRelation
instance GHC.Show.Show Geometry.Plane.General.Orientation
instance GHC.Show.Show Geometry.Plane.General.Incidence
instance (GHC.Show.Show (v n), GHC.Show.Show n) => GHC.Show.Show (Geometry.Plane.General.Plane v n)
instance (GHC.Classes.Ord (v n), GHC.Classes.Ord n) => GHC.Classes.Ord (Geometry.Plane.General.Plane v n)
instance (GHC.Classes.Eq (v n), GHC.Classes.Eq n) => GHC.Classes.Eq (Geometry.Plane.General.Plane v n)
instance (Control.DeepSeq.NFData (v n), Control.DeepSeq.NFData n) => Control.DeepSeq.NFData (Geometry.Plane.General.Plane v n)
instance (GHC.Num.Num n, GHC.Classes.Eq n) => Geometry.Plane.General.MakePlane Linear.V3.V3 n


module Geometry.SetOperations.CrossPoint
data Sign
M :: Sign
Z :: Sign
P :: Sign
toSign :: (EqZero n, Ord n, Num n) => n -> Sign
data CrossPoint v n
CP :: (Plane v n -> Sign) -> Point v n -> CrossPoint v n
[orientation] :: CrossPoint v n -> Plane v n -> Sign
[getPoint] :: CrossPoint v n -> Point v n
class MakeCrossPoint v n
makeCrossPoint :: MakeCrossPoint v n => v (Plane v n) -> Maybe (CrossPoint v n)

-- | Convert a point to CrossPoint
toCrossPoint :: (EqZero n, Foldable v, Num n, Ord n) => Point v n -> CrossPoint v n
instance GHC.Classes.Eq Geometry.SetOperations.CrossPoint.Sign
instance GHC.Show.Show Geometry.SetOperations.CrossPoint.Sign
instance (GHC.Real.Fractional n, GHC.Classes.Ord n, Data.EqZero.EqZero n) => Geometry.SetOperations.CrossPoint.MakeCrossPoint Linear.V2.V2 n
instance (GHC.Real.Fractional n, GHC.Classes.Ord n, Data.EqZero.EqZero n) => Geometry.SetOperations.CrossPoint.MakeCrossPoint Linear.V3.V3 n


module Geometry.SetOperations.Facet
data Facet b v n
Facet :: Plane v n -> b -> Facet b v n
[facetPlane] :: Facet b v n -> Plane v n
[facetBoundary] :: Facet b v n -> b
type Facet2D = Facet (FB2 V2 Double) V2 Double
type Facet3D = Facet (FB3 V3 Double) V3 Double

-- | Flip orientation of a facet.
flipFacet :: (Functor v, Num n) => Facet b v n -> Facet b v n
type FB2 v n = (CrossPoint v n, CrossPoint v n)
type FB3 v n = [(CrossPoint v n, Plane v n)]


module Geometry.SetOperations.Clip
class Clip b v n where clipFacet p f = fst $ splitFacet p f splitFacet p f = (clipFacet p f, clipFacet (flipPlane p) f)
clipFacet :: Clip b v n => Plane v n -> Facet b v n -> Maybe (Facet b v n)
splitFacet :: Clip b v n => Plane v n -> Facet b v n -> (Maybe (Facet b v n), Maybe (Facet b v n))
splitFacet :: (Clip b v n, Functor v, Num n) => Plane v n -> Facet b v n -> (Maybe (Facet b v n), Maybe (Facet b v n))
vec3 :: (R3 v, Applicative v) => n -> n -> n -> v n
instance (Geometry.SetOperations.CrossPoint.MakeCrossPoint v n, Linear.V2.R2 v, GHC.Base.Applicative v, Data.Foldable.Foldable v, GHC.Num.Num n, GHC.Classes.Ord n, Data.EqZero.EqZero n) => Geometry.SetOperations.Clip.Clip (Geometry.SetOperations.Facet.FB2 v n) v n
instance (Geometry.SetOperations.CrossPoint.MakeCrossPoint v n, Linear.V3.R3 v, GHC.Base.Applicative v, Data.Foldable.Foldable v, GHC.Num.Num n, GHC.Classes.Ord n, Data.EqZero.EqZero n) => Geometry.SetOperations.Clip.Clip (Geometry.SetOperations.Facet.FB3 v n) v n


-- | Boundary representations for conversion to and from BSP/Volumes.
module Geometry.SetOperations.BRep

-- | Convert from polytope to a list of Facets.
class FromPolytopeRep p b v n
fromPolytopeRep :: FromPolytopeRep p b v n => p v n -> [Facet b v n]

-- | Convert from list of Facets to a polytope boundary representation.
class ToPolytopeRep p b v n
toPolytopeRep :: ToPolytopeRep p b v n => [Facet b v n] -> p v n

-- | Indexed 3-BRep as a list of convex polygons. Continent as a way to
--   introduce new base shapes into the constructive geometry context.
data Poly3 v n
Poly3 :: (Vector (Point v n)) -> [[Int]] -> Poly3 v n
type Poly3D = Poly3 V3 Double

-- | Simple direct 3-BRep as a list of triangles. Useful as an output after
--   performing specified set operations of the base shapes for rendering.
newtype PolyT3 v n
PolyT3 :: [[Point v n]] -> PolyT3 v n
type PolyT3D = PolyT3 V3 Double
instance GHC.Classes.Ord a => GHC.Classes.Ord (Geometry.SetOperations.BRep.OrdPair a)
instance GHC.Classes.Eq a => GHC.Classes.Eq (Geometry.SetOperations.BRep.OrdPair a)
instance GHC.Show.Show a => GHC.Show.Show (Geometry.SetOperations.BRep.OrdPair a)
instance (Geometry.Plane.General.MakePlane v n, GHC.Classes.Eq (v n), Data.Foldable.Foldable v, GHC.Base.Applicative v, Linear.V3.R3 v, GHC.Num.Num n, GHC.Classes.Ord n, Data.EqZero.EqZero n) => Geometry.SetOperations.BRep.FromPolytopeRep Geometry.SetOperations.BRep.Poly3 (Geometry.SetOperations.Facet.FB3 v n) v n
instance Geometry.SetOperations.BRep.ToPolytopeRep Geometry.SetOperations.BRep.PolyT3 (Geometry.SetOperations.Facet.FB3 v n) v n


module Geometry.SetOperations.BSP

-- | Binary Tree parametrized by leafs and nodes
data BinaryTree l n
Node :: (BinaryTree l n) -> !n -> (BinaryTree l n) -> BinaryTree l n
Leaf :: !l -> BinaryTree l n
data LeafColor
Green :: LeafColor
Red :: LeafColor
swapColor :: LeafColor -> LeafColor
type BSP = BinaryTree LeafColor

-- | Complementary set
cmp :: BSP a -> BSP a
constructBSP :: Clip b v n => (Facet b v n -> c) -> [Facet b v n] -> BSP c
splitWith :: (a -> (Maybe a, Maybe a)) -> [a] -> ([a], [a])
destructBinaryTree :: BinaryTree l n -> [n]

-- | Pretty print BSP tree to stdout.
prettyBSP :: (Ord f) => BSP f -> IO ()

-- | Render BSP into a horizontal tree with a given context.
renderH :: (Doc -> Doc) -> Context k -> BSP k -> Doc

-- | Denormalize BSP with integers at nodes and IntMap of values.
denormalizeBSP :: Ord n => BSP n -> (BSP Int, IntMap n)
instance GHC.Show.Show Geometry.SetOperations.BSP.LeafColor
instance GHC.Classes.Eq Geometry.SetOperations.BSP.LeafColor
instance GHC.Base.Functor (Geometry.SetOperations.BSP.BinaryTree l)
instance (GHC.Show.Show l, GHC.Show.Show n) => GHC.Show.Show (Geometry.SetOperations.BSP.BinaryTree l n)
instance (GHC.Classes.Eq l, GHC.Classes.Eq n) => GHC.Classes.Eq (Geometry.SetOperations.BSP.BinaryTree l n)
instance Data.Bifunctor.Bifunctor Geometry.SetOperations.BSP.BinaryTree


-- | Set Operations of Polytopes by BSP Merging.
module Geometry.SetOperations.Merge
type BSP = BinaryTree LeafColor
type BSP3D = BSP Facet3D
type BSP2D = BSP Facet2D
class Clip b v n => Universe b v n

-- | Turn plane into a Facet by clipping it by the universe box.
makeFacet :: Universe b v n => Plane v n -> Facet b v n

-- | Planes bounding the UniverseBox.
universePlanes :: (Applicative v, Traversable v, Num n) => [Plane v n]

-- | List of facets bounding the Universe.
universeBox :: (Universe b v n, Applicative v, Traversable v, Num n) => [Facet b v n]

-- | Split a region within a Universe bounded by a list of Facets.
splitRegion :: (Universe b v n, Functor v, Num n) => Plane v n -> [Facet b v n] -> ([Facet b v n], [Facet b v n])

-- | Perform a given SetOperation of two BSPs by merging
mergeBSPs :: (Universe b v n, Applicative v, Traversable v, Num n, Ord n, EqZero n) => SetOperation -> BSP (Facet b v n) -> BSP (Facet b v n) -> BSP (Facet b v n)

-- | Optimize a resulting BSP after merging by removing superficial
--   splitting planes.
trim :: Clip b v n => BSP (Facet b v n) -> BSP (Facet b v n)

-- | Make a BSP from a list of bounding facets.
makeBSP :: Clip b v n => [Facet b v n] -> BSP (Facet b v n)

-- | Reconstruct boundary facets from the BSP.
toBoundary :: (Clip b v n, Functor v, Num n) => BSP (Facet b v n) -> [Facet b v n]
instance (GHC.Classes.Ord n, GHC.Real.Fractional n, Data.EqZero.EqZero n) => Geometry.SetOperations.Merge.Universe (Geometry.SetOperations.Facet.FB2 Linear.V2.V2 n) Linear.V2.V2 n
instance (GHC.Classes.Ord n, GHC.Real.Fractional n, Data.EqZero.EqZero n) => Geometry.SetOperations.Merge.Universe (Geometry.SetOperations.Facet.FB3 Linear.V3.V3 n) Linear.V3.V3 n


-- | Set Operations of Polytopes by Boundary Filtering.
module Geometry.SetOperations.Volume

-- | Volume, currently represented as a list of Facets and a BSP Tree.
data Volume b v n
Volume :: [Facet b v n] -> BSP (Plane v n) -> Volume b v n
[volumeFacets] :: Volume b v n -> [Facet b v n]
[volumeTree] :: Volume b v n -> BSP (Plane v n)

-- | Construct Volume from a list of Facets representing it's boundary.
makeVolume :: Clip b v n => [Facet b v n] -> Volume b v n

-- | Empty volume.
emptyVolume :: Volume b v n

-- | Merge two Volumes under a specified Set Operation.
mergeVolumes :: (Clip b v n, Functor v, Num n) => SetOperation -> Volume b v n -> Volume b v n -> Volume b v n
type Volume2D = Volume (FB2 V2 Double) V2 Double
type Volume3D = Volume (FB3 V3 Double) V3 Double


-- | Set Operations of Polytopes. You can read about implementation details
--   of this algorithm in a dedicated <a>Blog Post</a>.
--   
--   Small example:
--   
--   <pre>
--   test :: SetOperation -&gt; Double -&gt; PolyT3D
--   test op t = fromVolume $ merge op boxA boxB
--       where
--       boxA = cube
--       boxB = toVolume $ Poly3 (papply tr &lt;$&gt; ps) is
--       Poly3 ps is = cubePoly3
--       tr = translation (V3 (sin (t*0.3) * 0.3) 0.2 0.3)
--          &lt;&gt; aboutX (t*20 @@ deg)
--          &lt;&gt; aboutY (t*3  @@ deg)
--   </pre>
--   
--   Rendered:
--   
module Geometry.SetOperations

-- | Volume, currently represented as a list of Facets and a BSP Tree.
data Volume b v n

-- | Empty volume.
emptyVolume :: Volume b v n

-- | Convert an arbitrary polytope boundary representation into a Volume.
toVolume :: (FromPolytopeRep p b v n, Clip b v n, Functor v, Num n) => p v n -> Volume b v n

-- | Recover a boundary representation of a Volume.
fromVolume :: ToPolytopeRep p b v n => Volume b v n -> p v n

-- | Four basic set operations:
--   
data SetOperation
Union :: SetOperation
Intersection :: SetOperation
Difference :: SetOperation
SymmetricDifference :: SetOperation

-- | Merge two Volumes under a specified Set Operation.
merge :: Merge b v n => SetOperation -> Volume b v n -> Volume b v n -> Volume b v n

-- | Merges list of Volumes under a specified Set Operation. Empty list
--   equals empty set.
merges :: Merge b v n => SetOperation -> [Volume b v n] -> Volume b v n

-- | Union of two volumes. Convenience synonym for `merge Union`
union :: Merge b v n => Volume b v n -> Volume b v n -> Volume b v n

-- | Union of list of volumes.
unions :: Merge b v n => [Volume b v n] -> Volume b v n

-- | Intersection of two volumes.
intersection :: Merge b v n => Volume b v n -> Volume b v n -> Volume b v n

-- | Intersection of list of volumes.
intersections :: Merge b v n => [Volume b v n] -> Volume b v n

-- | Difference between two volumes.
difference :: Merge b v n => Volume b v n -> Volume b v n -> Volume b v n

-- | Subtract list of volumes from a given volume.
differences :: Merge b v n => Volume b v n -> [Volume b v n] -> Volume b v n

-- | Convert from polytope to a list of Facets.
class FromPolytopeRep p b v n

-- | Convert from list of Facets to a polytope boundary representation.
class ToPolytopeRep p b v n

-- | Indexed 3-BRep as a list of convex polygons. Continent as a way to
--   introduce new base shapes into the constructive geometry context.
data Poly3 v n
Poly3 :: (Vector (Point v n)) -> [[Int]] -> Poly3 v n

-- | Simple direct 3-BRep as a list of triangles. Useful as an output after
--   performing specified set operations of the base shapes for rendering.
newtype PolyT3 v n
PolyT3 :: [[Point v n]] -> PolyT3 v n

-- | Cube represented as a denormalized list of polygons.
cubePoly3 :: Poly3D

-- | Cube volume.
cube :: Volume3D

-- | Convert a simple 3-BRep polyhedron to a Volume.
toVolume3D :: Poly3D -> Volume3D

-- | Reconstruct a triangulated 3-BRep from a Volume.
fromVolume3D :: Volume3D -> PolyT3D