{-
%------------------------------------------------------------------------------
% Copyright (C) 1997, 1998, 2008, 2009 Joern Dinkla, www.dinkla.net
%------------------------------------------------------------------------------
%
% see
%     Joern Dinkla, Geometrische Algorithmen in Haskell, Diploma Thesis,
%     University of Bonn, Germany, 1998. 
%
-}

-- | The canonical algorithm by Garey et. al.

module GeomAlg.Triangulation.GareysTriangulation ( garey ) where

import GeomAlg.Polygon               ( Polygon2 )
import GeomAlg.Triangle              ( Triangle2 )
import GeomAlg.Triangulation.MonotoneTriangulation ( monoTri )
import GeomAlg.Triangulation.MonotonePartition     ( monotonePartition )

-- |garey trianguliert ein einfaches Polygon in $O(n\log n)$ nach dem Algorithmus von Garey, Johnson, Preparata und Tarjan.

garey                         :: (Ord a, Fractional a) => Polygon2 a -> [Triangle2 a]
garey                         = concatMap monoTri . monotonePartition