content: {-# LANGUAGE ConstraintKinds #-}
  -----------------------------------------------------------------------------
  -- |
  -- Module      :  Diagrams.TwoD.Points
  -- Copyright   :  (c) 2014 diagrams-lib team (see LICENSE)
  -- License     :  BSD-style (see LICENSE)
  -- Maintainer  :  diagrams-discuss@googlegroups.com
  --
  -- Special functions for points in R2.
  --
  -----------------------------------------------------------------------------
  
  {-# LANGUAGE TypeFamilies #-}
  
  module Diagrams.TwoD.Points where
  
  import Data.List
  
  import Diagrams.Core
  import Diagrams.TwoD.Vector
  import Diagrams.TwoD.Types (P2)
  
  import Linear.Affine
  
  -- | Find the convex hull of a list of points using Andrew's monotone chain
  --   algorithm O(n log n).
  --   
  --   Returns clockwise list of points starting from the left-most point.
  convexHull2D :: OrderedField n => [P2 n] -> [P2 n]
  convexHull2D ps = init upper ++ reverse (tail lower)
    where
      (upper, lower) = sortedConvexHull (sort ps)
  
  -- | Find the convex hull of a set of points already sorted in the x direction. 
  --   The first list of the tuple is the upper hull going clockwise from 
  --   left-most to right-most point. The second is the lower hull from 
  --   right-most to left-most in the anti-clockwise direction.
  sortedConvexHull :: OrderedField n => [P2 n] -> ([P2 n], [P2 n])
  sortedConvexHull ps = (chain True ps, chain False ps)
   where
     chain upper (p1_:p2_:rest_) =
       case go (p2_ .-. p1_) p2_ rest_ of
         Right l -> p1_:l
         Left l  -> chain upper (p1_:l)
       where
         test = if upper then (>0) else (<0)
         -- find the convex hull by comparing the angles of the vectors with
         -- the cross product and backtracking if necessary
         go dir p1 l@(p2:rest)
           -- backtrack if the direction is outward
           | test $ dir `cross2` dir' = Left l
           | otherwise                =
               case go dir' p2 rest of
                 Left m  -> go dir p1 m
                 Right m -> Right (p1:m)
           where
             dir' = p2 .-. p1
         go _ p1 p = Right (p1:p)
  
     chain _ l = l
  