Gift Wrap Implementation

giftwrap.hs

-- For the minimumBy function
import Data.List
type Point = (Float, Float)

-- Returns the relation between a line segment and a point. Takes three
-- arguments, the first two defining the line segment, The last a test
-- point. The value is 0 if the test point is on the line >0 if it is
-- to the right and <0 if it is to the left.
lineRelation :: Point -> Point -> Point -> Float
lineRelation (x1, y1) (x2, y2) (x, y) = (y - y1) * (x2 - x1) - (y2 - y1) * (x - x1)


-- Find a convex hull of a set of points using the gift wrap algorithm.
giftWrap :: [Point] -> [Point]
giftWrap points = giftWrap' anchor points
  where
    anchor = minimumBy minX points
    minX :: Point -> Point -> Ordering
    minX (x, y) (x1, y1)
      | x == x1 = compare y y1
      | otherwise = compare x x1
    giftWrap' :: Point -> [Point] -> [Point]
    giftWrap' p points
        | q == anchor = [p]
        | otherwise = p:(giftWrap' q points)
        -- Let q be the point such that for all r in S, r is right of the line pq.
        -- This satisfies the necessary property that all interior
        -- points are to the right of every edge of a clockwise
        -- traversal of a convex hull.
        where q = foldl1 (\cur r ->
                           if lineRelation p r cur < 0 then
                             r
                           else
                             cur) . filter (/= p) $ points