Finding the Convex Hull (Problem 12 of Real World Haskell)
I wrote a "solution" to this problem, but it appears to return incorrect results. There's a pastebin of the code at http://hpaste.org/fastcgi/hpaste.fcgi/view?id=2121 and a picture of the inputs, outputs, and expected results graphed at http://img510.imageshack.us/img510/9971/resultsg.jpg I'm wondering if this is a flaw in my code, my understanding of the problem, or both. Any ideas on how to track this one down would be very much appreciated. Thank you! -- ヽ(^o^)ノ -rob
Whenever I'm looking for a bug in Haskell code, I find it helpful to start
by seeing if I can simplify the code any first. In this case, there are a
couple of things I notice:
- validPointsOf is just a filter. It would be easier to write "valid ::
MyDirection -> Bool" and then "validPointsOf = filter (valid . snd)"
- Similarly, there's no need to write your own minimum-finder and call it
lowestY. Instead, write (or derive!) an Ord instance, and then use the
standard prelude function "minimum"
- a small simplification of sortByCoTan: sortByCoTan pivot = sortBy
(comparing (coTan pivot))
Hope this helps!
2009/3/5 Rob Crowther
I wrote a "solution" to this problem, but it appears to return incorrect results. There's a pastebin of the code at http://hpaste.org/fastcgi/hpaste.fcgi/view?id=2121 and a picture of the inputs, outputs, and expected results graphed at http://img510.imageshack.us/img510/9971/resultsg.jpg
I'm wondering if this is a flaw in my code, my understanding of the problem, or both. Any ideas on how to track this one down would be very much appreciated.
Thank you!
-- ヽ(^o^)ノ -rob
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Am Donnerstag, 5. März 2009 13:40 schrieb Rob Crowther:
I wrote a "solution" to this problem, but it appears to return incorrect results. There's a pastebin of the code at http://hpaste.org/fastcgi/hpaste.fcgi/view?id=2121 and a picture of the inputs, outputs, and expected results graphed at http://img510.imageshack.us/img510/9971/resultsg.jpg
I'm wondering if this is a flaw in my code, my understanding of the problem, or both.
Definitely flawed code, probably based on incorrect understanding of the algorithm.
Any ideas on how to track this one down would be very much appreciated.
To track it down, it would be helpful to look at the intermediate results and see where they differ in what way from your expectations. *ConvexHull> let pointlist :: [Point2D]; pointlist = [(0,0), (2,0), (4,0), (6,0), (5,-2), (5,2), (0,4), (6,4), (5,6)] *ConvexHull> lowestY pointlist (5.0,-2.0) *ConvexHull> sortByCoTan it pointlist [(0.0,0.0),(2.0,0.0),(0.0,4.0),(4.0,0.0),(5.0,2.0),(5.0,6.0),(6.0,4.0),(5.0,-2.0),(6.0,0.0)] *ConvexHull> let sortedpoints = it *ConvexHull> listOfTurns sortedpoints [MyRight,MyLeft,MyRight,MyRight,MyLeft,MyLeft,MyRight] *ConvexHull> zip sortedpoints (MyStraight:MyStraight:it) [((0.0,0.0),MyStraight),((2.0,0.0),MyStraight),((0.0,4.0),MyRight),((4.0,0.0),MyLeft),((5.0,2.0),MyRight),((5.0,6.0),MyRight),((6.0,4.0),MyLeft),((5.0,-2.0),MyLeft),((6.0,0.0),MyRight)] *ConvexHull> validPointsOf it
Thank you!
*ConvexHull> let ly = lowestY pointlist *ConvexHull> coTan ly ly NaN First, you'd want to separate the point with lowest y-coordinate from the rest, like lowestY :: [Point2D] -> (Point2D,[Point2D]) lowestY (x:xs) = foldr update (x,[]) xs where update a (b,cs) = -- left as an exercise Then it might be a good idea to make sortByCoTan insensitive to other points with the same lowest y-coordinate, and of course, sort only the points other than the starting point. Also, the way the points are sorted, you'll walk clockwise around the boundary, so you'd never turn left, only proceed straight or turn right. But the turn at each point does not depend on its neighbours in the list sorted by cotangent, but on which points have so far been chosen, so you have to compute the turn based on that. The selection of points is considerably more complicated than just looking at the turn, consider e.g. [(0,0), (-2,2), (-2,3),(-1,3),(0,4),(1,4),(2,6),(3,9)]. When you have three points a, b and c, and you go from a via b to c, the turn at b is right, iff crossProduct a b c < 0 left, iff crossProduct a b c > 0. HTH, Daniel
participants (3)
-
Andrew Wagner -
Daniel Fischer -
Rob Crowther