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

module GeomAlg.Pertub (noXdups, noYdups) where

import GeomAlg.Point2  ( 
	Point2D, Point2 (..), rotateOrg, leftOrBelow, belowOrLeft, 
	angle2, equalIth )
import List	 ( groupBy )
import GeomAlg.External.Utilities ( isSingleton )
import GeomAlg.External.Sorting ( sortBy )

type Pertub a b c d           = a -> (c -> d, b)
 
-- | 'noXdups' and 'noYdups' rotate a set of points so that no two points have the same x/y coordinates [K97, p.74-75] 

noXdups, noYdups              :: Pertub [Point2D] [Point2D] [Point2D] [Point2D]
noXdups ps                    = case xAngle ps of
                                  Nothing -> (id, ps)
                                  Just angle -> ( map (flip rotateOrg (-angle)), map (flip rotateOrg angle) ps )
  where rot phi		          = map (flip rotateOrg phi) 

noYdups ps                    = case yAngle ps of
                                  Nothing -> (id, ps)
                                  Just angle -> (rot (-angle), rot angle ps)
  where rot phi               = map (flip rotateOrg phi) 
				    
xAngle, yAngle                :: [Point2D] -> Maybe Double
xAngle                        = rotationAngle leftOrBelow (equalIth 1) (Point2 (0,-1))
yAngle                        = rotationAngle belowOrLeft (equalIth 2) (Point2 (-1,0))

rotationAngle                 :: (Point2D -> Point2D -> Bool) 
                                 -> (Point2D -> Point2D -> Bool) 
                                 -> Point2D -> [Point2D] -> Maybe Double
rotationAngle less rel v ps
  | isSingleton grouped       = Just (- (pi/2))
  | all isSingleton grouped   = Nothing
  | otherwise                 = Just (- (minimum angles / 2))
  where sorted                = sortBy less ps
        grouped               = groupBy rel sorted
        angles                = map angle' (connect grouped)
        angle' (p,q)          = angle2 v (q-p)
        connect (x:y:ys)      = (last x, head y) : connect (y:ys)
        connect _             = []