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

Daniel Fischer daniel.is.fischer at web.de
Thu Mar 5 09:00:00 EST 2009

```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

```