Graham Scan Implementation

Descriptions of this problem can be found in Real World Haskell, Chapter 3

--Graham Scan exercise

--Direction type
data Direction = LeftTurn
               | RightTurn
               | Straight
                deriving (Show, Eq)

--Point type
data Point = Point (Double, Double)
             deriving (Show)

--some points
p0 = Point (2.1,2.0)
p1 = Point (4.2,2.0)
p2 = Point (0.5,2.5)
p3 = Point (3.2,3.5)
p4 = Point (1.2,4.0)
p5 = Point (0.7,4.7)
p6 = Point (1.0,1.0)
p7 = Point (3.0,5.2)
p8 = Point (4.0,4.0)
p9 = Point (3.5,1.5)
pA = Point (0.5,1.0)
points = [p0,p1,p2,p3,p4,p5,p6,p7,p8,p9,pA]

--Get direction of single set of line segments
dir :: Point -> Point -> Point -> Direction
dir (Point (ax, ay)) (Point (bx, by)) (Point (cx, cy)) = case sign of
                                  EQ -> Straight
                                  GT -> LeftTurn
                                  LT -> RightTurn
                                  where sign = compare ((bx - ax) * (cy - ay) - (by - ay) * (cx - ax)) 0

--Get a list of Directions from a list of Points
dirlist :: [Point] -> [Direction]
dirlist (x:y:z:xs) = dir x y z : dirlist (y:z:xs)
dirlist _ = []

--Compare Y axes
sortByY :: [Point] -> [Point]
sortByY xs = sortBy lowestY xs
             where lowestY (Point(x1,y1)) (Point (x2,y2)) = if y1 == y2 
                                                            then compare x1 x2
                                                            else compare y1 y2
--get COT of line defined by two points and the x-axis
pointAngle :: Point -> Point -> Double
pointAngle (Point (x1, y1)) (Point (x2, y2)) = (x2 - x1) / (y2 - y1)

--compare based on point angle
pointOrdering :: Point -> Point -> Ordering
pointOrdering a b = compare (pointAngle a b) 0.0

--Sort by angle
sortByAngle :: [Point] -> [Point]
sortByAngle ps = bottomLeft : sortBy (compareAngles bottomLeft) (tail (sortedPs))
                where sortedPs = sortByY ps
                      bottomLeft = head (sortedPs)

                      

--Compare angles
compareAngles :: Point -> Point -> Point -> Ordering
compareAngles base a b = compare (pointAngle base b) (pointAngle base a)

--Graham Scan
gscan :: [Point] -> [Point]
gscan ps = scan (sortByAngle ps)
          where scan (x:y:z:xs) = if dir x y z == RightTurn 
                                  then x: scan (z:xs)
                                  else x: scan (y:z:xs)
                scan (x:y:[]) = (x:y:[])                  
                scan _ = []