Geographic Information Systems Stack Exchange is a question and answer site for cartographers, geographers and GIS professionals. It only takes a minute to sign up.
Sign up to join this community
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:
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.
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 for
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.
