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