# Finding concave hull for separated small clusters

Data :

 data3D = Import[file, "VertexData"];
Graphics3D[Point[data3D]]


How to find concave polygon for separated small clusters.

-
Have you already explored the earlier question Finding a Concave Hull? –  Joseph O'Rourke Jul 28 '12 at 0:24
@JosephO'Rourke That question came from the same poster –  belisarius Jul 28 '12 at 3:44

The procedure I suggested for your other "concave hull" question seems to work reasonably well here, simultaneously isolating the clusters and creating the surfaces.

Needs["TetGenLink"];
{pts,tetrahedra}=TetGenDelaunay[data3D];
csr[{aa_,bb_,cc_,dd_}]:=With[{a=aa-dd,b=bb-dd,c=cc-dd},
Norm[a.a Cross[b,c]+b.b Cross[c,a]+c.c Cross[a,b]]/(2Norm[a.Cross[b,c]])];
faces[tetras_]:=Flatten[tetras/.{a_,b_,c_,d_}:>{{a,b,c},{a,b,d},{a,c,d},{b,c,d}},1];
externalfaces[faces_]:=Cases[Tally[Sort/@faces],{face_,1}:>face];

polys=externalfaces@faces@alphashape[1.8];

Graphics3D[{EdgeForm[],GraphicsComplex[pts,Polygon@polys]},Boxed->False]


## Cluster colouring

The clusters using this method are just sets of connected polygons. We can build a graph of these connections and use ConnectedComponents to find the individual clusters. This allows such things as colouring the clusters for easier visualisation.

clusters=ConnectedComponents@Graph@DeleteDuplicates[
Sort/@Flatten[UndirectedEdge@@@Subsets[#,{2}]&/@polys]];

clusteredpolys=GatherBy[polys,Position[clusters,First@#][[1,1]]&];

Graphics3D[{EdgeForm[],GraphicsComplex[pts,
{Hue[RandomReal[]],Polygon@#}&/@clusteredpolys]},Boxed->False]


-

As I said before, there really isn't such a thing as a concave hull. What you want to do is plot your clusters here.

The first problem involves a machine vision problem known as 3D segmentation. Mathematica doesn't have any tools out of the box to do this, as far as I know.

One way is to guess how many "clusters" are in your data, although that's hard to say because it appear to be sort of fractal. You should experiment with heuristics for doing this.

Needs["TetGenLink"];

data3D = Import["http://dl.dropbox.com/u/68983831/process02.vtk",
"VertexData"];

cls = FindClusters[data3D, 40];

Show[(Graphics3D[{EdgeForm[None],
GraphicsComplex[#1, Polygon[TetGenConvexHull[#1]]]}] &) /@ cls]


You might also try a different metric, although it makes clustering slower:

cls = FindClusters[data3D, 40, DistanceFunction -> ManhattanDistance];

Show[(Graphics3D[{EdgeForm[None],
GraphicsComplex[#1, Polygon[TetGenConvexHull[#1]]]}] &) /@ cls]


If you want something besides the convex hull for each cluster, you might try adapting an answer to Finding a Concave Hull.

-