Alpha Shapes in Python

Alpha shapes include convex and concave hulls. Convex hull algorithms are ten a penny, so what we're really interested in here in the concave hull of an irregularly or otherwise non-convex shaped 2d point cloud, which by all accounts is more difficult.

The function is here:

	def get_alpha_shape(infile,radius):
	command = "%s -A -aa %s -r -m10000000 -oN -oFpoints < %s" % (hull_path, str(radius), infile)
	print >> sys.stderr, "Running command: %s" % command
	retcode = subprocess.call(command, shell=True)
	results_file = open("points-alf")
	results_file.next()
	results_indices = [[int(i) for i in line.rstrip().split()] for line in results_file]
	results_file.close()
	return results_indices

view raw alpha.py hosted with ❤ by GitHub

The above is essentially the same wrapper as posted here, except a different way of reading in the data, and providing the option to specify a probe radius. It uses Ken Clarkson's C-code, instructions on how to compile are here

An example implementation:

	t = linspace(0.6,5.7,500)
	C = 2*np.vstack([cos(t),sin(t)] )
	C=C+np.random.rand(2,500)

view raw alpha2.py hosted with ❤ by GitHub

The above data generation is translated from the example in a matlab alpha shape function . Then:

	hull_path = "./hull"
	infile='C.txt'
	with open(infile, 'w') as f:
	np.savetxt(f, C.T, delimiter=' ', fmt="%0.7f %0.7f\n")
	radius=1
	indices = get_alpha_shape(infile,radius)
	alpha=C.T[indices]
	plot(C[0],C[1],'.'), plot(alpha[1:].T[0],alpha[1:].T[1],'r')
	savefig("C_radius="+str(radius)+".png")
	close()

view raw using alpha.py hosted with ❤ by GitHub

Which produces (points are blue dots, alpha shape is red line):

and on a larger data set (with radius=1, this is essentially the convex hull):

and a true concave hull: