module Geometry.ConvexHull where

import qualified Data.List as L

import Geometry

convexHull :: (Num a, Ord a) => [Point a] -> [Point a]
convexHull :: forall a. (Num a, Ord a) => [Point a] -> [Point a]
convexHull [Point a]
points = case [Point a] -> [Point a]
forall a. Ord a => [a] -> [a]
L.sort [Point a]
points of
  [] -> []
  (Point a
leftest : [Point a]
sorted) ->
    [Point a] -> [Point a]
forall a. [a] -> [a]
reverse ([Point a] -> [Point a])
-> ([Point a] -> [Point a]) -> [Point a] -> [Point a]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [Point a] -> [Point a] -> [Point a]
forall {a}. (Num a, Ord a) => [Point a] -> [Point a] -> [Point a]
go [Point a
leftest] ([Point a] -> [Point a]) -> [Point a] -> [Point a]
forall a b. (a -> b) -> a -> b
$ (Point a -> Point a -> Ordering) -> [Point a] -> [Point a]
forall a. (a -> a -> Ordering) -> [a] -> [a]
L.sortBy (Point a -> Point a -> Point a -> Ordering
forall a.
(Num a, Ord a) =>
Point a -> Point a -> Point a -> Ordering
compareCCW Point a
leftest) [Point a]
sorted
  where
    go :: [Point a] -> [Point a] -> [Point a]
go (Point a
p : Point a
q : [Point a]
conv) (Point a
r : [Point a]
rs) = case Point a -> Point a -> Point a -> Ordering
forall a.
(Num a, Ord a) =>
Point a -> Point a -> Point a -> Ordering
compareCCW Point a
q Point a
p Point a
r of
      Ordering
LT -> [Point a] -> [Point a] -> [Point a]
go (Point a
r Point a -> [Point a] -> [Point a]
forall a. a -> [a] -> [a]
: Point a
p Point a -> [Point a] -> [Point a]
forall a. a -> [a] -> [a]
: Point a
q Point a -> [Point a] -> [Point a]
forall a. a -> [a] -> [a]
: [Point a]
conv) [Point a]
rs
      Ordering
GT -> [Point a] -> [Point a] -> [Point a]
go (Point a
q Point a -> [Point a] -> [Point a]
forall a. a -> [a] -> [a]
: [Point a]
conv) (Point a
r Point a -> [Point a] -> [Point a]
forall a. a -> [a] -> [a]
: [Point a]
rs)
      Ordering
EQ
        | Point a -> Point a -> a
forall a. Num a => Point a -> Point a -> a
dot (Point a
q Point a -> Point a -> Point a
forall a. Num a => a -> a -> a
- Point a
p) (Point a
r Point a -> Point a -> Point a
forall a. Num a => a -> a -> a
- Point a
p) a -> a -> Bool
forall a. Ord a => a -> a -> Bool
< a
0 -> [Point a] -> [Point a] -> [Point a]
go (Point a
r Point a -> [Point a] -> [Point a]
forall a. a -> [a] -> [a]
: Point a
q Point a -> [Point a] -> [Point a]
forall a. a -> [a] -> [a]
: [Point a]
conv) [Point a]
rs -- q--p--r
        | Bool
otherwise -> [Point a] -> [Point a] -> [Point a]
go (Point a
p Point a -> [Point a] -> [Point a]
forall a. a -> [a] -> [a]
: Point a
q Point a -> [Point a] -> [Point a]
forall a. a -> [a] -> [a]
: [Point a]
conv) [Point a]
rs -- q--r--p
    go [Point a]
conv (Point a
r : [Point a]
rs) = [Point a] -> [Point a] -> [Point a]
go (Point a
r Point a -> [Point a] -> [Point a]
forall a. a -> [a] -> [a]
: [Point a]
conv) [Point a]
rs
    go [Point a]
conv [] = [Point a]
conv