public
Last active

  • Download Gist
hull.py
Python
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
# 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

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.