vb_connected_vertex

 extract connected vertex index
  [Vinx, Nall, ix_rest] = vb_connected_vertex(Vindx,F)
 --- Input
 Vindx : vertex index list for search
 F     : patch index list
 --- Output
 Vinx{n} : vertex index of n-th connected surface
 Nall(n) : # of points for n-th connected surface
 ix_rest : disconnected points

 Ver 1.0  by M. Sato  2006-11-11

 ポリゴンモデルの連結面を取り出す
 ポリゴンモデルの三角面法線の向きを外向きに揃える

 　 アルゴリズム 
０．候補 周辺頂点リストに関するループ
１．候補 周辺頂点リストからルート頂点を選ぶ
２．ルート点の未処理隣接三角面を探す
３．隣接三角面の中で前回最終頂点を含むものを探す
４．三角面頂点の並び方を揃える
５．三角面のもう一つの頂点を今回の最終頂点にする
６．周辺頂点リストに向きを確定した辺の頂点を追加する
７．未処理面が残っていれば２へ戻る
８．未処理の周辺頂点が残っていれば１へ戻る
９．確定した周辺頂点リストを新しい候補リストにして０に戻る

 Copyright (C) 2011, ATR All Rights Reserved.
 License : New BSD License(see VBMEG_LICENSE.txt)

0001 function    [Vinx, Nall, ix_rest] = vb_connected_vertex(Vindx,F)
0002 % extract connected vertex index
0003 %  [Vinx, Nall, ix_rest] = vb_connected_vertex(Vindx,F)
0004 % --- Input
0005 % Vindx : vertex index list for search
0006 % F     : patch index list
0007 % --- Output
0008 % Vinx{n} : vertex index of n-th connected surface
0009 % Nall(n) : # of points for n-th connected surface
0010 % ix_rest : disconnected points
0011 %
0012 % Ver 1.0  by M. Sato  2006-11-11
0013 %
0014 % ポリゴンモデルの連結面を取り出す
0015 % ポリゴンモデルの三角面法線の向きを外向きに揃える
0016 %
0017 % 　 アルゴリズム
0018 %０．候補 周辺頂点リストに関するループ
0019 %１．候補 周辺頂点リストからルート頂点を選ぶ
0020 %２．ルート点の未処理隣接三角面を探す
0021 %３．隣接三角面の中で前回最終頂点を含むものを探す
0022 %４．三角面頂点の並び方を揃える
0023 %５．三角面のもう一つの頂点を今回の最終頂点にする
0024 %６．周辺頂点リストに向きを確定した辺の頂点を追加する
0025 %７．未処理面が残っていれば２へ戻る
0026 %８．未処理の周辺頂点が残っていれば１へ戻る
0027 %９．確定した周辺頂点リストを新しい候補リストにして０に戻る
0028 %
0029 % Copyright (C) 2011, ATR All Rights Reserved.
0030 % License : New BSD License(see VBMEG_LICENSE.txt)
0031 
0032 Npoint = max([F(:); Vindx(:)]);  % 頂点数
0033 
0034 % 'Vindx'を含むパッチのみを取り出す
0035 F = vb_patch_select(Vindx,F,Npoint);
0036 
0037 Npoint = max([F(:); Vindx(:)]);  % 頂点数
0038 Npatch = size(F,1);      % 三角面数
0039 
0040 Plist = zeros(Npoint,2);    % 候補 周辺頂点リスト
0041 Vlist = zeros(Npoint,2);    % 向き確定 周辺頂点リスト
0042 Vflg  = zeros(Npoint,1);    % 頂点処理済みフラグ
0043 Fflg  = zeros(Npatch,1);    % 三角面処理済みフラグ
0044 FF      = zeros(Npatch,3);    % 三角面インデックス
0045 
0046 % 'Vindx'以外を除外
0047 Vflg(:) = -1;
0048 
0049 % 'Vindx'を未処理にする
0050 Vflg(Vindx) = 0;
0051 
0052 % 隣接三角面インデックスリストの作成
0053 % xxF{n} : 頂点 n に隣接する面の頂点番号と面番号
0054 xxF  = vb_neighbor_index(zeros(Npoint,1),F);
0055 
0056 % ルートインデックス
0057 nextID = [];
0058 
0059 for j = 1:length(Vindx)
0060     root = Vindx(j);
0061     nextID = xxF{root};
0062      if ~isempty(nextID),  break; end;
0063 end
0064 
0065 if isempty(nextID), 
0066     ix_rest = Vindx;
0067     Vinx = [];
0068     Nall = 0;
0069     Fall = [];
0070     return
0071 end
0072 
0073 Plist(1,:) = [root, nextID(1,1)];
0074 
0075 Nsurf = 1;
0076 Nall  = [];
0077 
0078 while 1,
0079     
0080     Nlist =1;% 候補 周辺頂点数
0081     Nroot =0;% 処理済み頂点数
0082     
0083     while Nlist > 0,
0084     
0085         Nedge = 0;% 向き確定 周辺頂点数
0086         
0087         % 周辺頂点に関するループ
0088         for n=1:Nlist,
0089             % root インデックスと next インデックスの更新
0090             root = Plist(n,1);
0091             next = Plist(n,2);
0092             
0093             % root の隣接点インデックスリスト
0094             nextID = xxF{root};     
0095             
0096             % 隣接点リスト
0097             nlist1 = nextID(:,1);     % 隣接点リスト1
0098             nlist2 = nextID(:,2);     % 隣接点リスト2
0099             flist  = nextID(:,3);     % 隣接三角面リスト
0100             
0101             % 未処理の面インデックスを探す
0102             nextix = find( Fflg(flist) == 0 );
0103             
0104             if isempty(nextix), 
0105                 continue;
0106             end;
0107             
0108             % 未処理面のインデックスリスト
0109             nlist1 = nlist1(nextix);
0110             nlist2 = nlist2(nextix);
0111             flist  = flist(nextix);
0112             
0113             Nnext  = length(nextix);
0114             Nnew   = Nnext;
0115         
0116             % root に隣接する未処理面ループ
0117             for i=1:Nnext, 
0118                 % nlist1/2 の中で、前回の隣接頂点 next を含む面の探索
0119                 jx1  = find( nlist1==next );
0120                 jx2  = find( nlist2==next );
0121                 
0122                 if ~isempty(jx1),
0123                        nold  = next;
0124                     jj      = jx1(1);        % next を含む面のリスト内番号
0125                     fid   = flist(jj);  % next を含む面の面番号
0126                     next  = nlist2(jj); % この面のもう一つの三角面頂点
0127     
0128                     % 向き確定 周辺頂点リストに追加
0129                     Nedge = Nedge + 1;
0130                     Vlist(Nedge,:) = [next nold];
0131                     % 三角面頂点インデックスの入れ替え
0132                     FF(fid,:) = [root, nold, next];
0133                     % この面を処理済みリストに入れる
0134                     Fflg(fid) = 1;
0135                     % この頂点を処理済みにする(面番号代入)
0136                     Vflg([root, nold, next]) = Nsurf;
0137                     
0138                     % この面を隣接面リストから削除
0139                     inew   = [1:(jj-1),(jj+1):Nnew];
0140                     flist  = flist(inew);
0141                     nlist1 = nlist1(inew);
0142                     nlist2 = nlist2(inew);
0143                     Nnew   = Nnew-1;
0144                 elseif ~isempty(jx2),
0145                        nold  = next;
0146                     jj      = jx2(1);        % next を含む面のリスト内番号
0147                     fid   = flist(jj);  % next を含む面の面番号
0148                     next  = nlist1(jj); % この面のもう一つの三角面頂点
0149     
0150                     % 向き確定 周辺頂点リストに追加
0151                     Nedge = Nedge + 1;
0152                     Vlist(Nedge,:) = [next nold];
0153                     % 三角面頂点インデックスの入れ替え
0154                     FF(fid,:) = [root, nold, next];
0155                     % この面を処理済みリストに入れる
0156                     Fflg(fid) = 1;
0157                     % この頂点を処理済みにする(面番号代入)
0158                     Vflg([root, nold, next]) = Nsurf;
0159                     
0160                     % この面を隣接面リストから削除
0161                     inew   = [1:(jj-1),(jj+1):Nnew];
0162                     flist  = flist(inew);
0163                     nlist1 = nlist1(inew);
0164                     nlist2 = nlist2(inew);
0165                     Nnew   = Nnew-1;
0166                 end;
0167             end
0168             % END- (root) に隣接する未処理面ループ
0169             
0170         end;
0171         % END-周辺頂点に関するループ
0172         
0173         % 候補 周辺頂点リストの更新
0174         Nlist = Nedge;
0175         Plist(1:Nedge,:) = Vlist(1:Nedge,:);
0176     
0177     end
0178     % --- END of connected surface search ---
0179     
0180     % 処理済みの頂点数
0181     Nall(Nsurf) = sum(Vflg == Nsurf);
0182     
0183     % 未処理の頂点を取り出す
0184     ix_rest = find(Vflg == 0);
0185 
0186     if isempty(ix_rest), break; end;
0187     
0188     Plist = zeros(Npoint,2);    % 候補 周辺頂点リスト
0189     Vlist = zeros(Npoint,2);    % 向き確定 周辺頂点リスト
0190     
0191     % ルートインデックス
0192     seedJJ = [];
0193     
0194     for jj = 1:length(ix_rest)
0195         seedID = ix_rest(jj);
0196         seedJJ = xxF{seedID};
0197          if ~isempty(seedJJ),  break; end;
0198      end
0199 
0200     if isempty(seedJJ), break; end;
0201     
0202     Plist(1,:) = [seedID, seedJJ(1,1)];
0203     
0204     Nsurf = Nsurf + 1;
0205 end
0206 
0207 inxf = find(Fflg == 1);
0208 FF     = FF(inxf,:);
0209 
0210 % 未処理の頂点を取り出す
0211 ix_rest = find(Vflg == 0);
0212 ix_rest = ix_rest';
0213 
0214 % 大きい面の順に並び替え
0215 [Nall , id]= sort( -Nall );
0216 
0217 Vinx = cell(Nsurf,1);
0218 
0219 for n=1:Nsurf
0220     % id(n)-番目の面の頂点を取り出す
0221     indx = find( Vflg == id(n) );
0222     Vinx{n} = indx';
0223     Nall(n) = length(indx);
0224 end
0225 
0226 return
0227 
0228