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:
# return (not len(hull) or hull[-1] != r) and hull.append(r) or hull
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