Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

Data :

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

enter image description here

How to find concave polygon for separated small clusters.

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

2 Answers 2

up vote 5 down vote accepted

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]])];
radii=csr[pts[[#]]]&/@tetrahedra;
alphashape[rmax_]:=Pick[tetrahedra,radii,r_/;r<rmax];
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]

enter image description here

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]

enter image description here

share|improve this answer

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.

I guessed about 40 for your data:

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]

Clustered Data

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]

Clustered Using Manhattan Distance

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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