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
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?
If you are on *NIX and have g++ installed, it should be a matter of going to the directory with concaveman.cpp and running:
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.
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
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
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
I’m not just inviting you! But it will be interesting for sure loveawake.ru
Hurry up to look into loveawake.ru you will find a lot of interesting things
Hurry up to look into loveawake.ru you will find a lot of interesting things….
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.
Clearly, thanks for an explanation.
I think, that you are mistaken. Let’s discuss it.
You are mistaken. I can defend the position. Write to me in PM, we will talk.
I hope, you will find the correct decision. Do not despair.
I think, what is it — a false way. And from it it is necessary to turn off.
In my opinion you are mistaken. Let’s discuss. Write to me in PM.
In my opinion you are not right. I can defend the position. Write to me in PM, we will talk.
I am ready to help you, set questions. Together we can find the decision.
Yes, really. I agree with told all above.
Дочитайте наше сообщение до конца.
[url=]Клуб Вулкан Рояль[/url] предоставляет возможность сыграть в игровые автоматы в режиме демо.
In my opinion you are not right. I am assured. Let’s discuss it. Write to me in PM, we will communicate.
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.
It is the valuable answer
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
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.
?Vive en Espana?! ?Proporcionaremos credito! banks.credit credito rapido
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.