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

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

      • hello, thanks for the tool
        unfortunatelly i cannot compile the code.
        i am on Windows and i have installed MinGW
        i run the command “sh concaveman.cpp” but nothing is created
        any help appreciated

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

  • تاپ-اوج-بالا-نوک شرکتهای برای معاملاتی-بازرگانی-تجارت-تجاری-زنبیلها-معامله رمزنگاری پول-ارز. currency-trading-brokers.com/forex-comparisons-ratings-reviews-iran.html

  • Wow! After all I got a blog from where I be able to truly get useful information regarding my study and knowledge. sgemr.munhea.se/map9.php mГ¶rk choklad ica

  • Great website. Plenty of helpful info here. I am sending it to several friends ans additionally sharing in delicious. And certainly, thanks in your sweat! prefi.munhea.se/map13.php privatlГ¤kare stockholm pris

  • Sorry, my last post is caused by my fault.
    I used pandas to read csv, and used .values to convert to numpy.
    .values seems to be the criminal. I changed .values to to_numpy(), it worked well.

  • Привет,
    Ребята!

    Дочитайте наше сообщение до конца.
    [url=]Клуб Вулкан Рояль[/url] предоставляет возможность сыграть в игровые автоматы в режиме демо.

  • I recommend to you to visit on a site, with a large quantity of articles on a theme interesting you. I can look for the reference.

  • Hi there, just became aware of your blog through Google, and
    found that it is truly informative. I’m going to watch out for
    brussels. I’ll appreciate if you continue this in future.
    Many people will be benefited from your writing. Cheers!


Leave a Reply

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