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