Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

It looks like this is a really classical question, but I'd like to ask it one more time as all those solutions look quite long and complicated for me (maybe because I am dumb :) ) So this is a Graham convex hull algorithm from the very beginning of "Real World Haskell" book. And a perimeter function just for sake of implementing it.

Why the author suggests creating Direction datatype, as it acts only as Ordering? Is there any more elegant way to traverse through list considering pairs?

Any suggestions would be appreciated

import Text.Printf
import Data.List (sortBy)
data Point = Point Int Int deriving (Show, Eq, Ord)

turn :: Point -> Point -> Point -> Ordering
turn (Point x2 y2) (Point x1 y1) (Point x3 y3) = compare ((x2 - x1) * (y3 - y1) - (y2 - y1) * (x3 - x1)) 0

polarSort :: [Point] -> [Point]
polarSort points = sorted where
    pivot = minimum points
    sorted = pivot:(sortBy (\a b -> turn b pivot a) . filter (pivot /=)) points

grahamScan :: [Point] -> [Point]
grahamScan points = grahamScan' rest [p2, p1] where
    (p1:p2:rest) = polarSort points
    grahamScan' [] l = l
    grahamScan' (p:pointsLeft) (s1:s2:selectedPoints) = case turn s2 s1 p of
                                        GT -> grahamScan' (p:pointsLeft) (s2:selectedPoints) -- the turn is right, so we discard last selected point
                                        _  -> grahamScan' pointsLeft (p:s1:s2:selectedPoints) -- the turn is left, so we add another point to the list of selected ones

dist :: Point -> Point -> Double
dist (Point x1 y1) (Point x2 y2) = sqrt (fromIntegral ((x2 - x1)^(2 :: Int) + (y2 - y1)^(2 :: Int)))

perimeter :: [Point] -> Double
perimeter points@(p0:_) = dist p0 pn + rest where
    walk :: [Point] -> (Double, Point)
    walk [a] = (0, a)
    walk (p1:p2:ps) = (dist p1 p2 + next, lastPoint) where
        (next, lastPoint) = walk (p2:ps)
    (rest, pn) = walk points

main = do
    _ <- getLine
    content <- getContents
    putStrLn $ printf "%.1f" ((perimeter . grahamScan . map ((\([x, y]) -> Point x y) . map read . words) . lines) content)
share|improve this question
    
Why are your points limited to Int coordinates? –  200_success May 26 at 10:18

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.