Finding lists of connected triangles in TriRep class

Hi

I have a triangle mesh of type TriRep. I have selected few faces (or triangles) out based on some criteria. These few triangles are in connected groups. I want to find out how many groups of these triangles are there.

neighbors(tris,selectedFaces) Only give me connectivity of one triangle. e.g.

           3         NaN           2
         NaN         NaN           1
           1          11           4
         NaN          12           3  
% where tris is the TriRep triangular representation
and selectedFaces is the list of few selected faces in TriRep

The output above means that 1st face (1st row of the output) in selectedFaces has 3rd and 2nd face as neighbors and is not connected at one edge.

We can also see that face 3 (third row of the output) is connected to face 11 and 4 and face 4 (4th row of the output) is connected to 12 in addition to 3.

So this means that faces 1,2,3,4,11,12 form a group or a chain of triangles. I want to know if there is any way to find out this connectivity without using any adjacency matrix or Warshall's algorithms.

Any help is appreciated.

Best Regards

Wajahat

[Wajahat]

I found a way to do this.

I first computed a sparse adjacency matrix (NxN) where N is the total number of triangular faces. One of the ways to get the adjacency matrix is mentioned in:

http://www.mathworks.com/matlabcentral/newsreader/view_thread/46618

Suppose the name of the sparse Adjacency matrix is: adjSpr

Then I used Matlab's Grap Theory toolbox to compute the connected triangles:

[Sg,Cg]=graphconncomp(adjSpr);

where Sg gives the total number of groups formed by connected triangles, and Cg is a cell containing triangular faces in Sg number of groups. The method is quite efficient.

The graph can be visualized by:

bg=biograph(adjSpr);

view(bg);

A slightly in efficient way for the computation of adjacency matrix is:

numFaces=tris.size(1);

nbList=tris.neighbors;

adjMat=zeros(numFaces);

for count=1:numFaces

if ~isnan(nbList(count,1))

adjMat(count, nbList(count,1))=1;

end

if ~isnan(nbList(count,2))

adjMat(count, nbList(count,2))=1;

end

if ~isnan(nbList(count,3))

adjMat(count, nbList(count,3))=1;

end

end

adjMat=adjMat-diag(diag(adjMat)); % remove the diagonal since a face is always connected to itself

Best Regards

Wajahat

Answer 1

[Richard Brown]

Why don't you want to define an adjacency matrix? If you do, then you could just use the components routine in MATLAB-BGL

http://www.mathworks.com/matlabcentral/fileexchange/10922

[Wajahat]

Yes, this is what I found out and have added to the comments above.

In fact the function, graphconncomp() does the same and is included in Matlab BioInformatic Toolbox (above, I called it Graph Theory toolbox, my fault).

The only difference is that it uses a sparse matrix.

So either an adjacency matrix is created as a sparse matrix or a dense matrix can be transformed into a sparse matrix by:

sparse(densematrix)