Skip to content
Create a gist now

Instantly share code, notes, and snippets.

# Graham Scan - Tom Switzer <>
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:
if not len(hull) or hull[-1] != 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

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
Something went wrong with that request. Please try again.