Create a gist now

Instantly share code, notes, and snippets.

What would you like to do?
Graham Scan Implementation in Haskell
import Data.List
import Data.List.Split
import Data.Ord
import System.Environment
theta :: (Num a, Eq a, Ord a, Fractional a) => (a,a) -> (a,a) -> a
theta (x1,y1) (x2,y2)
| dx == 0 && dy == 0 = 0
| dx < 0 = 2 - t
| dy < 0 = 4 + t
| otherwise = t
where dx = x2 - x1
dy = y2 - y1
t = dy / (abs dx + abs dy)
minPoint :: (Ord a) => [(a,a)] -> (a,a)
minPoint [a] = a
minPoint ((x,y):xs)
| y == (snd other) = (minX (x,y) other)
| y < (snd other) = (x,y)
| otherwise = other
where other = (minPoint xs)
minX (x,y) (x1,y1)
| x > x1 = (x,y)
| otherwise = (x1,y1)
onLeft s e pt = (side s e pt) > 0
where side (x,y) (x1,y1) (x2, y2) = (x1 - x) * (y2 - y) - (y1 - y) * (x2 - x)
stringify list sep = (foldl section "" (init list))++(show (last list))
where section p i = p++(show i)++sep
tuplify strs = map split (filter (/= "") strs)
where split str = tuple (splitOn " " str)
tuple (a:b:[]) = (floatify a,floatify b)
floatify i = read i :: Float
merge [] item = [item]
merge (a:[]) item = [item, a]
merge stack@(e:s:_) pt = if onLeft (snd s) (snd e) (snd pt)
then (pt:stack)
else merge (tail stack) pt
getHull list = reverse (foldl (merge) [] sorted)
where anchor = minPoint list
sorted = sortBy (comparing (\(_,a) -> theta anchor a)) (zip [0..] list)
main = do
args <- getArgs
file <- readFile (head args)
let pts = tuplify.tail.(splitOn "\n") $ file
in putStrLn $ stringify ((map fst) $ getHull pts) " "
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment