Calculate bounding polygon of alpha shape from the

Question

Given a set of points in the plane, a notion of alpha-shape, for a given positive number alpha, is defined by finding the Delaunay triangulation and deleting any triangles for which at least one edge exceeds alpha in length. Here's an example using d3:

http://bl.ocks.org/gka/1552725

The problem is that, when there are thousands of points, simply drawing all the interior triangles is too slow for an interactive visualization, so I'd like to just find the bounding polygons. This isn't so simple, because as you can see from that example sometimes there might be two such polygons.

As a simplification, suppose some clustering has been performed so that there's guaranteed to be a unique bounding polygon for each triangulation. What's the best way to find this bounding polygon? In particular, the edges have to be ordered consistently and it must support the possibility of "holes" (think a torus or donut shape--this is expressible in GeoJSON).

Answer 1

There now exists a python package alphashape which is extremely easy to use, and can be installed by pip or conda.

The main function has similar inputs to the answer given by @Iddo Hanniel, adjusting the second positional argument would give you the desired outline. Alternatively, you could leave the seconda positional argument blank and the function would optimize that parameter for you to give you the best concave hull. Beware, the computational time is increased greatly if you let the function optimize the value.