Finally got it I think. This was bloody tricky.
Write a function that calculates the turn made by three two-dimensional points and returns a Direction.
data Point = Point Int Int
deriving (Show, Eq)
ccw :: Point -> Point -> Point -> Int
ccw (Point ax ay)
(Point bx by)
(Point cx cy) = (bx - ax)
* (cy - ay)
- (by - ay)
* (cx - ax)
direction :: Point -> Point -> Point -> Direction
direction a b c
| determinant > 0 = LeftTurn
| determinant < 0 = RightTurn
| determinant == 0 = Straight
where determinant = ccw a b c
Define a function that takes a list of two-dimensional points and computes the direction of each successive triple. Given a list of points [a,b,c,d,e], it should begin by computing the turn made by [a,b,c], then the turn made by [b,c,d], then [c,d,e]. Your function should return a list of Direction.
directions :: [Point] -> [Direction]
directions [] = []
directions (_:[]) = []
directions (_:_:[]) = []
directions (a:b:c:xs) = direction a b c : directions (b:c:xs)
Using the code from the preceding three exercises, implement Graham’s scan algorithm for the convex hull of a set of 2D points. You can find good description of what a convex hull is, and how the Graham scan algorithm should work, on Wikipedia.
sortByY :: [Point] -> [Point]
sortByY xs = sortBy yThenX xs
where yThenX (Point ax ay) (Point bx by)
| ay < by = LT
| ay > by = GT
| otherwise = compare ax bx
sortByAngle :: Point -> [Point] -> [Point]
sortByAngle p xs = sortBy angle xs
where angle a b
| det > 0 = LT
| det < 0 = GT
| otherwise = EQ
where det = ccw p a b
gScan :: [Point] -> [Point]
gScan [] = []
gScan (_:[]) = []
gScan (_:_:[]) = []
gScan xs = scan [p] ps
where sorted = sortByY xs
p = head sorted
ps = sortByAngle p (tail sorted)
scan (x:xs) (a:b:cs) = case direction x a b of
LeftTurn -> scan (a:x:xs) (b:cs)
RightTurn -> scan xs (x:b:cs)
Straight -> scan (x:xs) (b:cs)
scan xs [a] = a:xs