MATLAB Answers

Finding lists of connected triangles in TriRep class

13 ビュー (過去 30 日間)
Wajahat
Wajahat 2012 年 4 月 11 日
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 件のコメント
Wajahat
Wajahat 2012 年 5 月 1 日
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

サインインしてコメントする。

採用された回答

Richard Brown
Richard Brown 2012 年 5 月 1 日
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 件のコメント
Wajahat
Wajahat 2012 年 5 月 2 日
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)

サインインしてコメントする。

その他の回答 (0 件)

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by