Difference between revisions of "Newbie Code Critique"

From HaskellWiki
Jump to: navigation, search
Line 2: Line 2:
   
 
==[[Graham Scan Implementation]]==
 
==[[Graham Scan Implementation]]==
 
Descriptions of the problem can be found in [http://book.realworldhaskell.org/read/defining-types-streamlining-functions.html Real World Haskell, Chapter 3]
 
 
<haskell>
 
--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 _ = []
 
</haskell>
 

Revision as of 15:30, 26 September 2009

This page is a place for new users to post pieces of code that they want analyzed.

Graham Scan Implementation