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