Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
# Graham Scan - Tom Switzer <thomas.switzer@gmail.com>
TURN_LEFT, TURN_RIGHT, TURN_NONE = (1, -1, 0)
def turn(p, q, r):
return cmp((q[0] - p[0])*(r[1] - p[1]) - (r[0] - p[0])*(q[1] - p[1]), 0)
def _keep_left(hull, r):
while len(hull) > 1 and turn(hull[-2], hull[-1], r) != TURN_LEFT:
hull.pop()
# return (not len(hull) or hull[-1] != r) and hull.append(r) or hull
if not len(hull) or hull[-1] != r:
hull.append(r)
return hull
def convex_hull(points):
"""Returns points on convex hull of an array of points in CCW order."""
points = sorted(points)
l = reduce(_keep_left, points, [])
u = reduce(_keep_left, reversed(points), [])
return l.extend(u[i] for i in xrange(1, len(u) - 1)) or l
@adrianquiala

This comment has been minimized.

Copy link

adrianquiala commented May 16, 2016

Thanks. It had work for me. Now I need to get the concave hull.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.
You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session.