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


-- | triangulation of polygons
--   
--   An implementation of a simple triangulation algorithm for polygons
--   without crossings (holes are possible). The code is explained her:
--   <a>www.dinkla.net/download/GeomAlgHaskell.pdf</a>.
@package triangulation
@version 0.3

module Graphics.Triangulation.GJPTriangulation
data VertexType
TopCap :: VertexType
BottomCap :: VertexType
TopCup :: VertexType
BottomCup :: VertexType
Side :: VertexType
data Vertex
Vtx :: Int -> Int -> Int -> VertexType -> Float -> Float -> Vertex
idx :: Vertex -> Int
prev :: Vertex -> Int
next :: Vertex -> Int
vtype :: Vertex -> VertexType
px :: Vertex -> Float
py :: Vertex -> Float
type MonotoneSegment = ([Int], [Int])
type Separation = (Ordering, Int, Int)

-- | Checking whether an angle is within a given interval.
between :: Angle -> (Angle, Angle) -> Bool

-- | The sum of two angles.
(+<) :: Angle -> Angle -> Angle

-- | Linear interpolation between two angles along the smaller arc.
alerp :: Angle -> Angle -> Float -> Angle

-- | Applying a binary function to consecutive pairs in a vector with
--   wrap-around.
pairsWith :: (a -> a -> b) -> Vector a -> Vector b

-- | The edge vectors of a polygon given as a list of vertices.
edges :: Vector V2 -> Vector V2

-- | The absolute angles (with respect to the x axis) of the edges of a
--   polygon given as a list of vertices.
angles :: Vector V2 -> Vector Angle

-- | The signed area of a simple polygon (positive if vertices are in
--   counter-clockwise order).
area :: Vector V2 -> Float

-- | The centroid of a simple polygon.
centroid :: Vector V2 -> V2

-- | The moment of inertia of a simple polygon with respect to the origin.
moment :: Vector V2 -> Float

-- | The convex hull of a collection of vertices in counter-clockwise
--   order. (Andrew's Monotone Chain Algorithm)
convexHull :: Vector V2 -> Vector V2

-- | Monotone decomposition of a simple polygon.
monotoneDecomposition :: Vector V2 -> [MonotoneSegment]

-- | Triangulation of a monotone polygon.
monotoneTriangulation :: Vector V2 -> MonotoneSegment -> [(Int, Int, Int)]

-- | Triangulation of a simple polygon.
triangulation :: Vector V2 -> [(Int, Int, Int)]

-- | A 5-tuple <tt>(d2,ds,sep,v1,v2)</tt> that provides distance
--   information on two convex polygons, where <tt>d2</tt> is the square of
--   the distance, <tt>ds</tt> is its sign (negative in case of
--   penetration), <tt>sep</tt> describes the opposing features, while
--   <tt>v1</tt> and <tt>v2</tt> are the absolute coordinates of the
--   deepest points within the opposite polygon. If the third parameter is
--   <tt>True</tt>, only negative distances are reported, and the function
--   yields <tt>Nothing</tt> for non-overlapping polygons. This is more
--   efficient if we are only interested in collisions, since the
--   computation can be cancelled upon finding the first separating axis.
--   If the third parameter is <tt>False</tt>, the result cannot be
--   <tt>Nothing</tt>.
convexSeparation :: Vector V2 -> Vector V2 -> Bool -> Maybe (Float, Float, Separation, V2, V2)
instance Show VertexType
instance Show Vertex

module Graphics.Triangulation.Triangulation
type TriangulationFunction = Vector V2 -> [(Int, Int, Int)]
data Tree
Node :: Int -> Int -> [Tree] -> Tree

-- | since there are a lot of triangulation algorithms a triangulation
--   function can be passed
triangulate :: TriangulationFunction -> Geometry -> Geometry
v2s :: Vector V3 -> Vector Int -> Vector V2
gjpTri :: Vector V2 -> [(Int, Int, Int)]

-- | some triangulation algorithms on't support polygons with holes These
--   polygons with (nested) holes have to be cut so that they consist of
--   only one outline I.e. the chars a,b,d,e,g,o,p,q contain holes tat have
--   to be deleted.
deleteHoles :: Geometry -> Geometry
flatten :: Vector V2 -> [Tree] -> Vector (Vector Int) -> Vector (Vector Int)

-- | cut a polygon at a good position and insert the contained hole-polygon
--   with opposite direction
embed :: Vector V2 -> Vector (Vector Int) -> Vector Int -> Vector Int

-- | make sure that direction (clockwise or ccw) of polygons alternates
--   depending on the nesting number c of poly
alternate :: Int -> Bool -> Vector Int -> Vector Int

-- | f should be the funtion to test <a>contains</a> the trees then are the
--   hierarchy of containedness of outlines
generateTrees :: Vector V3 -> (Vector V2 -> Vector V2 -> Bool) -> Vector (Vector Int) -> [Tree]
treesList :: [[Int]] -> [Tree] -> [Tree]
insertTrees :: [Int] -> [Tree] -> [Tree]
insertTree :: [Int] -> Tree -> (Bool, Tree)

-- | how many positions to rotate a polygon until the start point is
--   nearest to some other point call i.e. with nearest (3,4) [(0,0),(1,2),
--   ... ] 0 0
rotatePoly :: V2 -> Vector V2 -> (Int, Float)
nearest :: V2 -> Vector V2 -> Float -> Int -> Int -> (Int, Float)

-- | returns True iff the first point of the first polygon is inside the
--   second poylgon
insidePoly :: Vector V2 -> Vector V2 -> Bool

-- | A point is inside a polygon if it has an odd number of intersections
--   with the boundary (Jordan Curve theorem)
pointInside :: V2 -> Vector V2 -> Bool

-- | the direction of a polygon can be obtained by looking at a maximal
--   point returns True if counterclockwise False if clockwise
polygonDirection :: Vector V2 -> Bool
maxim :: Vector V2 -> Int -> Int -> (Float, Float) -> Int
isLeftTurn :: V2 -> V2 -> V2 -> Bool
instance Show Tree


-- | Triangulation of simple polygons after Kong, Everett, Toussaint 91
--   with some changes by T.Vogt: return indices instead of coordinates of
--   triangles and Data.Vector instead of lists
--   
--   see Joern Dinkla, Geometrische Algorithmen in Haskell, Diploma Thesis,
--   University of Bonn, Germany, 1998.
module Graphics.Triangulation.KETTriangulation
ketTri :: Vector V2 -> [(Int, Int, Int)]