Skip to content

Instantly share code, notes, and snippets.

@yashsavani
Last active January 31, 2020 01:24
Show Gist options
  • Save yashsavani/d3168150fef7e48f95166ad9c757fbac to your computer and use it in GitHub Desktop.
Save yashsavani/d3168150fef7e48f95166ad9c757fbac to your computer and use it in GitHub Desktop.
Attempting Graham Scan problem from real world haskell
import Data.List (sortBy)
import Data.Function (on)
type Vector = (Double, Double)
data Direction
= LeftDir
| RightDir
| ForwardDir
| NoDir
deriving (Eq, Show)
direction :: Vector -> Vector -> Vector -> Direction
direction (xa, ya) (xb, yb) (xc, yc)
| dot < 0 = LeftDir
| dot > 0 = RightDir
| dot == 0 = ForwardDir
where
(xab, yab) = (xb - xa, yb - ya)
(xabcw90, yabcw90) = (yab, (-xab))
(xbc, ybc) = (xc - xb, yc - yb)
dot = (xabcw90 * xbc) + (yabcw90 * ybc)
direction _ _ _ = NoDir
directionList :: [Vector] -> [Direction]
directionList (a:b:c:xs) = (direction a b c) : directionList (b : c : xs)
directionList _ = []
minPoint :: [Vector] -> Vector
minPoint (x:[]) = x
minPoint ((xa, ya):(xb, yb):ys)
| ya < yb = minPoint ((xa, ya) : ys)
| ya > yb = minPoint ((xb, yb) : ys)
| xa < xb = minPoint ((xa, ya) : ys)
| otherwise = minPoint ((xb, yb) : ys)
minPoint [] = error "You must have at least one point"
norm :: Vector -> Double
norm (x,y) = sqrt (x**2 + y**2)
getCosAngle :: Vector -> Vector -> Vector
getCosAngle a b | a == b = (-2, 0)
getCosAngle (xa,ya) (xb,yb) = ((xa-xb) / norm (xb-xa, yb-ya), - norm (xb-xa, yb-ya))
sortPoints :: [Vector] -> [Vector]
sortPoints points = sortBy (compare `on` (getCosAngle p)) points
where
p = minPoint points
scan :: [Vector] -> [Vector] -> [Vector]
scan [] xs = xs
scan (x:xs) [] = scan xs [x]
scan (x:xs) (y:[]) = scan xs (x:y:[])
scan (x:xs) (a:b:bs) = if direction b a x == RightDir then scan (x:xs) (b:bs) else scan xs (x:a:b:bs)
grahamScan :: [Vector] -> [Vector]
grahamScan pts = reverse convexHull
where
sortedPts = sortPoints pts
convexHull = scan sortedPts []
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment