The existing algorithm for convex hull is not able to capture the feature for a set of 3D points. Moreover, I found few mathematic tools have this function to obtain the concave hull and their responding points.

Given the data of spheres:

enter image description here

x1 y1 z1 radii_1

x2 y2 z2 radii_2


xn yn zn radii_n

Any idea?

Update 1:

I found a 2D algorithm, it works fine depending on the threshold value. However, I need the 3D algorithm.

enter image description here

  • What software are you using, or are you after a mathematical principle? I found using the vector dot product to find the left-leftest the best. – Michael Stimson Apr 24 '15 at 0:36
  • I use Mathematics in Windows and Octave in Linux. Both coeds don't provide available function for this issue. I am looking for a algorithms based on above coeds. – KOF Apr 24 '15 at 0:42
  • en.wikipedia.org/wiki/Convex_hull_algorithms, that's where I started. The simplest (I found) is to use the vector product to find the left of the left then iterate. – Michael Stimson Apr 24 '15 at 0:46
  • Hi @KOF what algorithm are you using to produce the 2D version? I'm looking for something similar in gis.stackexchange.com/questions/152175/… – Paul Meems Jun 25 '15 at 8:33

A convex hull is unique, whereas there are many possible concave hulls. So you cannot say "the concave hull" but "a concave hull".

There is possibly a minimal volume concave hull, but this is not the case on the example you shown. It is also possible to define various criteria, such as the minimal acceptable concave edge angle, for avoiding deep trenches or pits in the obtained hull.

All hulls on the following picture are valid, depending on the level of "tightness" you are looking forenter image description here


The source code of concave hull for point cloud is written in http://pointclouds.org/documentation/tutorials/hull_2d.php:

In this tutorial we will learn how to calculate a simple 2D hull polygon (concave or convex) for a set of points supported by a plane.

  • I am sure that concave hull can not be calculated for 3D points. 3D points should be projected to 2D plane. – LenItsuki Aug 20 '15 at 23:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.