ConvexHull.hs

-- | Convex hull algorithm for credal set display.
module Viz.ConvexHull
  ( convexHull2D
  ) where

import Data.List (sort, nubBy)

-- | Compute the convex hull of a set of 2D points.
--   Returns the hull vertices in counterclockwise order.
--   Uses Andrew's monotone chain algorithm: O(n log n).
convexHull2D :: [(Double, Double)] -> [(Double, Double)]
convexHull2D pts
  | length unique <= 2 = unique
  | otherwise =
      let sorted = sort unique
          lower = reverse (buildHull sorted)
          upper = reverse (buildHull (reverse sorted))
      in  init lower ++ init upper
  where
    unique = dedup2D pts
    buildHull = foldl' add []
    add stack p = p : dropRightTurns stack
      where
        dropRightTurns (b : a : rest)
          | cross2D a b p <= 0 = dropRightTurns (a : rest)
        dropRightTurns s = s

-- | Cross product of vectors (b - a) and (c - a).
cross2D :: (Double, Double) -> (Double, Double) -> (Double, Double) -> Double
cross2D (ax, ay) (bx, by) (cx, cy) =
  (bx - ax) * (cy - ay) - (by - ay) * (cx - ax)

-- | Remove near-duplicate 2D points.
dedup2D :: [(Double, Double)] -> [(Double, Double)]
dedup2D = nubBy (\(x1, y1) (x2, y2) -> abs (x1 - x2) < epsSamePoint && abs (y1 - y2) < epsSamePoint)
  where epsSamePoint = 1e-10