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

Hi Stanislaw,

The github repo doesn’t have a file for `libconcaveman.so` and I’m not familiar enough yet with the conversion process. There’s a `concaveman.h` and a `concaveman.cpp` file though.

Would you be able to help me out with a crash-course in using cpp libraries in python?

Hi Coastal,

If you are on *NIX and have g++ installed, it should be a matter of going to the directory with concaveman.cpp and running:

sh concaveman.cpp

The path of the resulting .so file should be provided in place of the hard-coded one.

If you are on Windows, you will need some sort of compiler as well. MSYS or MinGW could be used to get g++. Otherwise, Visual Studio comes with a native compiler cl.exe.

This:

cl /std:c++14 /EHsc /c concaveman.cpp

link /DLL concaveman.obj /O:concaveman.dll

should do the trick with Visual Studio. Then you would need to provided path to concaveman.dll instead of libconcaveman.so.

I noticed that cl.exe requires also the following changes:

1) Add #include

2) Comment out make_unique function definition

3) Add using std::make_unique instead

4) Replace calls to random() with rand()

Hope this helps.

AD. 1. WordPress has eaten out the tags, the necessary header is called stdlib.h

Фотоотчет проделанных работ, оценеваем перила лестничные установленные в московской области