Points.hs

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