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

41 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

      • Hello Stanislaw
        I am on Linux and building using sh doesn’t work.
        I get a linking error:
        /usr/bin/ld: /tmp/ccZI97QD.o: warning: relocation against `_ZSt4cout@@GLIBCXX_3.4′ in read-only section `.text’
        /usr/bin/ld: /tmp/ccZI97QD.o: relocation R_X86_64_PC32 against symbol `_ZSt4cout@@GLIBCXX_3.4′ can not be used when making a shared object; recompile with -fPIC
        /usr/bin/ld: final link failed: bad value
        collect2: error: ld returned 1 exit status

        It’s about the cout. Apparantly cout can’t be in a shared library. Nor can the std::runtime_error class.
        Just removing the cout using an #ifdef worked for me. But i’m not sure what to place at the ‘throw std::runtime_error’?

        Can you please help?

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

  • تاپ-اوج-بالا-نوک شرکتهای برای معاملاتی-بازرگانی-تجارت-تجاری-زنبیلها-معامله رمزنگاری پول-ارز. 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!

  • SEO продвижение сайтов любой тематики и на любом CMS (движке). Команда профессионалов имеет индивидуальный подход к каждому клиенту. Грамотно создадим стратегию продвижения и запустим Ваш сайт в работу. Вы сразу заметите улучшение позиций и повышение траста на своих площадках. Обращаться в телеграмм @pokras777, каждый вебмастер останется довольным.

    либо в скайп логин pokras7777

    RHzs43hgndIpuiSy

  • I’m not sure where you’re getting your info, but great topic. I needs to spend some time learning much more or understanding more.
    Thanks for great info I was looking for this info for my mission.

  • Our main objective is to take you to an online casino that you will enjoy without worrying about your safety. All casino brands listed here are authorized by the respective US state gaming divisions. All winnings are paid out, 100% guaranteed! However, winning is not guaranteed, but the Return to Player (RTP) of all online casino games is audited by gaming regulators to ensure players are given a fair chance.

  • Hello, I believe your site could possibly be having web browser compatibility
    issues. Whenever I take a look at your blog in Safari, it looks
    fine however, when opening in IE, it has some overlapping issues.
    I simply wanted to give you a quick heads up!
    Aside from that, fantastic website!


Leave a Reply

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