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