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