2D alpha shape / concave hull problem in Python

I have a large set of 2D points that I’ve downsampled into a 44×2 numpy array (array defined later). I am trying to find the bounding shape of those points which are effectively a concave hull. In the 2nd image I’ve manually marked an approximate bounding shape that I am hoping to get.

points points+overlay

I have tried using alphashape and the Delauney triangulation method from here, both methods providing the same answer.

Unfortunately, I don’t seem to be able to achieve what I need, regardless of the alpha parameters. I’ve tried some manual settings and alphaoptimize, some examples of which are below.

alpha=0.1 alpha=0.5 alpha=1.0

Is there something critical I’m misunderstanding about alphashape? The documentation seems very clear, but obviously I’m missing something.

import numpy as np
import alphashape
from descartes import PolygonPatch
import matplotlib.pyplot as plt

points = np.array(
[[0.16,3.98],
[-0.48,3.33],
[-0.48,4.53],
[0.1,3.67],
[0.04,5.67],
[-7.94,3.02],
[-18.16,3.07],
[-0.15,5.67],
[-0.26,5.14],
[-0.1,5.11],
[-0.96,5.48],
[-0.03,3.86],
[-0.12,3.16],
[0.32,4.64],
[-0.1,4.32],
[-0.84,4.28],
[-0.56,3.16],
[-6.85,3.28],
[-0.7,3.24],
[-7.2,3.03],
[-1.0,3.28],
[-1.1,3.28],
[-2.4,3.28],
[-2.6,3.28],
[-2.9,3.28],
[-4.5,3.28],
[-12.3,3.28],
[-14.8,3.28],
[-16.7,3.28],
[-17.8,3.28],
[-0,3.03],
[-1,3.03],
[-2.1,3.03],
[-2.8,3.03],
[-3.2,3.03],
[-5,3.03],
[-12,3.03],
[-14,3.03],
[-17,3.03],
[-18,3.03],
[-0.68,4.86],
[-1.26,3.66],
[-1.71,3.51],
[-9.49,3.25]])

alpha = 0.1
alphashape = alphashape.alphashape(points, alpha)

fig = plt.figure()
ax = plt.gca()
ax.scatter(points[:,0],points[:,1])
ax.add_patch(PolygonPatch(alphashape,alpha=0.2))
plt.show()

Answer

The plots that you attached are misleading, since the scales on the x-axis and the y-axis are very different. If you set both axes to the same scale, you obtain the following plot:

point cloud.

Since differences between x-coordinates of points are on the average much larger than differences between y-coordinates, you cannot obtain an alpha shape resembling your desired result. For larger values of alpha points scattered along the x-axis will not be connected by edges, since alpha shape will use circles too small to connect these points. For values of alpha small enough that these points get connected you will obtain the long edges on the right-hand side of the plot.

You can fix this issue by rescaling y-coordinates of all points, effectively stretching the plot in the vertical direction. For example, multiplying y-coordinates by 7 and setting alpha = 0.4 gives the following picture:

alpha shape