src/Poly/Poly_MakeLoops.cxx

   1 // Created on: 2009-10-22
   2 // Created by: Mikhail SAZONOV
   3 // Copyright (c) 2009-2012 OPEN CASCADE SAS
   4 //
   5 // The content of this file is subject to the Open CASCADE Technology Public
   6 // License Version 6.5 (the "License"). You may not use the content of this file
   7 // except in compliance with the License. Please obtain a copy of the License
   8 // at http://www.opencascade.org and read it completely before using this file.
   9 //
  10 // The Initial Developer of the Original Code is Open CASCADE S.A.S., having its
  11 // main offices at: 1, place des Freres Montgolfier, 78280 Guyancourt, France.
  12 //
  13 // The Original Code and all software distributed under the License is
  14 // distributed on an "AS IS" basis, without warranty of any kind, and the
  15 // Initial Developer hereby disclaims all such warranties, including without
  16 // limitation, any warranties of merchantability, fitness for a particular
  17 // purpose or non-infringement. Please see the License for the specific terms
  18 // and conditions governing the rights and limitations under the License.
  19
  20
  21 #include <Poly_MakeLoops.hxx>
  22 #include <NCollection_IncAllocator.hxx>
  23 #include <NCollection_DataMap.hxx>
  24 #include <gp_Dir.hxx>
  25 #include <gp_Dir2d.hxx>
  26
  27 #ifdef _DEBUG
  28 static Standard_Integer doDebug = 0;
  29 #endif
  30
  31 //=======================================================================
  32 //function : Poly_MakeLoops
  33 //purpose  :
  34 //=======================================================================
  35
  36 Poly_MakeLoops::Poly_MakeLoops(const Helper* theHelper,
  37                                      const Handle_NCollection_BaseAllocator& theAlloc)
  38 : myHelper (theHelper),
  39   myAlloc (theAlloc),
  40   myMapLink (4000, myAlloc),
  41   myLoops (myAlloc),
  42   myStartIndices (4000)
  43 {
  44 }
  45
  46 //=======================================================================
  47 //function : Reset
  48 //purpose  :
  49 //=======================================================================
  50
  51 void Poly_MakeLoops::Reset
  52                    (const Helper* theHelper,
  53                     const Handle_NCollection_BaseAllocator& theAlloc)
  54 {
  55   myHelper = theHelper;
  56   myMapLink.Clear();
  57   myLoops.Clear(theAlloc);
  58   myStartIndices.Clear();
  59   myAlloc = theAlloc;
  60 }
  61
  62 //=======================================================================
  63 //function : AddLink
  64 //purpose  :
  65 //=======================================================================
  66
  67 void Poly_MakeLoops::AddLink(const Link& theLink)
  68 {
  69   if (theLink.node1 == theLink.node2)
  70     return;
  71   Standard_Integer aInd = myMapLink.Add(theLink);
  72   Link& aLink = const_cast<Link&>(myMapLink(aInd));
  73   aLink.flags |= theLink.flags;
  74 #ifdef _DEBUG
  75   myHelper->OnAddLink (aInd, aLink);
  76 #endif
  77 }
  78
  79 //=======================================================================
  80 //function : ReplaceLink
  81 //purpose  :
  82 //=======================================================================
  83
  84 void Poly_MakeLoops::ReplaceLink(const Link& theLink, const Link& theNewLink)
  85 {
  86   if (theNewLink.node1 == theNewLink.node2)
  87     return;
  88   Standard_Integer aInd = myMapLink.Add(theLink);
  89   if (aInd > 0)
  90   {
  91     Link aLink;
  92     // replace with a null link first (workaround exception)
  93     myMapLink.Substitute(aInd, aLink);
  94     aLink = theNewLink;
  95     // and now put there the final value of link
  96     myMapLink.Substitute(aInd, aLink);
  97 #ifdef _DEBUG
  98     myHelper->OnAddLink (aInd, aLink);
  99 #endif
 100   }
 101 }
 102
 103 //=======================================================================
 104 //function : SetLinkOrientation
 105 //purpose  :
 106 //=======================================================================
 107
 108 Poly_MakeLoops::LinkFlag Poly_MakeLoops::SetLinkOrientation
 109                    (const Link& theLink,
 110                     const LinkFlag theOrient)
 111 {
 112   Standard_Integer aInd = myMapLink.FindIndex(theLink);
 113   LinkFlag aOri = LF_None;
 114   if (aInd > 0)
 115   {
 116     Link& aLink = const_cast<Link&>(myMapLink(aInd));
 117     aOri = (LinkFlag) (aLink.flags & LF_Both);
 118     aLink.flags = theOrient;
 119 #ifdef _DEBUG
 120     myHelper->OnAddLink (aInd, aLink);
 121 #endif
 122   }
 123   return aOri;
 124 }
 125
 126 //=======================================================================
 127 //function : FindLink
 128 //purpose  :
 129 //=======================================================================
 130
 131 Poly_MakeLoops::Link Poly_MakeLoops::FindLink(const Link& theLink) const
 132 {
 133   Standard_Integer aInd = myMapLink.FindIndex(theLink);
 134   Poly_MakeLoops::Link aLink;
 135   if (aInd > 0)
 136     aLink = myMapLink(aInd);
 137   return aLink;
 138 }
 139
 140 //=======================================================================
 141 //function : Perform
 142 //purpose  :
 143 //=======================================================================
 144
 145 Standard_Integer Poly_MakeLoops::Perform()
 146 {
 147   // prepare the set of start indices
 148   myStartIndices.Clear();
 149   Standard_Integer i;
 150   for (i = 1; i <= myMapLink.Extent(); i++)
 151   {
 152     const Link& aLink = myMapLink(i);
 153     if (aLink.flags & LF_Fwd)
 154       myStartIndices.Add(i);
 155     if (aLink.flags & LF_Rev)
 156       myStartIndices.Add(-i);
 157   }
 158
 159 #ifdef _DEBUG
 160   if (doDebug)
 161     showBoundaryBreaks();
 162 #endif
 163
 164   Standard_Integer aResult = 0;
 165
 166   Handle(NCollection_IncAllocator) aTempAlloc = new NCollection_IncAllocator(4000);
 167   Handle(NCollection_IncAllocator) aTempAlloc1 = new NCollection_IncAllocator(4000);
 168
 169   // two pass loop
 170   Standard_Integer aPassNum, nbLoopsOnPass2 = 0;
 171   for (aPassNum=0; aPassNum < 2; aPassNum++)
 172   {
 173     myHangIndices.Clear();
 174     // main loop
 175     while (!myStartIndices.IsEmpty())
 176     {
 177       Standard_Integer aIndexS = myStartIndices.Top();
 178
 179       aTempAlloc->Reset();
 180       NCollection_IndexedMap<Standard_Integer> aContour (100, aTempAlloc);
 181       Standard_Integer aStartNumber = findContour (aIndexS, aContour, aTempAlloc, aTempAlloc1);
 182 #ifdef _DEBUG
 183       if (aStartNumber > 1)
 184         if (doDebug)
 185         {
 186           cout << "--- found contour with hanging links:" << endl;
 187           for (i = 1; i <= aContour.Extent(); i++)
 188             cout << " " << aContour(i);
 189           cout << endl;
 190         }
 191 #endif
 192       if (aStartNumber == 0)
 193       {      // error
 194         aResult |= RC_Failure;
 195         return aResult;
 196       }
 197       if (aStartNumber <= aContour.Extent())
 198       {
 199         // there is a closed loop in the contour
 200         if (aPassNum == 1)
 201           nbLoopsOnPass2++;
 202         acceptContour (aContour, aStartNumber);
 203       }
 204       if (aStartNumber > 1)
 205       {
 206         // it is required to mark hanging edges
 207         Standard_Integer aNode;
 208         if (aStartNumber <= aContour.Extent())
 209           // mark hanging edges starting from the first one till a bifurcation
 210           aNode = getFirstNode(aIndexS);
 211         else
 212         {
 213           // open contour - mark from the end back till a bifurcation
 214           aIndexS = aContour(aStartNumber - 1);
 215           aNode = getLastNode(aIndexS);
 216         }
 217         markHangChain(aNode, aIndexS);
 218       }
 219     }
 220
 221     if (aPassNum == 0)
 222     {
 223       // move hanging links to start indices to make the second pass
 224       TColStd_MapIteratorOfPackedMapOfInteger it(myHangIndices);
 225       for (; it.More(); it.Next())
 226         myStartIndices.Add(it.Key());
 227     }
 228   }
 229 #ifdef _DEBUG
 230   if (doDebug && nbLoopsOnPass2)
 231     cout << "MakeLoops: " << nbLoopsOnPass2
 232       << " contours accepted on the second pass" << endl;
 233 #endif
 234
 235   if (!myLoops.IsEmpty())
 236     aResult |= RC_LoopsDone;
 237   if (!myHangIndices.IsEmpty())
 238     aResult |= RC_HangingLinks;
 239   return aResult;
 240 }
 241
 242 //=======================================================================
 243 //function : findContour
 244 //purpose  : Collects edges in chain until they form a closed contour.
 245 // Returns the index in the map theContour where the loop starts.
 246 // It may return the number greater than the extent of the map by 1,
 247 // what means that the contour is open
 248 //=======================================================================
 249
 250 Standard_Integer Poly_MakeLoops::findContour
 251                    (Standard_Integer theIndexS,
 252                     NCollection_IndexedMap<Standard_Integer> &theContour,
 253                     const Handle_NCollection_BaseAllocator& theTempAlloc,
 254                     const Handle_NCollection_IncAllocator& theTempAlloc1) const
 255 {
 256   theContour.Clear();
 257   Standard_Integer aStartIndex = 0;
 258   Standard_Integer aIndexS = theIndexS;
 259   NCollection_DataMap<Standard_Integer,Standard_Integer> aNodeLink(100, theTempAlloc);
 260   Standard_Integer aLastNode  = getLastNode (aIndexS);
 261
 262   for (;;) {
 263     theContour.Add(aIndexS);
 264     aNodeLink.Bind(getFirstNode(aIndexS), aIndexS);
 265
 266     Standard_Integer aIndex = Abs (aIndexS);
 267
 268     // collect the list of links from this node able to participate
 269     // in this contour
 270     theTempAlloc1->Reset();
 271     NCollection_List<Standard_Integer> aLstIndS (theTempAlloc1);
 272     const ListOfLink& aLinks = myHelper->GetAdjacentLinks (aLastNode);
 273     Poly_MakeLoops::ListOfLink::Iterator itLinks (aLinks);
 274     for (; itLinks.More(); itLinks.Next()) {
 275       Standard_Integer aInd = myMapLink.FindIndex(itLinks.Value());
 276       if (aInd == 0 || aInd == aIndex)
 277         continue;
 278       // determine the orientation in which the link is to be taken
 279       Standard_Integer aIndS = aInd;
 280       Standard_Integer aNode1 = getFirstNode(aInd);
 281       if (aNode1 != aLastNode)
 282         aIndS = -aIndS;
 283
 284       if (canLinkBeTaken(aIndS))
 285         aLstIndS.Append(aIndS);
 286     }
 287
 288     if (aLstIndS.IsEmpty()) {
 289       // no more ways: open contour
 290       aStartIndex = theContour.Extent() + 1;
 291       break;
 292     }
 293
 294     Standard_Integer aIndexSNext = 0;
 295     if (aLstIndS.First() == aLstIndS.Last())
 296       // only one possible way
 297       aIndexSNext = aLstIndS.First();
 298     else
 299       // find the most left way
 300       aIndexSNext = chooseLeftWay (aLastNode, aIndexS, aLstIndS);
 301
 302     aIndexS = aIndexSNext;
 303
 304     if (aIndexS == 0)
 305     {
 306       // no more ways: open contour
 307       aStartIndex = theContour.Extent() + 1;
 308       break;
 309     }
 310     if (theContour.Contains(aIndexS))
 311     {
 312       // entering the loop second time, stop search
 313       aStartIndex = theContour.FindIndex (aIndexS);
 314       break;
 315     }
 316     if (theContour.Contains (-aIndexS))
 317     {
 318       // leaving the loop, stop search
 319       aStartIndex = theContour.FindIndex (-aIndexS) + 1;
 320       break;
 321     }
 322
 323     aLastNode  = getLastNode (aIndexS);
 324
 325     if (aNodeLink.IsBound(aLastNode))
 326     {
 327       // closing the loop, stop search
 328       theContour.Add(aIndexS);
 329       aStartIndex = theContour.FindIndex(aNodeLink.Find(aLastNode));
 330       break;
 331     }
 332   }
 333
 334   return aStartIndex;
 335 }
 336
 337 //=======================================================================
 338 //function : acceptContour
 339 //purpose  : Builds a wire from a given set of edge indices (starting with
 340 // theStartNumber) and appends it to the result list.
 341 // Also updates the start indices.
 342 //=======================================================================
 343
 344 void Poly_MakeLoops::acceptContour
 345                    (const NCollection_IndexedMap<Standard_Integer>& theContour,
 346                     Standard_Integer theStartNumber)
 347 {
 348   // append a new loop to the result
 349   Loop anEmptyLoop(myAlloc);
 350   myLoops.Append(anEmptyLoop);
 351   Loop& aLoop = myLoops.ChangeValue(myLoops.Length());
 352
 353   // build a loop, mark links as taken,
 354   // remove them from the set of start indices
 355   Standard_Integer i;
 356   for (i = theStartNumber; i <= theContour.Extent(); i++)
 357   {
 358     Standard_Integer aIndexS = theContour(i);   // index with sign
 359     Standard_Integer aIndex = Abs (aIndexS);
 360     const Link& aLink = myMapLink(aIndex);
 361     Link aOrientedLink = aLink;
 362     if (aIndexS < 0)
 363       aOrientedLink.Reverse();
 364     aLoop.Append(aOrientedLink);
 365     // remove from start set
 366     myStartIndices.Remove(aIndexS);
 367   }
 368 }
 369
 370 //=======================================================================
 371 //function : getFirstNode
 372 //purpose  : Returns the first node of the given link
 373 // taking into account its orientation (the sign of index)
 374 //=======================================================================
 375
 376 Standard_Integer Poly_MakeLoops::getFirstNode(Standard_Integer theIndexS) const
 377 {
 378   Standard_Integer aIndex = Abs(theIndexS);
 379   const Link& aLink = myMapLink(aIndex);
 380   if (theIndexS > 0)
 381     return aLink.node1;
 382   return aLink.node2;
 383 }
 384
 385 //=======================================================================
 386 //function : getLastNode
 387 //purpose  : Returns the last node of the given link
 388 // taking into account its orientation (the sign of index)
 389 //=======================================================================
 390
 391 Standard_Integer Poly_MakeLoops::getLastNode(int theIndexS) const
 392 {
 393   Standard_Integer aIndex = Abs(theIndexS);
 394   const Link& aLink = myMapLink(aIndex);
 395   if (theIndexS > 0)
 396     return aLink.node2;
 397   return aLink.node1;
 398 }
 399
 400 //=======================================================================
 401 //function : markHangChain
 402 //purpose  : Marks hanging links starting from the given node.
 403 // Also removes such links from the start indices.
 404 //=======================================================================
 405
 406 void Poly_MakeLoops::markHangChain(Standard_Integer theNode, Standard_Integer theIndexS)
 407 {
 408   Standard_Integer aNode1 = theNode;
 409   Standard_Integer aIndexS = theIndexS;
 410   Standard_Integer aIndex = Abs(aIndexS);
 411   Standard_Boolean isOut = (aNode1 == getFirstNode(aIndexS));
 412   for (;;)
 413   {
 414     // check if the current link is hanging:
 415     // if it is outcoming from aNode1 then count the number of
 416     // other incoming links and vise versa;
 417     // if the number is zero than it is hanging
 418     const ListOfLink& aLinks = myHelper->GetAdjacentLinks (aNode1);
 419     Standard_Integer nEdges = 0;
 420     Poly_MakeLoops::ListOfLink::Iterator itLinks (aLinks);
 421     for (; itLinks.More() && nEdges == 0; itLinks.Next())
 422     {
 423       const Link &aL = itLinks.Value();
 424       Standard_Integer aInd = myMapLink.FindIndex(aL);
 425       if (aInd == 0 || aInd == aIndex)
 426         continue;
 427       if (isOut && aNode1 == aL.node1 ||
 428           !isOut && aNode1 == aL.node2)
 429         aInd = -aInd;
 430       if (canLinkBeTaken(aInd))
 431         nEdges++;
 432     }
 433     if (nEdges > 0)
 434       // leave this chain
 435       break;
 436
 437     // mark the current link as hanging
 438     myStartIndices.Remove(aIndexS);
 439     myHangIndices.Add(aIndexS);
 440
 441     // get other node of the link and the next link
 442     if (isOut)
 443       aNode1 = getLastNode(aIndexS);
 444     else
 445       aNode1 = getFirstNode(aIndexS);
 446     const ListOfLink& aNextLinks = myHelper->GetAdjacentLinks (aNode1);
 447     Standard_Integer aNextIndexS = 0;
 448     for (itLinks.Init(aNextLinks); itLinks.More(); itLinks.Next())
 449     {
 450       const Link &aL = itLinks.Value();
 451       Standard_Integer aInd = myMapLink.FindIndex(aL);
 452       if (aInd == 0 || aInd == aIndex)
 453         continue;
 454       if (isOut && aNode1 == aL.node2 ||
 455           !isOut && aNode1 == aL.node1)
 456         aInd = -aInd;
 457       if (canLinkBeTaken(aInd))
 458       {
 459         if (aNextIndexS == 0)
 460           aNextIndexS = aInd;
 461         else
 462         {
 463           // more than 1 ways, stop the chain
 464           aNextIndexS = 0;
 465           break;
 466         }
 467       }
 468     }
 469     if (aNextIndexS == 0)
 470       break;
 471     aIndexS = aNextIndexS;
 472     aIndex = Abs(aIndexS);
 473   }
 474 }
 475
 476 //=======================================================================
 477 //function : canLinkBeTaken
 478 //purpose  : Returns True if the link appointed by the index can participate
 479 // in a loop in given orientation (it is the sign of index).
 480 // Remark: A boundary edge can be taken only once
 481 //=======================================================================
 482
 483 Standard_Boolean Poly_MakeLoops::canLinkBeTaken(Standard_Integer theIndexS) const
 484 {
 485   return myStartIndices.Contains(theIndexS);
 486 }
 487
 488 //=======================================================================
 489 //function : showBoundaryBreaks
 490 //purpose  :
 491 //=======================================================================
 492
 493 #ifdef _DEBUG
 494 void Poly_MakeLoops::showBoundaryBreaks() const
 495 {
 496   // collect nodes of boundary links
 497   TColStd_PackedMapOfInteger aNodesMap;
 498   Standard_Integer i;
 499   for (i = 1; i <= myMapLink.Extent(); i++)
 500   {
 501     const Link& aLink = myMapLink(i);
 502     Standard_Integer aFlags = aLink.flags & LF_Both;
 503     if (aFlags && aFlags != LF_Both)
 504     {
 505       // take only oriented links
 506       aNodesMap.Add(aLink.node1);
 507       aNodesMap.Add(aLink.node2);
 508     }
 509   }
 510
 511   // check each node if the number of input and output links are equal
 512   Standard_Boolean isFirst = Standard_True;
 513   TColStd_MapIteratorOfPackedMapOfInteger it(aNodesMap);
 514   for (; it.More(); it.Next())
 515   {
 516     Standard_Integer aNode = it.Key();
 517     Standard_Integer nb = 0;
 518     const ListOfLink& aLinks = myHelper->GetAdjacentLinks(aNode);
 519     Poly_MakeLoops::ListOfLink::Iterator itLinks (aLinks);
 520     for (; itLinks.More(); itLinks.Next())
 521     {
 522       const Poly_MakeLoops::Link& aLink = itLinks.Value();
 523       if (myMapLink.FindIndex(aLink) == 0)
 524         continue;
 525       Standard_Integer aFlags = aLink.flags & LF_Both;
 526       if (aFlags && aFlags != LF_Both)
 527       {
 528         if (aNode == aLink.node1) // output?
 529         {
 530           if (aFlags & LF_Fwd)
 531             nb++;  // yes, output
 532           else
 533             nb--;  // reversed, so input
 534         }
 535         else if (aNode == aLink.node2) // input?
 536         {
 537           if (aFlags & LF_Fwd)
 538             nb--;  // yes, input
 539           else
 540             nb++;  // reversed, so output
 541         }
 542         else
 543           // inconsistent
 544           nb += 100;
 545       }
 546     }
 547     if (nb != 0)
 548     {
 549       // indicate this node
 550       if (isFirst)
 551       {
 552         isFirst = Standard_False;
 553         cout << "boundary breaks are found in the following nodes:" << endl;
 554       }
 555       cout << aNode << " ";
 556     }
 557   }
 558   if (!isFirst)
 559     cout << endl;
 560 }
 561 #endif
 562
 563 //=======================================================================
 564 //function : GetHangingLinks
 565 //purpose  :
 566 //=======================================================================
 567
 568 void Poly_MakeLoops::GetHangingLinks(ListOfLink& theLinks) const
 569 {
 570   TColStd_MapIteratorOfPackedMapOfInteger it(myHangIndices);
 571   for (; it.More(); it.Next())
 572   {
 573     Standard_Integer aIndexS = it.Key();
 574     Link aLink = myMapLink(Abs(aIndexS));
 575     if (aIndexS < 0)
 576       aLink.Reverse();
 577     theLinks.Append(aLink);
 578   }
 579 }
 580
 581 //=======================================================================
 582 //function : Poly_MakeLoops3D
 583 //purpose  :
 584 //=======================================================================
 585
 586 Poly_MakeLoops3D::Poly_MakeLoops3D(const Helper* theHelper,
 587                                          const Handle_NCollection_BaseAllocator& theAlloc)
 588 : Poly_MakeLoops (theHelper, theAlloc)
 589 {
 590 }
 591
 592 //=======================================================================
 593 //function : Poly_MakeLoops3D::chooseLeftWay
 594 //purpose  :
 595 //=======================================================================
 596
 597 Standard_Integer Poly_MakeLoops3D::chooseLeftWay
 598                    (const Standard_Integer theNode,
 599                     const Standard_Integer theSegIndex,
 600                     const NCollection_List<Standard_Integer>& theLstIndS) const
 601 {
 602   Standard_Real aAngleMin = M_PI * 2;
 603   gp_Dir aNormal;
 604   const Helper* aHelper = getHelper();
 605   if (!aHelper->GetNormal (theNode, aNormal))
 606     return theLstIndS.First();
 607
 608   Link aLink = getLink(theSegIndex);
 609   gp_Dir aTgtRef;
 610   if (!aHelper->GetLastTangent (aLink, aTgtRef))
 611     return theLstIndS.First();
 612
 613   // project tangent vector to the plane orthogonal to normal
 614   // to get the reference direction
 615   gp_XYZ aTgtRefXYZ = aNormal.XYZ().CrossCrossed (aTgtRef.XYZ(), aNormal.XYZ());
 616   if (aTgtRefXYZ.SquareModulus() < 1e-14)
 617     // a problem with defining reference direction, take first way
 618     return theLstIndS.First();
 619   aTgtRef = aTgtRefXYZ;
 620
 621   // find the way with minimal angle to the reference direction
 622   // (the angle is in range ]-PI;PI])
 623   Standard_Integer aResIndex = 0;
 624   NCollection_List<Standard_Integer>::Iterator aItI (theLstIndS);
 625   for (; aItI.More(); aItI.Next())
 626   {
 627     Standard_Integer aIndS = aItI.Value();
 628
 629     aLink = getLink(aIndS);
 630     gp_Dir aTgt;
 631     if (!aHelper->GetFirstTangent (aLink, aTgt))
 632       continue;
 633
 634     gp_XYZ aTgtXYZ = aNormal.XYZ().CrossCrossed (aTgt.XYZ(), aNormal.XYZ());
 635     if (aTgtXYZ.SquareModulus() < 1e-14)
 636       // skip a problem way
 637       continue;
 638     aTgt = aTgtXYZ;
 639
 640     Standard_Real aAngle = aTgt.AngleWithRef(aTgtRef, aNormal);
 641     if (aAngle < 1e-4 - M_PI)
 642       aAngle = M_PI;
 643     if (aAngle < aAngleMin)
 644     {
 645       aAngleMin = aAngle;
 646       aResIndex = aIndS;
 647     }
 648   }
 649   return aResIndex == 0 ? theLstIndS.First() : aResIndex;
 650 }
 651
 652 //=======================================================================
 653 //function : Poly_MakeLoops2D
 654 //purpose  :
 655 //=======================================================================
 656
 657 Poly_MakeLoops2D::Poly_MakeLoops2D(const Standard_Boolean theLeftWay,
 658                                          const Helper* theHelper,
 659                                          const Handle_NCollection_BaseAllocator& theAlloc)
 660 : Poly_MakeLoops (theHelper, theAlloc),
 661   myRightWay(!theLeftWay)
 662 {
 663 }
 664
 665 //=======================================================================
 666 //function : Poly_MakeLoops2D::chooseLeftWay
 667 //purpose  :
 668 //=======================================================================
 669
 670 Standard_Integer Poly_MakeLoops2D::chooseLeftWay
 671                    (const Standard_Integer /*theNode*/,
 672                     const Standard_Integer theSegIndex,
 673                     const NCollection_List<Standard_Integer>& theLstIndS) const
 674 {
 675   Standard_Real aAngleMin = M_PI * 2;
 676   const Helper* aHelper = getHelper();
 677   Link aLink = getLink(theSegIndex);
 678   gp_Dir2d aTgtRef;
 679   if (!aHelper->GetLastTangent (aLink, aTgtRef))
 680     // a problem with defining reference direction, take first way
 681     return theLstIndS.First();
 682
 683   // find the way with minimal angle to the reference direction
 684   // (the angle is in range ]-PI;PI])
 685   Standard_Integer aResIndex = 0;
 686   NCollection_List<Standard_Integer>::Iterator aItI (theLstIndS);
 687   for (; aItI.More(); aItI.Next())
 688   {
 689     Standard_Integer aIndS = aItI.Value();
 690
 691     aLink = getLink(aIndS);
 692     gp_Dir2d aTgt;
 693     if (!aHelper->GetFirstTangent (aLink, aTgt))
 694       // skip a problem way
 695       continue;
 696
 697     Standard_Real aAngle = aTgt.Angle(aTgtRef);
 698     if (myRightWay)
 699       aAngle = -aAngle;
 700     if (aAngle < 1e-4 - M_PI)
 701       aAngle = M_PI;
 702     if (aAngle < aAngleMin)
 703     {
 704       aAngleMin = aAngle;
 705       aResIndex = aIndS;
 706     }
 707   }
 708   return aResIndex == 0 ? theLstIndS.First() : aResIndex;
 709 }