A nice, short compact 2d convex hull routine, implementing the Quickhull algorithm

quickhull-2d.py

import numpy



def quickhull_2d(S):
	def process(P, a, b):
		signed_dist = numpy.cross(S[P] - S[a], S[b] - S[a])		
		K = [i for s, i in zip(signed_dist, P) if s > 0 and i != a and i != b]

		if len(K) == 0:
			return [a, b]

		c = max(zip(signed_dist, P))[1]
		return process(K, a, c)[:-1] + process(K, c, b)
		
	a, b = numpy.argmin(S[:,0]), numpy.argmax(S[:,0])
	return process(range(S.shape[0]), a, b)[:-1] + process(range(S.shape[0]), b, a)[:-1]