Search code examples
javascriptpython2dpolygonconvex-hull

Convex hull - Monotone chain algorithm error

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: https://i.sstatic.net/wfVJN.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

Solution

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