Convex hull - Monotone chain algorithm error

Question

I'm using the Monotone chain algorithm to create a convex hull around a set of polygons. It works well sometimes, but on some shapes, it fails. Take a look at this example: http://i.imgur.com/KN40LgV.png

To the left is the shape before applying the algorithm, and to the right is after. There seems to be some minor calculation error somewhere, that I can't figure out.

Here is a link to my source-code (JavaScript): http://pastebin.com/GPVm9dQp

And here is the implementation in Python that I used as reference: http://pastebin.com/RgMKH3XN

Answer 1

Without digging too deep into it, aren't you supposed to sort the list of points by x-position at some point?