{-|
== 2D convex hull

The convex hull is calculated using Andrew's monotone chain algorithm.

Sources:

* https://cp-algorithms.com/geometry/convex-hull.html
* R. L. Graham, "An Efficient Algorithm for Determining the Convex Hull of a Finite Planar Set",
  1972
  https://www.math.ucsd.edu/~ronspubs/72_10_convex_hull.pdf
* A. M. Andrew, "Another efficient algorithm for convex hulls in two dimensions", 1979
  https://www.sciencedirect.com/science/article/abs/pii/0020019079900723

-}

{-
Implementation notes:
* The description says points should be distinct but this is only an issue when the input is one
  point p repeated multiple times, the hull returned is [p, p] instead of [p].
* Update the turn condition to ==GT to allow redundant points on the hull. Warning: this introduces
  a duplication issue when all points are collinear.
-}

module ConvexHull
    ( convexHull
    ) where

import Data.List

import Geometry ( V2, turn )

-- | Calculates the convex hull for a set of points. The points should be distinct. The points on the
-- hull are returned in clockwise order. O(n log n).
convexHull :: [V2] -> [V2]
convexHull :: [V2] -> [V2]
convexHull []  = []
convexHull [V2
p] = [V2
p]
convexHull [V2]
ps  = [V2] -> [V2]
forall a. [a] -> [a]
tail (([V2] -> V2 -> [V2]) -> [V2] -> [V2] -> [V2]
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' [V2] -> V2 -> [V2]
f [] ([V2] -> [V2]
forall a. [a] -> [a]
reverse [V2]
ps')) [V2] -> [V2] -> [V2]
forall a. [a] -> [a] -> [a]
++ [V2] -> [V2]
forall a. [a] -> [a]
tail (([V2] -> V2 -> [V2]) -> [V2] -> [V2] -> [V2]
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' [V2] -> V2 -> [V2]
f [] [V2]
ps') where
    ps' :: [V2]
ps' = [V2] -> [V2]
forall a. Ord a => [a] -> [a]
sort [V2]
ps
    f :: [V2] -> V2 -> [V2]
f [V2]
hull V2
p = [V2] -> [V2]
go [V2]
hull where
        go :: [V2] -> [V2]
go (V2
p1:h :: [V2]
h@(V2
p2:[V2]
_)) | V2 -> V2 -> V2 -> Ordering
turn V2
p2 V2
p1 V2
p Ordering -> Ordering -> Bool
forall a. Eq a => a -> a -> Bool
/= Ordering
LT = [V2] -> [V2]
go [V2]
h
        go [V2]
h = V2
pV2 -> [V2] -> [V2]
forall a. a -> [a] -> [a]
:[V2]
h