extractloops

 loops=extractloops(edges)

 extract individual loop or polyline segment from a collection of edges

 author: Qianqian Fang, <q.fang at neu.edu>
 date: 2007/11/21

 input:   
    edges:  two column matrix recording the starting/ending 
             points of all edge segments

 output:
    loops:  output, a single vector separated by NaN, each segment
             is a 3D polyline or loop consisted of node IDs

 example:
    edges=[1 2;2 3;1 4;3 4;7 3;1 9;5 6;6 7;10 9; 8 10;1 8;9 3;11 11;11 12];
    loops=extractloops(edges)

 -- this function is part of iso2mesh toolbox (http://iso2mesh.sf.net)

0001 function loops=extractloops(edges)
0002 %
0003 % loops=extractloops(edges)
0004 %
0005 % extract individual loop or polyline segment from a collection of edges
0006 %
0007 % author: Qianqian Fang, <q.fang at neu.edu>
0008 % date: 2007/11/21
0009 %
0010 % input:
0011 %    edges:  two column matrix recording the starting/ending
0012 %             points of all edge segments
0013 %
0014 % output:
0015 %    loops:  output, a single vector separated by NaN, each segment
0016 %             is a 3D polyline or loop consisted of node IDs
0017 %
0018 % example:
0019 %    edges=[1 2;2 3;1 4;3 4;7 3;1 9;5 6;6 7;10 9; 8 10;1 8;9 3;11 11;11 12];
0020 %    loops=extractloops(edges)
0021 %
0022 % -- this function is part of iso2mesh toolbox (http://iso2mesh.sf.net)
0023 %
0024 
0025 loops=[];
0026 loops=[loops,edges(1,:)];
0027 loophead=edges(1,1);
0028 loopend=edges(1,end);
0029 edges(1,:)=[];
0030 
0031 while(~isempty(edges))
0032     idx=[find(edges(:,1)==loopend)',find(edges(:,2)==loopend)'];
0033     if(length(idx)>1) % when a node with multiple connection found
0034         idx=idx(1);   % take the first connection and continue
0035     end
0036     if(isempty(idx)) % when an open-line segment gets to one end
0037         % when both open ends are found
0038         if(isempty([find(edges(:,1)==loophead)',find(edges(:,2)==loophead)']))
0039             loops=[loops,nan];
0040             loops=[loops,edges(1,:)];
0041             loophead=edges(1,1);
0042             loopend=edges(1,end);
0043             edges(1,:)=[];
0044         else % only the first open end is found, flip and trace the other
0045             [loophead, loopend]=deal(loopend, loophead);
0046             lp=fliplr(loops);
0047             seg=find(isnan(lp),1);
0048             if(isempty(seg))
0049                 loops=lp;
0050             else
0051                 loops=[loops(1:end-seg(1)+1) lp(1:seg(1)-1)];
0052             end
0053         end
0054         continue;    
0055     end
0056     if(length(idx)==1) % tracing along a single line thread
0057         idx=idx(1);
0058         newend=setdiff(edges(idx,:),loopend);
0059         if(newend==loophead)  % when a loop is found
0060             loops=[loops loophead nan];
0061             edges(idx,:)=[];
0062             if(size(edges,1)==0) break; end
0063             loops=[loops,edges(1,:)];
0064             loophead=edges(1,1);
0065             loopend=edges(1,end);
0066             edges(1,:)=[];
0067             continue;
0068         else
0069             loops=[loops,newend];
0070         end
0071         loopend=newend;
0072         edges(idx,:)=[];
0073     end
0074 end
0075