[Haskell-cafe] Finding the Convex Hull (Problem 12 of Real World Haskell)

[Daniel Fischer]

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