src/BRepMesh/BRepMesh_Delaun.cxx

   1 // Created on: 1993-05-12
   2 // Created by: Didier PIFFAULT
   3 // Copyright (c) 1993-1999 Matra Datavision
   4 // Copyright (c) 1999-2014 OPEN CASCADE SAS
   5 //
   6 // This file is part of Open CASCADE Technology software library.
   7 //
   8 // This library is free software; you can redistribute it and/or modify it under
   9 // the terms of the GNU Lesser General Public License version 2.1 as published
  10 // by the Free Software Foundation, with special exception defined in the file
  11 // OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT
  12 // distribution for complete text of the license and disclaimer of any warranty.
  13 //
  14 // Alternatively, this file may be used under the terms of Open CASCADE
  15 // commercial license or contractual agreement.
  16
  17 #include <BRepMesh_Delaun.hxx>
  18
  19 #include <gp.hxx>
  20 #include <gp_XY.hxx>
  21 #include <gp_Pnt2d.hxx>
  22 #include <gp_Vec2d.hxx>
  23
  24 #include <Precision.hxx>
  25 #include <Bnd_Box2d.hxx>
  26 #include <Bnd_B2d.hxx>
  27
  28 #include <BRepMesh_SelectorOfDataStructureOfDelaun.hxx>
  29
  30 #include <BRepMesh_Edge.hxx>
  31 #include <BRepMesh_Vertex.hxx>
  32 #include <BRepMesh_Triangle.hxx>
  33
  34 #include <NCollection_Vector.hxx>
  35
  36 #include <algorithm>
  37
  38 const Standard_Real AngDeviation1Deg  = M_PI/180.;
  39 const Standard_Real AngDeviation90Deg = 90 * AngDeviation1Deg;
  40 const Standard_Real Angle2PI          = 2 * M_PI;
  41
  42 const Standard_Real Precision    = Precision::PConfusion();
  43 const Standard_Real Precision2   = Precision * Precision;
  44
  45 namespace {
  46   //! Sort two points in projection on vector (1,1)
  47   struct ComparatorOfVertexOfDelaun
  48   {
  49     bool operator() (const BRepMesh_Vertex& theLeft, const BRepMesh_Vertex& theRight)
  50     {
  51       return theLeft.Coord().X() + theLeft.Coord().Y() < theRight.Coord().X() + theRight.Coord().Y();
  52     }
  53   };
  54
  55   //! Sort two points in projection on vector (1,1)
  56   struct ComparatorOfIndexedVertexOfDelaun
  57   {
  58   public:
  59     ComparatorOfIndexedVertexOfDelaun (const Handle(BRepMesh_DataStructureOfDelaun)& theDS)
  60       : myStructure(theDS) {}
  61
  62     bool operator() (Standard_Integer theLeft, Standard_Integer theRight)
  63     {
  64       const BRepMesh_Vertex& aLeft  = myStructure->GetNode(theLeft);
  65       const BRepMesh_Vertex& aRight = myStructure->GetNode(theRight);
  66       return ComparatorOfVertexOfDelaun() (aLeft, aRight);
  67     }
  68
  69   private:
  70     Handle(BRepMesh_DataStructureOfDelaun) myStructure;
  71   };
  72 } // anonymous namespace
  73
  74 //=======================================================================
  75 //function : BRepMesh_Delaun
  76 //purpose  : Creates the triangulation with an empty Mesh data structure
  77 //=======================================================================
  78 BRepMesh_Delaun::BRepMesh_Delaun(
  79   BRepMesh::Array1OfVertexOfDelaun& theVertices)
  80 : myCircles( theVertices.Length(), new NCollection_IncAllocator() )
  81 {
  82   if ( theVertices.Length() > 2 )
  83   {
  84     myMeshData = new BRepMesh_DataStructureOfDelaun( new NCollection_IncAllocator(),
  85                                                      theVertices.Length() );
  86     Init( theVertices );
  87   }
  88 }
  89
  90 //=======================================================================
  91 //function : BRepMesh_Delaun
  92 //purpose  : Creates the triangulation with and existent Mesh data structure
  93 //=======================================================================
  94 BRepMesh_Delaun::BRepMesh_Delaun(
  95   const Handle( BRepMesh_DataStructureOfDelaun )& theOldMesh,
  96   BRepMesh::Array1OfVertexOfDelaun&               theVertices)
  97  : myCircles( theVertices.Length(), theOldMesh->Allocator() )
  98 {
  99   myMeshData = theOldMesh;
 100   if ( theVertices.Length() > 2 )
 101     Init( theVertices );
 102 }
 103
 104 //=======================================================================
 105 //function : BRepMesh_Delaun
 106 //purpose  : Creates the triangulation with and existent Mesh data structure
 107 //=======================================================================
 108 BRepMesh_Delaun::BRepMesh_Delaun(
 109   const Handle( BRepMesh_DataStructureOfDelaun )& theOldMesh,
 110   BRepMesh::Array1OfInteger&                      theVertexIndices)
 111  : myCircles( theVertexIndices.Length(), theOldMesh->Allocator() )
 112 {
 113   myMeshData = theOldMesh;
 114   if ( theVertexIndices.Length() > 2 )
 115   {
 116     Bnd_Box2d aBox;
 117     Standard_Integer anIndex = theVertexIndices.Lower();
 118     Standard_Integer anUpper = theVertexIndices.Upper();
 119     for ( ; anIndex <= anUpper; ++anIndex )
 120       aBox.Add( gp_Pnt2d( GetVertex( theVertexIndices( anIndex) ).Coord() ) );
 121
 122     perform( aBox, theVertexIndices );
 123   }
 124 }
 125
 126 //=======================================================================
 127 //function : Init
 128 //purpose  : Initializes the triangulation with an Array of Vertex
 129 //=======================================================================
 130 void BRepMesh_Delaun::Init(BRepMesh::Array1OfVertexOfDelaun& theVertices)
 131 {
 132   Bnd_Box2d aBox;
 133   Standard_Integer aLowerIdx  = theVertices.Lower();
 134   Standard_Integer anUpperIdx = theVertices.Upper();
 135   BRepMesh::Array1OfInteger aVertexIndexes( aLowerIdx, anUpperIdx );
 136
 137   Standard_Integer anIndex = aLowerIdx;
 138   for ( ; anIndex <= anUpperIdx; ++anIndex )
 139   {
 140     aBox.Add( gp_Pnt2d( theVertices( anIndex ).Coord() ) );
 141     aVertexIndexes( anIndex ) = myMeshData->AddNode( theVertices( anIndex ) );
 142   }
 143
 144   perform( aBox, aVertexIndexes );
 145 }
 146
 147 //=======================================================================
 148 //function : perform
 149 //purpose  : Create super mesh and run triangulation procedure
 150 //=======================================================================
 151 void BRepMesh_Delaun::perform(Bnd_Box2d&                 theBndBox,
 152                               BRepMesh::Array1OfInteger& theVertexIndexes)
 153 {
 154   theBndBox.Enlarge( Precision );
 155   superMesh( theBndBox );
 156
 157   ComparatorOfIndexedVertexOfDelaun aCmp(myMeshData);
 158   std::make_heap(theVertexIndexes.begin(), theVertexIndexes.end(), aCmp);
 159   std::sort_heap(theVertexIndexes.begin(), theVertexIndexes.end(), aCmp);
 160
 161   compute( theVertexIndexes );
 162 }
 163
 164 //=======================================================================
 165 //function : superMesh
 166 //purpose  : Build the super mesh
 167 //=======================================================================
 168 void BRepMesh_Delaun::superMesh( const Bnd_Box2d& theBox )
 169 {
 170   Standard_Real aMinX, aMinY, aMaxX, aMaxY;
 171   theBox.Get( aMinX, aMinY, aMaxX, aMaxY );
 172   Standard_Real aDeltaX = aMaxX - aMinX;
 173   Standard_Real aDeltaY = aMaxY - aMinY;
 174
 175   Standard_Real aDeltaMin = Min( aDeltaX, aDeltaY );
 176   Standard_Real aDeltaMax = Max( aDeltaX, aDeltaY );
 177   Standard_Real aDelta    = aDeltaX + aDeltaY;
 178
 179   myCircles.SetMinMaxSize( gp_XY( aMinX, aMinY ), gp_XY( aMaxX, aMaxY ) );
 180
 181   Standard_Integer aScaler = 2;
 182   if ( myMeshData->NbNodes() > 100 )
 183     aScaler = 5;
 184   else if( myMeshData->NbNodes() > 1000 )
 185     aScaler = 7;
 186
 187   myCircles.SetCellSize( aDeltaX / aScaler,
 188                          aDeltaY / aScaler );
 189
 190   mySupVert[0] = myMeshData->AddNode(
 191     BRepMesh_Vertex( ( aMinX + aMaxX ) / 2, aMaxY + aDeltaMax, BRepMesh_Free ) );
 192
 193   mySupVert[1] = myMeshData->AddNode(
 194     BRepMesh_Vertex( aMinX - aDelta, aMinY - aDeltaMin, BRepMesh_Free ) );
 195
 196   mySupVert[2] = myMeshData->AddNode(
 197     BRepMesh_Vertex( aMaxX + aDelta, aMinY - aDeltaMin, BRepMesh_Free ) );
 198
 199   Standard_Integer e[3];
 200   Standard_Boolean o[3];
 201   for (Standard_Integer aNodeId = 0; aNodeId < 3; ++aNodeId)
 202   {
 203     Standard_Integer aFirstNode = aNodeId;
 204     Standard_Integer aLastNode  = (aNodeId + 1) % 3;
 205     Standard_Integer aLinkIndex = myMeshData->AddLink( BRepMesh_Edge(
 206       mySupVert[aFirstNode], mySupVert[aLastNode], BRepMesh_Free ) );
 207
 208     e[aNodeId] = Abs(aLinkIndex);
 209     o[aNodeId] = (aLinkIndex > 0);
 210   }
 211
 212   mySupTrian = BRepMesh_Triangle(e, o, BRepMesh_Free);
 213 }
 214
 215 //=======================================================================
 216 //function : deleteTriangle
 217 //purpose  : Deletes the triangle with the given index and adds the free
 218 //           edges into the map.
 219 //           When an edge is suppressed more than one time it is destroyed.
 220 //=======================================================================
 221 void BRepMesh_Delaun::deleteTriangle(const Standard_Integer         theIndex,
 222                                      BRepMesh::MapOfIntegerInteger& theLoopEdges )
 223 {
 224   myCircles.Delete( theIndex );
 225
 226   Standard_Integer e[3];
 227   Standard_Boolean o[3];
 228   GetTriangle( theIndex ).Edges( e, o );
 229
 230   myMeshData->RemoveElement( theIndex );
 231
 232   for ( Standard_Integer i = 0; i < 3; ++i )
 233   {
 234     if ( !theLoopEdges.Bind( e[i], o[i] ) )
 235     {
 236       theLoopEdges.UnBind( e[i] );
 237       myMeshData->RemoveLink( e[i] );
 238     }
 239   }
 240 }
 241
 242 //=======================================================================
 243 //function : compute
 244 //purpose  : Computes the triangulation and add the vertices edges and
 245 //           triangles to the Mesh data structure
 246 //=======================================================================
 247 void BRepMesh_Delaun::compute(BRepMesh::Array1OfInteger& theVertexIndexes)
 248 {
 249   // Insertion of edges of super triangles in the list of free edges:
 250   BRepMesh::MapOfIntegerInteger aLoopEdges( 10, myMeshData->Allocator() );
 251   Standard_Integer e[3];
 252   Standard_Boolean o[3];
 253   mySupTrian.Edges( e, o );
 254
 255   aLoopEdges.Bind( e[0], Standard_True );
 256   aLoopEdges.Bind( e[1], Standard_True );
 257   aLoopEdges.Bind( e[2], Standard_True );
 258
 259   if ( theVertexIndexes.Length() > 0 )
 260   {
 261     // Creation of 3 trianglers with the first node and the edges of the super triangle:
 262     Standard_Integer anVertexIdx = theVertexIndexes.Lower();
 263     createTriangles( theVertexIndexes( anVertexIdx ), aLoopEdges );
 264
 265     // Add other nodes to the mesh
 266     createTrianglesOnNewVertices( theVertexIndexes );
 267   }
 268
 269   // Destruction of triangles containing a top of the super triangle
 270   BRepMesh_SelectorOfDataStructureOfDelaun aSelector( myMeshData );
 271   for (Standard_Integer aSupVertId = 0; aSupVertId < 3; ++aSupVertId)
 272     aSelector.NeighboursOfNode( mySupVert[aSupVertId] );
 273
 274   aLoopEdges.Clear();
 275   BRepMesh::MapOfInteger::Iterator aFreeTriangles( aSelector.Elements() );
 276   for ( ; aFreeTriangles.More(); aFreeTriangles.Next() )
 277     deleteTriangle( aFreeTriangles.Key(), aLoopEdges );
 278
 279   // All edges that remain free are removed from aLoopEdges;
 280   // only the boundary edges of the triangulation remain there
 281   BRepMesh::MapOfIntegerInteger::Iterator aFreeEdges( aLoopEdges );
 282   for ( ; aFreeEdges.More(); aFreeEdges.Next() )
 283   {
 284     if ( myMeshData->ElementsConnectedTo( aFreeEdges.Key() ).IsEmpty() )
 285       myMeshData->RemoveLink( aFreeEdges.Key() );
 286   }
 287
 288   // The tops of the super triangle are destroyed
 289   for (Standard_Integer aSupVertId = 0; aSupVertId < 3; ++aSupVertId)
 290     myMeshData->RemoveNode( mySupVert[aSupVertId] );
 291 }
 292
 293 //=======================================================================
 294 //function : createTriangles
 295 //purpose  : Creates the triangles beetween the node and the polyline.
 296 //=======================================================================
 297 void BRepMesh_Delaun::createTriangles(const Standard_Integer         theVertexIndex,
 298                                       BRepMesh::MapOfIntegerInteger& thePoly)
 299 {
 300   BRepMesh::ListOfInteger aLoopEdges, anExternalEdges;
 301   const gp_XY& aVertexCoord = myMeshData->GetNode( theVertexIndex ).Coord();
 302
 303   BRepMesh::MapOfIntegerInteger::Iterator anEdges( thePoly );
 304   for ( ; anEdges.More(); anEdges.Next() )
 305   {
 306     Standard_Integer     anEdgeId = anEdges.Key();
 307     const BRepMesh_Edge& anEdge   = GetEdge( anEdgeId );
 308
 309     Standard_Boolean isPositive = (Standard_Boolean)thePoly( anEdgeId );
 310
 311     Standard_Integer aNodes[3];
 312     if ( isPositive )
 313     {
 314       aNodes[0] = anEdge.FirstNode();
 315       aNodes[2] = anEdge.LastNode();
 316     }
 317     else
 318     {
 319       aNodes[0] = anEdge.LastNode();
 320       aNodes[2] = anEdge.FirstNode();
 321     }
 322     aNodes[1] = theVertexIndex;
 323
 324     const BRepMesh_Vertex& aFirstVertex = GetVertex( aNodes[0] );
 325     const BRepMesh_Vertex& aLastVertex  = GetVertex( aNodes[2] );
 326
 327     gp_XY anEdgeDir( aLastVertex.Coord() - aFirstVertex.Coord() );
 328     Standard_Real anEdgeLen = anEdgeDir.Modulus();
 329     if ( anEdgeLen < Precision )
 330       continue;
 331
 332     anEdgeDir.SetCoord( anEdgeDir.X() / anEdgeLen,
 333                         anEdgeDir.Y() / anEdgeLen );
 334
 335     gp_XY aFirstLinkDir( aFirstVertex.Coord() - aVertexCoord );
 336     gp_XY aLastLinkDir ( aVertexCoord         - aLastVertex.Coord() );
 337
 338     Standard_Real aDist12 = aFirstLinkDir ^ anEdgeDir;
 339     Standard_Real aDist23 = anEdgeDir     ^ aLastLinkDir;
 340     if ( Abs( aDist12 ) < Precision ||
 341          Abs( aDist23 ) < Precision )
 342     {
 343       continue;
 344     }
 345
 346     BRepMesh_Edge aFirstLink( aNodes[1], aNodes[0], BRepMesh_Free );
 347     BRepMesh_Edge aLastLink ( aNodes[2], aNodes[1], BRepMesh_Free );
 348
 349     Standard_Integer anEdgesInfo[3] = {
 350       myMeshData->AddLink( aFirstLink ),
 351       isPositive ? anEdgeId : -anEdgeId,
 352       myMeshData->AddLink( aLastLink ) };
 353
 354     Standard_Boolean isSensOK = (aDist12 > 0. && aDist23 > 0.);
 355     if (isSensOK)
 356     {
 357       Standard_Integer anEdges[3];
 358       Standard_Boolean anEdgesOri[3];
 359       for ( Standard_Integer aTriLinkIt = 0; aTriLinkIt < 3; ++aTriLinkIt )
 360       {
 361         const Standard_Integer& anEdgeInfo = anEdgesInfo[aTriLinkIt];
 362         anEdges[aTriLinkIt]    = Abs( anEdgeInfo );
 363         anEdgesOri[aTriLinkIt] = anEdgeInfo > 0;
 364       }
 365
 366       addTriangle( anEdges, anEdgesOri, aNodes );
 367     }
 368     else
 369     {
 370       if ( isPositive )
 371         aLoopEdges.Append(  anEdges.Key() );
 372       else
 373         aLoopEdges.Append( -anEdges.Key() );
 374
 375       if ( aFirstLinkDir.SquareModulus() > aLastLinkDir.SquareModulus() )
 376         anExternalEdges.Append( Abs( anEdgesInfo[0] ) );
 377       else
 378         anExternalEdges.Append( Abs( anEdgesInfo[2] ) );
 379     }
 380   }
 381
 382   thePoly.Clear();
 383   while ( !anExternalEdges.IsEmpty() )
 384   {
 385     const BRepMesh_PairOfIndex& aPair =
 386       myMeshData->ElementsConnectedTo( Abs( anExternalEdges.First() ) );
 387
 388
 389     if ( !aPair.IsEmpty() )
 390       deleteTriangle( aPair.FirstIndex(), thePoly );
 391
 392     anExternalEdges.RemoveFirst();
 393   }
 394
 395   for ( anEdges.Initialize( thePoly ); anEdges.More(); anEdges.Next() )
 396   {
 397     if ( myMeshData->ElementsConnectedTo( anEdges.Key() ).IsEmpty() )
 398       myMeshData->RemoveLink( anEdges.Key() );
 399   }
 400
 401   while ( !aLoopEdges.IsEmpty() )
 402   {
 403     const BRepMesh_Edge& anEdge = GetEdge( Abs( aLoopEdges.First() ) );
 404     if ( anEdge.Movability() != BRepMesh_Deleted )
 405     {
 406       Standard_Integer anEdgeIdx = aLoopEdges.First();
 407       meshLeftPolygonOf( Abs( anEdgeIdx ), ( anEdgeIdx > 0 ) );
 408     }
 409
 410     aLoopEdges.RemoveFirst();
 411   }
 412 }
 413
 414 //=======================================================================
 415 //function : createTrianglesOnNewVertices
 416 //purpose  : Creation of triangles from the new nodes
 417 //=======================================================================
 418 void BRepMesh_Delaun::createTrianglesOnNewVertices(
 419   BRepMesh::Array1OfInteger& theVertexIndexes)
 420 {
 421   BRepMesh::MapOfIntegerInteger aLoopEdges( 10, myMeshData->Allocator() );
 422
 423   // Insertion of nodes :
 424   Standard_Boolean isModify = Standard_True;
 425
 426   Standard_Integer anIndex = theVertexIndexes.Lower();
 427   Standard_Integer anUpper = theVertexIndexes.Upper();
 428   for( ; anIndex <= anUpper; ++anIndex )
 429   {
 430     aLoopEdges.Clear();
 431
 432     Standard_Integer aVertexIdx = theVertexIndexes( anIndex );
 433     const BRepMesh_Vertex& aVertex = GetVertex( aVertexIdx );
 434
 435     // Iterator in the list of indexes of circles containing the node
 436     BRepMesh::ListOfInteger& aCirclesList = myCircles.Select( aVertex.Coord() );
 437
 438     Standard_Integer onEgdeId = 0, aTriangleId = 0;
 439     BRepMesh::ListOfInteger::Iterator aCircleIt( aCirclesList );
 440     for ( ; aCircleIt.More(); aCircleIt.Next() )
 441     {
 442       // To add a node in the mesh it is necessary to check conditions:
 443       // - the node should be within the boundaries of the mesh and so in an existing triangle
 444       // - all adjacent triangles should belong to a component connected with this triangle
 445       if ( Contains( aCircleIt.Value(), aVertex, onEgdeId ) )
 446       {
 447         if ( onEgdeId == 0 )
 448         {
 449           aTriangleId = aCircleIt.Value();
 450           aCirclesList.Remove( aCircleIt );
 451           break;
 452         }
 453         else if ( GetEdge( onEgdeId ).Movability() == BRepMesh_Free )
 454         {
 455           aTriangleId = aCircleIt.Value();
 456           aCirclesList.Remove( aCircleIt );
 457           break;
 458         }
 459       }
 460     }
 461
 462     if ( aTriangleId > 0 )
 463     {
 464       deleteTriangle( aTriangleId, aLoopEdges );
 465
 466       isModify = Standard_True;
 467       while ( isModify && !aCirclesList.IsEmpty() )
 468       {
 469         isModify = Standard_False;
 470         BRepMesh::ListOfInteger::Iterator aCircleIt1( aCirclesList );
 471         for ( ; aCircleIt1.More(); aCircleIt1.Next() )
 472         {
 473           Standard_Integer e[3];
 474           Standard_Boolean o[3];
 475           GetTriangle( aCircleIt1.Value() ).Edges( e, o );
 476
 477           if ( aLoopEdges.IsBound( e[0] ) ||
 478                aLoopEdges.IsBound( e[1] ) ||
 479                aLoopEdges.IsBound( e[2] ) )
 480           {
 481             isModify = Standard_True;
 482             deleteTriangle( aCircleIt1.Value(), aLoopEdges );
 483             aCirclesList.Remove( aCircleIt1 );
 484             break;
 485           }
 486         }
 487       }
 488
 489       // Creation of triangles with the current node and free edges
 490       // and removal of these edges from the list of free edges
 491       createTriangles( aVertexIdx, aLoopEdges );
 492     }
 493   }
 494   // Check that internal edges are not crossed by triangles
 495   BRepMesh::HMapOfInteger anInternalEdges = InternalEdges();
 496
 497   // Destruction of triancles intersecting internal edges
 498   // and their replacement by makeshift triangles
 499   BRepMesh::MapOfInteger::Iterator anInernalEdgesIt( *anInternalEdges );
 500   for ( ; anInernalEdgesIt.More(); anInernalEdgesIt.Next() )
 501   {
 502     Standard_Integer aNbC;
 503     aNbC = myMeshData->ElementsConnectedTo( anInernalEdgesIt.Key() ).Extent();
 504     if ( aNbC == 0 )
 505     {
 506       meshLeftPolygonOf( anInernalEdgesIt.Key(), Standard_True  );
 507       meshLeftPolygonOf( anInernalEdgesIt.Key(), Standard_False );
 508     }
 509   }
 510
 511   // Adjustment of meshes to boundary edges
 512   frontierAdjust();
 513 }
 514
 515 //=======================================================================
 516 //function : isBoundToFrontier
 517 //purpose  : Goes through the neighbour triangles around the given node
 518 //           started from the given link, returns TRUE if some triangle
 519 //           has a bounding frontier edge or FALSE elsewhere.
 520 //           Stop link is used to prevent cycles.
 521 //           Previous element Id is used to identify next neighbor element.
 522 //=======================================================================
 523 Standard_Boolean BRepMesh_Delaun::isBoundToFrontier(
 524   const Standard_Integer theRefNodeId,
 525   const Standard_Integer theRefLinkId,
 526   const Standard_Integer theStopLinkId,
 527   const Standard_Integer thePrevElementId)
 528 {
 529   const BRepMesh_PairOfIndex& aPair =
 530     myMeshData->ElementsConnectedTo( theRefLinkId );
 531   if ( aPair.IsEmpty() )
 532     return Standard_False;
 533
 534   Standard_Integer aNbElements = aPair.Extent();
 535   for ( Standard_Integer anElemIt = 1; anElemIt <= aNbElements; ++anElemIt )
 536   {
 537     const Standard_Integer aTriId = aPair.Index(anElemIt);
 538     if ( aTriId < 0 || aTriId == thePrevElementId )
 539       continue;
 540
 541     Standard_Integer anEdges[3];
 542     Standard_Boolean anEdgesOri[3];
 543     GetTriangle( aTriId ).Edges( anEdges, anEdgesOri );
 544
 545     for ( Standard_Integer anEdgeIt = 0; anEdgeIt < 3; ++anEdgeIt )
 546     {
 547       const Standard_Integer anEdgeId = anEdges[anEdgeIt];
 548       if ( anEdgeId == theRefLinkId )
 549         continue;
 550
 551       if ( anEdgeId == theStopLinkId )
 552         return Standard_False;
 553
 554       const BRepMesh_Edge& anEdge = GetEdge( anEdgeId );
 555       if ( anEdge.FirstNode() != theRefNodeId &&
 556            anEdge.LastNode()  != theRefNodeId )
 557       {
 558         continue;
 559       }
 560
 561       if ( anEdge.Movability() != BRepMesh_Free )
 562         return Standard_True;
 563
 564       return isBoundToFrontier( theRefNodeId, anEdgeId, theStopLinkId, aTriId );
 565     }
 566   }
 567
 568   return Standard_False;
 569 }
 570
 571 //=======================================================================
 572 //function : cleanupMesh
 573 //purpose  : Cleanup mesh from the free triangles
 574 //=======================================================================
 575 void BRepMesh_Delaun::cleanupMesh()
 576 {
 577   for(;;)
 578   {
 579     BRepMesh::MapOfIntegerInteger aLoopEdges( 10, myMeshData->Allocator() );
 580     BRepMesh::MapOfInteger aDelTriangles;
 581
 582     BRepMesh::HMapOfInteger aFreeEdges = FreeEdges();
 583     BRepMesh::MapOfInteger::Iterator aFreeEdgesIt( *aFreeEdges );
 584     for ( ; aFreeEdgesIt.More(); aFreeEdgesIt.Next() )
 585     {
 586       const Standard_Integer& aFreeEdgeId = aFreeEdgesIt.Key();
 587       const BRepMesh_Edge&    anEdge      = GetEdge( aFreeEdgeId );
 588       if ( anEdge.Movability() == BRepMesh_Frontier )
 589         continue;
 590
 591       const BRepMesh_PairOfIndex& aPair =
 592         myMeshData->ElementsConnectedTo( aFreeEdgeId );
 593       if ( aPair.IsEmpty() )
 594       {
 595         aLoopEdges.Bind( aFreeEdgeId, Standard_True );
 596         continue;
 597       }
 598
 599       Standard_Integer aTriId = aPair.FirstIndex();
 600
 601       // Check that the connected triangle is not surrounded by another triangles
 602       Standard_Integer anEdges[3];
 603       Standard_Boolean anEdgesOri[3];
 604       GetTriangle( aTriId ).Edges( anEdges, anEdgesOri );
 605
 606       Standard_Boolean isCanNotBeRemoved = Standard_True;
 607       for ( Standard_Integer aCurEdgeIdx = 0; aCurEdgeIdx < 3; ++aCurEdgeIdx )
 608       {
 609         if ( anEdges[aCurEdgeIdx] != aFreeEdgeId )
 610           continue;
 611
 612         for ( Standard_Integer anOtherEdgeIt = 1; anOtherEdgeIt <= 2; ++anOtherEdgeIt )
 613         {
 614           Standard_Integer anOtherEdgeId = ( aCurEdgeIdx + anOtherEdgeIt ) % 3;
 615           const BRepMesh_PairOfIndex& anOtherEdgePair =
 616             myMeshData->ElementsConnectedTo( anEdges[anOtherEdgeId] );
 617
 618           if ( anOtherEdgePair.Extent() < 2 )
 619           {
 620             isCanNotBeRemoved = Standard_False;
 621             break;
 622           }
 623         }
 624
 625         break;
 626       }
 627
 628       if ( isCanNotBeRemoved )
 629         continue;
 630
 631       Standard_Boolean isConnected[2] = { Standard_False, Standard_False };
 632       for ( Standard_Integer aLinkNodeIt = 0; aLinkNodeIt < 2; ++aLinkNodeIt )
 633       {
 634         isConnected[aLinkNodeIt] = isBoundToFrontier( ( aLinkNodeIt == 0 ) ?
 635           anEdge.FirstNode() : anEdge.LastNode(),
 636           aFreeEdgeId, aFreeEdgeId, -1);
 637       }
 638
 639       if ( !isConnected[0] || !isConnected[1] )
 640         aDelTriangles.Add( aTriId );
 641     }
 642
 643     // Destruction of triangles :
 644     Standard_Integer aDeletedTrianglesNb = 0;
 645     BRepMesh::MapOfInteger::Iterator aDelTrianglesIt( aDelTriangles );
 646     for ( ; aDelTrianglesIt.More(); aDelTrianglesIt.Next() )
 647     {
 648       deleteTriangle( aDelTrianglesIt.Key(), aLoopEdges );
 649       aDeletedTrianglesNb++;
 650     }
 651
 652     // Destruction of remaining hanging edges
 653     BRepMesh::MapOfIntegerInteger::Iterator aLoopEdgesIt( aLoopEdges );
 654     for ( ; aLoopEdgesIt.More(); aLoopEdgesIt.Next() )
 655     {
 656       if ( myMeshData->ElementsConnectedTo( aLoopEdgesIt.Key() ).IsEmpty() )
 657         myMeshData->RemoveLink( aLoopEdgesIt.Key() );
 658     }
 659
 660     if ( aDeletedTrianglesNb == 0 )
 661       break;
 662   }
 663 }
 664
 665 //=======================================================================
 666 //function : frontierAdjust
 667 //purpose  : Adjust the mesh on the frontier
 668 //=======================================================================
 669 void BRepMesh_Delaun::frontierAdjust()
 670 {
 671   BRepMesh::HMapOfInteger        aFrontier = Frontier();
 672   BRepMesh::VectorOfInteger      aFailedFrontiers;
 673   BRepMesh::MapOfIntegerInteger  aLoopEdges( 10, myMeshData->Allocator() );
 674   BRepMesh::HMapOfInteger        aIntFrontierEdges = new BRepMesh::MapOfInteger;
 675   for ( Standard_Integer aPass = 1; aPass <= 2; ++aPass )
 676   {
 677     // 1 pass): find external triangles on boundary edges;
 678     // 2 pass): find external triangles on boundary edges appeared
 679     //          during triangles replacement.
 680
 681     BRepMesh::MapOfInteger::Iterator aFrontierIt( *aFrontier );
 682     for ( ; aFrontierIt.More(); aFrontierIt.Next() )
 683     {
 684       Standard_Integer aFrontierId = aFrontierIt.Key();
 685       const BRepMesh_PairOfIndex& aPair = myMeshData->ElementsConnectedTo( aFrontierId );
 686       Standard_Integer aNbElem = aPair.Extent();
 687       for( Standard_Integer aElemIt = 1; aElemIt <= aNbElem; ++aElemIt )
 688       {
 689         const Standard_Integer aPriorElemId = aPair.Index( aElemIt );
 690         if( aPriorElemId < 0 )
 691           continue;
 692
 693         Standard_Integer e[3];
 694         Standard_Boolean o[3];
 695         GetTriangle( aPriorElemId ).Edges( e, o );
 696
 697         Standard_Boolean isTriangleFound = Standard_False;
 698         for ( Standard_Integer n = 0; n < 3; ++n )
 699         {
 700           if ( aFrontierId == e[n] && !o[n] )
 701           {
 702             // Destruction  of external triangles on boundary edges
 703             isTriangleFound = Standard_True;
 704             deleteTriangle( aPriorElemId, aLoopEdges );
 705             break;
 706           }
 707         }
 708
 709         if ( isTriangleFound )
 710           break;
 711       }
 712     }
 713
 714     // destrucrion of remaining hanging edges :
 715     BRepMesh::MapOfIntegerInteger::Iterator aLoopEdgesIt( aLoopEdges );
 716     for ( ; aLoopEdgesIt.More(); aLoopEdgesIt.Next() )
 717     {
 718       Standard_Integer aLoopEdgeId = aLoopEdgesIt.Key();
 719       if (myMeshData->ElementsConnectedTo( aLoopEdgeId ).IsEmpty() )
 720         myMeshData->RemoveLink( aLoopEdgeId );
 721     }
 722
 723     // destruction of triangles crossing the boundary edges and
 724     // their replacement by makeshift triangles
 725     for ( aFrontierIt.Reset(); aFrontierIt.More(); aFrontierIt.Next() )
 726     {
 727       Standard_Integer aFrontierId = aFrontierIt.Key();
 728       if ( !myMeshData->ElementsConnectedTo( aFrontierId ).IsEmpty() )
 729         continue;
 730
 731       Standard_Boolean isSuccess =
 732         meshLeftPolygonOf( aFrontierId, Standard_True, aIntFrontierEdges );
 733
 734       if ( aPass == 2 && !isSuccess )
 735         aFailedFrontiers.Append( aFrontierId );
 736     }
 737   }
 738
 739   cleanupMesh();
 740
 741   // When the mesh has been cleaned up, try to process frontier edges
 742   // once again to fill the possible gaps that might be occured in case of "saw" -
 743   // situation when frontier edge has a triangle at a right side, but its free
 744   // links cross another frontieres  and meshLeftPolygonOf itself can't collect
 745   // a closed polygon.
 746   BRepMesh::VectorOfInteger::Iterator aFailedFrontiersIt( aFailedFrontiers );
 747   for ( ; aFailedFrontiersIt.More(); aFailedFrontiersIt.Next() )
 748   {
 749     Standard_Integer aFrontierId = aFailedFrontiersIt.Value();
 750     if ( !myMeshData->ElementsConnectedTo( aFrontierId ).IsEmpty() )
 751       continue;
 752
 753     meshLeftPolygonOf( aFrontierId, Standard_True, aIntFrontierEdges );
 754   }
 755 }
 756
 757 //=======================================================================
 758 //function : fillBndBox
 759 //purpose  : Add boundig box for edge defined by start & end point to
 760 //           the given vector of bounding boxes for triangulation edges
 761 //=======================================================================
 762 void BRepMesh_Delaun::fillBndBox(BRepMesh::SequenceOfBndB2d& theBoxes,
 763                                  const BRepMesh_Vertex&      theV1,
 764                                  const BRepMesh_Vertex&      theV2)
 765 {
 766   Bnd_B2d aBox;
 767   aBox.Add( theV1.Coord() );
 768   aBox.Add( theV2.Coord() );
 769   theBoxes.Append( aBox );
 770 }
 771
 772 //=======================================================================
 773 //function : meshLeftPolygonOf
 774 //purpose  : Collect the polygon at the left of the given edge (material side)
 775 //=======================================================================
 776 Standard_Boolean BRepMesh_Delaun::meshLeftPolygonOf(
 777   const Standard_Integer  theStartEdgeId,
 778   const Standard_Boolean  isForward,
 779   BRepMesh::HMapOfInteger theSkipped )
 780 {
 781   if ( !theSkipped.IsNull() && theSkipped->Contains( theStartEdgeId ) )
 782     return Standard_True;
 783
 784   const BRepMesh_Edge& aRefEdge = GetEdge( theStartEdgeId );
 785
 786   BRepMesh::SequenceOfInteger aPolygon;
 787   Standard_Integer aStartNode, aPivotNode;
 788   if ( isForward )
 789   {
 790     aPolygon.Append( theStartEdgeId );
 791     aStartNode = aRefEdge.FirstNode();
 792     aPivotNode = aRefEdge.LastNode();
 793   }
 794   else
 795   {
 796     aPolygon.Append( -theStartEdgeId );
 797     aStartNode = aRefEdge.LastNode();
 798     aPivotNode = aRefEdge.FirstNode();
 799   }
 800
 801
 802   const BRepMesh_Vertex& aStartEdgeVertexS = GetVertex( aStartNode );
 803   BRepMesh_Vertex        aPivotVertex      = GetVertex( aPivotNode );
 804
 805   gp_Vec2d aRefLinkDir( aPivotVertex.Coord() -
 806     aStartEdgeVertexS.Coord() );
 807
 808   if ( aRefLinkDir.SquareMagnitude() < Precision2 )
 809     return Standard_True;
 810
 811   // Auxilary structures.
 812   // Bounding boxes of polygon links to be used for preliminary
 813   // analysis of intersections
 814   BRepMesh::SequenceOfBndB2d aBoxes;
 815   fillBndBox( aBoxes, aStartEdgeVertexS, aPivotVertex );
 816
 817   // Hanging ends
 818   BRepMesh::MapOfInteger aDeadLinks;
 819
 820   // Links are temporarily excluded from consideration
 821   BRepMesh::MapOfInteger aLeprousLinks;
 822   aLeprousLinks.Add( theStartEdgeId );
 823
 824   Standard_Boolean isSkipLeprous = Standard_True;
 825   Standard_Integer aFirstNode    = aStartNode;
 826   while ( aPivotNode != aFirstNode )
 827   {
 828     Bnd_B2d          aNextLinkBndBox;
 829     gp_Vec2d         aNextLinkDir;
 830     Standard_Integer aNextPivotNode = 0;
 831
 832     Standard_Integer aNextLinkId = findNextPolygonLink(
 833       aFirstNode,
 834       aPivotNode,     aPivotVertex,  aRefLinkDir,
 835       aBoxes,         aPolygon,      theSkipped,
 836       isSkipLeprous,  aLeprousLinks, aDeadLinks,
 837       aNextPivotNode, aNextLinkDir,  aNextLinkBndBox );
 838
 839     if ( aNextLinkId != 0 )
 840     {
 841       aStartNode   = aPivotNode;
 842       aRefLinkDir  = aNextLinkDir;
 843
 844       aPivotNode   = aNextPivotNode;
 845       aPivotVertex = GetVertex( aNextPivotNode );
 846
 847       aBoxes.Append  ( aNextLinkBndBox );
 848       aPolygon.Append( aNextLinkId );
 849
 850       isSkipLeprous = Standard_True;
 851     }
 852     else
 853     {
 854       // Nothing to do
 855       if ( aPolygon.Length() == 1 )
 856         return Standard_False;
 857
 858       // Return to the previous point
 859       Standard_Integer aDeadLinkId = Abs( aPolygon.Last() );
 860       aDeadLinks.Add      ( aDeadLinkId );
 861
 862       aLeprousLinks.Remove( aDeadLinkId );
 863       aPolygon.Remove     ( aPolygon.Length() );
 864       aBoxes.Remove       ( aBoxes.Length() );
 865
 866       Standard_Integer aPrevLinkInfo = aPolygon.Last();
 867       const BRepMesh_Edge& aPrevLink = GetEdge( Abs( aPrevLinkInfo ) );
 868
 869       if( aPrevLinkInfo > 0 )
 870       {
 871         aStartNode = aPrevLink.FirstNode();
 872         aPivotNode = aPrevLink.LastNode();
 873       }
 874       else
 875       {
 876         aStartNode = aPrevLink.LastNode();
 877         aPivotNode = aPrevLink.FirstNode();
 878       }
 879
 880       aPivotVertex = GetVertex( aPivotNode );
 881       aRefLinkDir =
 882         aPivotVertex.Coord() - GetVertex( aStartNode ).Coord();
 883
 884       isSkipLeprous = Standard_False;
 885     }
 886   }
 887
 888   if ( aPolygon.Length() < 3 )
 889     return Standard_False;
 890
 891   cleanupPolygon( aPolygon, aBoxes );
 892   meshPolygon   ( aPolygon, aBoxes, theSkipped );
 893
 894   return Standard_True;
 895 }
 896
 897 //=======================================================================
 898 //function : findNextPolygonLink
 899 //purpose  : Find next link starting from the given node and has maximum
 900 //           angle respect the given reference link.
 901 //           Each time the next link is found other neighbor links at the
 902 //           pivot node are marked as leprous and will be excluded from
 903 //           consideration next time until a hanging end is occured.
 904 //=======================================================================
 905 Standard_Integer BRepMesh_Delaun::findNextPolygonLink(
 906   const Standard_Integer&            theFirstNode,
 907   const Standard_Integer&            thePivotNode,
 908   const BRepMesh_Vertex&             thePivotVertex,
 909   const gp_Vec2d&                    theRefLinkDir,
 910   const BRepMesh::SequenceOfBndB2d&  theBoxes,
 911   const BRepMesh::SequenceOfInteger& thePolygon,
 912   const BRepMesh::HMapOfInteger      theSkipped,
 913   const Standard_Boolean&            isSkipLeprous,
 914   BRepMesh::MapOfInteger&            theLeprousLinks,
 915   BRepMesh::MapOfInteger&            theDeadLinks,
 916   Standard_Integer&                  theNextPivotNode,
 917   gp_Vec2d&                          theNextLinkDir,
 918   Bnd_B2d&                           theNextLinkBndBox )
 919 {
 920   // Find the next link having the greatest angle
 921   // respect to a direction of a reference one
 922   Standard_Real aMaxAngle = RealFirst();
 923
 924   Standard_Integer aNextLinkId = 0;
 925   BRepMesh::ListOfInteger::Iterator aLinkIt( myMeshData->LinksConnectedTo( thePivotNode ) );
 926   for ( ; aLinkIt.More(); aLinkIt.Next() )
 927   {
 928     const Standard_Integer& aNeighbourLinkInfo = aLinkIt.Value();
 929     Standard_Integer        aNeighbourLinkId   = Abs( aNeighbourLinkInfo );
 930
 931     if ( theDeadLinks.Contains( aNeighbourLinkId ) ||
 932        ( !theSkipped.IsNull() && theSkipped->Contains( aNeighbourLinkId ) ) )
 933     {
 934       continue;
 935     }
 936
 937     Standard_Boolean isLeprous = theLeprousLinks.Contains( aNeighbourLinkId );
 938     if ( isSkipLeprous && isLeprous )
 939       continue;
 940
 941     const BRepMesh_Edge& aNeighbourLink = GetEdge( aNeighbourLinkId );
 942
 943     // Determine whether the link belongs to the mesh
 944     if ( aNeighbourLink.Movability() == BRepMesh_Free &&
 945          myMeshData->ElementsConnectedTo( aNeighbourLinkInfo ).IsEmpty() )
 946     {
 947       theDeadLinks.Add( aNeighbourLinkId );
 948       continue;
 949     }
 950
 951     Standard_Integer anOtherNode = aNeighbourLink.FirstNode();
 952     if ( anOtherNode == thePivotNode )
 953       anOtherNode = aNeighbourLink.LastNode();
 954
 955     gp_Vec2d aCurLinkDir( GetVertex( anOtherNode ).Coord() -
 956       thePivotVertex.Coord() );
 957
 958     if ( aCurLinkDir.SquareMagnitude() < Precision2 )
 959     {
 960       theDeadLinks.Add( aNeighbourLinkId );
 961       continue;
 962     }
 963
 964     if ( !isLeprous )
 965       theLeprousLinks.Add( aNeighbourLinkId );
 966
 967     Standard_Real    anAngle    = theRefLinkDir.Angle( aCurLinkDir );
 968     Standard_Boolean isFrontier =
 969       ( aNeighbourLink.Movability() == BRepMesh_Frontier );
 970
 971     Standard_Boolean isCheckPointOnEdge = Standard_True;
 972     if ( isFrontier )
 973     {
 974       if ( Abs( Abs(anAngle) - M_PI ) < Precision::Angular() )
 975       {
 976         // Glued constrains - don't check intersection
 977         isCheckPointOnEdge = Standard_False;
 978         anAngle            = Abs( anAngle );
 979       }
 980     }
 981
 982     if (anAngle <= aMaxAngle)
 983       continue;
 984
 985     Standard_Boolean isCheckEndPoints = ( anOtherNode != theFirstNode );
 986
 987     Bnd_B2d aBox;
 988     Standard_Boolean isNotIntersect =
 989       checkIntersection( aNeighbourLink, thePolygon, theBoxes,
 990       isCheckEndPoints, isCheckPointOnEdge, Standard_True, aBox );
 991
 992     if( isNotIntersect )
 993     {
 994       aMaxAngle         = anAngle;
 995
 996       theNextLinkDir    = aCurLinkDir;
 997       theNextPivotNode  = anOtherNode;
 998       theNextLinkBndBox = aBox;
 999
1000       aNextLinkId       = ( aNeighbourLink.FirstNode() == thePivotNode ) ?
1001         aNeighbourLinkId : -aNeighbourLinkId;
1002     }
1003   }
1004
1005   return aNextLinkId;
1006 }
1007
1008 //=======================================================================
1009 //function : checkIntersection
1010 //purpose  : Check is the given link intersects the polygon boundaries.
1011 //           Returns bounding box for the given link trough the
1012 //           <theLinkBndBox> parameter.
1013 //=======================================================================
1014 Standard_Boolean BRepMesh_Delaun::checkIntersection(
1015   const BRepMesh_Edge&               theLink,
1016   const BRepMesh::SequenceOfInteger& thePolygon,
1017   const BRepMesh::SequenceOfBndB2d&  thePolyBoxes,
1018   const Standard_Boolean             isConsiderEndPointTouch,
1019   const Standard_Boolean             isConsiderPointOnEdge,
1020   const Standard_Boolean             isSkipLastEdge,
1021   Bnd_B2d&                           theLinkBndBox ) const
1022 {
1023   theLinkBndBox.Add( GetVertex( theLink.FirstNode() ).Coord() );
1024   theLinkBndBox.Add( GetVertex( theLink.LastNode()  ).Coord() );
1025
1026   Standard_Integer aPolyLen = thePolygon.Length();
1027   // Don't check intersection with the last link
1028   if ( isSkipLastEdge )
1029     --aPolyLen;
1030
1031   Standard_Boolean isFrontier =
1032     ( theLink.Movability() == BRepMesh_Frontier );
1033
1034   for ( Standard_Integer aPolyIt = 1; aPolyIt <= aPolyLen; ++aPolyIt )
1035   {
1036     if ( !theLinkBndBox.IsOut( thePolyBoxes.Value( aPolyIt ) ) )
1037     {
1038       // intersection is possible...
1039       Standard_Integer aPolyLinkId   = Abs( thePolygon( aPolyIt ) );
1040       const BRepMesh_Edge& aPolyLink = GetEdge( aPolyLinkId );
1041
1042       // skip intersections between frontier edges
1043       if ( aPolyLink.Movability() == BRepMesh_Frontier && isFrontier )
1044         continue;
1045
1046       gp_Pnt2d anIntPnt;
1047       BRepMesh_GeomTool::IntFlag aIntFlag = intSegSeg( theLink, aPolyLink,
1048         isConsiderEndPointTouch, isConsiderPointOnEdge, anIntPnt );
1049
1050       if ( aIntFlag != BRepMesh_GeomTool::NoIntersection )
1051         return Standard_False;
1052     }
1053   }
1054
1055   // Ok, no intersection
1056   return Standard_True;
1057 }
1058
1059 //=======================================================================
1060 //function : addTriangle
1061 //purpose  : Add a triangle based on the given oriented edges into mesh
1062 //=======================================================================
1063 inline void BRepMesh_Delaun::addTriangle( const Standard_Integer (&theEdgesId)[3],
1064                                           const Standard_Boolean (&theEdgesOri)[3],
1065                                           const Standard_Integer (&theNodesId)[3] )
1066 {
1067   Standard_Integer aNewTriangleId =
1068     myMeshData->AddElement(BRepMesh_Triangle(theEdgesId,
1069       theEdgesOri, BRepMesh_Free));
1070
1071   Standard_Boolean isAdded = myCircles.Bind(
1072     aNewTriangleId,
1073     GetVertex( theNodesId[0] ).Coord(),
1074     GetVertex( theNodesId[1] ).Coord(),
1075     GetVertex( theNodesId[2] ).Coord() );
1076
1077   if ( !isAdded )
1078     myMeshData->RemoveElement( aNewTriangleId );
1079 }
1080
1081 //=======================================================================
1082 //function : cleanupPolygon
1083 //purpose  : Remove internal triangles from the given polygon
1084 //=======================================================================
1085 void BRepMesh_Delaun::cleanupPolygon(const BRepMesh::SequenceOfInteger& thePolygon,
1086                                      const BRepMesh::SequenceOfBndB2d&  thePolyBoxes )
1087 {
1088   Standard_Integer aPolyLen = thePolygon.Length();
1089   if ( aPolyLen < 3 )
1090     return;
1091
1092   BRepMesh::MapOfIntegerInteger aLoopEdges( 10, myMeshData->Allocator() );
1093   BRepMesh::MapOfInteger    anIgnoredEdges;
1094   BRepMesh::MapOfInteger    aPolyVerticesFindMap;
1095   BRepMesh::VectorOfInteger aPolyVertices;
1096   // Collect boundary vertices of the polygon
1097   for ( Standard_Integer aPolyIt = 1; aPolyIt <= aPolyLen; ++aPolyIt )
1098   {
1099     Standard_Integer aPolyEdgeInfo = thePolygon( aPolyIt );
1100     Standard_Integer aPolyEdgeId   = Abs( aPolyEdgeInfo );
1101     anIgnoredEdges.Add( aPolyEdgeId );
1102
1103     Standard_Boolean isForward = ( aPolyEdgeInfo > 0 );
1104     const BRepMesh_PairOfIndex& aPair =
1105       myMeshData->ElementsConnectedTo( aPolyEdgeId );
1106
1107     Standard_Integer anElemIt = 1;
1108     for ( ; anElemIt <= aPair.Extent(); ++anElemIt )
1109     {
1110       Standard_Integer anElemId = aPair.Index( anElemIt );
1111       if ( anElemId < 0 )
1112         continue;
1113
1114       Standard_Integer anEdges[3];
1115       Standard_Boolean anEdgesOri[3];
1116       GetTriangle( anElemId ).Edges(anEdges, anEdgesOri);
1117
1118       Standard_Integer isTriangleFound = Standard_False;
1119       for ( Standard_Integer anEdgeIt = 0; anEdgeIt < 3; ++anEdgeIt )
1120       {
1121         if ( anEdges[anEdgeIt]    == aPolyEdgeId &&
1122              anEdgesOri[anEdgeIt] == isForward )
1123         {
1124           isTriangleFound = Standard_True;
1125           deleteTriangle( anElemId, aLoopEdges );
1126           break;
1127         }
1128       }
1129
1130       if ( isTriangleFound )
1131         break;
1132     }
1133
1134     // Skip a neighbor link to extract unique vertices each time
1135     if ( aPolyIt % 2 )
1136     {
1137       const BRepMesh_Edge& aPolyEdge = GetEdge( aPolyEdgeId );
1138       Standard_Integer aFirstVertex  = aPolyEdge.FirstNode();
1139       Standard_Integer aLastVertex   = aPolyEdge.LastNode();
1140
1141       aPolyVerticesFindMap.Add( aFirstVertex );
1142       aPolyVerticesFindMap.Add( aLastVertex );
1143
1144       if ( aPolyEdgeInfo > 0 )
1145       {
1146         aPolyVertices.Append( aFirstVertex );
1147         aPolyVertices.Append( aLastVertex );
1148       }
1149       else
1150       {
1151         aPolyVertices.Append( aLastVertex );
1152         aPolyVertices.Append( aFirstVertex );
1153       }
1154     }
1155   }
1156
1157   // Make closed sequence
1158   if ( aPolyVertices.First() != aPolyVertices.Last() )
1159     aPolyVertices.Append( aPolyVertices.First() );
1160
1161   BRepMesh::MapOfInteger aSurvivedLinks( anIgnoredEdges );
1162
1163   Standard_Integer aPolyVertIt          = 0;
1164   Standard_Integer anUniqueVerticesNum  = aPolyVertices.Length() - 1;
1165   for ( ; aPolyVertIt < anUniqueVerticesNum; ++aPolyVertIt )
1166   {
1167     killTrianglesAroundVertex( aPolyVertices( aPolyVertIt ),
1168       aPolyVertices, aPolyVerticesFindMap, thePolygon,
1169       thePolyBoxes, aSurvivedLinks, aLoopEdges );
1170   }
1171
1172   BRepMesh::MapOfIntegerInteger::Iterator aLoopEdgesIt( aLoopEdges );
1173   for ( ; aLoopEdgesIt.More(); aLoopEdgesIt.Next() )
1174   {
1175     const Standard_Integer& aLoopEdgeId = aLoopEdgesIt.Key();
1176     if ( anIgnoredEdges.Contains( aLoopEdgeId ) )
1177       continue;
1178
1179     if ( myMeshData->ElementsConnectedTo( aLoopEdgeId ).IsEmpty() )
1180       myMeshData->RemoveLink( aLoopEdgesIt.Key() );
1181   }
1182 }
1183
1184 //=======================================================================
1185 //function : killTrianglesAroundVertex
1186 //purpose  : Remove all triangles and edges that are placed
1187 //           inside the polygon or crossed it.
1188 //=======================================================================
1189 void BRepMesh_Delaun::killTrianglesAroundVertex(
1190   const Standard_Integer             theZombieNodeId,
1191   const BRepMesh::VectorOfInteger&   thePolyVertices,
1192   const BRepMesh::MapOfInteger&      thePolyVerticesFindMap,
1193   const BRepMesh::SequenceOfInteger& thePolygon,
1194   const BRepMesh::SequenceOfBndB2d&  thePolyBoxes,
1195   BRepMesh::MapOfInteger&            theSurvivedLinks,
1196   BRepMesh::MapOfIntegerInteger&     theLoopEdges )
1197 {
1198   BRepMesh::ListOfInteger::Iterator aNeighborsIt =
1199     myMeshData->LinksConnectedTo( theZombieNodeId );
1200
1201   // Try to infect neighbor nodes
1202   BRepMesh::VectorOfInteger aVictimNodes;
1203   for ( ; aNeighborsIt.More(); aNeighborsIt.Next() )
1204   {
1205     const Standard_Integer& aNeighborLinkId = aNeighborsIt.Value();
1206     if ( theSurvivedLinks.Contains( aNeighborLinkId ) )
1207       continue;
1208
1209     const BRepMesh_Edge& aNeighborLink = GetEdge( aNeighborLinkId );
1210     if ( aNeighborLink.Movability() == BRepMesh_Frontier )
1211     {
1212       // Though, if it lies onto the polygon boundary -
1213       // take its triangles
1214       Bnd_B2d aBox;
1215       Standard_Boolean isNotIntersect =
1216         checkIntersection( aNeighborLink, thePolygon,
1217         thePolyBoxes, Standard_False, Standard_True,
1218         Standard_False, aBox );
1219
1220       if ( isNotIntersect )
1221       {
1222         // Don't touch it
1223         theSurvivedLinks.Add( aNeighborLinkId );
1224         continue;
1225       }
1226     }
1227     else
1228     {
1229       Standard_Integer anOtherNode = aNeighborLink.FirstNode();
1230       if ( anOtherNode == theZombieNodeId )
1231         anOtherNode = aNeighborLink.LastNode();
1232
1233       // Possible sacrifice
1234       if ( !thePolyVerticesFindMap.Contains( anOtherNode ) )
1235       {
1236         if ( isVertexInsidePolygon( anOtherNode, thePolyVertices ) )
1237         {
1238           // Got you!
1239           aVictimNodes.Append( anOtherNode );
1240         }
1241         else
1242         {
1243           // Lucky. But it may intersect the polygon boundary.
1244           // Let's check it!
1245           killTrianglesOnIntersectingLinks( aNeighborLinkId,
1246             aNeighborLink, anOtherNode, thePolygon,
1247             thePolyBoxes, theSurvivedLinks, theLoopEdges );
1248
1249           continue;
1250         }
1251       }
1252     }
1253
1254     // Add link to the survivers to avoid cycling
1255     theSurvivedLinks.Add( aNeighborLinkId );
1256     killLinkTriangles( aNeighborLinkId, theLoopEdges );
1257   }
1258
1259   // Go and do your job!
1260   BRepMesh::VectorOfInteger::Iterator aVictimIt( aVictimNodes );
1261   for ( ; aVictimIt.More(); aVictimIt.Next() )
1262   {
1263     killTrianglesAroundVertex( aVictimIt.Value(), thePolyVertices,
1264       thePolyVerticesFindMap, thePolygon, thePolyBoxes,
1265       theSurvivedLinks, theLoopEdges );
1266   }
1267 }
1268
1269 //=======================================================================
1270 //function : isVertexInsidePolygon
1271 //purpose  : Checks is the given vertex lies inside the polygon
1272 //=======================================================================
1273 Standard_Boolean BRepMesh_Delaun::isVertexInsidePolygon(
1274   const Standard_Integer&          theVertexId,
1275   const BRepMesh::VectorOfInteger& thePolygonVertices ) const
1276 {
1277   Standard_Integer aPolyLen = thePolygonVertices.Length();
1278   if ( aPolyLen < 3 )
1279     return Standard_False;
1280
1281
1282   const gp_XY aCenterPointXY = GetVertex( theVertexId ).Coord();
1283
1284   const BRepMesh_Vertex& aFirstVertex = GetVertex( thePolygonVertices( 0 ) );
1285   gp_Vec2d aPrevVertexDir( aFirstVertex.Coord() - aCenterPointXY );
1286   if ( aPrevVertexDir.SquareMagnitude() < Precision2 )
1287     return Standard_True;
1288
1289   Standard_Real aTotalAng = 0.0;
1290   for ( Standard_Integer aPolyIt = 1; aPolyIt < aPolyLen; ++aPolyIt )
1291   {
1292     const BRepMesh_Vertex& aPolyVertex = GetVertex( thePolygonVertices( aPolyIt ) );
1293
1294     gp_Vec2d aCurVertexDir( aPolyVertex.Coord() - aCenterPointXY );
1295     if ( aCurVertexDir.SquareMagnitude() < Precision2 )
1296       return Standard_True;
1297
1298     aTotalAng     += aCurVertexDir.Angle( aPrevVertexDir );
1299     aPrevVertexDir = aCurVertexDir;
1300   }
1301
1302   if ( Abs( Angle2PI - aTotalAng ) > Precision::Angular() )
1303     return Standard_False;
1304
1305   return Standard_True;
1306 }
1307
1308 //=======================================================================
1309 //function : killTrianglesOnIntersectingLinks
1310 //purpose  : Checks is the given link crosses the polygon boundary.
1311 //           If yes, kills its triangles and checks neighbor links on
1312 //           boundary intersection. Does nothing elsewhere.
1313 //=======================================================================
1314 void BRepMesh_Delaun::killTrianglesOnIntersectingLinks(
1315   const Standard_Integer&            theLinkToCheckId,
1316   const BRepMesh_Edge&               theLinkToCheck,
1317   const Standard_Integer&            theEndPoint,
1318   const BRepMesh::SequenceOfInteger& thePolygon,
1319   const BRepMesh::SequenceOfBndB2d&  thePolyBoxes,
1320   BRepMesh::MapOfInteger&            theSurvivedLinks,
1321   BRepMesh::MapOfIntegerInteger&     theLoopEdges )
1322 {
1323   if ( theSurvivedLinks.Contains( theLinkToCheckId ) )
1324     return;
1325
1326   Bnd_B2d aBox;
1327   Standard_Boolean isNotIntersect =
1328     checkIntersection( theLinkToCheck, thePolygon,
1329       thePolyBoxes, Standard_False, Standard_False,
1330       Standard_False, aBox );
1331
1332   theSurvivedLinks.Add( theLinkToCheckId );
1333
1334   if ( isNotIntersect )
1335     return;
1336
1337   killLinkTriangles( theLinkToCheckId, theLoopEdges );
1338
1339   BRepMesh::ListOfInteger::Iterator aNeighborsIt =
1340     myMeshData->LinksConnectedTo( theEndPoint );
1341
1342   for ( ; aNeighborsIt.More(); aNeighborsIt.Next() )
1343   {
1344     const Standard_Integer& aNeighborLinkId = aNeighborsIt.Value();
1345     const BRepMesh_Edge&    aNeighborLink   = GetEdge( aNeighborLinkId );
1346     Standard_Integer anOtherNode = aNeighborLink.FirstNode();
1347     if ( anOtherNode == theEndPoint )
1348       anOtherNode = aNeighborLink.LastNode();
1349
1350     killTrianglesOnIntersectingLinks( aNeighborLinkId,
1351       aNeighborLink, anOtherNode, thePolygon,
1352       thePolyBoxes, theSurvivedLinks, theLoopEdges );
1353   }
1354 }
1355
1356 //=======================================================================
1357 //function : killLinkTriangles
1358 //purpose  : Kill triangles bound to the given link.
1359 //=======================================================================
1360 void BRepMesh_Delaun::killLinkTriangles(
1361   const Standard_Integer&        theLinkId,
1362   BRepMesh::MapOfIntegerInteger& theLoopEdges )
1363 {
1364   const BRepMesh_PairOfIndex& aPair =
1365     myMeshData->ElementsConnectedTo( theLinkId );
1366
1367   Standard_Integer anElemNb = aPair.Extent();
1368   for ( Standard_Integer aPairIt = 1; aPairIt <= anElemNb; ++aPairIt )
1369   {
1370     Standard_Integer anElemId = aPair.FirstIndex();
1371     if ( anElemId < 0 )
1372       continue;
1373
1374     deleteTriangle( anElemId, theLoopEdges );
1375   }
1376 }
1377
1378 //=======================================================================
1379 //function : getOrientedNodes
1380 //purpose  : Returns start and end nodes of the given edge in respect to
1381 //           its orientation.
1382 //=======================================================================
1383 void BRepMesh_Delaun::getOrientedNodes(const BRepMesh_Edge&   theEdge,
1384                                        const Standard_Boolean isForward,
1385                                        Standard_Integer       *theNodes) const
1386 {
1387   if ( isForward )
1388   {
1389     theNodes[0] = theEdge.FirstNode();
1390     theNodes[1] = theEdge.LastNode();
1391   }
1392   else
1393   {
1394     theNodes[0] = theEdge.LastNode();
1395     theNodes[1] = theEdge.FirstNode();
1396   }
1397 }
1398
1399 //=======================================================================
1400 //function : processLoop
1401 //purpose  : Processes loop within the given polygon formed by range of
1402 //           its links specified by start and end link indices.
1403 //=======================================================================
1404 void BRepMesh_Delaun::processLoop(const Standard_Integer             theLinkFrom,
1405                                   const Standard_Integer             theLinkTo,
1406                                   const BRepMesh::SequenceOfInteger& thePolygon,
1407                                   const BRepMesh::SequenceOfBndB2d&  thePolyBoxes)
1408 {
1409   Standard_Integer aNbOfLinksInLoop = theLinkTo - theLinkFrom - 1;
1410   if ( aNbOfLinksInLoop < 3 )
1411     return;
1412
1413   BRepMesh::SequenceOfInteger aPolygon;
1414   BRepMesh::SequenceOfBndB2d  aPolyBoxes;
1415   for ( ; aNbOfLinksInLoop > 0; --aNbOfLinksInLoop )
1416   {
1417     Standard_Integer aLoopLinkIndex = theLinkFrom + aNbOfLinksInLoop;
1418     aPolygon  .Prepend( thePolygon  ( aLoopLinkIndex ) );
1419     aPolyBoxes.Prepend( thePolyBoxes( aLoopLinkIndex ) );
1420   }
1421   meshPolygon( aPolygon, aPolyBoxes );
1422 }
1423
1424 //=======================================================================
1425 //function : createAndReplacePolygonLink
1426 //purpose  : Creates new link based on the given nodes and updates the
1427 //           given polygon.
1428 //=======================================================================
1429 Standard_Integer BRepMesh_Delaun::createAndReplacePolygonLink(
1430   const Standard_Integer       *theNodes,
1431   const gp_Pnt2d               *thePnts,
1432   const Standard_Integer       theRootIndex,
1433   const ReplaceFlag            theReplaceFlag,
1434   BRepMesh::SequenceOfInteger& thePolygon,
1435   BRepMesh::SequenceOfBndB2d&  thePolyBoxes )
1436 {
1437   Standard_Integer aNewEdgeId =
1438     myMeshData->AddLink( BRepMesh_Edge(
1439     theNodes[0], theNodes[1], BRepMesh_Free ) );
1440
1441   Bnd_B2d aNewBox;
1442   aNewBox.Add( thePnts[0] );
1443   aNewBox.Add( thePnts[1] );
1444
1445   switch ( theReplaceFlag )
1446   {
1447   case BRepMesh_Delaun::Replace:
1448     thePolygon  .SetValue( theRootIndex, aNewEdgeId );
1449     thePolyBoxes.SetValue( theRootIndex, aNewBox );
1450     break;
1451
1452   case BRepMesh_Delaun::InsertAfter:
1453     thePolygon  .InsertAfter( theRootIndex, aNewEdgeId );
1454     thePolyBoxes.InsertAfter( theRootIndex, aNewBox );
1455     break;
1456
1457   case BRepMesh_Delaun::InsertBefore:
1458     thePolygon  .InsertBefore( theRootIndex, aNewEdgeId );
1459     thePolyBoxes.InsertBefore( theRootIndex, aNewBox );
1460     break;
1461   }
1462
1463   return aNewEdgeId;
1464 }
1465
1466 //=======================================================================
1467 //function : meshPolygon
1468 //purpose  :
1469 //=======================================================================
1470 void BRepMesh_Delaun::meshPolygon(BRepMesh::SequenceOfInteger& thePolygon,
1471                                   BRepMesh::SequenceOfBndB2d&  thePolyBoxes,
1472                                   BRepMesh::HMapOfInteger      theSkipped )
1473 {
1474   // Check is the source polygon elementary
1475   if ( meshElementaryPolygon( thePolygon ) )
1476     return;
1477
1478   // Check and correct boundary edges
1479   Standard_Integer aPolyLen = thePolygon.Length();
1480   const Standard_Real aPolyArea      = Abs( polyArea( thePolygon, 1, aPolyLen ) );
1481   const Standard_Real aSmallLoopArea = 0.001 * aPolyArea;
1482   for ( Standard_Integer aPolyIt = 1; aPolyIt < aPolyLen; ++aPolyIt )
1483   {
1484     Standard_Integer aCurEdgeInfo = thePolygon( aPolyIt );
1485     Standard_Integer aCurEdgeId   = Abs( aCurEdgeInfo );
1486     const BRepMesh_Edge* aCurEdge = &GetEdge( aCurEdgeId );
1487     if ( aCurEdge->Movability() != BRepMesh_Frontier )
1488       continue;
1489
1490     Standard_Integer aCurNodes[2];
1491     getOrientedNodes( *aCurEdge, aCurEdgeInfo > 0, aCurNodes );
1492
1493     gp_Pnt2d aCurPnts[2] = {
1494       GetVertex(aCurNodes[0]).Coord(),
1495       GetVertex(aCurNodes[1]).Coord()
1496     };
1497
1498     gp_Vec2d aCurVec( aCurPnts[0], aCurPnts[1] );
1499
1500     // check further links
1501     Standard_Integer aNextPolyIt = aPolyIt + 1;
1502     for ( ; aNextPolyIt <= aPolyLen; ++aNextPolyIt )
1503     {
1504       Standard_Integer aNextEdgeInfo = thePolygon( aNextPolyIt );
1505       Standard_Integer aNextEdgeId   = Abs( aNextEdgeInfo );
1506       const BRepMesh_Edge* aNextEdge = &GetEdge( aNextEdgeId );
1507       if ( aNextEdge->Movability() != BRepMesh_Frontier )
1508         continue;
1509
1510       Standard_Integer aNextNodes[2];
1511       getOrientedNodes( *aNextEdge, aNextEdgeInfo > 0, aNextNodes );
1512
1513       gp_Pnt2d aNextPnts[2] = {
1514         GetVertex(aNextNodes[0]).Coord(),
1515         GetVertex(aNextNodes[1]).Coord()
1516       };
1517
1518       gp_Pnt2d anIntPnt;
1519       BRepMesh_GeomTool::IntFlag aIntFlag = intSegSeg( *aCurEdge, *aNextEdge,
1520         Standard_False, Standard_True, anIntPnt );
1521
1522       if ( aIntFlag == BRepMesh_GeomTool::NoIntersection )
1523         continue;
1524
1525       Standard_Boolean isRemoveFromFirst  = Standard_False;
1526       Standard_Boolean isAddReplacingEdge = Standard_True;
1527       Standard_Integer aIndexToRemoveTo   = aNextPolyIt;
1528       if ( aIntFlag == BRepMesh_GeomTool::Cross )
1529       {
1530         Standard_Real aLoopArea = polyArea( thePolygon, aPolyIt + 1, aNextPolyIt );
1531         gp_Vec2d aVec1( anIntPnt, aCurPnts [1] );
1532         gp_Vec2d aVec2( anIntPnt, aNextPnts[0] );
1533
1534         aLoopArea += ( aVec1 ^ aVec2 ) / 2.;
1535         if ( Abs( aLoopArea ) > aSmallLoopArea )
1536         {
1537           aNextNodes[1] = aCurNodes[0];
1538           aNextPnts [1] = aCurPnts [0];
1539
1540           aNextEdgeId = Abs( createAndReplacePolygonLink( aNextNodes, aNextPnts,
1541             aNextPolyIt, BRepMesh_Delaun::Replace, thePolygon, thePolyBoxes ) );
1542
1543           processLoop( aPolyIt, aNextPolyIt, thePolygon, thePolyBoxes );
1544           return;
1545         }
1546
1547         Standard_Real aDist1 = anIntPnt.SquareDistance(aNextPnts[0]);
1548         Standard_Real aDist2 = anIntPnt.SquareDistance(aNextPnts[1]);
1549
1550         // Choose node with lower distance
1551         const Standard_Boolean isCloseToStart = ( aDist1 < aDist2 );
1552         const Standard_Integer aEndPointIndex = isCloseToStart ? 0 : 1;
1553         aCurNodes[1] = aNextNodes[aEndPointIndex];
1554         aCurPnts [1] = aNextPnts [aEndPointIndex];
1555
1556         if ( isCloseToStart )
1557           --aIndexToRemoveTo;
1558
1559         // In this context only intersections between frontier edges
1560         // are possible. If intersection between edges of different
1561         // types occured - treat this case as invalid (i.e. result
1562         // might not reflect the expectations).
1563         if ( !theSkipped.IsNull() )
1564         {
1565           Standard_Integer aSkippedLinkIt = aPolyIt;
1566           for ( ; aSkippedLinkIt <= aIndexToRemoveTo; ++aSkippedLinkIt )
1567             theSkipped->Add( Abs( thePolygon( aSkippedLinkIt ) ) );
1568         }
1569       }
1570       else if ( aIntFlag == BRepMesh_GeomTool::PointOnSegment )
1571       {
1572         // Indentify chopping link
1573         Standard_Boolean isFirstChopping = Standard_False;
1574         Standard_Integer aCheckPointIt = 0;
1575         for ( ; aCheckPointIt < 2; ++aCheckPointIt )
1576         {
1577           gp_Pnt2d& aRefPoint = aCurPnts[aCheckPointIt];
1578           // Check is second link touches the first one
1579           gp_Vec2d aVec1( aRefPoint, aNextPnts[0] );
1580           gp_Vec2d aVec2( aRefPoint, aNextPnts[1] );
1581           if ( Abs( aVec1 ^ aVec2 ) < Precision )
1582           {
1583             isFirstChopping = Standard_True;
1584             break;
1585           }
1586         }
1587
1588         if ( isFirstChopping )
1589         {
1590           // Split second link
1591           isAddReplacingEdge = Standard_False;
1592           isRemoveFromFirst  = ( aCheckPointIt == 0 );
1593
1594           Standard_Integer aSplitLink[3] = {
1595             aNextNodes[0],
1596             aCurNodes [aCheckPointIt],
1597             aNextNodes[1]
1598           };
1599
1600           gp_Pnt2d aSplitPnts[3] = {
1601             aNextPnts[0],
1602             aCurPnts [aCheckPointIt],
1603             aNextPnts[1]
1604           };
1605
1606           Standard_Integer aSplitLinkIt = 0;
1607           for ( ; aSplitLinkIt < 2; ++aSplitLinkIt )
1608           {
1609             createAndReplacePolygonLink( &aSplitLink[aSplitLinkIt],
1610               &aSplitPnts[aSplitLinkIt], aNextPolyIt, ( aSplitLinkIt == 0 ) ?
1611               BRepMesh_Delaun::Replace : BRepMesh_Delaun::InsertAfter,
1612               thePolygon, thePolyBoxes );
1613           }
1614
1615           processLoop( aPolyIt + aCheckPointIt, aIndexToRemoveTo,
1616             thePolygon, thePolyBoxes );
1617         }
1618         else
1619         {
1620           // Split first link
1621           Standard_Integer aSplitLinkNodes[2] = {
1622             aNextNodes[1],
1623             aCurNodes [1]
1624           };
1625
1626           gp_Pnt2d aSplitLinkPnts[2] = {
1627             aNextPnts[1],
1628             aCurPnts [1]
1629           };
1630           createAndReplacePolygonLink( aSplitLinkNodes, aSplitLinkPnts,
1631             aPolyIt, BRepMesh_Delaun::InsertAfter, thePolygon, thePolyBoxes );
1632
1633           aCurNodes[1] = aNextNodes[1];
1634           aCurPnts [1] = aNextPnts [1];
1635           ++aIndexToRemoveTo;
1636
1637           processLoop( aPolyIt + 1, aIndexToRemoveTo,
1638             thePolygon, thePolyBoxes );
1639         }
1640       }
1641       else if ( aIntFlag == BRepMesh_GeomTool::Glued )
1642       {
1643         if ( aCurNodes[1] == aNextNodes[0] )
1644         {
1645           aCurNodes[1] = aNextNodes[1];
1646           aCurPnts [1] = aNextPnts [1];
1647         }
1648         // TODO: Non-adjacent glued links within the polygon
1649       }
1650       else if ( aIntFlag == BRepMesh_GeomTool::Same )
1651       {
1652         processLoop( aPolyIt, aNextPolyIt, thePolygon, thePolyBoxes );
1653
1654         isRemoveFromFirst  = Standard_True;
1655         isAddReplacingEdge = Standard_False;
1656       }
1657       else
1658         continue; // Not supported type
1659
1660       if ( isAddReplacingEdge )
1661       {
1662         aCurEdgeId = Abs( createAndReplacePolygonLink( aCurNodes, aCurPnts,
1663           aPolyIt, BRepMesh_Delaun::Replace, thePolygon, thePolyBoxes ) );
1664
1665         aCurEdge = &GetEdge( aCurEdgeId );
1666         aCurVec  = gp_Vec2d( aCurPnts[0], aCurPnts[1] );
1667       }
1668
1669       Standard_Integer aIndexToRemoveFrom =
1670         isRemoveFromFirst ? aPolyIt : aPolyIt + 1;
1671
1672       thePolygon  .Remove( aIndexToRemoveFrom, aIndexToRemoveTo );
1673       thePolyBoxes.Remove( aIndexToRemoveFrom, aIndexToRemoveTo );
1674
1675       aPolyLen = thePolygon.Length();
1676       if ( isRemoveFromFirst )
1677       {
1678         --aPolyIt;
1679         break;
1680       }
1681
1682       aNextPolyIt = aPolyIt;
1683     }
1684   }
1685
1686   meshSimplePolygon( thePolygon, thePolyBoxes );
1687 }
1688
1689 //=======================================================================
1690 //function : meshElementaryPolygon
1691 //purpose  : Triangulation of closed polygon containing only three edges.
1692 //=======================================================================
1693 inline Standard_Boolean BRepMesh_Delaun::meshElementaryPolygon(
1694   const BRepMesh::SequenceOfInteger& thePolygon)
1695 {
1696   Standard_Integer aPolyLen = thePolygon.Length();
1697   if ( aPolyLen < 3 )
1698     return Standard_True;
1699   else if ( aPolyLen > 3 )
1700     return Standard_False;
1701
1702   // Just create a triangle
1703   Standard_Integer anEdges[3];
1704   Standard_Boolean anEdgesOri[3];
1705
1706   for ( Standard_Integer anEdgeIt = 0; anEdgeIt < 3; ++anEdgeIt )
1707   {
1708     Standard_Integer anEdgeInfo = thePolygon( anEdgeIt + 1 );
1709     anEdges[anEdgeIt]           = Abs( anEdgeInfo );
1710     anEdgesOri[anEdgeIt]        = ( anEdgeInfo > 0 );
1711   }
1712
1713   const BRepMesh_Edge& anEdge1 = GetEdge( anEdges[0] );
1714   const BRepMesh_Edge& anEdge2 = GetEdge( anEdges[1] );
1715
1716   Standard_Integer aNodes[3] = { anEdge1.FirstNode(),
1717                                  anEdge1.LastNode(),
1718                                  anEdge2.FirstNode() };
1719   if ( aNodes[2] == aNodes[0] ||
1720        aNodes[2] == aNodes[1] )
1721   {
1722     aNodes[2] = anEdge2.LastNode();
1723   }
1724
1725   addTriangle( anEdges, anEdgesOri, aNodes );
1726   return Standard_True;
1727 }
1728
1729 //=======================================================================
1730 //function : meshSimplePolygon
1731 //purpose  : Triangulatiion of a closed simple polygon (polygon without
1732 //           glued edges and loops) described by the list of indexes of
1733 //           its edges in the structure.
1734 //           (negative index means reversed edge)
1735 //=======================================================================
1736 void BRepMesh_Delaun::meshSimplePolygon(BRepMesh::SequenceOfInteger& thePolygon,
1737                                         BRepMesh::SequenceOfBndB2d&  thePolyBoxes )
1738 {
1739   // Check is the given polygon elementary
1740   if ( meshElementaryPolygon( thePolygon ) )
1741     return;
1742
1743
1744   // Polygon contains more than 3 links
1745   Standard_Integer aFirstEdgeInfo = thePolygon(1);
1746   const BRepMesh_Edge& aFirstEdge = GetEdge( Abs( aFirstEdgeInfo ) );
1747
1748   Standard_Integer aNodes[3];
1749   getOrientedNodes( aFirstEdge, aFirstEdgeInfo > 0, aNodes );
1750
1751   gp_Pnt2d aRefVertices[3];
1752   aRefVertices[0] = GetVertex( aNodes[0] ).Coord();
1753   aRefVertices[1] = GetVertex( aNodes[1] ).Coord();
1754
1755   gp_Vec2d aRefEdgeDir( aRefVertices[0], aRefVertices[1] );
1756
1757   Standard_Real aRefEdgeLen = aRefEdgeDir.Magnitude();
1758   if ( aRefEdgeLen < Precision )
1759     return;
1760
1761   aRefEdgeDir /= aRefEdgeLen;
1762
1763   // Find a point with minimum distance respect
1764   // the end of reference link
1765   Standard_Integer aUsedLinkId = 0;
1766   Standard_Real    aOptAngle   = 0.0;
1767   Standard_Real    aMinDist    = RealLast();
1768   Standard_Integer aPivotNode  = aNodes[1];
1769   Standard_Integer aPolyLen    = thePolygon.Length();
1770   for ( Standard_Integer aLinkIt = 3; aLinkIt <= aPolyLen; ++aLinkIt )
1771   {
1772     Standard_Integer aLinkInfo = thePolygon( aLinkIt );
1773     const BRepMesh_Edge& aNextEdge = GetEdge( Abs( aLinkInfo ) );
1774
1775     aPivotNode = aLinkInfo > 0 ?
1776       aNextEdge.FirstNode() :
1777       aNextEdge.LastNode();
1778
1779     gp_Pnt2d aPivotVertex = GetVertex( aPivotNode ).Coord();
1780     gp_Vec2d aDistanceDir( aRefVertices[1], aPivotVertex );
1781
1782     Standard_Real aDist     = aRefEdgeDir ^ aDistanceDir;
1783     Standard_Real aAngle    = Abs( aRefEdgeDir.Angle(aDistanceDir) );
1784     Standard_Real anAbsDist = Abs( aDist );
1785     if (anAbsDist < Precision || aDist < 0.)
1786       continue;
1787
1788     if ( ( anAbsDist >= aMinDist                             ) &&
1789          ( aAngle <= aOptAngle || aAngle > AngDeviation90Deg ) )
1790     {
1791       continue;
1792     }
1793
1794     // Check is the test link crosses the polygon boudaries
1795     Standard_Boolean isIntersect = Standard_False;
1796     for ( Standard_Integer aRefLinkNodeIt = 0; aRefLinkNodeIt < 2; ++aRefLinkNodeIt )
1797     {
1798       const Standard_Integer& aLinkFirstNode   = aNodes[aRefLinkNodeIt];
1799       const gp_Pnt2d&         aLinkFirstVertex = aRefVertices[aRefLinkNodeIt];
1800
1801       Bnd_B2d aBox;
1802       aBox.Add( aLinkFirstVertex );
1803       aBox.Add( aPivotVertex );
1804
1805       BRepMesh_Edge aCheckLink( aLinkFirstNode, aPivotNode, BRepMesh_Free );
1806
1807       Standard_Integer aCheckLinkIt = 2;
1808       for ( ; aCheckLinkIt <= aPolyLen; ++aCheckLinkIt )
1809       {
1810         if( aCheckLinkIt == aLinkIt )
1811           continue;
1812
1813         if ( !aBox.IsOut( thePolyBoxes.Value( aCheckLinkIt ) ) )
1814         {
1815           const BRepMesh_Edge& aPolyLink =
1816             GetEdge( Abs( thePolygon( aCheckLinkIt ) ) );
1817
1818           if ( aCheckLink.IsEqual( aPolyLink ) )
1819             continue;
1820
1821           // intersection is possible...
1822           gp_Pnt2d anIntPnt;
1823           BRepMesh_GeomTool::IntFlag aIntFlag = intSegSeg( aCheckLink, aPolyLink,
1824             Standard_False, Standard_False, anIntPnt );
1825
1826           if( aIntFlag != BRepMesh_GeomTool::NoIntersection )
1827           {
1828             isIntersect = Standard_True;
1829             break;
1830           }
1831         }
1832       }
1833
1834       if ( isIntersect )
1835         break;
1836     }
1837
1838     if( isIntersect )
1839       continue;
1840
1841
1842     aOptAngle       = aAngle;
1843     aMinDist        = anAbsDist;
1844     aNodes[2]       = aPivotNode;
1845     aRefVertices[2] = aPivotVertex;
1846     aUsedLinkId     = aLinkIt;
1847   }
1848
1849   if ( aUsedLinkId == 0 )
1850     return;
1851
1852
1853   BRepMesh_Edge aNewEdges[2] = {
1854     BRepMesh_Edge( aNodes[1], aNodes[2], BRepMesh_Free ),
1855     BRepMesh_Edge( aNodes[2], aNodes[0], BRepMesh_Free ) };
1856
1857   Standard_Integer aNewEdgesInfo[3] = {
1858     aFirstEdgeInfo,
1859     myMeshData->AddLink( aNewEdges[0] ),
1860     myMeshData->AddLink( aNewEdges[1] ) };
1861
1862
1863   Standard_Integer anEdges[3];
1864   Standard_Boolean anEdgesOri[3];
1865   for ( Standard_Integer aTriEdgeIt = 0; aTriEdgeIt < 3; ++aTriEdgeIt )
1866   {
1867     const Standard_Integer& anEdgeInfo = aNewEdgesInfo[aTriEdgeIt];
1868     anEdges[aTriEdgeIt]    = Abs( anEdgeInfo );
1869     anEdgesOri[aTriEdgeIt] = anEdgeInfo > 0;
1870   }
1871   addTriangle( anEdges, anEdgesOri, aNodes );
1872
1873   // Create triangle and split the source polygon on two
1874   // parts (if possible) and mesh each part as independent
1875   // polygon.
1876   if ( aUsedLinkId < aPolyLen )
1877   {
1878     BRepMesh::SequenceOfInteger aRightPolygon;
1879     thePolygon.Split( aUsedLinkId, aRightPolygon );
1880     aRightPolygon.Prepend( -aNewEdgesInfo[2] );
1881
1882     BRepMesh::SequenceOfBndB2d aRightPolyBoxes;
1883     thePolyBoxes.Split( aUsedLinkId, aRightPolyBoxes );
1884
1885     Bnd_B2d aBox;
1886     aBox.Add( aRefVertices[0] );
1887     aBox.Add( aRefVertices[2] );
1888     aRightPolyBoxes.Prepend( aBox );
1889
1890     meshSimplePolygon( aRightPolygon, aRightPolyBoxes );
1891   }
1892   else
1893   {
1894     thePolygon.Remove  ( aPolyLen );
1895     thePolyBoxes.Remove( aPolyLen );
1896   }
1897
1898   if ( aUsedLinkId > 3 )
1899   {
1900     thePolygon.SetValue( 1, -aNewEdgesInfo[1] );
1901
1902     Bnd_B2d aBox;
1903     aBox.Add( aRefVertices[1] );
1904     aBox.Add( aRefVertices[2] );
1905
1906     thePolyBoxes.SetValue( 1, aBox );
1907
1908     meshSimplePolygon( thePolygon, thePolyBoxes );
1909   }
1910 }
1911
1912 //=======================================================================
1913 //function : RemoveVertex
1914 //purpose  : Removes a vertex from the triangulation
1915 //=======================================================================
1916 void BRepMesh_Delaun::RemoveVertex( const BRepMesh_Vertex& theVertex )
1917 {
1918   BRepMesh_SelectorOfDataStructureOfDelaun aSelector( myMeshData );
1919   aSelector.NeighboursOf( theVertex );
1920
1921   BRepMesh::MapOfIntegerInteger aLoopEdges( 10, myMeshData->Allocator() );
1922
1923   // Loop on triangles to be destroyed :
1924   BRepMesh::MapOfInteger::Iterator aTriangleIt( aSelector.Elements() );
1925   for ( ; aTriangleIt.More(); aTriangleIt.Next() )
1926     deleteTriangle( aTriangleIt.Key(), aLoopEdges );
1927
1928   BRepMesh::SequenceOfBndB2d  aBoxes;
1929   BRepMesh::SequenceOfInteger aPolygon;
1930   Standard_Integer aLoopEdgesCount = aLoopEdges.Extent();
1931   BRepMesh::MapOfIntegerInteger::Iterator aLoopEdgesIt( aLoopEdges );
1932
1933   if ( aLoopEdgesIt.More() )
1934   {
1935     const BRepMesh_Edge& anEdge = GetEdge( aLoopEdgesIt.Key() );
1936     Standard_Integer aFirstNode = anEdge.FirstNode();
1937     Standard_Integer aLastNode;
1938     Standard_Integer aPivotNode = anEdge.LastNode();
1939     Standard_Integer anEdgeId   = aLoopEdgesIt.Key();
1940
1941     Standard_Boolean isPositive = (Standard_Boolean)aLoopEdges( anEdgeId );
1942     if ( !isPositive )
1943     {
1944       Standard_Integer aTmp;
1945       aTmp       = aFirstNode;
1946       aFirstNode = aPivotNode;
1947       aPivotNode = aTmp;
1948
1949       aPolygon.Append( -anEdgeId );
1950     }
1951     else
1952       aPolygon.Append( anEdgeId );
1953
1954     fillBndBox( aBoxes, GetVertex( aFirstNode ), GetVertex( aPivotNode ) );
1955
1956     aLoopEdges.UnBind( anEdgeId );
1957
1958     aLastNode = aFirstNode;
1959     while ( aPivotNode != aLastNode )
1960     {
1961       BRepMesh::ListOfInteger::Iterator aLinkIt( myMeshData->LinksConnectedTo( aPivotNode ) );
1962       for ( ; aLinkIt.More(); aLinkIt.Next() )
1963       {
1964         if ( aLinkIt.Value() != anEdgeId &&
1965              aLoopEdges.IsBound( aLinkIt.Value() ) )
1966         {
1967           Standard_Integer aCurrentNode;
1968           anEdgeId = aLinkIt.Value();
1969           const BRepMesh_Edge& anEdge1 = GetEdge( anEdgeId );
1970
1971           aCurrentNode = anEdge1.LastNode();
1972           if ( aCurrentNode != aPivotNode )
1973           {
1974             aCurrentNode = anEdge1.FirstNode();
1975             aPolygon.Append( -anEdgeId );
1976           }
1977           else
1978             aPolygon.Append( anEdgeId );
1979
1980           fillBndBox( aBoxes, GetVertex( aCurrentNode ), GetVertex( aPivotNode ) );
1981
1982           aPivotNode = aCurrentNode;
1983           aLoopEdges.UnBind( anEdgeId );
1984           break;
1985         }
1986       }
1987
1988       if ( aLoopEdgesCount <= 0 )
1989         break;
1990       --aLoopEdgesCount;
1991     }
1992
1993     meshPolygon( aPolygon, aBoxes );
1994   }
1995 }
1996
1997
1998 //=======================================================================
1999 //function : AddVertices
2000 //purpose  : Adds some vertices in the triangulation.
2001 //=======================================================================
2002 void BRepMesh_Delaun::AddVertices(BRepMesh::Array1OfVertexOfDelaun& theVertices)
2003 {
2004   std::make_heap(theVertices.begin(), theVertices.end(), ComparatorOfVertexOfDelaun());
2005   std::sort_heap(theVertices.begin(), theVertices.end(), ComparatorOfVertexOfDelaun());
2006
2007   Standard_Integer aLower  = theVertices.Lower();
2008   Standard_Integer anUpper = theVertices.Upper();
2009
2010   BRepMesh::Array1OfInteger aVertexIndexes( aLower, anUpper );
2011   for ( Standard_Integer i = aLower; i <= anUpper; ++i )
2012     aVertexIndexes(i) = myMeshData->AddNode( theVertices(i) );
2013
2014   createTrianglesOnNewVertices( aVertexIndexes );
2015 }
2016
2017 //=======================================================================
2018 //function : UseEdge
2019 //purpose  : Modify mesh to use the edge. Return True if done
2020 //=======================================================================
2021 Standard_Boolean BRepMesh_Delaun::UseEdge( const Standard_Integer /*theIndex*/ )
2022 {
2023   /*
2024   const BRepMesh_PairOfIndex& aPair = myMeshData->ElemConnectedTo( theIndex );
2025   if ( aPair.Extent() == 0 )
2026   {
2027     const BRepMesh_Edge& anEdge = GetEdge( theIndex );
2028
2029     Standard_Integer aStartNode, aPivotNode, anOtherNode;
2030     aStartNode = anEdge.FirstNode();
2031     aPivotNode = anEdge.LastNode();
2032
2033     const BRepMesh_ListOfInteger& aStartNodeNeighbors = myMeshData->LinkNeighboursOf( aStartNode );
2034     const BRepMesh_ListOfInteger& aPivotNodeNeighbors = myMeshData->LinkNeighboursOf( aPivotNode );
2035
2036     if ( aStartNodeNeighbors.Extent() > 0 &&
2037          aPivotNodeNeighbors.Extent() > 0 )
2038     {
2039       const BRepMesh_Vertex& aStartVertex = GetVertex( aStartNode );
2040       const BRepMesh_Vertex& aPivotVertex = GetVertex( aPivotNode );
2041
2042       gp_XY aVEdge   ( aPivotVertex.Coord() );
2043       aVEdge.Subtract( aStartVertex.Coord() );
2044
2045       Standard_Real    anAngle    = 0.;
2046       Standard_Real    anAngleMin = RealLast();
2047       Standard_Real    anAngleMax = RealFirst();
2048       Standard_Integer aLeftEdge  = 0, aRightEdge = 0;
2049
2050       BRepMesh_ListOfInteger::Iterator aNeighborIt( aPivotNodeNeighbors );
2051       for ( ; aNeighborIt.More(); aNeighborIt.Next() )
2052       {
2053         Standard_Integer anEdgeId = aNeighborIt.Value();
2054         if ( anEdgeId != theIndex )
2055         {
2056           const BRepMesh_Edge& aNextEdge = GetEdge( anEdgeId );
2057
2058           Standard_Boolean isInMesh = Standard_True;
2059           if ( aNextEdge.Movability() == BRepMesh_Free )
2060           {
2061             if ( myMeshData->ElemConnectedTo( anEdgeId ).IsEmpty() )
2062               isInMesh = Standard_False;
2063           }
2064
2065           if ( isInMesh )
2066           {
2067             anOtherNode = aNextEdge.FirstNode();
2068             if ( anOtherNode == aPivotNode )
2069               anOtherNode = aNextEdge.LastNode();
2070
2071             gp_XY aVEdgeCur = GetVertex( anOtherNode ).Coord();
2072             aVEdgeCur.Subtract( aPivotVertex.Coord() );
2073
2074             anAngle = gp_Vec2d( aVEdge ).Angle( gp_Vec2d( aVEdgeCur ) );
2075           }
2076
2077           if ( anAngle > anAngleMax )
2078           {
2079             anAngleMax = anAngle;
2080             aLeftEdge  = anEdgeId;
2081           }
2082           if ( anAngle < anAngleMin )
2083           {
2084             anAngleMin = anAngle;
2085             aRightEdge = anEdgeId;
2086           }
2087         }
2088       }
2089
2090       if ( aLeftEdge > 0 )
2091       {
2092         if (aLeftEdge==aRightEdge)
2093         {
2094         }
2095         else
2096         {
2097         }
2098       }
2099     }
2100   }
2101   */
2102   return Standard_False;
2103 }
2104
2105 //=======================================================================
2106 //function : getEdgesByType
2107 //purpose  : Gives the list of edges with type defined by input parameter
2108 //=======================================================================
2109 BRepMesh::HMapOfInteger BRepMesh_Delaun::getEdgesByType(
2110   const BRepMesh_DegreeOfFreedom theEdgeType ) const
2111 {
2112   BRepMesh::HMapOfInteger aResult = new BRepMesh::MapOfInteger;
2113   BRepMesh::MapOfInteger::Iterator anEdgeIt( myMeshData->LinksOfDomain() );
2114
2115   for ( ; anEdgeIt.More(); anEdgeIt.Next() )
2116   {
2117     Standard_Integer anEdge = anEdgeIt.Key();
2118     Standard_Boolean isToAdd = (theEdgeType == BRepMesh_Free) ?
2119       (myMeshData->ElementsConnectedTo( anEdge ).Extent() <= 1) :
2120       (GetEdge( anEdge ).Movability() == theEdgeType);
2121
2122     if (isToAdd)
2123       aResult->Add( anEdge );
2124   }
2125
2126   return aResult;
2127 }
2128
2129 //=======================================================================
2130 //function : calculateDist
2131 //purpose  : Calculates distances between the given point and edges of
2132 //           triangle
2133 //=======================================================================
2134 Standard_Real BRepMesh_Delaun::calculateDist( const gp_XY            theVEdges[3],
2135                                               const gp_XY            thePoints[3],
2136                                               const Standard_Integer theEdgesId[3],
2137                                               const BRepMesh_Vertex& theVertex,
2138                                               Standard_Real          theDistance[3],
2139                                               Standard_Real          theSqModulus[3],
2140                                               Standard_Integer&      theEdgeOn ) const
2141 {
2142   Standard_Real aMinDist = -1;
2143   if ( !theVEdges || !thePoints || !theEdgesId ||
2144        !theDistance || !theSqModulus )
2145     return aMinDist;
2146
2147   for( Standard_Integer i = 0; i < 3; ++i )
2148   {
2149     theSqModulus[i] = theVEdges[i].SquareModulus();
2150     if ( theSqModulus[i] <= Precision2 )
2151       return -1;
2152
2153     theDistance[i] = theVEdges[i] ^ ( theVertex.Coord() - thePoints[i] );
2154
2155     Standard_Real aDist = theDistance[i] * theDistance[i];
2156     aDist /= theSqModulus[i];
2157
2158     if ( aMinDist < 0 || aDist < aMinDist )
2159     {
2160       theEdgeOn = theEdgesId[i];
2161       aMinDist  = aDist;
2162     }
2163   }
2164
2165   return aMinDist;
2166 }
2167
2168 //=======================================================================
2169 //function : Contains
2170 //purpose  : Test if triangle of index <TrianIndex> contains geometricaly
2171 //           <theVertex>. If <theEdgeOn> is != 0 then theVertex is on Edge
2172 //           of  index <theEdgeOn>
2173 //=======================================================================
2174 Standard_Boolean BRepMesh_Delaun::Contains( const Standard_Integer theTriangleId,
2175                                             const BRepMesh_Vertex& theVertex,
2176                                             Standard_Integer&      theEdgeOn ) const
2177 {
2178   theEdgeOn = 0;
2179
2180   Standard_Integer e[3];
2181   Standard_Boolean o[3];
2182   Standard_Integer p[3];
2183
2184   const BRepMesh_Triangle& aElement = GetTriangle( theTriangleId );
2185   aElement.Edges(e, o);
2186
2187   const BRepMesh_Edge* anEdges[3] = { &GetEdge( e[0] ),
2188                                       &GetEdge( e[1] ),
2189                                       &GetEdge( e[2] ) };
2190
2191   myMeshData->ElementNodes(aElement, p);
2192
2193   gp_XY aPoints[3];
2194   aPoints[0] = GetVertex( p[0] ).Coord();
2195   aPoints[1] = GetVertex( p[1] ).Coord();
2196   aPoints[2] = GetVertex( p[2] ).Coord();
2197
2198   gp_XY aVEdges[3];
2199   aVEdges[0] = aPoints[1];
2200   aVEdges[0].Subtract( aPoints[0] );
2201
2202   aVEdges[1] = aPoints[2];
2203   aVEdges[1].Subtract( aPoints[1] );
2204
2205   aVEdges[2] = aPoints[0];
2206   aVEdges[2].Subtract( aPoints[2] );
2207
2208   Standard_Real aDistance[3];
2209   Standard_Real aSqModulus[3];
2210
2211   Standard_Real aMinDist;
2212   aMinDist = calculateDist( aVEdges, aPoints, e, theVertex, aDistance, aSqModulus, theEdgeOn );
2213   if ( aMinDist < 0 )
2214     return Standard_False;
2215
2216   if ( aMinDist > Precision2 )
2217   {
2218     Standard_Integer anEdgeId = theEdgeOn;
2219     theEdgeOn = 0;
2220
2221     if ( anEdgeId != 0 )
2222     {
2223       Standard_Integer i = 0;
2224       for ( ; i < 3; ++i )
2225       {
2226         if( e[i] == anEdgeId )
2227           break;
2228       }
2229
2230       if( anEdges[i]->Movability() != BRepMesh_Free )
2231         if ( aDistance[i] < ( aSqModulus[i] / 5. ) )
2232           theEdgeOn = e[i];
2233     }
2234   }
2235
2236   return ( aDistance[0] + aDistance[1] + aDistance[2] != 0. &&
2237             ( ( aDistance[0] >= 0. && aDistance[1] >= 0. && aDistance[2] >= 0. ) ||
2238               ( aDistance[0] <= 0. && aDistance[1] <= 0. && aDistance[2] <= 0. ) ) );
2239 }
2240
2241 //=============================================================================
2242 //function : intSegSeg
2243 //purpose  : Checks intersection between the two segments.
2244 //=============================================================================
2245 BRepMesh_GeomTool::IntFlag BRepMesh_Delaun::intSegSeg(
2246   const BRepMesh_Edge&   theEdg1,
2247   const BRepMesh_Edge&   theEdg2,
2248   const Standard_Boolean isConsiderEndPointTouch,
2249   const Standard_Boolean isConsiderPointOnEdge,
2250   gp_Pnt2d&              theIntPnt) const
2251 {
2252   gp_XY p1, p2, p3, p4;
2253   p1 = GetVertex( theEdg1.FirstNode() ).Coord();
2254   p2 = GetVertex( theEdg1.LastNode()  ).Coord();
2255   p3 = GetVertex( theEdg2.FirstNode() ).Coord();
2256   p4 = GetVertex( theEdg2.LastNode()  ).Coord();
2257
2258   return BRepMesh_GeomTool::IntSegSeg(p1, p2, p3, p4,
2259     isConsiderEndPointTouch, isConsiderPointOnEdge, theIntPnt);
2260 }
2261
2262 //=============================================================================
2263 //function : polyArea
2264 //purpose  : Returns area of the loop of the given polygon defined by indices
2265 //           of its start and end links.
2266 //=============================================================================
2267 Standard_Real BRepMesh_Delaun::polyArea(const BRepMesh::SequenceOfInteger& thePolygon,
2268                                         const Standard_Integer             theStartIndex,
2269                                         const Standard_Integer             theEndIndex) const
2270 {
2271   Standard_Real aArea = 0.0;
2272   Standard_Integer aPolyLen = thePolygon.Length();
2273   if ( theStartIndex >= theEndIndex ||
2274        theStartIndex > aPolyLen )
2275   {
2276     return aArea;
2277   }
2278   Standard_Integer aCurEdgeInfo = thePolygon( theStartIndex );
2279   Standard_Integer aCurEdgeId   = Abs( aCurEdgeInfo );
2280   const BRepMesh_Edge* aCurEdge = &GetEdge( aCurEdgeId );
2281
2282   Standard_Integer aNodes[2];
2283   getOrientedNodes( *aCurEdge, aCurEdgeInfo > 0, aNodes );
2284
2285   gp_Pnt2d aRefPnt = GetVertex( aNodes[0] ).Coord();
2286   Standard_Integer aPolyIt = theStartIndex + 1;
2287   for ( ; aPolyIt <= theEndIndex; ++aPolyIt )
2288   {
2289     aCurEdgeInfo = thePolygon( aPolyIt );
2290     aCurEdgeId   = Abs( aCurEdgeInfo );
2291     aCurEdge     = &GetEdge( aCurEdgeId );
2292
2293     getOrientedNodes( *aCurEdge, aCurEdgeInfo > 0, aNodes );
2294     gp_Vec2d aVec1( aRefPnt, GetVertex( aNodes[0] ).Coord() );
2295     gp_Vec2d aVec2( aRefPnt, GetVertex( aNodes[1] ).Coord() );
2296
2297     aArea += aVec1 ^ aVec2;
2298   }
2299
2300   return aArea / 2.;
2301 }