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