# Chapter 3 Boss

Chapter 3 of Real World Haskell ends with an epic boss. Exercise question 12 states:

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.

Yea I just said WTF out loud too.

It took me a day or so but I accomplished the task and here is a walk though. But first we will need the previous two questions and their answers that I came up with.

## Exercise 10

Write a function that calculates the turn made by three two-dimensional points and returns a Direction.

``````data Direction = LEFT | RIGHT | STRAIGHT
deriving (Show, Eq)

data CartesianPoint = Point {x :: Double, y :: Double}
deriving (Show)

directionOf :: CartesianPoint -- ^ Point A
-> CartesianPoint -- ^ Vertex
-> CartesianPoint -- ^ Point B
-> Direction
directionOf a v b | sign > 0  = RIGHT
| sign < 0  = LEFT
| otherwise = STRAIGHT
where sign = (x v - x a) * (y b - y a) - (y v - y a) * (x b - x a)``````

I original struggled with this one, I had a partial solution that kinda worked halfway it wasn’t till I read the Wikipedia page for Graham Scan that I saw this specific equation.

## Exercise 11

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.

``````directionsOf (a : v : b : ps) = directionOf a v b : directionsOf(v:b:ps)
directionsOf _                = []``````

This one was pretty simple given that `directionOf` works correctly.

## The Boss - Exercise 12

Ugh WTF again. Anyway lets walk though the algorithm that Wikipedia lists.

1. Find the point with the lowest y-coordinate. Call this point P.
2. Order the set of points in increasing order of the angle they and the point P make with the x-axis.
3. Consider each of the sorted points in sequence. Check if it is a Left or a Right turn. If it is a right turn, then the second-to-last point is not part of the convex hull and should be removed from consideration.
4. Continue until the point P is returned.

So how did I do this. First step. I sorted all of the points by their y value. The head of this list will be P.

``````sortByY xs = sortBy lowestY xs
where lowestY a b = compare (y a, x a) (y b, x b)``````

Step two, the first item in the sorted set is P, and now I need to sort the set by their angle.

``````sortByAngle ps = bottomLeft : sortBy (compareAngles bottomLeft) (tail (sortedPs))
where sortedPs       = sortByY ps
pointAngle a b = (x b - x a) / (y b - y a)
compareAngles  = comparing . pointAngle``````

Finally, given that I have my set of sorted points now, I can check if it is a left or right turn and drop the middle point.

``````grahamScan :: [CartesianPoint] -> [CartesianPoint]
grahamScan ps = scan (sortByAngle ps)
where scan (a:v:b:xs) = if directionOf a v b == RIGHT
then a : scan(b:xs)
else a : scan(v:b:xs)
scan [a, b]     = [a, b]
scan _          = []``````

The decomposition and recomposition of the list here is pretty cool.

And this gets me past the boss. I had to do a bit of grinding before I could beat him, but I am really super happy with my result.