src/SMESHUtils/SMESH_FreeBorders.cxx

   1 // Copyright (C) 2007-2015  CEA/DEN, EDF R&D, OPEN CASCADE
   2 //
   3 // This library is free software; you can redistribute it and/or
   4 // modify it under the terms of the GNU Lesser General Public
   5 // License as published by the Free Software Foundation; either
   6 // version 2.1 of the License, or (at your option) any later version.
   7 //
   8 // This library is distributed in the hope that it will be useful,
   9 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  10 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  11 // Lesser General Public License for more details.
  12 //
  13 // You should have received a copy of the GNU Lesser General Public
  14 // License along with this library; if not, write to the Free Software
  15 // Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307 USA
  16 //
  17 // See http://www.salome-platform.org/ or email : webmaster.salome@opencascade.com
  18 //
  19 // File      : SMESH_FreeBorders.cxx
  20 // Created   : Tue Sep  8 17:08:39 2015
  21 // Author    : Edward AGAPOV (eap)
  22
  23 //================================================================================
  24 // Implementation of SMESH_MeshAlgos::FindCoincidentFreeBorders()
  25 //================================================================================
  26
  27 #include "SMESH_MeshAlgos.hxx"
  28
  29 #include "SMDS_LinearEdge.hxx"
  30 #include "SMDS_Mesh.hxx"
  31 #include "SMDS_SetIterator.hxx"
  32
  33 #include <algorithm>
  34 #include <limits>
  35 #include <set>
  36 #include <vector>
  37
  38 #include <NCollection_DataMap.hxx>
  39 #include <gp_Pnt.hxx>
  40
  41 using namespace SMESH_MeshAlgos;
  42
  43 namespace
  44 {
  45   struct BEdge;
  46
  47   /*!
  48    * \brief Node on a free border
  49    */
  50   struct BNode : public SMESH_TNodeXYZ
  51   {
  52     mutable std::vector< BEdge* > myLinkedEdges;
  53     mutable std::vector< std::pair < BEdge*, double > > myCloseEdges; // edge & U
  54
  55     BNode(const SMDS_MeshNode * node): SMESH_TNodeXYZ( node ) {}
  56     const SMDS_MeshNode * Node() const { return _node; }
  57     void   AddLinked( BEdge* e ) const;
  58     void   AddClose ( const BEdge* e, double u ) const;
  59     BEdge* GetCloseEdge( size_t i ) const { return myCloseEdges[i].first; }
  60     double GetCloseU( size_t i ) const { return myCloseEdges[i].second; }
  61     BEdge* GetCloseEdgeOfBorder( int borderID, double * u = 0 ) const;
  62     bool   HasCloseEdgeWithNode( const BNode* n ) const;
  63     bool   IsCloseEdge( const BEdge*, double * u = 0 ) const;
  64     bool operator<(const BNode& other) const { return Node()->GetID() < other.Node()->GetID(); }
  65   };
  66   /*!
  67    * \brief Edge of a free border
  68    */
  69   struct BEdge : public SMDS_LinearEdge
  70   {
  71     const BNode*            myBNode1;
  72     const BNode*            myBNode2;
  73     int                     myBorderID;
  74     int                     myID; // within a border
  75     BEdge*                  myPrev;
  76     BEdge*                  myNext;
  77     const SMDS_MeshElement* myFace;
  78     std::set< int >         myCloseBorders;
  79     int                     myInGroup;
  80
  81     BEdge():SMDS_LinearEdge( 0, 0 ), myBorderID(-1), myID(-1), myPrev(0), myNext(0), myInGroup(-1) {}
  82
  83     void Set( const BNode *           node1,
  84               const BNode *           node2,
  85               const SMDS_MeshElement* face,
  86               const int               ID)
  87     {
  88       myBNode1   = node1;
  89       myBNode2   = node2;
  90       myNodes[0] = node1->Node();
  91       myNodes[1] = node2->Node();
  92       myFace     = face;
  93       setId( ID ); // mesh element ID
  94     }
  95     bool IsInGroup() const
  96     {
  97       return myInGroup >= 0;
  98     }
  99     bool Contains( const BNode* n ) const
 100     {
 101       return ( n == myBNode1 || n == myBNode2 );
 102     }
 103     void AddLinked( BEdge* e )
 104     {
 105       if ( e->Contains( myBNode1 )) myPrev = e;
 106       else                          myNext = e;
 107     }
 108     void RemoveLinked( BEdge* e )
 109     {
 110       if ( myPrev == e ) myPrev = 0;
 111       if ( myNext == e ) myNext = 0;
 112     }
 113     void Reverse()
 114     {
 115       std::swap( myBNode1, myBNode2 );
 116       myNodes[0] = myBNode1->Node();
 117       myNodes[1] = myBNode2->Node();
 118     }
 119     void Orient()
 120     {
 121       if (( myPrev && !myPrev->Contains( myBNode1 )) ||
 122           ( myNext && !myNext->Contains( myBNode2 )))
 123         std::swap( myPrev, myNext );
 124       if ( myPrev && myPrev->myBNode2 != myBNode1 ) myPrev->Reverse();
 125       if ( myNext && myNext->myBNode1 != myBNode2 ) myNext->Reverse();
 126     }
 127     void SetID( int id )
 128     {
 129       if ( myID < 0 )
 130       {
 131         myID = id;
 132         if ( myNext )
 133           myNext->SetID( id + 1 );
 134       }
 135     }
 136     bool IsOut( const gp_XYZ& point, const double tol, double& u ) const
 137     {
 138       gp_XYZ  me = *myBNode2 - *myBNode1;
 139       gp_XYZ n1p = point     - *myBNode1;
 140       u = ( me * n1p ) / me.SquareModulus(); // param [0,1] on this
 141       if ( u < 0. ) return ( n1p.SquareModulus() > tol * tol );
 142       if ( u > 1. ) return ( ( point - *myBNode2 ).SquareModulus() > tol * tol );
 143
 144       gp_XYZ  proj = ( 1. - u ) * *myBNode1 + u * *myBNode2; // projection of the point on this
 145       double dist2 = ( point - proj ).SquareModulus();
 146       return ( dist2 > tol * tol );
 147     }
 148     bool IsOverlappingProjection( const BEdge* toE, const double u, bool is1st ) const
 149     {
 150       // is1st shows which end of toE is projected on this at u
 151       double u2;
 152       const double eps = 0.1;
 153       if ( myBNode1->IsCloseEdge( toE, &u2 ) ||
 154            myBNode2->IsCloseEdge( toE, &u2 ))
 155         return (( 0 < u2 && u2 < 1 ) &&     // u2 is proj param of myBNode's on toE
 156                 ( Abs( u2 - int( !is1st )) > eps ));
 157
 158       const BNode* n = is1st ? toE->myBNode2 : toE->myBNode1;
 159       if ( this == n->GetCloseEdgeOfBorder( this->myBorderID, &u2 ))
 160         return Abs( u - u2 ) > eps;
 161       return false;
 162     }
 163     bool GetRangeOfSameCloseBorders(BEdge* eRange[2], const std::set< int >& bordIDs)
 164     {
 165       if ( this->myCloseBorders != bordIDs )
 166         return false;
 167
 168       if ( bordIDs.size() == 1 && bordIDs.count( myBorderID )) // border close to self
 169       {
 170         double u;
 171         eRange[0] = this;
 172         while ( eRange[0]->myBNode1->GetCloseEdgeOfBorder( myBorderID, &u ))
 173         {
 174           if ( eRange[0]->myPrev == this || u < 0 || u > 1 )
 175             break;
 176           eRange[0] = eRange[0]->myPrev;
 177         }
 178         eRange[1] = this;
 179         while ( eRange[1]->myBNode2->GetCloseEdgeOfBorder( myBorderID, &u ))
 180         {
 181           if ( eRange[1]->myNext == this || u < 0 || u > 1 )
 182             break;
 183           eRange[1] = eRange[1]->myNext;
 184         }
 185       }
 186       else
 187       {
 188         eRange[0] = this;
 189         while ( eRange[0]->myPrev && eRange[0]->myPrev->myCloseBorders == bordIDs )
 190         {
 191           if ( eRange[0]->myPrev == this )
 192             break;
 193           eRange[0] = eRange[0]->myPrev;
 194         }
 195
 196         eRange[1] = this;
 197         if ( eRange[0]->myPrev != this ) // not closed border
 198           while ( eRange[1]->myNext && eRange[1]->myNext->myCloseBorders == bordIDs )
 199           {
 200             if ( eRange[1]->myNext == this )
 201               break;
 202             eRange[1] = eRange[1]->myNext;
 203           }
 204       }
 205
 206       if ( eRange[0] == eRange[1] )
 207       {
 208         std::set<int>::iterator closeBord = eRange[0]->myCloseBorders.begin();
 209         for ( ; closeBord != eRange[0]->myCloseBorders.end(); ++closeBord )
 210         {
 211           if ( BEdge* be = eRange[0]->myBNode1->GetCloseEdgeOfBorder( *closeBord ))
 212             if ( be->myCloseBorders == eRange[0]->myCloseBorders )
 213               return true;
 214           if ( BEdge* be = eRange[0]->myBNode2->GetCloseEdgeOfBorder( *closeBord ))
 215             if ( be->myCloseBorders == eRange[0]->myCloseBorders )
 216               return true;
 217         }
 218         return false;
 219       }
 220       return true;
 221     }
 222   }; // class BEdge
 223
 224   void extendPart( BEdge* & e1, BEdge* & e2, const std::set< int >& bordIDs, int groupID )
 225   {
 226     if (( e1->myPrev == e2 ) ||
 227         ( e1 == e2 && e1->myPrev && e1->myPrev->myInGroup == groupID ))
 228       return; // full free border already
 229
 230     double u;
 231     BEdge* be;
 232     std::set<int>::const_iterator bord;
 233     if ( e1->myPrev )
 234     {
 235       for ( bord = bordIDs.begin(); bord != bordIDs.end(); ++bord )
 236         if ((( be = e1->myBNode1->GetCloseEdgeOfBorder( *bord, &u ))) &&
 237             (  be->myInGroup == groupID ) &&
 238             (  0 < u && u < 1 ) &&
 239             (  be->IsOverlappingProjection( e1->myPrev, u, false )))
 240         {
 241           e1 = e1->myPrev;
 242           break;
 243         }
 244       if ( bord == bordIDs.end() && // not extended
 245            e1->myBNode1->HasCloseEdgeWithNode( e1->myPrev->myBNode1 ))
 246       {
 247         e1 = e1->myPrev;
 248       }
 249       e1->myInGroup = groupID;
 250     }
 251     if ( e2->myNext )
 252     {
 253       for ( bord = bordIDs.begin(); bord != bordIDs.end(); ++bord )
 254         if ((( be = e2->myBNode2->GetCloseEdgeOfBorder( *bord, &u ))) &&
 255             (  be->myInGroup == groupID ) &&
 256             (  0 < u && u < 1 ) &&
 257             (  be->IsOverlappingProjection( e2->myNext, u, true )))
 258         {
 259           e2 = e2->myNext;
 260           break;
 261         }
 262       if ( bord == bordIDs.end() && // not extended
 263            e2->myBNode2->HasCloseEdgeWithNode( e2->myNext->myBNode2 ))
 264       {
 265         e2 = e2->myNext;
 266       }
 267       e2->myInGroup = groupID;
 268     }
 269   }
 270
 271   void BNode::AddLinked( BEdge* e ) const
 272   {
 273     myLinkedEdges.reserve(2);
 274     myLinkedEdges.push_back( e );
 275     if ( myLinkedEdges.size() < 2 ) return;
 276
 277     if ( myLinkedEdges.size() == 2 )
 278     {
 279       myLinkedEdges[0]->AddLinked( myLinkedEdges[1] );
 280       myLinkedEdges[1]->AddLinked( myLinkedEdges[0] );
 281     }
 282     else
 283     {
 284       for ( size_t i = 0; i < myLinkedEdges.size(); ++i )
 285         for ( size_t j = 0; j < myLinkedEdges.size(); ++j )
 286           if ( i != j )
 287             myLinkedEdges[i]->RemoveLinked( myLinkedEdges[j] );
 288     }
 289   }
 290   void BNode::AddClose ( const BEdge* e, double u ) const
 291   {
 292     if ( ! e->Contains( this ))
 293       myCloseEdges.push_back( make_pair( const_cast< BEdge* >( e ), u ));
 294   }
 295   BEdge* BNode::GetCloseEdgeOfBorder( int borderID, double * uPtr ) const
 296   {
 297     BEdge* e = 0;
 298     double u = 0;
 299     for ( size_t i = 0; i < myCloseEdges.size(); ++i )
 300       if ( borderID == GetCloseEdge( i )->myBorderID )
 301       {
 302         if ( e && Abs( u - 0.5 ) < Abs( GetCloseU( i ) - 0.5 ))
 303           continue;
 304         u = GetCloseU( i );
 305         e = GetCloseEdge ( i );
 306       }
 307     if ( uPtr ) *uPtr = u;
 308     return e;
 309   }
 310   bool BNode::HasCloseEdgeWithNode( const BNode* n ) const
 311   {
 312     for ( size_t i = 0; i < myCloseEdges.size(); ++i )
 313       if ( GetCloseEdge( i )->Contains( n ) &&
 314            0 < GetCloseU( i ) && GetCloseU( i ) < 1 )
 315         return true;
 316     return false;
 317   }
 318   bool BNode::IsCloseEdge( const BEdge* e, double * uPtr ) const
 319   {
 320     for ( size_t i = 0; i < myCloseEdges.size(); ++i )
 321       if ( e == GetCloseEdge( i ) )
 322       {
 323         if ( uPtr ) *uPtr = GetCloseU( i );
 324         return true;
 325       }
 326     return false;
 327   }
 328
 329   /// Accessor to SMDS_MeshElement* inherited by BEdge
 330   struct ElemAcess
 331   {
 332     static const SMDS_MeshElement* value( std::vector< BEdge >::const_iterator it)
 333     {
 334       return & (*it);
 335     }
 336   };
 337   /// Iterator over a vector of BEdge's
 338   static SMDS_ElemIteratorPtr getElemIterator( const std::vector< BEdge > & bedges )
 339   {
 340     typedef SMDS_SetIterator
 341       < const SMDS_MeshElement*, std::vector< BEdge >::const_iterator, ElemAcess > BEIter;
 342     return SMDS_ElemIteratorPtr( new BEIter( bedges.begin(), bedges.end() ));
 343   }
 344
 345 } // namespace
 346
 347 // struct needed for NCollection_Map
 348 struct TLinkHasher
 349 {
 350   static int HashCode(const SMESH_TLink& link, int aLimit)
 351   {
 352     return ::HashCode( link.node1()->GetID() + link.node2()->GetID(), aLimit );
 353   }
 354   static Standard_Boolean IsEqual(const SMESH_TLink& l1, const SMESH_TLink& l2)
 355   {
 356     return ( l1.node1() == l2.node1() && l1.node2() == l2.node2() );
 357   }
 358 };
 359
 360 //================================================================================
 361 /*
 362  * Returns groups of TFreeBorder's coincident within the given tolerance.
 363  * If the tolerance <= 0.0 then one tenth of an average size of elements adjacent
 364  * to free borders being compared is used.
 365  */
 366 //================================================================================
 367
 368 void SMESH_MeshAlgos::FindCoincidentFreeBorders(SMDS_Mesh&              mesh,
 369                                                 double                  tolerance,
 370                                                 CoincidentFreeBorders & foundFreeBordes)
 371 {
 372   // find free links
 373   typedef NCollection_DataMap<SMESH_TLink, const SMDS_MeshElement*, TLinkHasher > TLink2FaceMap;
 374   TLink2FaceMap linkMap;
 375   int nbSharedLinks = 0;
 376   SMDS_FaceIteratorPtr faceIt = mesh.facesIterator();
 377   while ( faceIt->more() )
 378   {
 379     const SMDS_MeshElement* face = faceIt->next();
 380     if ( !face ) continue;
 381
 382     const SMDS_MeshNode*     n0 = face->GetNode( face->NbNodes() - 1 );
 383     SMDS_NodeIteratorPtr nodeIt = face->interlacedNodesIterator();
 384     while ( nodeIt->more() )
 385     {
 386       const SMDS_MeshNode* n1 = nodeIt->next();
 387       SMESH_TLink link( n0, n1 );
 388       if ( const SMDS_MeshElement** faceInMap = linkMap.ChangeSeek( link ))
 389       {
 390         nbSharedLinks += bool( *faceInMap );
 391         *faceInMap = 0;
 392       }
 393       else
 394       {
 395         linkMap.Bind( link, face );
 396       }
 397       n0 = n1;
 398     }
 399   }
 400   if ( linkMap.Extent() == nbSharedLinks )
 401     return;
 402
 403   // form free borders
 404   std::set   < BNode > bNodes;
 405   std::vector< BEdge > bEdges( linkMap.Extent() - nbSharedLinks );
 406
 407   TLink2FaceMap::Iterator linkIt( linkMap );
 408   for ( int iEdge = 0; linkIt.More(); linkIt.Next() )
 409   {
 410     if ( !linkIt.Value() ) continue;
 411     const SMESH_TLink & link = linkIt.Key();
 412     std::set< BNode >::iterator n1 = bNodes.insert( BNode( link.node1() )).first;
 413     std::set< BNode >::iterator n2 = bNodes.insert( BNode( link.node2() )).first;
 414     bEdges[ iEdge ].Set( &*n1, &*n2, linkIt.Value(), iEdge+1 );
 415     n1->AddLinked( & bEdges[ iEdge ] );
 416     n2->AddLinked( & bEdges[ iEdge ] );
 417     ++iEdge;
 418   }
 419   linkMap.Clear();
 420
 421   // assign IDs to borders
 422   std::vector< BEdge* > borders; // 1st of connected (via myPrev and myNext) edges
 423   std::set< BNode >::iterator bn = bNodes.begin();
 424   for ( ; bn != bNodes.end(); ++bn )
 425   {
 426     for ( size_t i = 0; i < bn->myLinkedEdges.size(); ++i )
 427     {
 428       if ( bn->myLinkedEdges[i]->myBorderID < 0 )
 429       {
 430         BEdge* be = bn->myLinkedEdges[i];
 431         int borderID = borders.size();
 432         borders.push_back( be );
 433         for ( ; be && be->myBorderID < 0; be = be->myNext )
 434         {
 435           be->myBorderID = borderID;
 436           be->Orient();
 437         }
 438         bool isClosed = ( be == bn->myLinkedEdges[i] );
 439         be = bn->myLinkedEdges[i]->myPrev;
 440         for ( ; be && be->myBorderID < 0; be = be->myPrev )
 441         {
 442           be->myBorderID = borderID;
 443           be->Orient();
 444         }
 445         if ( !isClosed )
 446           while ( borders.back()->myPrev )
 447             borders.back() = borders.back()->myPrev;
 448
 449         borders.back()->SetID( 0 ); // set IDs to all edges of the border
 450       }
 451     }
 452   }
 453
 454   // compute tolerance of each border
 455   double maxTolerance = tolerance;
 456   std::vector< double > bordToler( borders.size(), tolerance );
 457   if ( maxTolerance < std::numeric_limits< double >::min() )
 458   {
 459     // no tolerance provided by the user; compute tolerance of each border
 460     // as one tenth of an average size of faces adjacent to a border
 461     for ( size_t i = 0; i < borders.size(); ++i )
 462     {
 463       double avgFaceSize = 0;
 464       int    nbFaces     = 0;
 465       BEdge* be = borders[ i ];
 466       do {
 467         double facePerimeter = 0;
 468         gp_Pnt p0 = SMESH_TNodeXYZ( be->myFace->GetNode( be->myFace->NbNodes() - 1 ));
 469         SMDS_NodeIteratorPtr nodeIt = be->myFace->interlacedNodesIterator();
 470         while ( nodeIt->more() )
 471         {
 472           gp_Pnt p1 = SMESH_TNodeXYZ( nodeIt->next() );
 473           facePerimeter += p0.Distance( p1 );
 474           p0 = p1;
 475         }
 476         avgFaceSize += ( facePerimeter / be->myFace->NbCornerNodes() );
 477         nbFaces++;
 478
 479         be = be->myNext;
 480       }
 481       while ( be && be != borders[i] );
 482
 483       bordToler[ i ] = 0.1 * avgFaceSize / nbFaces;
 484       maxTolerance = Max( maxTolerance, bordToler[ i ]);
 485     }
 486   }
 487
 488   // for every border node find close border edges
 489   SMESH_ElementSearcher* searcher =
 490     GetElementSearcher( mesh, getElemIterator( bEdges ), maxTolerance );
 491   SMESHUtils::Deleter< SMESH_ElementSearcher > searcherDeleter( searcher );
 492   std::vector< const SMDS_MeshElement* > candidateEdges;
 493   for ( bn = bNodes.begin(); bn != bNodes.end(); ++bn )
 494   {
 495     searcher->FindElementsByPoint( *bn, SMDSAbs_Edge, candidateEdges );
 496     if ( candidateEdges.size() <= bn->myLinkedEdges.size() )
 497       continue;
 498
 499     double nodeTol = 0, u;
 500     for ( size_t i = 0; i < bn->myLinkedEdges.size(); ++i )
 501       nodeTol = Max( nodeTol, bordToler[ bn->myLinkedEdges[ i ]->myBorderID ]);
 502
 503     for ( size_t i = 0; i < candidateEdges.size(); ++i )
 504     {
 505       const BEdge* be = static_cast< const BEdge* >( candidateEdges[ i ]);
 506       double      tol = Max( nodeTol, bordToler[ be->myBorderID ]);
 507       if ( !be->IsOut( *bn, tol, u ))
 508         bn->AddClose( be, u );
 509     }
 510   }
 511
 512   // for every border edge find close borders
 513
 514   std::vector< BEdge* > closeEdges;
 515   for ( size_t i = 0; i < bEdges.size(); ++i )
 516   {
 517     BEdge& be = bEdges[i];
 518     if ( be.myBNode1->myCloseEdges.empty() ||
 519          be.myBNode2->myCloseEdges.empty() )
 520       continue;
 521
 522     closeEdges.clear();
 523     for ( size_t iE1 = 0; iE1 < be.myBNode1->myCloseEdges.size(); ++iE1 )
 524     {
 525       // find edges of the same border close to both nodes of the edge
 526       BEdge* closeE1 = be.myBNode1->GetCloseEdge( iE1 );
 527       BEdge* closeE2 = be.myBNode2->GetCloseEdgeOfBorder( closeE1->myBorderID );
 528       if ( !closeE2 )
 529         continue;
 530       // check that edges connecting closeE1 and closeE2 (if any) are also close to 'be'
 531       if ( closeE1 != closeE2 )
 532       {
 533         bool coincide;
 534         for ( int j = 0; j < 2; ++j ) // move closeE1 -> closeE2 or inversely
 535         {
 536           BEdge* ce = closeE1;
 537           do {
 538             coincide = ( ce->myBNode2->GetCloseEdgeOfBorder( be.myBorderID ));
 539             ce       = ce->myNext;
 540           } while ( coincide && ce && ce != closeE2 );
 541
 542           if ( coincide && ce == closeE2 )
 543             break;
 544           if ( j == 0 )
 545             std::swap( closeE1, closeE2 );
 546           coincide = false;
 547         }
 548         if ( !coincide )
 549           continue;
 550         closeEdges.push_back( closeE1 );
 551         closeEdges.push_back( closeE2 );
 552       }
 553       else
 554       {
 555         closeEdges.push_back( closeE1 );
 556       }
 557       be.myCloseBorders.insert( closeE1->myBorderID );
 558     }
 559     if ( !closeEdges.empty() )
 560     {
 561       be.myCloseBorders.insert( be.myBorderID );
 562       // for ( size_t iB = 0; iB < closeEdges.size(); ++iB )
 563       //   closeEdges[ iB ]->myCloseBorders.insert( be.myCloseBorders.begin(),
 564       //                                            be.myCloseBorders.end() );
 565     }
 566   }
 567
 568   // Fill in CoincidentFreeBorders
 569
 570   // save nodes of free borders
 571   foundFreeBordes._borders.resize( borders.size() );
 572   for ( size_t i = 0; i < borders.size(); ++i )
 573   {
 574     BEdge* be = borders[i];
 575     foundFreeBordes._borders[i].push_back( be->myBNode1->Node() );
 576     do {
 577       foundFreeBordes._borders[i].push_back( be->myBNode2->Node() );
 578       be = be->myNext;
 579     }
 580     while ( be && be != borders[i] );
 581   }
 582
 583   // form groups of coincident parts of free borders
 584
 585   TFreeBorderPart  part;
 586   TCoincidentGroup group;
 587   vector< BEdge* > ranges; // couples of edges delimiting parts
 588   BEdge* be = 0; // a current edge
 589   int skipGroup = bEdges.size(); // a group ID used to avoid repeating treatment of edges
 590
 591   for ( int i = 0, nbBords = borders.size(); i < nbBords; i += bool(!be) )
 592   {
 593     if ( !be )
 594       be = borders[i];
 595
 596     // look for an edge close to other borders
 597     do {
 598       if ( !be->IsInGroup() && !be->myCloseBorders.empty() )
 599         break;
 600       be = be->myNext;
 601     } while ( be && be != borders[i] );
 602
 603     if ( !be || be->IsInGroup() || be->myCloseBorders.empty() )
 604     {
 605       be = 0;
 606       continue; // all edges of a border are treated or non-coincident
 607     }
 608     group.clear();
 609     ranges.clear();
 610
 611     // look for the 1st and last edge of a coincident group
 612     BEdge* beRange[2];
 613     if ( !be->GetRangeOfSameCloseBorders( beRange, be->myCloseBorders ))
 614     {
 615       be->myInGroup = skipGroup;
 616       be = be->myNext;
 617       continue;
 618     }
 619
 620     ranges.push_back( beRange[0] );
 621     ranges.push_back( beRange[1] );
 622
 623     int groupID = foundFreeBordes._coincidentGroups.size();
 624     be = beRange[0];
 625     be->myInGroup = groupID;
 626     while ( be != beRange[1] )
 627     {
 628       be->myInGroup = groupID;
 629       be = be->myNext;
 630     }
 631     beRange[1]->myInGroup = groupID;
 632
 633     // get starting edge of each close border
 634     closeEdges.clear();
 635     be = beRange[0];
 636     if ( be->myCloseBorders.empty() )
 637       be = beRange[0]->myNext;
 638     std::set<int>::iterator closeBord = be->myCloseBorders.begin();
 639     for ( ; closeBord != be->myCloseBorders.end(); ++closeBord )
 640       if ( BEdge* e = be->myBNode2->GetCloseEdgeOfBorder( *closeBord ))
 641         closeEdges.push_back( e );
 642
 643     for ( size_t iE = 0; iE < closeEdges.size(); ++iE )
 644       if ( be->myCloseBorders != closeEdges[iE]->myCloseBorders )
 645       {
 646         closeBord = closeEdges[iE]->myCloseBorders.begin();
 647         for ( ; closeBord != closeEdges[iE]->myCloseBorders.end(); ++closeBord )
 648           if ( !be->myCloseBorders.count( *closeBord ))
 649             if ( BEdge* e = closeEdges[iE]->myBNode2->GetCloseEdgeOfBorder( *closeBord ))
 650               if ( std::find( closeEdges.begin(), closeEdges.end(), e ) == closeEdges.end() )
 651                 closeEdges.push_back( e );
 652       }
 653
 654     // add parts of other borders
 655
 656     BEdge* be1st = beRange[0];
 657     for ( size_t iE = 0; iE < closeEdges.size(); ++iE )
 658     {
 659       be = closeEdges[ iE ];
 660       if ( !be ) continue;
 661
 662       bool ok = be->GetRangeOfSameCloseBorders( beRange, be->myCloseBorders );
 663       // if ( !ok && be->myPrev )
 664       //   ok = be->myPrev->GetRangeOfSameCloseBorders( beRange, be1st->myCloseBorders );
 665       // if ( !ok && be->myNext )
 666       //   ok = be->myNext->GetRangeOfSameCloseBorders( beRange, be1st->myCloseBorders );
 667       if ( !ok )
 668         continue;
 669
 670       be = beRange[0];
 671
 672       ranges.push_back( beRange[0] );
 673       ranges.push_back( beRange[1] );
 674
 675       be->myInGroup = groupID;
 676       while ( be != beRange[1] )
 677       {
 678         be->myInGroup = groupID;
 679         be = be->myNext;
 680       }
 681       beRange[1]->myInGroup = groupID;
 682     }
 683
 684     if ( ranges.size() > 2 )
 685     {
 686       for ( size_t iR = 1; iR < ranges.size(); iR += 2 )
 687         extendPart( ranges[ iR-1 ], ranges[ iR ], be1st->myCloseBorders, groupID );
 688
 689       // fill in a group
 690       beRange[0] = ranges[0];
 691       beRange[1] = ranges[1];
 692
 693       part._border   = i;
 694       part._node1    = beRange[0]->myID;
 695       part._node2    = beRange[0]->myID + 1;
 696       part._nodeLast = beRange[1]->myID + 1;
 697       group.push_back( part );
 698
 699       be1st = beRange[0];
 700       for ( size_t iR = 3; iR < ranges.size(); iR += 2 )
 701       {
 702         beRange[0] = ranges[iR-1];
 703         beRange[1] = ranges[iR-0];
 704
 705         // find out mutual orientation of borders
 706         double u1, u2;
 707         be1st       ->IsOut( *beRange[ 0 ]->myBNode1, maxTolerance, u1 );
 708         beRange[ 0 ]->IsOut( *be1st->myBNode1,        maxTolerance, u2 );
 709         bool reverse = (( u1 < 0 || u1 > 1 ) && ( u2 < 0 || u2 > 1 ));
 710
 711         // fill in a group
 712         part._border   = beRange[0]->myBorderID;
 713         if ( reverse ) {
 714           part._node1    = beRange[1]->myID + 1;
 715           part._node2    = beRange[1]->myID;
 716           part._nodeLast = beRange[0]->myID;
 717         }
 718         else  {
 719           part._node1    = beRange[0]->myID;
 720           part._node2    = beRange[0]->myID + 1;
 721           part._nodeLast = beRange[1]->myID + 1;
 722         }
 723         // if ( group[0]._node2 != part._node2 )
 724         group.push_back( part );
 725       }
 726       //if ( group.size() > 1 )
 727         foundFreeBordes._coincidentGroups.push_back( group );
 728     }
 729     else
 730     {
 731       beRange[0] = ranges[0];
 732       beRange[1] = ranges[1];
 733
 734       be = beRange[0];
 735       be->myInGroup = skipGroup;
 736       while ( be != beRange[1] )
 737       {
 738         be->myInGroup = skipGroup;
 739         be = be->myNext;
 740       }
 741       beRange[1]->myInGroup = skipGroup;
 742     }
 743
 744     be = ranges[1];
 745
 746   } // loop on free borders
 747
 748   return;
 749
 750 } // SMESH_MeshAlgos::FindCoincidentFreeBorders()
 751