convexHull.hs

import Control.Arrow
import Data.List

clockwise :: (Int, Int) -> (Int, Int) -> (Int, Int) -> Bool
clockwise (x1, y1) (x2, y2) (x3, y3) = (x1 - x2) * (y3 - y2) - (x3 - x2) * (y1 - y2) < 0

-- Graph == [(Int, Int)]
convexHull :: Graph -> Graph
convexHull = (uncurry (++)) . (upperHalf &&& lowerHalf) . sort
  where
    lowerHalf = upperHalf . reverse
    upperHalf xs = go [] xs
    go xs [] = tail . reverse $ xs
    go (x1:x2:xs) (y:ys) = if clockwise x2 x1 y then go (y:x1:x2:xs) ys else go (x2:xs) (y:ys)
    go xs (y:ys) = go (y:xs) ys

{-

>>> convexHull [(0, 1), (2, -2), (2, -3), (1, 0), (-2, -2), (-1, 0), (0, -1), (-2, 2), (0, 0), (3, 0), (2, 1), (2, -4), (-3, 0), (1, -2)]
[(-2,-2),(2,-4),(3,0),(2,1),(-2,2),(-3,0)]

-}