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