Graham Scan Implementation
Jump to navigation
Jump to search
The printable version is no longer supported and may have rendering errors. Please update your browser bookmarks and please use the default browser print function instead.
Descriptions of this problem can be found in Real World Haskell, Chapter 3
import Data.List (sortBy)
import Data.Function (on)
-- define data `Direction`
data Direction = GoLeft | GoRight | GoStraight
deriving (Show, Eq)
-- determine direction change via point a->b->c
-- -- define 2D point
data Pt = Pt (Double, Double) deriving (Show, Eq, Ord)
isTurned :: Pt -> Pt -> Pt -> Direction
isTurned (Pt (ax, ay)) (Pt (bx, by)) (Pt (cx, cy)) = case sign of
EQ -> GoStraight
LT -> GoRight
GT -> GoLeft
where sign = compare ((bx - ax) * (cy - ay))
((cx - ax) * (by - ay))
-- implement Graham scan algorithm
-- -- Helper functions
-- -- Find the most button left point
buttonLeft :: [Pt] -> Pt
buttonLeft [] = Pt (1/0, 1/0)
buttonLeft [pt] = pt
buttonLeft (pt:pts) = minY pt (buttonLeft pts) where
minY (Pt (ax, ay)) (Pt (bx, by))
| ay > by = Pt (bx, by)
| ay < by = Pt (ax, ay)
| ax < bx = Pt (ax, ay)
| otherwise = Pt (bx, by)
-- -- Main
convex :: [Pt] -> [Pt]
convex [] = []
convex [pt] = [pt]
convex [pt0, pt1] = [pt0, pt1]
convex pts = scan [pt0] spts where
-- Find the most buttonleft point pt0
pt0 = buttonLeft pts
-- Sort other points `ptx` based on angle <pt0->ptx>
spts = tail (sortBy (compare `on` compkey pt0) pts) where
compkey (Pt (ax, ay)) (Pt (bx, by)) = (atan2 (by - ay) (bx - ax),
{-the secondary key make sure collinear points in order-}
abs (bx - ax))
-- Scan the points to find out convex
-- -- handle the case that all points are collinear
scan [p0] (p1:ps)
| isTurned pz p0 p1 == GoStraight = [pz, p0]
where pz = last ps
scan (x:xs) (y:z:rsts) = case isTurned x y z of
GoRight -> scan xs (x:z:rsts)
GoStraight -> scan (x:xs) (z:rsts) -- I choose to skip the collinear points
GoLeft -> scan (y:x:xs) (z:rsts)
scan xs [z] = z : xs
-- Test data
pts1 = [Pt (0,0), Pt (1,0), Pt (2,1), Pt (3,1), Pt (2.5,1), Pt (2.5,0), Pt (2,0)]
-- (2,1)--(2.5,1)<>(3,1)
-- -> |
-- ---- v
-- (0,0)------->(1,0)-- (2,0)<-(2.5,0)
pts2 = [Pt (1,-2), Pt (-1, 2), Pt (-3, 6), Pt (-7, 3)]
-- -- This case demonstrate a collinear points across the button-left point
-- |-----(-3,6)
-- |----- ^__
-- <----- |---
-- (-7,3) |
-- |-- (-1,2)
-- |---- <--
-- |------------- |--|
-- |------------>(1,-2)
pts3 = [Pt (6,0), Pt (5.5,2), Pt (5,2), Pt (0,4), Pt (1,4), Pt (6,4), Pt (0,0)]
-- -- This case demonstrates a consecutive inner points
-- (0,4)<-(1,4)<--------------------(6,4)
-- | |-----------^
-- v (5,2)<(5.5,2)<-|
-- (0,0)--------------------------->(6,0)
pts4 = [Pt (0,0), Pt (0,4), Pt (1,4), Pt (2,3), Pt (6,5), Pt (6,0)]
-- -- This case demonstrates a consecutive inner points
-- collinear points
pts5 = [Pt (5,5), Pt (4,4), Pt (3,3), Pt (2,2), Pt (1,1)]
pts6 = reverse pts5