MATLAB Answers

Finding lists of connected triangles in TriRep class

29 views (last 30 days)
Wajahat
Wajahat on 11 Apr 2012
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

  1 Comment

Wajahat
Wajahat on 1 May 2012
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

Sign in to comment.

Accepted Answer

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

  1 Comment

Wajahat
Wajahat on 2 May 2012
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)

Sign in to comment.

More Answers (0)

Sign in to answer this question.


Translated by