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