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