3

I have a large set of 2D points that I've downsampled into a 44x2 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()
bb1
  • 7,174
  • 2
  • 8
  • 23
shanryan
  • 33
  • 1
  • 6

1 Answers1

2

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

bb1
  • 7,174
  • 2
  • 8
  • 23
  • 1
    This works great. I ended up using [MinMaxScaler](https://scikit-learn.org/stable/modules/generated/sklearn.preprocessing.MinMaxScaler.html) from scikitlearn instead of the multiplier you used as I need this to be generic. I managed to extract the points of the polygon with [geometry.mapping](https://shapely.readthedocs.io/en/stable/manual.html#shapely.geometry.mapping) and could then use [scaler.inverse_transform](https://scikit-learn.org/stable/modules/generated/sklearn.preprocessing.MinMaxScaler.html#sklearn.preprocessing.MinMaxScaler.inverse_transform) to recover the original scale. – shanryan Sep 15 '21 at 06:34