[GIS] How to find the concave hull for a cloud of points in 3D space

3dalgorithmconcave hullpoint

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

Best Answer

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

PostGIS

If you are using the PostGIS stack, pgRouting's optional Driving Distance extension exposes an alpha shape implementation. I'm not sure if you can vary the alpha parameter, however.

Usage is below:

SELECT the_geom AS alpha_shape 
FROM 
  points_as_polygon(
    'SELECT id, ST_X(your_geom) AS x, ST_Y(your_geom) AS y FROM your_table');

Python

There are probably many Python modules you could use. I have heard good things about CGAL, a C++ computational geometry library. Python wrappers exist for parts of CGAL, including exposing CGAL's alpha shape implementation to Python.

Be aware that parts of CGAL are licensed under the QPL, which means that if you distribute your program, linked to CGAL, you may need to release it under the QPL. It is fine to keep your code proprietary if you do not redistribute your program code or binaries.

[GIS] inner convex-hulls in a set of 2D points

One solution could be this one:

1) Calculate a triangulation of the whole area.

2) For each triangle, test if inclusion of neighbouring triangles retains the convexity. If more than 1, pick the neighbour, that adds the most to the area. Run the test again with a new set of neighbouring triangles.

I don't know if this will actually find the largest ICH, but it should be a good candidate.

Best Answer

Related Solutions

Concave Hull Algorithm – Definition, Algorithms, and Practical Solutions for Concave Hull

PostGIS

Python

[GIS] inner convex-hulls in a set of 2D points

Related Question