I have a 3d clustered data:
Is there any other way to get concavehull of 3D data points?
|show 7 more comments|
Here's a possible approach.
First use TetGen to tetrahedralize the data:
Next define a function to compute the radius of the circumsphere of a tetrahedron (formula from Wikipedia)
Now calculate the radius of each tetrahedron in your data, and define a function to pick out only those tetrahedra with radius below a given threshold:
This function converts a tetrahedron into a list of 4 triangular faces:
We also need to remove internal polygons. Internal polygons appear twice, since they belong to two tetrahedra, so we simply need to prune the list of faces to those which only appear once in the list.
Now we can generate the graphics for a particular value of
Here's an animation showing the effect of different values of
As pointed out in the comments, there's really no mathematical definition of a concave hull.
Of course, just because there's no mathematical definition does not preclude coming up with something that sort of works. I can think of two ways to do this:
Easy Way, Not General
Your data roughly has axial symmetry parallel to the x-axis. Moreover, all of your coordinates appear to be integers.
So for every integral value of x, you can make a slice of your data between x and x+1. Then, for each slice, compute the convex hull. Finally, stitch all of the results together, like so:
I'd call this a "duct tape" solution.
Addendum: This works on Mathematica v8.0.0, however it appears that v22.214.171.124 makes a change to the output of
Complicated Way, More General (And Not Implemented ;-)
A complicated but perhaps more general solution to this problem would be to use Voronoi diagrams. Similar techniques have been proposed for removing data points from banks in k-Nearest Neighbor searches. Here's a paper on this if you're interested.
Sketch of the algorithm:
This would effectively keep only "exterior" points in your set.
This approach has drawbacks: the first is that it will sometimes discard points that, intuitively, a child with a crayon would probably not. The second is that it's slow. Finally, it violates the KISS design pattern, so it's a chore to write (hence, I didn't bother).