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