-- 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. The code is explained in this diploma thesis:
--   <a>www.dinkla.net/download/GeomAlgHaskell.pdf</a>. The original author
--   made a very big library that needs a long time to compile. Thats why
--   only one algorithm was extracted and freed from a big net of inner
--   dependencies and types.
@package triangulation
@version 0.2

module Graphics.Triangulation.Triangulation
type Points = Array Int (Float, Float)
type TriangulationFunction = Points -> [Int] -> [(Int, Int, Int)]
data Tree
Node :: Int -> Int -> [Tree] -> Tree
type F2 = (Float, Float)

-- | since there are a lot of triangulation algorithms a triangulation
--   function can be passed
triangulate :: TriangulationFunction -> Geometry -> Geometry

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

-- | cut a polygon at a good position and insert the contained hole-polygon
--   with opposite direction
embed :: Points -> [[Int]] -> [Int] -> [Int]

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

-- | f should be the funtion to test <a>contains</a> the trees then are the
--   hierarchy of containedness of outlines
generateTrees :: Points -> (Points -> [Int] -> [Int] -> Bool) -> [[Int]] -> [Tree]
treesList :: Points -> [[Int]] -> [Tree] -> [Tree]
insertTrees :: Points -> [Int] -> [Tree] -> [Tree]
insertTree :: Points -> [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 :: Int -> Points -> [Int] -> (Int, Float)
nearest :: F2 -> [F2] -> Float -> Int -> Int -> (Int, Float)

-- | returns True iff the first point of the first polygon is inside the
--   second poylgon
insidePoly :: Points -> [Int] -> [Int] -> Bool

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

-- | the direction of a polygon can be obtained by looking at a maximal
--   point returns True if counterclockwise False if clockwise
polygonDirection :: [F2] -> Bool
isLeftTurn :: F2 -> F2 -> F2 -> 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
--   
--   see Joern Dinkla, Geometrische Algorithmen in Haskell, Diploma Thesis,
--   University of Bonn, Germany, 1998.
module Graphics.Triangulation.KETTriangulation
ketTri :: Points -> [Int] -> [(Int, Int, Int)]