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-2012 OPEN CASCADE SAS
   5 //
   6 // The content of this file is subject to the Open CASCADE Technology Public
   7 // License Version 6.5 (the "License"). You may not use the content of this file
   8 // except in compliance with the License. Please obtain a copy of the License
   9 // at http://www.opencascade.org and read it completely before using this file.
  10 //
  11 // The Initial Developer of the Original Code is Open CASCADE S.A.S., having its
  12 // main offices at: 1, place des Freres Montgolfier, 78280 Guyancourt, France.
  13 //
  14 // The Original Code and all software distributed under the License is
  15 // distributed on an "AS IS" basis, without warranty of any kind, and the
  16 // Initial Developer hereby disclaims all such warranties, including without
  17 // limitation, any warranties of merchantability, fitness for a particular
  18 // purpose or non-infringement. Please see the License for the specific terms
  19 // and conditions governing the rights and limitations under the License.
  20
  21
  22 #include <BRepMesh_Delaun.ixx>
  23 #include <gp_XY.hxx>
  24 #include <gp_Pnt2d.hxx>
  25 #include <gp_Vec2d.hxx>
  26 #include <TColStd_ListIteratorOfListOfInteger.hxx>
  27 #include <TColStd_ListOfInteger.hxx>
  28 #include <Precision.hxx>
  29 #include <Bnd_Box2d.hxx>
  30 #include <gp.hxx>
  31 #include <TColStd_MapOfInteger.hxx>
  32 #include <TColStd_MapIteratorOfMapOfInteger.hxx>
  33 #include <TColStd_Array1OfBoolean.hxx>
  34 #include <BRepMesh_MapOfIntegerInteger.hxx>
  35 #include <BRepMesh_HeapSortIndexedVertexOfDelaun.hxx>
  36 #include <BRepMesh_ComparatorOfIndexedVertexOfDelaun.hxx>
  37 #include <BRepMesh_HeapSortIndexedVertexOfDelaun.hxx>
  38 #include <BRepMesh_SelectorOfDataStructureOfDelaun.hxx>
  39 #include <BRepMesh_HeapSortVertexOfDelaun.hxx>
  40 #include <BRepMesh_ComparatorOfVertexOfDelaun.hxx>
  41 #include <TColgp_Array1OfXY.hxx>
  42 #include <TColStd_Array1OfReal.hxx>
  43
  44 typedef TColStd_ListIteratorOfListOfInteger  IteratorOnListOfInteger;
  45 typedef TColStd_ListOfInteger                ListOfInteger;
  46
  47 const Standard_Real EPSEPS = Precision::PConfusion() * Precision::PConfusion();
  48 const gp_XY SortingDirection(M_SQRT1_2, M_SQRT1_2);
  49
  50 //=======================================================================
  51 //function : fillBndBox
  52 //purpose  : Add boundig box for edge defined by start & end point to
  53 //           the given vector of bounding boxes for triangulation edges
  54 //=======================================================================
  55 static void fillBndBox( NCollection_Vector <Bnd_Box2d>& theVB,
  56                         const BRepMesh_Vertex& theV1,
  57                         const BRepMesh_Vertex& theV2 )
  58 {
  59   Bnd_Box2d aBox;
  60   aBox.Add( gp_Pnt2d( theV1.Coord() ) );
  61   aBox.Add( gp_Pnt2d( theV2.Coord() ) );
  62   theVB.Append( aBox );
  63 }
  64
  65 //=======================================================================
  66 //function : BRepMesh_Delaun
  67 //purpose  : Creates the triangulation with an empty Mesh data structure
  68 //=======================================================================
  69 BRepMesh_Delaun::BRepMesh_Delaun( BRepMesh_Array1OfVertexOfDelaun& theVertices,
  70                                   const Standard_Boolean isPositive )
  71 : myPositiveOrientation( isPositive ),
  72   myCircles( theVertices.Length(), new NCollection_IncAllocator() )
  73 {
  74   if ( theVertices.Length() > 2 )
  75   {
  76     myMeshData = new BRepMesh_DataStructureOfDelaun( new NCollection_IncAllocator(),
  77                                                      theVertices.Length() );
  78     Init( theVertices );
  79   }
  80 }
  81
  82 //=======================================================================
  83 //function : BRepMesh_Delaun
  84 //purpose  : Creates the triangulation with and existent Mesh data structure
  85 //=======================================================================
  86 BRepMesh_Delaun::BRepMesh_Delaun ( const Handle( BRepMesh_DataStructureOfDelaun )& theOldMesh,
  87                                    BRepMesh_Array1OfVertexOfDelaun& theVertices,
  88                                    const Standard_Boolean isPositive )
  89  : myPositiveOrientation( isPositive ),
  90    myCircles( theVertices.Length(), theOldMesh->Allocator() )
  91 {
  92   myMeshData = theOldMesh;
  93   if ( theVertices.Length() > 2 )
  94     Init( theVertices );
  95 }
  96
  97 //=======================================================================
  98 //function : BRepMesh_Delaun
  99 //purpose  : Creates the triangulation with and existent Mesh data structure
 100 //=======================================================================
 101 BRepMesh_Delaun::BRepMesh_Delaun( const Handle( BRepMesh_DataStructureOfDelaun )& theOldMesh,
 102                                   TColStd_Array1OfInteger& theVertexIndexes,
 103                                   const Standard_Boolean isPositive )
 104  : myPositiveOrientation( isPositive ),
 105    myCircles( theVertexIndexes.Length(), theOldMesh->Allocator() )
 106 {
 107   myMeshData = theOldMesh;
 108   if ( theVertexIndexes.Length() > 2 )
 109   {
 110     Bnd_Box2d aBox;
 111     Standard_Integer anIndex = theVertexIndexes.Lower();
 112     Standard_Integer anUpper = theVertexIndexes.Upper();
 113     for ( ; anIndex <= anUpper; ++anIndex )
 114       aBox.Add( gp_Pnt2d( GetVertex( theVertexIndexes( anIndex) ).Coord() ) );
 115
 116     Perform( aBox, theVertexIndexes );
 117   }
 118 }
 119
 120 //=======================================================================
 121 //function : Init
 122 //purpose  : Initializes the triangulation with an Array of Vertex
 123 //=======================================================================
 124 void BRepMesh_Delaun::Init( BRepMesh_Array1OfVertexOfDelaun& theVertices )
 125 {
 126   Bnd_Box2d aBox;
 127   Standard_Integer aLowerIdx  = theVertices.Lower();
 128   Standard_Integer anUpperIdx = theVertices.Upper();
 129   TColStd_Array1OfInteger aVertexIndexes( aLowerIdx, anUpperIdx );
 130
 131   Standard_Integer anIndex = aLowerIdx;
 132   for ( ; anIndex <= anUpperIdx; ++anIndex )
 133   {
 134     aBox.Add( gp_Pnt2d( theVertices( anIndex ).Coord() ) );
 135     aVertexIndexes( anIndex ) = myMeshData->AddNode( theVertices( anIndex ) );
 136   }
 137
 138   Perform( aBox, aVertexIndexes );
 139 }
 140
 141 //=======================================================================
 142 //function : Perform
 143 //purpose  : Create super mesh and run triangulation procedure
 144 //=======================================================================
 145 void BRepMesh_Delaun::Perform( Bnd_Box2d& theBndBox,
 146                                TColStd_Array1OfInteger& theVertexIndexes )
 147 {
 148   theBndBox.Enlarge( Precision::PConfusion() );
 149   SuperMesh( theBndBox );
 150
 151   BRepMesh_HeapSortIndexedVertexOfDelaun::Sort( theVertexIndexes,
 152       BRepMesh_ComparatorOfIndexedVertexOfDelaun( SortingDirection,
 153         Precision::PConfusion(), myMeshData ) );
 154
 155   Compute( theVertexIndexes );
 156 }
 157
 158 //=======================================================================
 159 //function : SuperMesh
 160 //purpose  : Build the super mesh
 161 //=======================================================================
 162 void BRepMesh_Delaun::SuperMesh( const Bnd_Box2d& theBox )
 163 {
 164   Standard_Real aMinX, aMinY, aMaxX, aMaxY;
 165   theBox.Get( aMinX, aMinY, aMaxX, aMaxY );
 166   Standard_Real aDeltaX = aMaxX - aMinX;
 167   Standard_Real aDeltaY = aMaxY - aMinY;
 168
 169   Standard_Real aDeltaMin = Min( aDeltaX, aDeltaY );
 170   Standard_Real aDeltaMax = Max( aDeltaX, aDeltaY );
 171   Standard_Real aDelta    = aDeltaX + aDeltaY;
 172
 173   myCircles.SetMinMaxSize( gp_XY( aMinX, aMinY ), gp_XY( aMaxX, aMaxY ) );
 174
 175   Standard_Integer aScaler = 2;
 176   if ( myMeshData->NbNodes() > 100 )
 177     aScaler = 5;
 178   else if( myMeshData->NbNodes() > 1000 )
 179     aScaler = 7;
 180
 181   myCircles.SetCellSize( aDeltaX / aScaler,
 182                          aDeltaY / aScaler );
 183
 184   mySupVert1 = myMeshData->AddNode(
 185     BRepMesh_Vertex( ( aMinX + aMaxX ) / 2, aMaxY + aDeltaMax, BRepMesh_Free ) );
 186
 187   mySupVert2 = myMeshData->AddNode(
 188     BRepMesh_Vertex( aMinX - aDelta, aMinY - aDeltaMin, BRepMesh_Free ) );
 189
 190   mySupVert3 = myMeshData->AddNode(
 191     BRepMesh_Vertex( aMaxX + aDelta, aMinY - aDeltaMin, BRepMesh_Free ) );
 192
 193   if ( !myPositiveOrientation )
 194   {
 195     Standard_Integer aTmp;
 196     aTmp       = mySupVert2;
 197     mySupVert2 = mySupVert3;
 198     mySupVert3 = aTmp;
 199   }
 200
 201   Standard_Integer anEdge1, anEdge2, anEdge3;
 202
 203   anEdge1 = myMeshData->AddLink( BRepMesh_Edge( mySupVert1, mySupVert2, BRepMesh_Free ) );
 204   anEdge2 = myMeshData->AddLink( BRepMesh_Edge( mySupVert2, mySupVert3, BRepMesh_Free ) );
 205   anEdge3 = myMeshData->AddLink( BRepMesh_Edge( mySupVert3, mySupVert1, BRepMesh_Free ) );
 206
 207   mySupTrian = BRepMesh_Triangle( Abs( anEdge1 ), Abs( anEdge2 ), Abs( anEdge3 ),
 208     ( anEdge1 > 0 ), ( anEdge2 > 0 ), ( anEdge1 > 0), BRepMesh_Free);
 209 }
 210
 211 //=======================================================================
 212 //function : DeleteTriangle
 213 //purpose : The concerned triangles are deleted and the freed edges are added in
 214 //           <theLoopEdges>. If an edge is added twice, it does not exist and
 215 //          it is necessary to destroy it. This corresponds to the destruction of two
 216 //          connected triangles.
 217 //=======================================================================
 218 void  BRepMesh_Delaun::DeleteTriangle( const Standard_Integer theIndex,
 219                                        BRepMesh_MapOfIntegerInteger& theLoopEdges )
 220 {
 221   myCircles.Delete( theIndex );
 222
 223   Standard_Integer e[3];
 224   Standard_Boolean o[3];
 225   GetTriangle( theIndex ).Edges( e[0], e[1], e[2],
 226                                  o[0], o[1], o[2] );
 227
 228   myMeshData->RemoveElement( theIndex );
 229
 230   for ( Standard_Integer i = 0; i < 3; ++i )
 231   {
 232     if ( !theLoopEdges.Bind( e[i], o[i] ) )
 233     {
 234       theLoopEdges.UnBind( e[i] );
 235       myMeshData->RemoveLink( e[i] );
 236     }
 237   }
 238 }
 239
 240 //=======================================================================
 241 //function : Compute
 242 //purpose  : Computes the triangulation and add the vertices edges and
 243 //           triangles to the Mesh data structure
 244 //=======================================================================
 245 void BRepMesh_Delaun::Compute( TColStd_Array1OfInteger& theVertexIndexes )
 246 {
 247   // Insertion of edges of super triangles in the list of free edges:
 248   BRepMesh_MapOfIntegerInteger aLoopEdges( 10, myMeshData->Allocator() );
 249   Standard_Integer e[3];
 250   Standard_Boolean o[3];
 251   mySupTrian.Edges( e[0], e[1], e[2],
 252                     o[0], o[1], o[2] );
 253
 254   aLoopEdges.Bind( e[0], Standard_True );
 255   aLoopEdges.Bind( e[1], Standard_True );
 256   aLoopEdges.Bind( e[2], Standard_True );
 257
 258   if ( theVertexIndexes.Length() > 0 )
 259   {
 260     // Creation of 3 trianglers with the first node and the edges of the super triangle:
 261     Standard_Integer anVertexIdx = theVertexIndexes.Lower();
 262     CreateTriangles( theVertexIndexes( anVertexIdx ), aLoopEdges );
 263
 264     // Add other nodes to the mesh
 265     CreateTrianglesOnNewVertices( theVertexIndexes );
 266   }
 267
 268   // Destruction of triangles containing a top of the super triangle
 269   BRepMesh_SelectorOfDataStructureOfDelaun aSelector( myMeshData );
 270   aSelector.NeighboursOfNode( mySupVert1 );
 271   aSelector.NeighboursOfNode( mySupVert2 );
 272   aSelector.NeighboursOfNode( mySupVert3 );
 273
 274   aLoopEdges.Clear();
 275   BRepMesh_MapOfInteger::Iterator aFreeTriangles( aSelector.Elements() );
 276   for ( ; aFreeTriangles.More(); aFreeTriangles.Next() )
 277     DeleteTriangle( aFreeTriangles.Key(), aLoopEdges );
 278
 279   // All edges that remain free are removed from aLoopEdges;
 280   // only the boundary edges of the triangulation remain there
 281   BRepMesh_MapOfIntegerInteger::Iterator aFreeEdges( aLoopEdges );
 282   for ( ; aFreeEdges.More(); aFreeEdges.Next() )
 283   {
 284     if ( myMeshData->ElemConnectedTo( aFreeEdges.Key() ).IsEmpty() )
 285       myMeshData->RemoveLink( aFreeEdges.Key() );
 286   }
 287
 288   // The tops of the super triangle are destroyed
 289   myMeshData->RemoveNode( mySupVert1 );
 290   myMeshData->RemoveNode( mySupVert2 );
 291   myMeshData->RemoveNode( mySupVert3 );
 292 }
 293
 294 //=======================================================================
 295 //function : CreateTriangles
 296 //purpose  : Creates the triangles beetween the node and the polyline.
 297 //=======================================================================
 298 void BRepMesh_Delaun::CreateTriangles ( const Standard_Integer theVertexIndex,
 299                                         BRepMesh_MapOfIntegerInteger& thePoly )
 300 {
 301   ListOfInteger aLoopEdges, anExternalEdges;
 302   const gp_XY& aVertexCoord = myMeshData->GetNode( theVertexIndex ).Coord();
 303
 304   BRepMesh_MapOfIntegerInteger::Iterator anEdges( thePoly );
 305   for ( ; anEdges.More(); anEdges.Next() )
 306   {
 307     const BRepMesh_Edge& anEdge = GetEdge( anEdges.Key() );
 308     Standard_Integer aFirstNode = anEdge.FirstNode();
 309     Standard_Integer aLastNode  = anEdge.LastNode();
 310     Standard_Boolean isPositive = (Standard_Boolean)thePoly( anEdges.Key() );
 311     if ( !isPositive )
 312     {
 313       Standard_Integer aTmp;
 314       aTmp       = aFirstNode;
 315       aFirstNode = aLastNode;
 316       aLastNode  = aTmp;
 317     }
 318
 319     const BRepMesh_Vertex& aFirstVertex = GetVertex( aFirstNode );
 320     const BRepMesh_Vertex& aLastVertex  = GetVertex( aLastNode  );
 321
 322     gp_XY aVEdge1, aVEdge2, aVEdge3;
 323     aVEdge1 = aFirstVertex.Coord();
 324     aVEdge1.Subtract( aVertexCoord );
 325
 326     aVEdge2 = aLastVertex.Coord();
 327     aVEdge2.Subtract( aFirstVertex.Coord() );
 328
 329     aVEdge3 = aVertexCoord;
 330     aVEdge3.Subtract( aLastVertex.Coord() );
 331
 332     Standard_Real aDist12 = 0., aDist23 = 0.;
 333     Standard_Real aV2Len  = aVEdge2.Modulus();
 334     if ( aV2Len > Precision::PConfusion() )
 335     {
 336       aVEdge2.SetCoord( aVEdge2.X() / aV2Len,
 337                         aVEdge2.Y() / aV2Len );
 338
 339       aDist12 = aVEdge1 ^ aVEdge2;
 340       aDist23 = aVEdge2 ^ aVEdge3;
 341     }
 342
 343     if ( Abs( aDist12 ) >= Precision::PConfusion() &&
 344          Abs( aDist23 ) >= Precision::PConfusion() )
 345     {
 346       Standard_Boolean isSensOK;
 347       if ( myPositiveOrientation )
 348         isSensOK = ( aDist12 > 0. && aDist23 > 0.);
 349       else
 350         isSensOK = ( aDist12 < 0. && aDist23 < 0.);
 351
 352       if ( isSensOK )
 353       {
 354         BRepMesh_Edge aNewEdge1 (theVertexIndex, aFirstNode, BRepMesh_Free);
 355         BRepMesh_Edge aNewEdge3 (aLastNode, theVertexIndex, BRepMesh_Free);
 356
 357         Standard_Integer iNewEdge1 = myMeshData->AddLink (aNewEdge1);
 358         Standard_Integer iNewEdge3 = myMeshData->AddLink (aNewEdge3);
 359
 360         BRepMesh_Triangle aNewTri (Abs (iNewEdge1), anEdges.Key(), Abs (iNewEdge3),
 361                                    (iNewEdge1 > 0), isPositive, (iNewEdge3 > 0),
 362                                    BRepMesh_Free);
 363         Standard_Integer iNewTri = myMeshData->AddElement(aNewTri);
 364
 365         Standard_Boolean isCircleCreated =
 366           myCircles.Add (aVertexCoord, aFirstVertex.Coord(), aLastVertex.Coord(), iNewTri);
 367
 368         if ( !isCircleCreated )
 369           myMeshData->RemoveElement (iNewTri);
 370       }
 371       else
 372       {
 373         if ( isPositive )
 374           aLoopEdges.Append(  anEdges.Key() );
 375         else
 376           aLoopEdges.Append( -anEdges.Key() );
 377
 378         if ( aVEdge1.SquareModulus() > aVEdge3.SquareModulus() )
 379         {
 380           BRepMesh_Edge aNewEdge (theVertexIndex, aFirstNode, BRepMesh_Free);
 381           Standard_Integer iNewEdge = myMeshData->AddLink(aNewEdge);
 382           anExternalEdges.Append (Abs (iNewEdge));
 383         }
 384         else
 385         {
 386           BRepMesh_Edge aNewEdge (aLastNode, theVertexIndex, BRepMesh_Free);
 387           Standard_Integer iNewEdge = myMeshData->AddLink (aNewEdge);
 388           anExternalEdges.Append (Abs (iNewEdge));
 389         }
 390       }
 391     }
 392   }
 393
 394   thePoly.Clear();
 395   while ( !anExternalEdges.IsEmpty() )
 396   {
 397     const BRepMesh_PairOfIndex& aPair =
 398       myMeshData->ElemConnectedTo( Abs( anExternalEdges.First() ) );
 399
 400
 401     if ( !aPair.IsEmpty() )
 402       DeleteTriangle( aPair.FirstIndex(), thePoly );
 403
 404     anExternalEdges.RemoveFirst();
 405   }
 406
 407   for ( anEdges.Initialize( thePoly ); anEdges.More(); anEdges.Next() )
 408   {
 409     if ( myMeshData->ElemConnectedTo( anEdges.Key() ).IsEmpty() )
 410       myMeshData->RemoveLink( anEdges.Key() );
 411   }
 412
 413   while ( !aLoopEdges.IsEmpty() )
 414   {
 415     const BRepMesh_Edge& anEdge = GetEdge( Abs( aLoopEdges.First() ) );
 416     if ( anEdge.Movability() != BRepMesh_Deleted )
 417     {
 418       Standard_Integer anEdgeIdx = aLoopEdges.First();
 419       MeshLeftPolygonOf( Abs( anEdgeIdx ), ( anEdgeIdx > 0 ) );
 420     }
 421
 422     aLoopEdges.RemoveFirst();
 423   }
 424 }
 425
 426 //=======================================================================
 427 //function : CreateTrianglesOnNewVertices
 428 //purpose  : Creation of triangles from the new nodes
 429 //=======================================================================
 430 void BRepMesh_Delaun::CreateTrianglesOnNewVertices( TColStd_Array1OfInteger& theVertexIndexes )
 431 {
 432   BRepMesh_MapOfIntegerInteger aLoopEdges( 10, myMeshData->Allocator() );
 433
 434   // Insertion of nodes :
 435   Standard_Boolean isModify = Standard_True;
 436
 437   Standard_Integer anIndex = theVertexIndexes.Lower();
 438   Standard_Integer anUpper = theVertexIndexes.Upper();
 439   for( ; anIndex <= anUpper; ++anIndex )
 440   {
 441     aLoopEdges.Clear();
 442
 443     Standard_Integer aVertexIdx = theVertexIndexes( anIndex );
 444     const BRepMesh_Vertex& aVertex = GetVertex( aVertexIdx );
 445
 446     // Iterator in the list of indexes of circles containing the node
 447     BRepMesh_ListOfInteger& aCirclesList = myCircles.Select( aVertex.Coord() );
 448
 449     Standard_Integer onEgdeId = 0, aTriangleId = 0;
 450     BRepMesh_ListOfInteger::Iterator aCircleIt( aCirclesList );
 451     for ( ; aCircleIt.More(); aCircleIt.Next() )
 452     {
 453       // To add a node in the mesh it is necessary to check conditions:
 454       // - the node should be within the boundaries of the mesh and so in an existing triangle
 455       // - all adjacent triangles should belong to a component connected with this triangle
 456       if ( Contains( aCircleIt.Value(), aVertex, onEgdeId ) )
 457       {
 458         if ( onEgdeId == 0 )
 459         {
 460           aTriangleId = aCircleIt.Value();
 461           aCirclesList.Remove( aCircleIt );
 462           break;
 463         }
 464         else if ( GetEdge( onEgdeId ).Movability() == BRepMesh_Free )
 465         {
 466           aTriangleId = aCircleIt.Value();
 467           aCirclesList.Remove( aCircleIt );
 468           break;
 469         }
 470       }
 471     }
 472
 473     if ( aTriangleId > 0 )
 474     {
 475       DeleteTriangle( aTriangleId, aLoopEdges );
 476
 477       isModify = Standard_True;
 478       while ( isModify && !aCirclesList.IsEmpty() )
 479       {
 480         isModify = Standard_False;
 481         BRepMesh_ListOfInteger::Iterator aCircleIt1( aCirclesList );
 482         for ( ; aCircleIt1.More(); aCircleIt1.Next() )
 483         {
 484           Standard_Integer e[3];
 485           Standard_Boolean o[3];
 486           GetTriangle( aCircleIt1.Value() ).Edges( e[0], e[1], e[2],
 487                                                    o[0], o[1], o[2] );
 488
 489           if ( aLoopEdges.IsBound( e[0] ) ||
 490                aLoopEdges.IsBound( e[1] ) ||
 491                aLoopEdges.IsBound( e[2] ) )
 492           {
 493             isModify = Standard_True;
 494             DeleteTriangle( aCircleIt1.Value(), aLoopEdges );
 495             aCirclesList.Remove( aCircleIt1 );
 496             break;
 497           }
 498         }
 499       }
 500
 501       // Creation of triangles with the current node and free edges
 502       // and removal of these edges from the list of free edges
 503       CreateTriangles( aVertexIdx, aLoopEdges );
 504     }
 505   }
 506   // Check that internal edges are not crossed by triangles
 507   BRepMesh_MapOfInteger::Iterator anInernalEdgesIt( InternalEdges() );
 508
 509   // Destruction of triancles intersecting internal edges
 510   // and their replacement by makeshift triangles
 511   anInernalEdgesIt.Reset();
 512   for ( ; anInernalEdgesIt.More(); anInernalEdgesIt.Next() )
 513   {
 514     Standard_Integer aNbC;
 515     aNbC = myMeshData->ElemConnectedTo( anInernalEdgesIt.Key() ).Extent();
 516     if ( aNbC == 0 )
 517     {
 518       MeshLeftPolygonOf( anInernalEdgesIt.Key(), Standard_True  );
 519       MeshLeftPolygonOf( anInernalEdgesIt.Key(), Standard_False );
 520     }
 521   }
 522
 523   // Adjustment of meshes to boundary edges
 524   FrontierAdjust();
 525 }
 526
 527 //=======================================================================
 528 //function : CleanupMesh
 529 //purpose  : Cleanup mesh from the free triangles
 530 //=======================================================================
 531 void BRepMesh_Delaun::CleanupMesh()
 532 {
 533   BRepMesh_MapOfIntegerInteger aLoopEdges( 10, myMeshData->Allocator() );
 534   ListOfInteger aTrianglesList;
 535
 536   for(;;)
 537   {
 538     aTrianglesList.Clear();
 539     aLoopEdges.Clear();
 540
 541     BRepMesh_MapOfInteger::Iterator aFreeEdgesIt( FreeEdges() );
 542     for ( ; aFreeEdgesIt.More(); aFreeEdgesIt.Next() )
 543     {
 544       const BRepMesh_Edge& anEdge = GetEdge( aFreeEdgesIt.Key() );
 545       if ( anEdge.Movability() != BRepMesh_Frontier )
 546       {
 547         Standard_Integer aFrontierNb = 0;
 548         if ( myMeshData->ElemConnectedTo( aFreeEdgesIt.Key() ).IsEmpty() )
 549           aLoopEdges.Bind( aFreeEdgesIt.Key(), Standard_True );
 550         else
 551         {
 552           BRepMesh_ListOfInteger::Iterator aConnectedLinksIt(
 553             myMeshData->LinkNeighboursOf( anEdge.FirstNode() ) );
 554
 555           for ( ; aConnectedLinksIt.More(); aConnectedLinksIt.Next() )
 556           {
 557             if ( GetEdge( aConnectedLinksIt.Value() ).Movability() == BRepMesh_Frontier )
 558             {
 559               aFrontierNb++;
 560               if ( aFrontierNb > 1 )
 561                 break;
 562             }
 563           }
 564
 565           if ( aFrontierNb == 2 )
 566           {
 567             const BRepMesh_PairOfIndex& aPair = myMeshData->ElemConnectedTo( aFreeEdgesIt.Key() );
 568             for ( Standard_Integer j = 1, jn = aPair.Extent(); j <= jn; ++j )
 569             {
 570               const Standard_Integer anElemId = aPair.Index(j);
 571               if ( anElemId < 0 )
 572                 continue;
 573
 574               Standard_Integer e[3];
 575               Standard_Boolean o[3];
 576               GetTriangle( anElemId ).Edges( e[0], e[1], e[2],
 577                                              o[0], o[1], o[2] );
 578
 579               Standard_Boolean isTriangleToDelete = Standard_True;
 580               for ( Standard_Integer k = 0; k < 3; ++k )
 581               {
 582                 if ( GetEdge( e[k] ).Movability() != BRepMesh_Free )
 583                 {
 584                   isTriangleToDelete = Standard_False;
 585                   break;
 586                 }
 587               }
 588
 589               if ( isTriangleToDelete )
 590                 aTrianglesList.Append( anElemId );
 591             }
 592           }
 593         }
 594       }
 595     }
 596
 597     // Destruction of triangles :
 598     Standard_Integer aDeletedTrianglesNb = 0;
 599     for ( ; !aTrianglesList.IsEmpty(); aTrianglesList.RemoveFirst() )
 600     {
 601       DeleteTriangle( aTrianglesList.First(), aLoopEdges );
 602       aDeletedTrianglesNb++;
 603     }
 604
 605     // Destruction of remaining hanging edges
 606     BRepMesh_MapOfIntegerInteger::Iterator aLoopEdgesIt( aLoopEdges );
 607     for ( ; aLoopEdgesIt.More(); aLoopEdgesIt.Next() )
 608     {
 609       if ( myMeshData->ElemConnectedTo( aLoopEdgesIt.Key() ).IsEmpty() )
 610         myMeshData->RemoveLink( aLoopEdgesIt.Key() );
 611     }
 612
 613     if ( aDeletedTrianglesNb == 0 )
 614       break;
 615   }
 616 }
 617
 618 //=======================================================================
 619 //function : FrontierAdjust
 620 //purpose  : Adjust the mesh on the frontier
 621 //=======================================================================
 622 void BRepMesh_Delaun::FrontierAdjust()
 623 {
 624   BRepMesh_MapOfIntegerInteger aLoopEdges( 10, myMeshData->Allocator() );
 625   ListOfInteger aTrianglesList;
 626
 627   for ( Standard_Integer aPass = 1; aPass <= 2; ++aPass )
 628   {
 629     // 1 pass): find external triangles on boundary edges
 630     // 2 pass): find external triangles on boundary edges
 631     // because in comlex curved boundaries external triangles can appear
 632     // after "mesh left aPolygonon"
 633
 634     BRepMesh_MapOfInteger::Iterator aFrontierIt( Frontier() );
 635     for ( ; aFrontierIt.More(); aFrontierIt.Next() )
 636     {
 637       const BRepMesh_PairOfIndex& aPair = myMeshData->ElemConnectedTo( aFrontierIt.Key() );
 638       for( Standard_Integer j = 1, jn = aPair.Extent(); j <= jn; ++j )
 639       {
 640         const Standard_Integer aPriorElemId = aPair.Index(j);
 641         if( aPriorElemId < 0 )
 642             continue;
 643
 644         Standard_Integer e[3];
 645         Standard_Boolean o[3];
 646         GetTriangle( aPriorElemId ).Edges( e[0], e[1], e[2],
 647                                            o[0], o[1], o[2] );
 648
 649         for ( Standard_Integer n = 0; n < 3; ++n )
 650         {
 651           if ( aFrontierIt.Key() == e[n] && !o[n] )
 652           {
 653             aTrianglesList.Append( aPriorElemId );
 654             break;
 655           }
 656         }
 657       }
 658     }
 659
 660     // destruction  of external triangles on boundary edges
 661     for ( ; !aTrianglesList.IsEmpty(); aTrianglesList.RemoveFirst() )
 662       DeleteTriangle( aTrianglesList.First(), aLoopEdges );
 663
 664     // destrucrion of remaining hanging edges :
 665     BRepMesh_MapOfIntegerInteger::Iterator aLoopEdgesIt( aLoopEdges );
 666     for ( ; aLoopEdgesIt.More(); aLoopEdgesIt.Next() )
 667     {
 668       if (myMeshData->ElemConnectedTo( aLoopEdgesIt.Key() ).IsEmpty() )
 669         myMeshData->RemoveLink( aLoopEdgesIt.Key() );
 670     }
 671
 672
 673     // destruction of triangles crossing the boundary edges and
 674     // their replacement by makeshift triangles
 675     if ( aPass == 1 )
 676       aFrontierIt.Reset();
 677     else
 678       // in some cases there remain unused boundaries check
 679       aFrontierIt.Initialize( Frontier() );
 680
 681     NCollection_Vector<Bnd_Box2d> aFrontBoxes;
 682     for ( ; aFrontierIt.More(); aFrontierIt.Next() )
 683     {
 684       const BRepMesh_Edge& anEdge = GetEdge( aFrontierIt.Key() );
 685       const BRepMesh_Vertex& aV1  = GetVertex( anEdge.FirstNode() );
 686       const BRepMesh_Vertex& aV2  = GetVertex( anEdge.LastNode()  );
 687       fillBndBox( aFrontBoxes, aV1, aV2 );
 688
 689       if ( myMeshData->ElemConnectedTo( aFrontierIt.Key() ).IsEmpty() )
 690         MeshLeftPolygonOf( aFrontierIt.Key(), Standard_True );
 691     }
 692
 693     if ( aPass == 1 )
 694       continue;
 695
 696     CleanupMesh();
 697   }
 698 }
 699
 700 //=======================================================================
 701 //function : KillInternalTriangles
 702 //purpose  : Removes triangles within polygon
 703 //=======================================================================
 704 void BRepMesh_Delaun::KillInternalTriangles( Standard_Integer theEdgeId,
 705                                              const TColStd_MapOfInteger& theIgnoredEdges,
 706                                              BRepMesh_MapOfIntegerInteger& theLoopEdges )
 707 {
 708   if ( theIgnoredEdges.Contains( theEdgeId ) )
 709     return;
 710
 711   const BRepMesh_PairOfIndex& aPair = myMeshData->ElemConnectedTo( theEdgeId );
 712   for ( Standard_Integer i = 1; i <= aPair.Extent(); ++i )
 713   {
 714     Standard_Integer anElemId = aPair.Index(i);
 715     if( anElemId < 0 )
 716       continue;
 717
 718     Standard_Integer e[3];
 719     Standard_Boolean o[3];
 720     GetTriangle( anElemId ).Edges( e[0], e[1], e[2],
 721                                    o[0], o[1], o[2] );
 722
 723     for ( Standard_Integer anIndex = 0; anIndex < 3; ++anIndex )
 724     {
 725       if ( e[anIndex] == theEdgeId )
 726       {
 727         DeleteTriangle( anElemId, theLoopEdges );
 728         for ( Standard_Integer n = 0; n < 2; ++n )
 729         {
 730           Standard_Integer aCurEdge = e[(anIndex + n + 1) % 3];
 731           KillInternalTriangles( aCurEdge, theIgnoredEdges, theLoopEdges );
 732         }
 733       }
 734     }
 735   }
 736 }
 737
 738 //=======================================================================
 739 //function : RemovePivotTriangles
 740 //purpose  : Removes triangles around the given pivot node
 741 //=======================================================================
 742 void BRepMesh_Delaun::RemovePivotTriangles( const Standard_Integer theEdgeInfo,
 743                                             const Standard_Integer thePivotNode,
 744                                             TColStd_MapOfInteger& theInfectedEdges,
 745                                             BRepMesh_MapOfIntegerInteger& theLoopEdges,
 746                                             const Standard_Boolean isFirstPass )
 747 {
 748   Standard_Integer e[3];
 749   Standard_Boolean o[3];
 750   Standard_Integer aGeneralEdgeId = -1;
 751
 752   Standard_Integer anMainEdgeId = Abs( theEdgeInfo );
 753   Standard_Boolean anIsForward = theEdgeInfo > 0;
 754   const BRepMesh_PairOfIndex& aPair = myMeshData->ElemConnectedTo( anMainEdgeId );
 755   for ( Standard_Integer j = 1, jn = aPair.Extent(); j <= jn; ++j )
 756   {
 757     Standard_Integer anElemId = aPair.Index(j);
 758     if( anElemId < 0 )
 759       continue;
 760
 761     GetTriangle( anElemId ).Edges( e[0], e[1], e[2],
 762                                    o[0], o[1], o[2] );
 763
 764     for ( Standard_Integer anIndex = 0; anIndex < 3; ++anIndex )
 765     {
 766       if ( e[anIndex] == anMainEdgeId && o[anIndex] == anIsForward )
 767       {
 768         // triangle detected
 769         DeleteTriangle( anElemId, theLoopEdges );
 770         aGeneralEdgeId = anIndex;
 771         break;
 772       }
 773     }
 774
 775     if ( aGeneralEdgeId != -1 )
 776       break;
 777   }
 778
 779   if ( aGeneralEdgeId != -1 )
 780   {
 781     // delete triangles around of aPivotNode starting from the bounding one
 782     // define edge connected to vertes
 783     Standard_Integer anEdgeId = -1;
 784     for ( Standard_Integer i = 0; i < 2; ++i )
 785     {
 786       Standard_Integer aTmpEdgeId = e[(aGeneralEdgeId + i + 1) % 3];
 787       const BRepMesh_Edge& anEdge = GetEdge( aTmpEdgeId );
 788       if ( anEdge.FirstNode() == thePivotNode ||
 789            anEdge.LastNode()  == thePivotNode )
 790       {
 791         anEdgeId = aTmpEdgeId;
 792       }
 793
 794       if ( theInfectedEdges.Contains( aTmpEdgeId ) )
 795         theInfectedEdges.Remove( aTmpEdgeId );
 796       else
 797         theInfectedEdges.Add( aTmpEdgeId );
 798     }
 799
 800     if ( isFirstPass )
 801       return;
 802
 803     while ( anEdgeId > 0 )
 804     {
 805       const BRepMesh_PairOfIndex& aFreePair = myMeshData->ElemConnectedTo( anEdgeId );
 806       Standard_Integer anOldEdge = anEdgeId;
 807       anEdgeId = -1;
 808
 809       for ( Standard_Integer aPairIndex = 1; aPairIndex <= aFreePair.Extent(); ++aPairIndex )
 810       {
 811         Standard_Integer anElemId = aFreePair.Index( aPairIndex );
 812         if( anElemId < 0 )
 813           continue;
 814
 815         Standard_Integer e1[3];
 816         Standard_Boolean o1[3];
 817         GetTriangle( anElemId ).Edges( e1[0], e1[1], e1[2],
 818                                        o1[0], o1[1], o1[2] );
 819
 820         DeleteTriangle( anElemId, theLoopEdges );
 821
 822         for ( Standard_Integer i = 0; i < 3; ++i )
 823         {
 824           if ( e1[i] == anOldEdge )
 825           {
 826             for ( Standard_Integer j = 0; j < 2; ++j )
 827             {
 828               Standard_Integer aTmpEdgeId = e1[(j + i + 1) % 3];
 829               const BRepMesh_Edge& anEdge = GetEdge( aTmpEdgeId );
 830               if ( anEdge.FirstNode() == thePivotNode ||
 831                    anEdge.LastNode()  == thePivotNode )
 832               {
 833                 anEdgeId = aTmpEdgeId;
 834               }
 835
 836               if ( theInfectedEdges.Contains( aTmpEdgeId ) )
 837                 theInfectedEdges.Remove( aTmpEdgeId );
 838               else
 839                 theInfectedEdges.Add( aTmpEdgeId );
 840             }
 841             break;
 842           }
 843         }
 844       }
 845     }
 846   }
 847 }
 848
 849 //=======================================================================
 850 //function : CleanupPolygon
 851 //purpose  : Remove internal triangles from the given polygon
 852 //=======================================================================
 853 void BRepMesh_Delaun::CleanupPolygon( const TColStd_SequenceOfInteger& thePolygon,
 854                                       TColStd_MapOfInteger& theInfectedEdges,
 855                                       BRepMesh_MapOfIntegerInteger& theLoopEdges )
 856 {
 857   Standard_Integer aPolyLen = thePolygon.Length();
 858
 859   TColStd_MapOfInteger anIgnoredEdges;
 860   NCollection_Map<Standard_Integer> aPolyVertices;
 861   for ( Standard_Integer i = 1; i <= aPolyLen; ++i )
 862   {
 863     Standard_Integer aPolyEdgeId = Abs( thePolygon(i) );
 864     anIgnoredEdges.Add( aPolyEdgeId );
 865
 866     const BRepMesh_Edge& aPolyEdge = GetEdge( aPolyEdgeId );
 867     aPolyVertices.Add( aPolyEdge.FirstNode() );
 868     aPolyVertices.Add( aPolyEdge.LastNode() );
 869
 870     if ( theInfectedEdges.Contains( aPolyEdgeId ) )
 871       theInfectedEdges.Remove( aPolyEdgeId );
 872   }
 873
 874   Standard_Real aRefTotalAngle = 2 * M_PI;
 875   TColStd_MapIteratorOfMapOfInteger anInfectedIt( theInfectedEdges );
 876   for ( ; anInfectedIt.More(); anInfectedIt.Next() )
 877   {
 878     Standard_Integer anEdgeId = anInfectedIt.Key();
 879     const BRepMesh_Edge& anInfectedEdge = GetEdge( anEdgeId );
 880     Standard_Integer anEdgeVertices[2] = { anInfectedEdge.FirstNode(),
 881                                            anInfectedEdge.LastNode() };
 882
 883     Standard_Boolean isToExclude = Standard_False;
 884     for ( Standard_Integer i = 0; i < 2; ++i )
 885     {
 886       Standard_Integer aCurVertex = anEdgeVertices[i];
 887       if ( aPolyVertices.Contains( aCurVertex ) )
 888         continue;
 889
 890       gp_XY aCenterPointXY = GetVertex( aCurVertex ).Coord();
 891       Standard_Real aTotalAng = 0.0;
 892
 893       for ( Standard_Integer i = 1; i <= aPolyLen; ++i )
 894       {
 895         Standard_Integer aPolyEdgeId = thePolygon(i);
 896         const BRepMesh_Edge& aPolyEdge = GetEdge( Abs( aPolyEdgeId ) );
 897         Standard_Integer aStartPoint, anEndPoint;
 898         if ( aPolyEdgeId >= 0 )
 899         {
 900           aStartPoint = aPolyEdge.FirstNode();
 901           anEndPoint  = aPolyEdge.LastNode();
 902         }
 903         else
 904         {
 905           aStartPoint = aPolyEdge.LastNode();
 906           anEndPoint  = aPolyEdge.FirstNode();
 907         }
 908
 909         gp_XY aStartV = GetVertex( aStartPoint ).Coord() - aCenterPointXY;
 910         gp_XY anEndV  = GetVertex( anEndPoint ).Coord()  - aCenterPointXY;
 911
 912         Standard_Real anAngle = gp_Vec2d( anEndV ).Angle( gp_Vec2d( aStartV ) );
 913         aTotalAng += anAngle;
 914       }
 915
 916       if ( Abs( aRefTotalAngle - aTotalAng ) > Precision::Angular() )
 917         isToExclude = Standard_True;
 918     }
 919
 920     if ( isToExclude )
 921       anIgnoredEdges.Add( anEdgeId );
 922   }
 923
 924
 925   anInfectedIt.Initialize( theInfectedEdges );
 926   for ( ; anInfectedIt.More(); anInfectedIt.Next() )
 927   {
 928     Standard_Integer anEdgeId = anInfectedIt.Key();
 929     KillInternalTriangles( anEdgeId, anIgnoredEdges, theLoopEdges);
 930   }
 931
 932   BRepMesh_MapOfIntegerInteger::Iterator aLoopEdgesIt( theLoopEdges );
 933   for ( ; aLoopEdgesIt.More(); aLoopEdgesIt.Next() )
 934   {
 935     if ( myMeshData->ElemConnectedTo( aLoopEdgesIt.Key() ).IsEmpty() )
 936       myMeshData->RemoveLink( aLoopEdgesIt.Key() );
 937   }
 938 }
 939
 940 //=======================================================================
 941 //function : MeshLeftPolygonOf
 942 //purpose  : Triangulation of the aPolygonon to the left of <theEdgeIndex>.(material side)
 943 //=======================================================================
 944 void BRepMesh_Delaun::MeshLeftPolygonOf( const Standard_Integer theEdgeIndex,
 945                                          const Standard_Boolean isForward )
 946 {
 947   const BRepMesh_Edge& anEdge = GetEdge( theEdgeIndex );
 948   NCollection_Map<Standard_Integer> aDealLinks;
 949   TColStd_SequenceOfInteger aPolygon;
 950   BRepMesh_MapOfIntegerInteger aLoopEdges( 10, myMeshData->Allocator() );
 951   TColStd_MapOfInteger anUsedEdges;
 952   TColStd_MapOfInteger anInfectedEdges;
 953
 954   // Find the aPolygonon
 955   anUsedEdges.Add( theEdgeIndex );
 956   Standard_Integer aFirstNode, aStartNode, aPivotNode;
 957
 958   if ( isForward )
 959   {
 960     aPolygon.Append( theEdgeIndex );
 961     aStartNode = anEdge.FirstNode();
 962     aPivotNode = anEdge.LastNode();
 963   }
 964   else
 965   {
 966     aPolygon.Append( -theEdgeIndex );
 967     aStartNode = anEdge.LastNode();
 968     aPivotNode = anEdge.FirstNode();
 969   }
 970   aFirstNode = aStartNode;
 971
 972   const BRepMesh_Vertex& aStartVertex = GetVertex( aFirstNode );
 973   const BRepMesh_Vertex& anEndVertex  = GetVertex( aPivotNode );
 974
 975   Standard_Integer aRefOtherNode = 0, anOtherNode = 0;
 976   // Check the presence of the previous edge <theEdgeIndex> :
 977   BRepMesh_ListOfInteger::Iterator aLinkIt( myMeshData->LinkNeighboursOf( aStartNode ) );
 978   for ( ; aLinkIt.More(); aLinkIt.Next() )
 979   {
 980     if ( aLinkIt.Value() != theEdgeIndex )
 981     {
 982       const BRepMesh_Edge& aNextEdge = GetEdge( aLinkIt.Value() );
 983       anOtherNode = aNextEdge.LastNode();
 984       if ( anOtherNode == aStartNode )
 985         anOtherNode = aNextEdge.FirstNode();
 986       break;
 987     }
 988   }
 989   if ( anOtherNode == 0 )
 990     return;
 991
 992
 993   gp_XY aVEdge( anEndVertex.Coord() );
 994   aVEdge.Subtract( aStartVertex.Coord() );
 995   gp_XY aPrevVEdge( aVEdge );
 996   gp_XY aRefCurrVEdge, aCurrVEdge;
 997
 998   Standard_Integer aCurrEdgeId = theEdgeIndex;
 999   Standard_Integer aNextEdgeId;
1000
1001   // Find the nearest to <theEdgeIndex> closed aPolygonon :
1002   Standard_Boolean isInMesh, isNotInters;
1003   Standard_Real anAngle, aRefAngle;
1004
1005   NCollection_Vector <Bnd_Box2d> aBoxes;
1006   fillBndBox( aBoxes, aStartVertex, anEndVertex );
1007
1008   while ( aPivotNode != aFirstNode )
1009   {
1010     aNextEdgeId = 0;
1011     if ( myPositiveOrientation )
1012       aRefAngle = RealFirst();
1013     else
1014       aRefAngle = RealLast();
1015
1016     const BRepMesh_Vertex& aPivotVertex = GetVertex( aPivotNode );
1017
1018     // Find the next edge with the greatest angle with <theEdgeIndex>
1019     // and non intersecting <theEdgeIndex> :
1020
1021     aLinkIt.Init( myMeshData->LinkNeighboursOf( aPivotNode ) );
1022     for ( ; aLinkIt.More(); aLinkIt.Next() )
1023     {
1024       Standard_Integer aNextLink = aLinkIt.Value();
1025       Standard_Integer aNextLinkId = Abs( aNextLink );
1026       if ( aDealLinks.Contains( aNextLinkId ) )
1027         continue;
1028
1029       if ( aNextLinkId != aCurrEdgeId )
1030       {
1031         isNotInters = Standard_True;
1032         const BRepMesh_Edge& aNextEdge = GetEdge( aNextLinkId );
1033
1034         isInMesh = Standard_True;
1035
1036         //define if link exist in mesh
1037         if ( aNextEdge.Movability() == BRepMesh_Free )
1038         {
1039           if ( myMeshData->ElemConnectedTo( aLinkIt.Value() ).IsEmpty() )
1040             isInMesh = Standard_False;
1041         }
1042
1043         if ( isInMesh )
1044         {
1045           anOtherNode = aNextEdge.FirstNode();
1046           if ( anOtherNode == aPivotNode )
1047             anOtherNode = aNextEdge.LastNode();
1048
1049           aCurrVEdge = GetVertex( anOtherNode ).Coord();
1050           aCurrVEdge.Subtract( aPivotVertex.Coord() );
1051
1052           if ( aCurrVEdge.Modulus() >= gp::Resolution() &&
1053                aPrevVEdge.Modulus() >= gp::Resolution() )
1054           {
1055             anAngle = gp_Vec2d( aPrevVEdge ).Angle( gp_Vec2d( aCurrVEdge ) );
1056
1057             if ( ( myPositiveOrientation && anAngle > aRefAngle ) ||
1058                 ( !myPositiveOrientation && anAngle < aRefAngle ) )
1059             {
1060               Bnd_Box2d aBox;
1061               aBox.Add( gp_Pnt2d( GetVertex( aNextEdge.FirstNode() ).Coord() ) );
1062               aBox.Add( gp_Pnt2d( GetVertex( aNextEdge.LastNode()  ).Coord() ) );
1063
1064               for ( Standard_Integer k = 0, aLen = aPolygon.Length(); k < aLen; ++k )
1065               {
1066                 if ( !aBox.IsOut( aBoxes.Value( k ) ) )
1067                 {
1068                   // intersection is possible...
1069                   if ( IntSegSeg( aNextEdge, GetEdge( Abs( aPolygon( k + 1 ) ) ) ) )
1070                   {
1071                     isNotInters = Standard_False;
1072                     break;
1073                   }
1074                 }
1075               }
1076
1077               if( isNotInters )
1078               {
1079                 aRefAngle = anAngle;
1080                 aRefCurrVEdge = aCurrVEdge;
1081
1082                 if ( aNextEdge.FirstNode() == aPivotNode )
1083                   aNextEdgeId =  aLinkIt.Value();
1084                 else
1085                   aNextEdgeId = -aLinkIt.Value();
1086
1087                 aRefOtherNode = anOtherNode;
1088               }
1089             }
1090           }
1091         }
1092       }
1093     }
1094     if ( aNextEdgeId != 0 )
1095     {
1096       if ( Abs( aNextEdgeId ) != theEdgeIndex && Abs( aNextEdgeId ) != aCurrEdgeId )
1097       {
1098         aCurrEdgeId = Abs( aNextEdgeId );
1099
1100         if ( !anUsedEdges.Add( aCurrEdgeId ) )
1101         {
1102           //if this edge has already been added to the aPolygon,
1103           //there is a risk of looping (attention to open contours)
1104           //remove last edge and continue
1105
1106           aDealLinks.Add( aCurrEdgeId );
1107
1108           //roll back
1109           continue;
1110         }
1111
1112         aPolygon.Append( aNextEdgeId );
1113
1114         const BRepMesh_Edge& aCurrEdge = GetEdge( aCurrEdgeId );
1115         Standard_Integer aVert1 = aCurrEdge.FirstNode();
1116         Standard_Integer aVert2 = aCurrEdge.LastNode();
1117         fillBndBox( aBoxes, GetVertex( aVert1 ), GetVertex( aVert2 ) );
1118
1119         RemovePivotTriangles( aNextEdgeId, aPivotNode,
1120           anInfectedEdges, aLoopEdges, (aPolygon.Length() == 2) );
1121       }
1122     }
1123     else
1124     {
1125       //hanging end
1126       if ( aPolygon.Length() == 1 )
1127         return;
1128
1129       Standard_Integer aDeadEdgeId = Abs( aPolygon.Last() );
1130
1131       aDealLinks.Add( aDeadEdgeId );
1132
1133       anUsedEdges.Remove( aDeadEdgeId );
1134       aPolygon.Remove( aPolygon.Length() );
1135
1136       // return to previous point
1137       Standard_Integer aLastValidEdge = aPolygon.Last();
1138       const BRepMesh_Edge& aLastEdge = GetEdge( Abs( aLastValidEdge ) );
1139
1140       if( aLastValidEdge > 0 )
1141       {
1142         aStartNode = aLastEdge.FirstNode();
1143         aPivotNode = aLastEdge.LastNode();
1144       }
1145       else
1146       {
1147         aStartNode = aLastEdge.LastNode();
1148         aPivotNode = aLastEdge.FirstNode();
1149       }
1150
1151       const BRepMesh_Vertex& dV = GetVertex( aStartNode );
1152       const BRepMesh_Vertex& fV = GetVertex( aPivotNode );
1153       aPrevVEdge = fV.Coord() - dV.Coord();
1154       continue;
1155     }
1156
1157     aStartNode = aPivotNode;
1158     aPivotNode = aRefOtherNode;
1159     aPrevVEdge = aRefCurrVEdge;
1160   }
1161
1162   CleanupPolygon( aPolygon, anInfectedEdges, aLoopEdges );
1163   MeshPolygon( aPolygon );
1164 }
1165
1166 //=======================================================================
1167 //function : MeshPolygon
1168 //purpose  : Triangulatiion of a closed aPolygonon described by the list of indexes of
1169 //           its edges in the structure. (negative index == reversed)
1170 //=======================================================================
1171 void BRepMesh_Delaun::MeshPolygon( TColStd_SequenceOfInteger& thePoly )
1172 {
1173   Standard_Integer aPivotNode, aVertex3 = 0;
1174   Standard_Integer aFirstNode, aLastNode;
1175   Standard_Integer aTriId;
1176
1177   if ( thePoly.Length() == 3 )
1178   {
1179     aTriId = myMeshData->AddElement( BRepMesh_Triangle(
1180       Abs( thePoly(1) ), Abs( thePoly(2) ), Abs( thePoly(3) ),
1181       thePoly(1) > 0,    thePoly(2) > 0,    thePoly(3) > 0,
1182       BRepMesh_Free ) );
1183
1184     myCircles.MocAdd( aTriId );
1185     const BRepMesh_Edge& anEdge1 = GetEdge( Abs( thePoly(1) ) );
1186     const BRepMesh_Edge& anEdge2 = GetEdge( Abs( thePoly(2) ) );
1187
1188     if ( thePoly(1) > 0)
1189     {
1190       aFirstNode = anEdge1.FirstNode();
1191       aLastNode  = anEdge1.LastNode();
1192     }
1193     else
1194     {
1195       aFirstNode = anEdge1.LastNode();
1196       aLastNode  = anEdge1.FirstNode();
1197     }
1198
1199     if ( thePoly(2) > 0 )
1200       aVertex3 = anEdge2.LastNode();
1201     else
1202       aVertex3 = anEdge2.FirstNode();
1203
1204     Standard_Boolean isAdded = myCircles.Add( GetVertex( aFirstNode ).Coord(),
1205       GetVertex( aLastNode ).Coord(), GetVertex( aVertex3 ).Coord(), aTriId );
1206
1207     if ( !isAdded )
1208       myMeshData->RemoveElement( aTriId );
1209   }
1210   else if ( thePoly.Length() > 3 )
1211   {
1212     NCollection_Vector <Bnd_Box2d> aBoxes;
1213     Standard_Integer aPolyIdx, aUsedIdx = 0;
1214     Standard_Integer aPolyLen = thePoly.Length();
1215
1216     for ( aPolyIdx = 1; aPolyIdx <= aPolyLen; ++aPolyIdx )
1217     {
1218       const BRepMesh_Edge& anEdge = GetEdge( Abs( thePoly( aPolyIdx ) ) );
1219       aFirstNode = anEdge.FirstNode();
1220       aLastNode  = anEdge.LastNode();
1221       fillBndBox( aBoxes, GetVertex( aFirstNode ), GetVertex( aLastNode ) );
1222     }
1223
1224     const BRepMesh_Edge& anEdge = GetEdge( Abs( thePoly(1) ) );
1225     Standard_Real aMinDist = RealLast();
1226
1227     if ( thePoly(1) > 0 )
1228     {
1229       aFirstNode = anEdge.FirstNode();
1230       aLastNode  = anEdge.LastNode();
1231     }
1232     else
1233     {
1234       aFirstNode = anEdge.LastNode();
1235       aLastNode  = anEdge.FirstNode();
1236     }
1237
1238     gp_XY aVEdge( GetVertex( aLastNode  ).Coord() -
1239                   GetVertex( aFirstNode ).Coord() );
1240
1241     Standard_Real aVEdgeLen = aVEdge.Modulus();
1242     if ( aVEdgeLen > 0.)
1243     {
1244       aVEdge.SetCoord( aVEdge.X() / aVEdgeLen,
1245                        aVEdge.Y() / aVEdgeLen );
1246
1247       for ( aPolyIdx = 3; aPolyIdx <= aPolyLen; ++aPolyIdx )
1248       {
1249         const BRepMesh_Edge& aNextEdge = GetEdge( Abs( thePoly( aPolyIdx ) ) );
1250         if ( thePoly( aPolyIdx ) > 0)
1251           aPivotNode = aNextEdge.FirstNode();
1252         else
1253           aPivotNode = aNextEdge.LastNode();
1254
1255         gp_XY aVEdgePivot( GetVertex( aPivotNode ).Coord() -
1256                            GetVertex( aLastNode  ).Coord() );
1257
1258         Standard_Real aDist = aVEdge ^ aVEdgePivot;
1259         if ( Abs( aDist ) > Precision::PConfusion() )
1260         {
1261           if ( ( aDist > 0. &&  myPositiveOrientation ) ||
1262                ( aDist < 0. && !myPositiveOrientation ) )
1263           {
1264             if ( Abs( aDist ) < aMinDist )
1265             {
1266               Bnd_Box2d aBoxFirst, aBoxLast;
1267               aBoxFirst.Add( gp_Pnt2d( GetVertex( aPivotNode ).Coord() ) );
1268               aBoxFirst.Add( gp_Pnt2d( GetVertex( aLastNode  ).Coord() ) );
1269
1270               aBoxLast.Add( gp_Pnt2d( GetVertex( aPivotNode ).Coord() ) );
1271               aBoxLast.Add( gp_Pnt2d( GetVertex( aFirstNode ).Coord() ) );
1272
1273               BRepMesh_Edge aCheckE1( aLastNode,  aPivotNode, BRepMesh_Free );
1274               BRepMesh_Edge aCheckE2( aFirstNode, aPivotNode, BRepMesh_Free );
1275
1276               Standard_Boolean isIntersect = Standard_False;
1277               for ( Standard_Integer aPolyIdx1 = 2; aPolyIdx1 <= aPolyLen; ++aPolyIdx1 )
1278               {
1279                 if( aPolyIdx1 == aPolyIdx )
1280                   continue;
1281
1282                 const BRepMesh_Edge& aNextEdge1 = GetEdge( Abs( thePoly( aPolyIdx1 ) ) );
1283                 if ( !aBoxFirst.IsOut( aBoxes.Value( aPolyIdx1 - 1 ) ) )
1284                 {
1285                   // intersection is possible...
1286                   if( IntSegSeg( aCheckE1, aNextEdge1 ) )
1287                   {
1288                     isIntersect = Standard_True;
1289                     break;
1290                   }
1291                 }
1292
1293                 if ( !aBoxLast.IsOut( aBoxes.Value( aPolyIdx1 - 1 ) ) &&
1294                      !aCheckE2.IsEqual( aNextEdge1 ) )
1295                 {
1296                   // intersection is possible...
1297                   if( IntSegSeg( aCheckE2, aNextEdge1 ) )
1298                   {
1299                     isIntersect = Standard_True;
1300                     break;
1301                   }
1302                 }
1303               }
1304
1305               if( !isIntersect )
1306               {
1307                 aMinDist = aDist;
1308                 aVertex3 = aPivotNode;
1309                 aUsedIdx = aPolyIdx;
1310               }
1311             }
1312           }
1313         }
1314       }
1315     }
1316
1317     Standard_Integer aNewEdge2, aNewEdge3;
1318     if ( aMinDist < RealLast() )
1319     {
1320       aNewEdge2 = myMeshData->AddLink( BRepMesh_Edge( aLastNode, aVertex3,   BRepMesh_Free ) );
1321       aNewEdge3 = myMeshData->AddLink( BRepMesh_Edge( aVertex3,  aFirstNode, BRepMesh_Free ) );
1322       aTriId    = myMeshData->AddElement( BRepMesh_Triangle(
1323         Abs( thePoly(1) ), Abs( aNewEdge2 ), Abs( aNewEdge3 ),
1324         thePoly(1) > 0,    aNewEdge2 > 0,    aNewEdge3 > 0,
1325         BRepMesh_Free ) );
1326
1327       Standard_Boolean isAdded = myCircles.Add( GetVertex( aFirstNode ).Coord(),
1328         GetVertex( aLastNode ).Coord(), GetVertex( aVertex3 ).Coord(), aTriId );
1329
1330       if ( !isAdded )
1331         myMeshData->RemoveElement( aTriId );
1332
1333       if ( aUsedIdx < aPolyLen )
1334       {
1335         TColStd_SequenceOfInteger aSuitePoly;
1336         thePoly.Split( aUsedIdx, aSuitePoly );
1337         aSuitePoly.Prepend( -aNewEdge3 );
1338         MeshPolygon( aSuitePoly );
1339       }
1340       else
1341         thePoly.Remove( aPolyLen );
1342
1343       if ( aUsedIdx > 3 )
1344       {
1345         thePoly.SetValue( 1, -aNewEdge2 );
1346         MeshPolygon( thePoly );
1347       }
1348     }
1349   }
1350 }
1351
1352 //=======================================================================
1353 //function : RemoveVertex
1354 //purpose  : Removes a vertex from the triangulation
1355 //=======================================================================
1356 void  BRepMesh_Delaun::RemoveVertex( const BRepMesh_Vertex& theVertex )
1357 {
1358   BRepMesh_SelectorOfDataStructureOfDelaun aSelector( myMeshData );
1359   aSelector.NeighboursOf( theVertex );
1360
1361   BRepMesh_MapOfIntegerInteger aLoopEdges( 10, myMeshData->Allocator() );
1362
1363   // Loop on triangles to be destroyed :
1364   BRepMesh_MapOfInteger::Iterator aTriangleIt( aSelector.Elements() );
1365   for ( ; aTriangleIt.More(); aTriangleIt.Next() )
1366     DeleteTriangle( aTriangleIt.Key(), aLoopEdges );
1367
1368   TColStd_SequenceOfInteger aPolygon;
1369   Standard_Integer aLoopEdgesCount = aLoopEdges.Extent();
1370   BRepMesh_MapOfIntegerInteger::Iterator aLoopEdgesIt( aLoopEdges );
1371
1372   if ( aLoopEdgesIt.More() )
1373   {
1374     const BRepMesh_Edge& anEdge = GetEdge( aLoopEdgesIt.Key() );
1375     Standard_Integer aFirstNode = anEdge.FirstNode();
1376     Standard_Integer aLastNode;
1377     Standard_Integer aPivotNode = anEdge.LastNode();
1378     Standard_Integer anEdgeId   = aLoopEdgesIt.Key();
1379
1380     Standard_Boolean isPositive = (Standard_Boolean)aLoopEdges( anEdgeId );
1381     if ( !isPositive )
1382     {
1383       Standard_Integer aTmp;
1384       aTmp       = aFirstNode;
1385       aFirstNode = aPivotNode;
1386       aPivotNode = aTmp;
1387
1388       aPolygon.Append( -anEdgeId );
1389     }
1390     else
1391       aPolygon.Append( anEdgeId );
1392
1393     aLoopEdges.UnBind( anEdgeId );
1394
1395     aLastNode = aFirstNode;
1396     while ( aPivotNode != aLastNode )
1397     {
1398       BRepMesh_ListOfInteger::Iterator aLinkIt( myMeshData->LinkNeighboursOf( aPivotNode ) );
1399       for ( ; aLinkIt.More(); aLinkIt.Next() )
1400       {
1401         if ( aLinkIt.Value() != anEdgeId &&
1402              aLoopEdges.IsBound( aLinkIt.Value() ) )
1403         {
1404           Standard_Integer aCurrentNode;
1405           anEdgeId = aLinkIt.Value();
1406           const BRepMesh_Edge& anEdge1 = GetEdge( anEdgeId );
1407
1408           aCurrentNode = anEdge1.LastNode();
1409           if ( aCurrentNode != aPivotNode )
1410           {
1411             aCurrentNode = anEdge1.FirstNode();
1412             aPolygon.Append( -anEdgeId );
1413           }
1414           else
1415             aPolygon.Append( anEdgeId );
1416
1417           aPivotNode = aCurrentNode;
1418           aLoopEdges.UnBind( anEdgeId );
1419           break;
1420         }
1421       }
1422
1423       if ( aLoopEdgesCount <= 0 )
1424         break;
1425       --aLoopEdgesCount;
1426     }
1427
1428     MeshPolygon( aPolygon );
1429   }
1430 }
1431
1432
1433 //=======================================================================
1434 //function : AddVertices
1435 //purpose  : Adds some vertices in the triangulation.
1436 //=======================================================================
1437 void  BRepMesh_Delaun::AddVertices( BRepMesh_Array1OfVertexOfDelaun& theVertices )
1438 {
1439   BRepMesh_HeapSortVertexOfDelaun::Sort( theVertices,
1440     BRepMesh_ComparatorOfVertexOfDelaun( SortingDirection, Precision::PConfusion() ) );
1441
1442   Standard_Integer aLower  = theVertices.Lower();
1443   Standard_Integer anUpper = theVertices.Upper();
1444
1445   TColStd_Array1OfInteger aVertexIndexes( aLower, anUpper );
1446   for ( Standard_Integer i = aLower; i <= anUpper; ++i )
1447     aVertexIndexes(i) = myMeshData->AddNode( theVertices(i) );
1448
1449   CreateTrianglesOnNewVertices( aVertexIndexes );
1450 }
1451
1452 //=======================================================================
1453 //function : UseEdge
1454 //purpose  : Modify mesh to use the edge. Return True if done
1455 //=======================================================================
1456 Standard_Boolean BRepMesh_Delaun::UseEdge( const Standard_Integer theIndex )
1457 {
1458   /*
1459   const BRepMesh_PairOfIndex& aPair = myMeshData->ElemConnectedTo( theIndex );
1460   if ( aPair.Extent() == 0 )
1461   {
1462     const BRepMesh_Edge& anEdge = GetEdge( theIndex );
1463
1464     Standard_Integer aStartNode, aPivotNode, anOtherNode;
1465     aStartNode = anEdge.FirstNode();
1466     aPivotNode = anEdge.LastNode();
1467
1468     const BRepMesh_ListOfInteger& aStartNodeNeighbors = myMeshData->LinkNeighboursOf( aStartNode );
1469     const BRepMesh_ListOfInteger& aPivotNodeNeighbors = myMeshData->LinkNeighboursOf( aPivotNode );
1470
1471     if ( aStartNodeNeighbors.Extent() > 0 &&
1472          aPivotNodeNeighbors.Extent() > 0 )
1473     {
1474       const BRepMesh_Vertex& aStartVertex = GetVertex( aStartNode );
1475       const BRepMesh_Vertex& aPivotVertex = GetVertex( aPivotNode );
1476
1477       gp_XY aVEdge   ( aPivotVertex.Coord() );
1478       aVEdge.Subtract( aStartVertex.Coord() );
1479
1480       Standard_Real    anAngle    = 0.;
1481       Standard_Real    anAngleMin = RealLast();
1482       Standard_Real    anAngleMax = RealFirst();
1483       Standard_Integer aLeftEdge  = 0, aRightEdge = 0;
1484
1485       BRepMesh_ListOfInteger::Iterator aNeighborIt( aPivotNodeNeighbors );
1486       for ( ; aNeighborIt.More(); aNeighborIt.Next() )
1487       {
1488         Standard_Integer anEdgeId = aNeighborIt.Value();
1489         if ( anEdgeId != theIndex )
1490         {
1491           const BRepMesh_Edge& aNextEdge = GetEdge( anEdgeId );
1492
1493           Standard_Boolean isInMesh = Standard_True;
1494           if ( aNextEdge.Movability() == BRepMesh_Free )
1495           {
1496             if ( myMeshData->ElemConnectedTo( anEdgeId ).IsEmpty() )
1497               isInMesh = Standard_False;
1498           }
1499
1500           if ( isInMesh )
1501           {
1502             anOtherNode = aNextEdge.FirstNode();
1503             if ( anOtherNode == aPivotNode )
1504               anOtherNode = aNextEdge.LastNode();
1505
1506             gp_XY aVEdgeCur = GetVertex( anOtherNode ).Coord();
1507             aVEdgeCur.Subtract( aPivotVertex.Coord() );
1508
1509             anAngle = gp_Vec2d( aVEdge ).Angle( gp_Vec2d( aVEdgeCur ) );
1510           }
1511
1512           if ( anAngle > anAngleMax )
1513           {
1514             anAngleMax = anAngle;
1515             aLeftEdge  = anEdgeId;
1516           }
1517           if ( anAngle < anAngleMin )
1518           {
1519             anAngleMin = anAngle;
1520             aRightEdge = anEdgeId;
1521           }
1522         }
1523       }
1524
1525       if ( aLeftEdge > 0 )
1526       {
1527         if (aLeftEdge==aRightEdge)
1528         {
1529         }
1530         else
1531         {
1532         }
1533       }
1534     }
1535   }
1536   */
1537   return Standard_False;
1538 }
1539
1540 //=======================================================================
1541 //function : Result
1542 //purpose  : Gives the Mesh data structure
1543 //=======================================================================
1544 const Handle( BRepMesh_DataStructureOfDelaun )& BRepMesh_Delaun::Result() const
1545 {
1546   return myMeshData;
1547 }
1548
1549 //=======================================================================
1550 //function : Frontier
1551 //purpose  : Gives the list of frontier edges
1552 //=======================================================================
1553 const BRepMesh_MapOfInteger& BRepMesh_Delaun::Frontier()
1554 {
1555   BRepMesh_MapOfInteger::Iterator anEdgeIt( myMeshData->LinkOfDomain() );
1556
1557   myMapEdges.Clear();
1558   for ( ; anEdgeIt.More(); anEdgeIt.Next() )
1559   {
1560     Standard_Integer anEdge = anEdgeIt.Key();
1561     if ( GetEdge( anEdge ).Movability() == BRepMesh_Frontier )
1562       myMapEdges.Add( anEdge );
1563   }
1564
1565   return myMapEdges;
1566 }
1567
1568 //=======================================================================
1569 //function : InternalEdges
1570 //purpose  : Gives the list of internal edges
1571 //=======================================================================
1572 const BRepMesh_MapOfInteger& BRepMesh_Delaun::InternalEdges()
1573 {
1574   BRepMesh_MapOfInteger::Iterator anEdgeIt( myMeshData->LinkOfDomain() );
1575
1576   myMapEdges.Clear();
1577   for ( ; anEdgeIt.More(); anEdgeIt.Next() )
1578   {
1579     Standard_Integer anEdge = anEdgeIt.Key();
1580     if ( GetEdge( anEdge ).Movability() == BRepMesh_Fixed )
1581       myMapEdges.Add( anEdge );
1582   }
1583
1584   return myMapEdges;
1585 }
1586
1587 //=======================================================================
1588 //function : FreeEdges
1589 //purpose  : Gives the list of free edges used only one time
1590 //=======================================================================
1591 const BRepMesh_MapOfInteger& BRepMesh_Delaun::FreeEdges()
1592 {
1593   BRepMesh_MapOfInteger::Iterator anEdgeIt( myMeshData->LinkOfDomain() );
1594
1595   myMapEdges.Clear();
1596   for ( ; anEdgeIt.More(); anEdgeIt.Next() )
1597   {
1598     Standard_Integer anEdge = anEdgeIt.Key();
1599     if ( myMeshData->ElemConnectedTo( anEdge ).Extent() <= 1 )
1600       myMapEdges.Add( anEdge );
1601   }
1602
1603   return myMapEdges;
1604 }
1605
1606 //=======================================================================
1607 //function : calculateDist
1608 //purpose  : Calculates distances between the given point and edges of
1609 //           triangle
1610 //=======================================================================
1611 static Standard_Real calculateDist( const gp_XY theVEdges[3],
1612                                     const gp_XY thePoints[3],
1613                                     const Standard_Integer theEdgesId[3],
1614                                     const BRepMesh_Vertex& theVertex,
1615                                     Standard_Real theDistance[3],
1616                                     Standard_Real theSqModulus[3],
1617                                     Standard_Integer& theEdgeOn )
1618 {
1619   Standard_Real aMinDist = -1;
1620   if ( !theVEdges || !thePoints || !theEdgesId ||
1621        !theDistance || !theSqModulus )
1622     return aMinDist;
1623
1624   for( Standard_Integer i = 0; i < 3; ++i )
1625   {
1626     theSqModulus[i] = theVEdges[i].SquareModulus();
1627     if ( theSqModulus[i] <= EPSEPS )
1628       return -1;
1629
1630     theDistance[i] = theVEdges[i] ^ ( theVertex.Coord() - thePoints[i] );
1631
1632     Standard_Real aDist = theDistance[i] * theDistance[i];
1633     aDist /= theSqModulus[i];
1634
1635     if ( aMinDist < 0 || aDist < aMinDist )
1636     {
1637       theEdgeOn = theEdgesId[i];
1638       aMinDist  = aDist;
1639     }
1640   }
1641
1642   return aMinDist;
1643 }
1644
1645 //=======================================================================
1646 //function : Contains
1647 //purpose  : Test if triangle of index <TrianIndex> contains geometricaly
1648 //           <theVertex>. If <theEdgeOn> is != 0 then theVertex is on Edge
1649 //           of  index <theEdgeOn>
1650 //=======================================================================
1651 Standard_Boolean BRepMesh_Delaun::Contains( const Standard_Integer theTriangleId,
1652                                             const BRepMesh_Vertex& theVertex,
1653                                             Standard_Integer& theEdgeOn ) const
1654 {
1655   theEdgeOn = 0;
1656
1657   Standard_Integer e[3];
1658   Standard_Boolean o[3];
1659   Standard_Integer p[3];
1660
1661   GetTriangle( theTriangleId ).Edges( e[0], e[1], e[2],
1662                                       o[0], o[1], o[2] );
1663
1664   const BRepMesh_Edge* anEdges[3] = { &GetEdge( e[0] ),
1665                                       &GetEdge( e[1] ),
1666                                       &GetEdge( e[2] ) };
1667   if ( o[0] )
1668   {
1669     p[0] = anEdges[0]->FirstNode();
1670     p[1] = anEdges[0]->LastNode();
1671   }
1672   else
1673   {
1674     p[1] = anEdges[0]->FirstNode();
1675     p[0] = anEdges[0]->LastNode();
1676   }
1677
1678   if ( o[2] )
1679     p[2] = anEdges[2]->FirstNode();
1680   else
1681     p[2] = anEdges[2]->LastNode();
1682
1683   gp_XY aPoints[3];
1684   aPoints[0] = GetVertex( p[0] ).Coord();
1685   aPoints[1] = GetVertex( p[1] ).Coord();
1686   aPoints[2] = GetVertex( p[2] ).Coord();
1687
1688   gp_XY aVEdges[3];
1689   aVEdges[0] = aPoints[1];
1690   aVEdges[0].Subtract( aPoints[0] );
1691
1692   aVEdges[1] = aPoints[2];
1693   aVEdges[1].Subtract( aPoints[1] );
1694
1695   aVEdges[2] = aPoints[0];
1696   aVEdges[2].Subtract( aPoints[2] );
1697
1698   Standard_Real aDistance[3];
1699   Standard_Real aSqModulus[3];
1700
1701   Standard_Real aMinDist;
1702   aMinDist = calculateDist( aVEdges, aPoints, e, theVertex, aDistance, aSqModulus, theEdgeOn );
1703   if ( aMinDist < 0 )
1704     return Standard_False;
1705
1706   if ( aMinDist > EPSEPS )
1707   {
1708     Standard_Integer anEdgeId = theEdgeOn;
1709     theEdgeOn = 0;
1710
1711     if ( anEdgeId != 0 )
1712     {
1713       Standard_Integer i = 0;
1714       for ( ; i < 3; ++i )
1715       {
1716         if( e[i] == anEdgeId )
1717           break;
1718       }
1719
1720       if( anEdges[i]->Movability() != BRepMesh_Free )
1721         if ( aDistance[i] < ( aSqModulus[i] / 5. ) )
1722           theEdgeOn = e[i];
1723     }
1724   }
1725
1726   return ( aDistance[0] + aDistance[1] + aDistance[2] != 0. &&
1727             ( ( aDistance[0] >= 0. && aDistance[1] >= 0. && aDistance[2] >= 0. ) ||
1728               ( aDistance[0] <= 0. && aDistance[1] <= 0. && aDistance[2] <= 0. ) ) );
1729 }
1730
1731
1732 //=============================================================================
1733 // Function: classifyPoint
1734 // This function is used for point classifying in case of coincidence of two
1735 // vectors.
1736 // Returns zero value if point is out of segment and non zero value if point is
1737 // between the first and the second point of segment.
1738 //
1739 // thePoint1       - the start point of a segment (base point)
1740 // thePoint2       - the end point of a segment
1741 // thePointToCheck - the point to classify
1742 //=============================================================================
1743 static Standard_Integer classifyPoint( const gp_XY& thePoint1,
1744                                        const gp_XY& thePoint2,
1745                                        const gp_XY& thePointToCheck )
1746 {
1747   gp_XY aP1 = thePoint2       - thePoint1;
1748   gp_XY aP2 = thePointToCheck - thePoint1;
1749
1750   Standard_Real aDist = Abs( aP1 ^ aP2 );
1751   if ( aDist >= Precision::PConfusion() )
1752   {
1753     aDist = ( aDist * aDist ) / aP1.SquareModulus();
1754     if ( aDist >= EPSEPS )
1755       return 0; //out
1756   }
1757
1758   gp_XY aMult = aP1.Multiplied( aP2 );
1759   if ( aMult.X() < 0.0 || aMult.Y() < 0.0 )
1760     return 0; //out
1761
1762   if ( aP1.SquareModulus() < aP2.SquareModulus() )
1763     return 0; //out
1764
1765   if ( thePointToCheck.IsEqual( thePoint1, Precision::PConfusion() ) ||
1766        thePointToCheck.IsEqual( thePoint2, Precision::PConfusion() ) )
1767     return -1; //end point
1768
1769   return 1;
1770 }
1771
1772 //=============================================================================
1773 // Function: IntSegSeg
1774 //=============================================================================
1775 Standard_Boolean BRepMesh_Delaun::IntSegSeg( const BRepMesh_Edge& theEdg1,
1776                                              const BRepMesh_Edge& theEdg2 )
1777 {
1778   gp_XY p1, p2, p3, p4;
1779   p1 = GetVertex( theEdg1.FirstNode() ).Coord();
1780   p2 = GetVertex( theEdg1.LastNode()  ).Coord();
1781   p3 = GetVertex( theEdg2.FirstNode() ).Coord();
1782   p4 = GetVertex( theEdg2.LastNode()  ).Coord();
1783
1784   Standard_Integer aPoint1 = classifyPoint( p1, p2, p3 );
1785   Standard_Integer aPoint2 = classifyPoint( p1, p2, p4 );
1786   Standard_Integer aPoint3 = classifyPoint( p3, p4, p1 );
1787   Standard_Integer aPoint4 = classifyPoint( p3, p4, p2 );
1788
1789   if ( aPoint1 > 0 || aPoint2 > 0 ||
1790        aPoint3 > 0 || aPoint4 > 0 )
1791     return Standard_True;
1792
1793   gp_XY aPl1 = p2 - p1;
1794   gp_XY aPl2 = p4 - p3;
1795   gp_XY aPl3 = p1 - p3;
1796
1797   Standard_Real aCrossD1D2 = aPl1 ^ aPl2;
1798   Standard_Real aCrossD1D3 = aPl1 ^ aPl3;
1799   if ( Abs( aCrossD1D2 ) < Precision::PConfusion() )
1800   {
1801     if( Abs( aCrossD1D3 ) < Precision::PConfusion() )
1802     {
1803       Standard_Integer aPosHash = aPoint1 + aPoint2;
1804       if ( ( !aPosHash && aPoint3 ) ) //|| aPosHash < -1 )
1805         return Standard_True;
1806
1807       return Standard_False;
1808     }
1809     else
1810       //parallel case
1811       return Standard_False;
1812   }
1813
1814   Standard_Real aPar = aCrossD1D3 / aCrossD1D2;
1815   // inrersects out of first segment range
1816   if( aPar < Precision::Angular() || aPar > 1 - Precision::Angular() )
1817     return Standard_False;
1818
1819   Standard_Real aCrossD2D3 = aPl2 ^ aPl3;
1820   aPar = aCrossD2D3 / aCrossD1D2;
1821   // inrersects out of second segment range
1822   if( aPar < Precision::Angular() || aPar > 1 - Precision::Angular() )
1823     return Standard_False;
1824
1825   return Standard_True;
1826 }