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

6 Comments

  • 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.

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


Leave a Reply

Your email address will not be published. Required fields are marked *