concaveman-cpp a very fast 2D concave hull maybe even faster with C++ and Python

In mathematics, the convex hull or convex envelope or convex closure of a set X of points in the Euclidean plane or in a Euclidean space (or, more generally, in an affine space over the reals) is the smallest convex set that contains X. For instance, when X is a bounded subset of the plane, the convex hull may be visualized as the shape enclosed by a rubber band stretched around X.

An alpha-shape associated with a set of points is a generalization of the concept of the convex hull, i.e. every convex hull is an alpha-shape but not every alpha shape is a convex hull. An edge of the alpha-shape is drawn between two members of the finite point set whenever there exists a generalized disk of radius 1/α containing the entire point set and which has the property that the two points lie on its boundary. If α = 0, then the alpha-shape associated with the finite point set is its ordinary convex hull.

Recently I have been looking for a way of finding precise outlines of 2D point clouds coming from an image processing pipeline. I have stumbled upon many interesting approaches to improve on rather crude convex hulls. One of them is the above-mentioned alpha-shape concept implemented in the well-renowned CGAL library – CGAL::Alpha_shape_2.

Another solution which instantly caught my attention due to its funny name and seemingly excellent results was concaveman. It is a concave hull implementation based on the ideas from Park and Oh, 2012 paper. In a brief, the algorithm starts from a convex hull and iteratively refines it by including inner vertices according to concavity and edge length criteria. In concaveman this idea is realized very efficiently using RTree and a priority queue for candidate vertex searches, producing sweet results in an eye blink.

I decided to go ahead with concaveman and adjust it to my needs which at the time required it to be accessible from Python. I could’ve taken the easy route of passing data to nodejs but since I am pretty familiar with both JS and C++ translating a bit of JS code didn’t seem like too much of a hassle. And thus I have created concaveman-cpp.

concaveman-cpp offers a modern C++11 implementation of concaveman along with a Python wrapper using cffi. It requires an external implementation to provide it with the initial convex hull. To this end I rely on scipy.spatial.ConvexHull which behind the scenes uses the grand daddy of all hull libraries – QHull. You can see the results of my implementation in the very first image. I have tested it so far on a couple of real-life datasets and it seems to be working to my complete satisfaction. Therefore, big thanks to Park and Oh and to mapbox guys – Vladimir Agafonkin & co. for the ideas and JS implementation.

Please visit the project GitHub and try it out! 🙂

Citation 1: Wikipedia
Illustration of Alpha Shape: Wikimedia Commons
Citation 2: Wikipedia
Feature Photo: Nikola Radojcic on Unsplash