How to Find the Concave Hull in Python

By | February 1, 2015

How to Find the Concave Hull in Python

The Python module Shapely has a built in function for determining the convex hull, but for determining the concave hull (or alpha shape), you have to do a bit more work.

Thankfully a few people on the internet have already done much of the work in determining the concave hull of a shape.

For me the starting point was this blog post post, which uses circumscribing of the triangulation of the starting polygon. It uses a few functions introduced in this StackOverflow answer.

This blog post develops those ideas further, and fills in some of the blanks in the original code. Rather handily, it’s also available as an IPython Notebook.

Image:  Kku; CC BY-SA 4.0

python polygons