0023946: Uninitialized variable aNewEdge3 used
[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-2012 OPEN CASCADE SAS
5 //
6 // The content of this file is subject to the Open CASCADE Technology Public
7 // License Version 6.5 (the "License"). You may not use the content of this file
8 // except in compliance with the License. Please obtain a copy of the License
9 // at http://www.opencascade.org and read it completely before using this file.
10 //
11 // The Initial Developer of the Original Code is Open CASCADE S.A.S., having its
12 // main offices at: 1, place des Freres Montgolfier, 78280 Guyancourt, France.
13 //
14 // The Original Code and all software distributed under the License is
15 // distributed on an "AS IS" basis, without warranty of any kind, and the
16 // Initial Developer hereby disclaims all such warranties, including without
17 // limitation, any warranties of merchantability, fitness for a particular
18 // purpose or non-infringement. Please see the License for the specific terms
19 // and conditions governing the rights and limitations under the License.
20
21
22 #include <BRepMesh_Delaun.ixx>
23 #include <gp_XY.hxx>
24 #include <gp_Pnt2d.hxx>
25 #include <gp_Vec2d.hxx>
26 #include <TColStd_ListIteratorOfListOfInteger.hxx>
27 #include <TColStd_ListOfInteger.hxx>
28 #include <Precision.hxx>
29 #include <Bnd_Box2d.hxx>
30 #include <gp.hxx>
31 #include <TColStd_MapOfInteger.hxx>
32 #include <TColStd_MapIteratorOfMapOfInteger.hxx>
33 #include <TColStd_Array1OfBoolean.hxx>
34 #include <BRepMesh_MapOfIntegerInteger.hxx>
35 #include <BRepMesh_HeapSortIndexedVertexOfDelaun.hxx>
36 #include <BRepMesh_ComparatorOfIndexedVertexOfDelaun.hxx>
37 #include <BRepMesh_HeapSortIndexedVertexOfDelaun.hxx>
38 #include <BRepMesh_SelectorOfDataStructureOfDelaun.hxx>
39 #include <BRepMesh_HeapSortVertexOfDelaun.hxx>
40 #include <BRepMesh_ComparatorOfVertexOfDelaun.hxx>
41 #include <TColgp_Array1OfXY.hxx>
42 #include <TColStd_Array1OfReal.hxx>
43
44 typedef TColStd_ListIteratorOfListOfInteger  IteratorOnListOfInteger;
45 typedef TColStd_ListOfInteger                ListOfInteger;
46
47 const Standard_Real EPSEPS = Precision::PConfusion() * Precision::PConfusion();
48 const gp_XY SortingDirection(M_SQRT1_2, M_SQRT1_2);
49
50 //=======================================================================
51 //function : fillBndBox
52 //purpose  : Add boundig box for edge defined by start & end point to
53 //           the given vector of bounding boxes for triangulation edges
54 //=======================================================================
55 static void fillBndBox( NCollection_Vector <Bnd_Box2d>& theVB,
56                         const BRepMesh_Vertex& theV1,
57                         const BRepMesh_Vertex& theV2 )
58 {
59   Bnd_Box2d aBox;      
60   aBox.Add( gp_Pnt2d( theV1.Coord() ) );
61   aBox.Add( gp_Pnt2d( theV2.Coord() ) );
62   theVB.Append( aBox );
63 }
64
65 //=======================================================================
66 //function : BRepMesh_Delaun
67 //purpose  : Creates the triangulation with an empty Mesh data structure
68 //=======================================================================
69 BRepMesh_Delaun::BRepMesh_Delaun( BRepMesh_Array1OfVertexOfDelaun& theVertices,
70                                   const Standard_Boolean isPositive )
71 : myPositiveOrientation( isPositive ),
72   myCircles( theVertices.Length(), new NCollection_IncAllocator() )
73 {
74   if ( theVertices.Length() > 2 )
75   {
76     myMeshData = new BRepMesh_DataStructureOfDelaun( new NCollection_IncAllocator(),
77                                                      theVertices.Length() );
78     Init( theVertices );
79   }
80 }
81
82 //=======================================================================
83 //function : BRepMesh_Delaun
84 //purpose  : Creates the triangulation with and existent Mesh data structure
85 //=======================================================================
86 BRepMesh_Delaun::BRepMesh_Delaun ( const Handle( BRepMesh_DataStructureOfDelaun )& theOldMesh, 
87                                    BRepMesh_Array1OfVertexOfDelaun& theVertices,
88                                    const Standard_Boolean isPositive )
89  : myPositiveOrientation( isPositive ),
90    myCircles( theVertices.Length(), theOldMesh->Allocator() )
91 {
92   myMeshData = theOldMesh;
93   if ( theVertices.Length() > 2 )
94     Init( theVertices );
95 }
96
97 //=======================================================================
98 //function : BRepMesh_Delaun
99 //purpose  : Creates the triangulation with and existent Mesh data structure
100 //=======================================================================
101 BRepMesh_Delaun::BRepMesh_Delaun( const Handle( BRepMesh_DataStructureOfDelaun )& theOldMesh, 
102                                   TColStd_Array1OfInteger& theVertexIndexes,
103                                   const Standard_Boolean isPositive )
104  : myPositiveOrientation( isPositive ),
105    myCircles( theVertexIndexes.Length(), theOldMesh->Allocator() )
106 {
107   myMeshData = theOldMesh;
108   if ( theVertexIndexes.Length() > 2 )
109   {
110     Bnd_Box2d aBox;
111     Standard_Integer anIndex = theVertexIndexes.Lower();
112     Standard_Integer anUpper = theVertexIndexes.Upper();
113     for ( ; anIndex <= anUpper; ++anIndex )
114       aBox.Add( gp_Pnt2d( GetVertex( theVertexIndexes( anIndex) ).Coord() ) );
115
116     Perform( aBox, theVertexIndexes );
117   }
118 }
119
120 //=======================================================================
121 //function : Init
122 //purpose  : Initializes the triangulation with an Array of Vertex
123 //=======================================================================
124 void BRepMesh_Delaun::Init( BRepMesh_Array1OfVertexOfDelaun& theVertices )
125 {
126   Bnd_Box2d aBox;
127   Standard_Integer aLowerIdx  = theVertices.Lower();
128   Standard_Integer anUpperIdx = theVertices.Upper();
129   TColStd_Array1OfInteger aVertexIndexes( aLowerIdx, anUpperIdx );
130   
131   Standard_Integer anIndex = aLowerIdx;
132   for ( ; anIndex <= anUpperIdx; ++anIndex )
133   {
134     aBox.Add( gp_Pnt2d( theVertices( anIndex ).Coord() ) );
135     aVertexIndexes( anIndex ) = myMeshData->AddNode( theVertices( anIndex ) );
136   }
137
138   Perform( aBox, aVertexIndexes );
139 }
140
141 //=======================================================================
142 //function : Perform
143 //purpose  : Create super mesh and run triangulation procedure
144 //=======================================================================
145 void BRepMesh_Delaun::Perform( Bnd_Box2d& theBndBox,
146                                TColStd_Array1OfInteger& theVertexIndexes )
147 {
148   theBndBox.Enlarge( Precision::PConfusion() );
149   SuperMesh( theBndBox );
150
151   BRepMesh_HeapSortIndexedVertexOfDelaun::Sort( theVertexIndexes, 
152       BRepMesh_ComparatorOfIndexedVertexOfDelaun( SortingDirection,
153         Precision::PConfusion(), myMeshData ) );
154
155   Compute( theVertexIndexes );
156 }
157
158 //=======================================================================
159 //function : SuperMesh
160 //purpose  : Build the super mesh
161 //=======================================================================
162 void BRepMesh_Delaun::SuperMesh( const Bnd_Box2d& theBox )
163 {
164   Standard_Real aMinX, aMinY, aMaxX, aMaxY;
165   theBox.Get( aMinX, aMinY, aMaxX, aMaxY );
166   Standard_Real aDeltaX = aMaxX - aMinX;
167   Standard_Real aDeltaY = aMaxY - aMinY;
168
169   Standard_Real aDeltaMin = Min( aDeltaX, aDeltaY );
170   Standard_Real aDeltaMax = Max( aDeltaX, aDeltaY );
171   Standard_Real aDelta    = aDeltaX + aDeltaY;
172   
173   myCircles.SetMinMaxSize( gp_XY( aMinX, aMinY ), gp_XY( aMaxX, aMaxY ) );
174
175   Standard_Integer aScaler = 2;
176   if ( myMeshData->NbNodes() > 100 )
177     aScaler = 5;
178   else if( myMeshData->NbNodes() > 1000 )
179     aScaler = 7;
180
181   myCircles.SetCellSize( aDeltaX / aScaler,
182                          aDeltaY / aScaler );
183
184   mySupVert1 = myMeshData->AddNode(
185     BRepMesh_Vertex( ( aMinX + aMaxX ) / 2, aMaxY + aDeltaMax, BRepMesh_Free ) );
186     
187   mySupVert2 = myMeshData->AddNode(
188     BRepMesh_Vertex( aMinX - aDelta, aMinY - aDeltaMin, BRepMesh_Free ) );
189     
190   mySupVert3 = myMeshData->AddNode(
191     BRepMesh_Vertex( aMaxX + aDelta, aMinY - aDeltaMin, BRepMesh_Free ) );
192
193   if ( !myPositiveOrientation )
194   {
195     Standard_Integer aTmp;
196     aTmp       = mySupVert2;
197     mySupVert2 = mySupVert3;
198     mySupVert3 = aTmp;
199   }
200
201   Standard_Integer anEdge1, anEdge2, anEdge3;
202   
203   anEdge1 = myMeshData->AddLink( BRepMesh_Edge( mySupVert1, mySupVert2, BRepMesh_Free ) );
204   anEdge2 = myMeshData->AddLink( BRepMesh_Edge( mySupVert2, mySupVert3, BRepMesh_Free ) );
205   anEdge3 = myMeshData->AddLink( BRepMesh_Edge( mySupVert3, mySupVert1, BRepMesh_Free ) );
206   
207   mySupTrian = BRepMesh_Triangle( Abs( anEdge1 ), Abs( anEdge2 ), Abs( anEdge3 ), 
208     ( anEdge1 > 0 ), ( anEdge2 > 0 ), ( anEdge1 > 0), BRepMesh_Free);
209 }
210
211 //=======================================================================
212 //function : DeleteTriangle
213 //purpose : The concerned triangles are deleted and the freed edges are added in 
214 //           <theLoopEdges>. If an edge is added twice, it does not exist and
215 //          it is necessary to destroy it. This corresponds to the destruction of two
216 //          connected triangles.
217 //=======================================================================
218 void  BRepMesh_Delaun::DeleteTriangle( const Standard_Integer theIndex, 
219                                        BRepMesh_MapOfIntegerInteger& theLoopEdges )
220 {
221   myCircles.Delete( theIndex );
222
223   Standard_Integer e[3];
224   Standard_Boolean o[3];
225   GetTriangle( theIndex ).Edges( e[0], e[1], e[2],
226                                  o[0], o[1], o[2] );
227                                  
228   myMeshData->RemoveElement( theIndex );
229
230   for ( Standard_Integer i = 0; i < 3; ++i )
231   {
232     if ( !theLoopEdges.Bind( e[i], o[i] ) ) 
233     {
234       theLoopEdges.UnBind( e[i] );
235       myMeshData->RemoveLink( e[i] );
236     }
237   }
238 }
239
240 //=======================================================================
241 //function : Compute
242 //purpose  : Computes the triangulation and add the vertices edges and 
243 //           triangles to the Mesh data structure
244 //=======================================================================
245 void BRepMesh_Delaun::Compute( TColStd_Array1OfInteger& theVertexIndexes )
246 {
247   // Insertion of edges of super triangles in the list of free edges: 
248   BRepMesh_MapOfIntegerInteger aLoopEdges( 10, myMeshData->Allocator() );
249   Standard_Integer e[3];
250   Standard_Boolean o[3];
251   mySupTrian.Edges( e[0], e[1], e[2],
252                     o[0], o[1], o[2] );
253                     
254   aLoopEdges.Bind( e[0], Standard_True );
255   aLoopEdges.Bind( e[1], Standard_True );
256   aLoopEdges.Bind( e[2], Standard_True );
257
258   if ( theVertexIndexes.Length() > 0 )
259   {
260     // Creation of 3 trianglers with the first node and the edges of the super triangle:
261     Standard_Integer anVertexIdx = theVertexIndexes.Lower();
262     CreateTriangles( theVertexIndexes( anVertexIdx ), aLoopEdges );
263
264     // Add other nodes to the mesh
265     CreateTrianglesOnNewVertices( theVertexIndexes );
266   }
267
268   // Destruction of triangles containing a top of the super triangle
269   BRepMesh_SelectorOfDataStructureOfDelaun aSelector( myMeshData );
270   aSelector.NeighboursOfNode( mySupVert1 );
271   aSelector.NeighboursOfNode( mySupVert2 );
272   aSelector.NeighboursOfNode( mySupVert3 );
273   
274   aLoopEdges.Clear();
275   BRepMesh_MapOfInteger::Iterator aFreeTriangles( aSelector.Elements() );
276   for ( ; aFreeTriangles.More(); aFreeTriangles.Next() )
277     DeleteTriangle( aFreeTriangles.Key(), aLoopEdges );
278
279   // All edges that remain free are removed from aLoopEdges;
280   // only the boundary edges of the triangulation remain there
281   BRepMesh_MapOfIntegerInteger::Iterator aFreeEdges( aLoopEdges );
282   for ( ; aFreeEdges.More(); aFreeEdges.Next() )
283   {
284     if ( myMeshData->ElemConnectedTo( aFreeEdges.Key() ).IsEmpty() )
285       myMeshData->RemoveLink( aFreeEdges.Key() );
286   }
287
288   // The tops of the super triangle are destroyed
289   myMeshData->RemoveNode( mySupVert1 );
290   myMeshData->RemoveNode( mySupVert2 );
291   myMeshData->RemoveNode( mySupVert3 );
292 }
293
294 //=======================================================================
295 //function : CreateTriangles
296 //purpose  : Creates the triangles beetween the node and the polyline.
297 //=======================================================================
298 void BRepMesh_Delaun::CreateTriangles ( const Standard_Integer theVertexIndex,  
299                                         BRepMesh_MapOfIntegerInteger& thePoly )
300 {
301   ListOfInteger aLoopEdges, anExternalEdges;
302   const gp_XY& aVertexCoord = myMeshData->GetNode( theVertexIndex ).Coord();
303   
304   BRepMesh_MapOfIntegerInteger::Iterator anEdges( thePoly );
305   for ( ; anEdges.More(); anEdges.Next() )
306   {
307     const BRepMesh_Edge& anEdge = GetEdge( anEdges.Key() );
308     Standard_Integer aFirstNode = anEdge.FirstNode();
309     Standard_Integer aLastNode  = anEdge.LastNode();
310     Standard_Boolean isPositive = (Standard_Boolean)thePoly( anEdges.Key() );
311     if ( !isPositive )
312     {
313       Standard_Integer aTmp;
314       aTmp       = aFirstNode;
315       aFirstNode = aLastNode;
316       aLastNode  = aTmp;
317     }
318
319     const BRepMesh_Vertex& aFirstVertex = GetVertex( aFirstNode );
320     const BRepMesh_Vertex& aLastVertex  = GetVertex( aLastNode  );
321
322     gp_XY aVEdge1, aVEdge2, aVEdge3;
323     aVEdge1 = aFirstVertex.Coord();
324     aVEdge1.Subtract( aVertexCoord );
325     
326     aVEdge2 = aLastVertex.Coord();
327     aVEdge2.Subtract( aFirstVertex.Coord() );
328     
329     aVEdge3 = aVertexCoord;
330     aVEdge3.Subtract( aLastVertex.Coord() );
331
332     Standard_Real aDist12 = 0., aDist23 = 0.;
333     Standard_Real aV2Len  = aVEdge2.Modulus();
334     if ( aV2Len > Precision::PConfusion() )
335     {
336       aVEdge2.SetCoord( aVEdge2.X() / aV2Len,
337                         aVEdge2.Y() / aV2Len );
338                         
339       aDist12 = aVEdge1 ^ aVEdge2;
340       aDist23 = aVEdge2 ^ aVEdge3;
341     }
342
343     if ( Abs( aDist12 ) >= Precision::PConfusion() && 
344          Abs( aDist23 ) >= Precision::PConfusion() )
345     {
346       Standard_Boolean isSensOK;
347       if ( myPositiveOrientation )
348         isSensOK = ( aDist12 > 0. && aDist23 > 0.);
349       else
350         isSensOK = ( aDist12 < 0. && aDist23 < 0.);
351         
352       if ( isSensOK )
353       {
354         BRepMesh_Edge aNewEdge1 (theVertexIndex, aFirstNode, BRepMesh_Free);
355         BRepMesh_Edge aNewEdge3 (aLastNode, theVertexIndex, BRepMesh_Free);
356
357         Standard_Integer iNewEdge1 = myMeshData->AddLink (aNewEdge1);
358         Standard_Integer iNewEdge3 = myMeshData->AddLink (aNewEdge3);
359           
360         BRepMesh_Triangle aNewTri (Abs (iNewEdge1), anEdges.Key(), Abs (iNewEdge3),
361                                    (iNewEdge1 > 0), isPositive, (iNewEdge3 > 0),
362                                    BRepMesh_Free);
363         Standard_Integer iNewTri = myMeshData->AddElement(aNewTri);
364
365         Standard_Boolean isCircleCreated = 
366           myCircles.Add (aVertexCoord, aFirstVertex.Coord(), aLastVertex.Coord(), iNewTri);
367                          
368         if ( !isCircleCreated )
369           myMeshData->RemoveElement (iNewTri);
370       }
371       else
372       {
373         if ( isPositive )
374           aLoopEdges.Append(  anEdges.Key() );
375         else
376           aLoopEdges.Append( -anEdges.Key() );
377           
378         if ( aVEdge1.SquareModulus() > aVEdge3.SquareModulus() )
379         {
380           BRepMesh_Edge aNewEdge (theVertexIndex, aFirstNode, BRepMesh_Free);
381           Standard_Integer iNewEdge = myMeshData->AddLink(aNewEdge);
382           anExternalEdges.Append (Abs (iNewEdge));
383         }
384         else
385         {
386           BRepMesh_Edge aNewEdge (aLastNode, theVertexIndex, BRepMesh_Free);
387           Standard_Integer iNewEdge = myMeshData->AddLink (aNewEdge);
388           anExternalEdges.Append (Abs (iNewEdge));
389         }
390       }
391     }
392   }
393   
394   thePoly.Clear();
395   while ( !anExternalEdges.IsEmpty() )
396   {
397     const BRepMesh_PairOfIndex& aPair = 
398       myMeshData->ElemConnectedTo( Abs( anExternalEdges.First() ) );
399     
400     
401     if ( !aPair.IsEmpty() )
402       DeleteTriangle( aPair.FirstIndex(), thePoly );
403       
404     anExternalEdges.RemoveFirst();
405   }
406
407   for ( anEdges.Initialize( thePoly ); anEdges.More(); anEdges.Next() )
408   {
409     if ( myMeshData->ElemConnectedTo( anEdges.Key() ).IsEmpty() )
410       myMeshData->RemoveLink( anEdges.Key() );
411   }
412
413   while ( !aLoopEdges.IsEmpty() )
414   {
415     const BRepMesh_Edge& anEdge = GetEdge( Abs( aLoopEdges.First() ) );
416     if ( anEdge.Movability() != BRepMesh_Deleted )
417     {
418       Standard_Integer anEdgeIdx = aLoopEdges.First();
419       MeshLeftPolygonOf( Abs( anEdgeIdx ), ( anEdgeIdx > 0 ) );
420     }
421       
422     aLoopEdges.RemoveFirst();
423   }
424 }
425
426 //=======================================================================
427 //function : CreateTrianglesOnNewVertices
428 //purpose  : Creation of triangles from the new nodes
429 //=======================================================================
430 void BRepMesh_Delaun::CreateTrianglesOnNewVertices( TColStd_Array1OfInteger& theVertexIndexes )
431 {
432   BRepMesh_MapOfIntegerInteger aLoopEdges( 10, myMeshData->Allocator() );
433
434   // Insertion of nodes :
435   Standard_Boolean isModify = Standard_True;
436   
437   Standard_Integer anIndex = theVertexIndexes.Lower();
438   Standard_Integer anUpper = theVertexIndexes.Upper();
439   for( ; anIndex <= anUpper; ++anIndex ) 
440   {
441     aLoopEdges.Clear();
442     
443     Standard_Integer aVertexIdx = theVertexIndexes( anIndex );    
444     const BRepMesh_Vertex& aVertex = GetVertex( aVertexIdx );
445
446     // Iterator in the list of indexes of circles containing the node
447     BRepMesh_ListOfInteger& aCirclesList = myCircles.Select( aVertex.Coord() );
448     
449     Standard_Integer onEgdeId = 0, aTriangleId = 0;
450     BRepMesh_ListOfInteger::Iterator aCircleIt( aCirclesList );
451     for ( ; aCircleIt.More(); aCircleIt.Next() )
452     {
453       // To add a node in the mesh it is necessary to check conditions: 
454       // - the node should be within the boundaries of the mesh and so in an existing triangle
455       // - all adjacent triangles should belong to a component connected with this triangle
456       if ( Contains( aCircleIt.Value(), aVertex, onEgdeId ) )
457       {
458         if ( onEgdeId == 0 )
459         {
460           aTriangleId = aCircleIt.Value();
461           aCirclesList.Remove( aCircleIt );
462           break;
463         }
464         else if ( GetEdge( onEgdeId ).Movability() == BRepMesh_Free )
465         {
466           aTriangleId = aCircleIt.Value();
467           aCirclesList.Remove( aCircleIt );
468           break;
469         }
470       }
471     }
472
473     if ( aTriangleId > 0 )
474     {
475       DeleteTriangle( aTriangleId, aLoopEdges );
476
477       isModify = Standard_True;    
478       while ( isModify && !aCirclesList.IsEmpty() )
479       {
480         isModify = Standard_False;
481         BRepMesh_ListOfInteger::Iterator aCircleIt1( aCirclesList );
482         for ( ; aCircleIt1.More(); aCircleIt1.Next() )
483         {
484           Standard_Integer e[3];
485           Standard_Boolean o[3];
486           GetTriangle( aCircleIt1.Value() ).Edges( e[0], e[1], e[2],
487                                                    o[0], o[1], o[2] );
488                                                    
489           if ( aLoopEdges.IsBound( e[0] ) || 
490                aLoopEdges.IsBound( e[1] ) || 
491                aLoopEdges.IsBound( e[2] ) )
492           {
493             isModify = Standard_True;
494             DeleteTriangle( aCircleIt1.Value(), aLoopEdges );
495             aCirclesList.Remove( aCircleIt1 );
496             break;
497           }
498         }
499       }
500
501       // Creation of triangles with the current node and free edges
502       // and removal of these edges from the list of free edges
503       CreateTriangles( aVertexIdx, aLoopEdges );
504     }
505   }
506   // Check that internal edges are not crossed by triangles
507   BRepMesh_MapOfInteger::Iterator anInernalEdgesIt( InternalEdges() );
508
509   // Destruction of triancles intersecting internal edges 
510   // and their replacement by makeshift triangles
511   anInernalEdgesIt.Reset();
512   for ( ; anInernalEdgesIt.More(); anInernalEdgesIt.Next() )
513   {
514     Standard_Integer aNbC;
515     aNbC = myMeshData->ElemConnectedTo( anInernalEdgesIt.Key() ).Extent();
516     if ( aNbC == 0 )
517     {
518       MeshLeftPolygonOf( anInernalEdgesIt.Key(), Standard_True  ); 
519       MeshLeftPolygonOf( anInernalEdgesIt.Key(), Standard_False ); 
520     }
521   }
522
523   // Adjustment of meshes to boundary edges
524   FrontierAdjust();
525 }
526
527 //=======================================================================
528 //function : CleanupMesh
529 //purpose  : Cleanup mesh from the free triangles
530 //=======================================================================
531 void BRepMesh_Delaun::CleanupMesh()
532 {
533   BRepMesh_MapOfIntegerInteger aLoopEdges( 10, myMeshData->Allocator() );
534   ListOfInteger aTrianglesList;
535
536   for(;;)
537   {
538     aTrianglesList.Clear();
539     aLoopEdges.Clear();
540
541     BRepMesh_MapOfInteger::Iterator aFreeEdgesIt( FreeEdges() );
542     for ( ; aFreeEdgesIt.More(); aFreeEdgesIt.Next() )
543     {
544       const BRepMesh_Edge& anEdge = GetEdge( aFreeEdgesIt.Key() );
545       if ( anEdge.Movability() != BRepMesh_Frontier )
546       {
547         Standard_Integer aFrontierNb = 0;
548         if ( myMeshData->ElemConnectedTo( aFreeEdgesIt.Key() ).IsEmpty() ) 
549           aLoopEdges.Bind( aFreeEdgesIt.Key(), Standard_True );
550         else
551         {
552           BRepMesh_ListOfInteger::Iterator aConnectedLinksIt( 
553             myMeshData->LinkNeighboursOf( anEdge.FirstNode() ) );
554             
555           for ( ; aConnectedLinksIt.More(); aConnectedLinksIt.Next() )
556           {
557             if ( GetEdge( aConnectedLinksIt.Value() ).Movability() == BRepMesh_Frontier )
558             {
559               aFrontierNb++;
560               if ( aFrontierNb > 1 )
561                 break;
562             }
563           }
564           
565           if ( aFrontierNb == 2 )
566           {
567             const BRepMesh_PairOfIndex& aPair = myMeshData->ElemConnectedTo( aFreeEdgesIt.Key() );
568             for ( Standard_Integer j = 1, jn = aPair.Extent(); j <= jn; ++j )
569             {
570               const Standard_Integer anElemId = aPair.Index(j);
571               if ( anElemId < 0 )
572                 continue;
573                 
574               Standard_Integer e[3];
575               Standard_Boolean o[3];
576               GetTriangle( anElemId ).Edges( e[0], e[1], e[2],
577                                              o[0], o[1], o[2] );
578               
579               Standard_Boolean isTriangleToDelete = Standard_True;
580               for ( Standard_Integer k = 0; k < 3; ++k )
581               {
582                 if ( GetEdge( e[k] ).Movability() != BRepMesh_Free )
583                 {
584                   isTriangleToDelete = Standard_False;
585                   break;
586                 }
587               }
588
589               if ( isTriangleToDelete )
590                 aTrianglesList.Append( anElemId );
591             }
592           }
593         }
594       }
595     }
596
597     // Destruction of triangles :
598     Standard_Integer aDeletedTrianglesNb = 0;
599     for ( ; !aTrianglesList.IsEmpty(); aTrianglesList.RemoveFirst() )
600     {
601       DeleteTriangle( aTrianglesList.First(), aLoopEdges );
602       aDeletedTrianglesNb++;
603     }
604
605     // Destruction of remaining hanging edges
606     BRepMesh_MapOfIntegerInteger::Iterator aLoopEdgesIt( aLoopEdges );
607     for ( ; aLoopEdgesIt.More(); aLoopEdgesIt.Next() )
608     {
609       if ( myMeshData->ElemConnectedTo( aLoopEdgesIt.Key() ).IsEmpty() )
610         myMeshData->RemoveLink( aLoopEdgesIt.Key() );
611     }
612
613     if ( aDeletedTrianglesNb == 0 )
614       break;
615   }
616 }
617
618 //=======================================================================
619 //function : FrontierAdjust
620 //purpose  : Adjust the mesh on the frontier
621 //=======================================================================
622 void BRepMesh_Delaun::FrontierAdjust()
623 {
624   BRepMesh_MapOfIntegerInteger aLoopEdges( 10, myMeshData->Allocator() );
625   ListOfInteger aTrianglesList;
626
627   for ( Standard_Integer aPass = 1; aPass <= 2; ++aPass )
628   {      
629     // 1 pass): find external triangles on boundary edges
630     // 2 pass): find external triangles on boundary edges
631     // because in comlex curved boundaries external triangles can appear  
632     // after "mesh left aPolygonon"
633     
634     BRepMesh_MapOfInteger::Iterator aFrontierIt( Frontier() );
635     for ( ; aFrontierIt.More(); aFrontierIt.Next() )
636     {
637       const BRepMesh_PairOfIndex& aPair = myMeshData->ElemConnectedTo( aFrontierIt.Key() );
638       for( Standard_Integer j = 1, jn = aPair.Extent(); j <= jn; ++j )
639       {
640         const Standard_Integer aPriorElemId = aPair.Index(j);
641         if( aPriorElemId < 0 )
642             continue;
643             
644         Standard_Integer e[3];
645         Standard_Boolean o[3];
646         GetTriangle( aPriorElemId ).Edges( e[0], e[1], e[2],
647                                            o[0], o[1], o[2] );
648
649         for ( Standard_Integer n = 0; n < 3; ++n )
650         {
651           if ( aFrontierIt.Key() == e[n] && !o[n] )
652           {
653             aTrianglesList.Append( aPriorElemId );
654             break;
655           }
656         }
657       }
658     }
659
660     // destruction  of external triangles on boundary edges
661     for ( ; !aTrianglesList.IsEmpty(); aTrianglesList.RemoveFirst() )
662       DeleteTriangle( aTrianglesList.First(), aLoopEdges );
663
664     // destrucrion of remaining hanging edges :
665     BRepMesh_MapOfIntegerInteger::Iterator aLoopEdgesIt( aLoopEdges );
666     for ( ; aLoopEdgesIt.More(); aLoopEdgesIt.Next() )
667     {
668       if (myMeshData->ElemConnectedTo( aLoopEdgesIt.Key() ).IsEmpty() )
669         myMeshData->RemoveLink( aLoopEdgesIt.Key() );
670     }
671       
672
673     // destruction of triangles crossing the boundary edges and 
674     // their replacement by makeshift triangles
675     if ( aPass == 1 )
676       aFrontierIt.Reset();
677     else
678       // in some cases there remain unused boundaries check
679       aFrontierIt.Initialize( Frontier() );
680
681     NCollection_Vector<Bnd_Box2d> aFrontBoxes;
682     for ( ; aFrontierIt.More(); aFrontierIt.Next() )
683     {
684       const BRepMesh_Edge& anEdge = GetEdge( aFrontierIt.Key() );
685       const BRepMesh_Vertex& aV1  = GetVertex( anEdge.FirstNode() );
686       const BRepMesh_Vertex& aV2  = GetVertex( anEdge.LastNode()  );
687       fillBndBox( aFrontBoxes, aV1, aV2 );
688
689       if ( myMeshData->ElemConnectedTo( aFrontierIt.Key() ).IsEmpty() )
690         MeshLeftPolygonOf( aFrontierIt.Key(), Standard_True ); 
691     }
692
693     if ( aPass == 1 ) 
694       continue;
695
696     CleanupMesh();
697   }
698 }
699
700 //=======================================================================
701 //function : KillInternalTriangles
702 //purpose  : Removes triangles within polygon
703 //=======================================================================
704 void BRepMesh_Delaun::KillInternalTriangles( Standard_Integer theEdgeId, 
705                                              const TColStd_MapOfInteger& theIgnoredEdges,
706                                              BRepMesh_MapOfIntegerInteger& theLoopEdges )
707 {
708   if ( theIgnoredEdges.Contains( theEdgeId ) )
709     return;   
710
711   const BRepMesh_PairOfIndex& aPair = myMeshData->ElemConnectedTo( theEdgeId );
712   for ( Standard_Integer i = 1; i <= aPair.Extent(); ++i )
713   {
714     Standard_Integer anElemId = aPair.Index(i);
715     if( anElemId < 0 )
716       continue;
717
718     Standard_Integer e[3];
719     Standard_Boolean o[3];
720     GetTriangle( anElemId ).Edges( e[0], e[1], e[2],
721                                    o[0], o[1], o[2] );
722
723     for ( Standard_Integer anIndex = 0; anIndex < 3; ++anIndex )
724     {
725       if ( e[anIndex] == theEdgeId )
726       {
727         DeleteTriangle( anElemId, theLoopEdges );
728         for ( Standard_Integer n = 0; n < 2; ++n )
729         {
730           Standard_Integer aCurEdge = e[(anIndex + n + 1) % 3];
731           KillInternalTriangles( aCurEdge, theIgnoredEdges, theLoopEdges );
732         }
733       }
734     }
735   }
736 }
737
738 //=======================================================================
739 //function : RemovePivotTriangles
740 //purpose  : Removes triangles around the given pivot node
741 //=======================================================================
742 void BRepMesh_Delaun::RemovePivotTriangles( const Standard_Integer theEdgeInfo,
743                                             const Standard_Integer thePivotNode,
744                                             TColStd_MapOfInteger& theInfectedEdges,
745                                             BRepMesh_MapOfIntegerInteger& theLoopEdges,
746                                             const Standard_Boolean isFirstPass )
747 {
748   Standard_Integer e[3];
749   Standard_Boolean o[3];
750   Standard_Integer aGeneralEdgeId = -1;
751
752   Standard_Integer anMainEdgeId = Abs( theEdgeInfo );
753   Standard_Boolean anIsForward = theEdgeInfo > 0;
754   const BRepMesh_PairOfIndex& aPair = myMeshData->ElemConnectedTo( anMainEdgeId );
755   for ( Standard_Integer j = 1, jn = aPair.Extent(); j <= jn; ++j )
756   {
757     Standard_Integer anElemId = aPair.Index(j);
758     if( anElemId < 0 )
759       continue;
760
761     GetTriangle( anElemId ).Edges( e[0], e[1], e[2],
762                                    o[0], o[1], o[2] );
763
764     Standard_Boolean isFind = Standard_False;
765     for ( Standard_Integer anIndex = 0; anIndex < 3; ++anIndex )
766     {
767       if ( e[anIndex] == anMainEdgeId && o[anIndex] == anIsForward )
768       {
769         // triangle detected
770         DeleteTriangle( anElemId, theLoopEdges );
771         aGeneralEdgeId = anIndex;
772         break;
773       }
774     }
775        
776     if ( aGeneralEdgeId != -1 )
777       break;
778   }
779
780   if ( aGeneralEdgeId != -1 )
781   {
782     // delete triangles around of aPivotNode starting from the bounding one
783     // define edge connected to vertes
784     Standard_Integer anEdgeId = -1;
785     for ( Standard_Integer i = 0; i < 2; ++i )
786     {
787       Standard_Integer aTmpEdgeId = e[(aGeneralEdgeId + i + 1) % 3];
788       const BRepMesh_Edge& anEdge = GetEdge( aTmpEdgeId );
789       if ( anEdge.FirstNode() == thePivotNode || 
790            anEdge.LastNode()  == thePivotNode )
791       {
792         anEdgeId = aTmpEdgeId;
793       }
794
795       if ( theInfectedEdges.Contains( aTmpEdgeId ) )
796         theInfectedEdges.Remove( aTmpEdgeId );
797       else
798         theInfectedEdges.Add( aTmpEdgeId );
799     }
800
801     if ( isFirstPass )
802       return;
803
804     while ( anEdgeId > 0 )
805     {
806       const BRepMesh_PairOfIndex& aFreePair = myMeshData->ElemConnectedTo( anEdgeId );
807       Standard_Integer anOldEdge = anEdgeId;
808       anEdgeId = -1;
809
810       for ( Standard_Integer aPairIndex = 1; aPairIndex <= aFreePair.Extent(); ++aPairIndex )
811       {
812         Standard_Integer anElemId = aFreePair.Index( aPairIndex );
813         if( anElemId < 0 )
814           continue;
815           
816         Standard_Integer e1[3];
817         Standard_Boolean o1[3];
818         GetTriangle( anElemId ).Edges( e1[0], e1[1], e1[2],
819                                        o1[0], o1[1], o1[2] );
820         
821         DeleteTriangle( anElemId, theLoopEdges );
822
823         for ( Standard_Integer i = 0; i < 3; ++i )
824         {
825           if ( e1[i] == anOldEdge )
826           {
827             for ( Standard_Integer j = 0; j < 2; ++j )
828             {              
829               Standard_Integer aTmpEdgeId = e1[(j + i + 1) % 3];
830               const BRepMesh_Edge& anEdge = GetEdge( aTmpEdgeId );
831               if ( anEdge.FirstNode() == thePivotNode || 
832                    anEdge.LastNode()  == thePivotNode )
833               {
834                 anEdgeId = aTmpEdgeId;
835               }
836             
837               if ( theInfectedEdges.Contains( aTmpEdgeId ) )
838                 theInfectedEdges.Remove( aTmpEdgeId );
839               else
840                 theInfectedEdges.Add( aTmpEdgeId );
841             }
842             break;
843           }
844         }
845       }
846     }
847   }
848 }
849
850 //=======================================================================
851 //function : CleanupPolygon
852 //purpose  : Remove internal triangles from the given polygon
853 //=======================================================================
854 void BRepMesh_Delaun::CleanupPolygon( const TColStd_SequenceOfInteger& thePolygon,
855                                       TColStd_MapOfInteger& theInfectedEdges,
856                                       BRepMesh_MapOfIntegerInteger& theLoopEdges )
857 {
858   Standard_Integer aPolyLen = thePolygon.Length();
859
860   TColStd_MapOfInteger anIgnoredEdges;
861   NCollection_Map<Standard_Integer> aPolyVertices;
862   for ( Standard_Integer i = 1; i <= aPolyLen; ++i )
863   {
864     Standard_Integer aPolyEdgeId = Abs( thePolygon(i) );
865     anIgnoredEdges.Add( aPolyEdgeId );
866
867     const BRepMesh_Edge& aPolyEdge = GetEdge( aPolyEdgeId );
868     aPolyVertices.Add( aPolyEdge.FirstNode() );
869     aPolyVertices.Add( aPolyEdge.LastNode() );
870
871     if ( theInfectedEdges.Contains( aPolyEdgeId ) )
872       theInfectedEdges.Remove( aPolyEdgeId );
873   }
874
875   Standard_Real aRefTotalAngle = 2 * M_PI;
876   TColStd_MapIteratorOfMapOfInteger anInfectedIt( theInfectedEdges );
877   for ( ; anInfectedIt.More(); anInfectedIt.Next() )
878   {
879     Standard_Integer anEdgeId = anInfectedIt.Key();
880     const BRepMesh_Edge& anInfectedEdge = GetEdge( anEdgeId );
881     Standard_Integer anEdgeVertices[2] = { anInfectedEdge.FirstNode(),
882                                            anInfectedEdge.LastNode() };
883
884     Standard_Boolean isToExclude = Standard_False;
885     for ( Standard_Integer i = 0; i < 2; ++i )
886     {
887       Standard_Integer aCurVertex = anEdgeVertices[i];
888       if ( aPolyVertices.Contains( aCurVertex ) )
889         continue;
890
891       gp_XY aCenterPointXY = GetVertex( aCurVertex ).Coord();
892       Standard_Real aTotalAng = 0.0;
893
894       for ( Standard_Integer i = 1; i <= aPolyLen; ++i )
895       {
896         Standard_Integer aPolyEdgeId = thePolygon(i);
897         const BRepMesh_Edge& aPolyEdge = GetEdge( Abs( aPolyEdgeId ) );
898         Standard_Integer aStartPoint, anEndPoint;
899         if ( aPolyEdgeId >= 0 )
900         {
901           aStartPoint = aPolyEdge.FirstNode();
902           anEndPoint  = aPolyEdge.LastNode();
903         }
904         else
905         {
906           aStartPoint = aPolyEdge.LastNode();
907           anEndPoint  = aPolyEdge.FirstNode();
908         }
909
910         gp_XY aStartV = GetVertex( aStartPoint ).Coord() - aCenterPointXY;
911         gp_XY anEndV  = GetVertex( anEndPoint ).Coord()  - aCenterPointXY;
912
913         Standard_Real anAngle = gp_Vec2d( anEndV ).Angle( gp_Vec2d( aStartV ) );
914         aTotalAng += anAngle;
915       }
916       
917       if ( Abs( aRefTotalAngle - aTotalAng ) > Precision::Angular() )
918         isToExclude = Standard_True;
919     }
920
921     if ( isToExclude )
922       anIgnoredEdges.Add( anEdgeId );
923   }
924
925
926   anInfectedIt.Initialize( theInfectedEdges );
927   for ( ; anInfectedIt.More(); anInfectedIt.Next() )
928   {
929     Standard_Integer anEdgeId = anInfectedIt.Key();
930     KillInternalTriangles( anEdgeId, anIgnoredEdges, theLoopEdges);
931   }
932
933   BRepMesh_MapOfIntegerInteger::Iterator aLoopEdgesIt( theLoopEdges );
934   for ( ; aLoopEdgesIt.More(); aLoopEdgesIt.Next() )
935   {
936     if ( myMeshData->ElemConnectedTo( aLoopEdgesIt.Key() ).IsEmpty() )
937       myMeshData->RemoveLink( aLoopEdgesIt.Key() );
938   }
939 }
940
941 //=======================================================================
942 //function : MeshLeftPolygonOf
943 //purpose  : Triangulation of the aPolygonon to the left of <theEdgeIndex>.(material side)
944 //=======================================================================
945 void BRepMesh_Delaun::MeshLeftPolygonOf( const Standard_Integer theEdgeIndex,
946                                          const Standard_Boolean isForward )
947 {
948   const BRepMesh_Edge& anEdge = GetEdge( theEdgeIndex );
949   NCollection_Map<Standard_Integer> aDealLinks;
950   TColStd_SequenceOfInteger aPolygon;
951   BRepMesh_MapOfIntegerInteger aLoopEdges( 10, myMeshData->Allocator() );
952   TColStd_MapOfInteger anUsedEdges;
953   TColStd_MapOfInteger anInfectedEdges;
954   
955   // Find the aPolygonon
956   anUsedEdges.Add( theEdgeIndex );
957   Standard_Integer aFirstNode, aStartNode, aPivotNode;
958   
959   if ( isForward )
960   {
961     aPolygon.Append( theEdgeIndex );
962     aStartNode = anEdge.FirstNode();
963     aPivotNode = anEdge.LastNode();
964   }
965   else
966   {
967     aPolygon.Append( -theEdgeIndex );
968     aStartNode = anEdge.LastNode();
969     aPivotNode = anEdge.FirstNode();
970   }
971   aFirstNode = aStartNode;
972
973   const BRepMesh_Vertex& aStartVertex = GetVertex( aFirstNode );
974   const BRepMesh_Vertex& anEndVertex  = GetVertex( aPivotNode );
975
976   Standard_Integer aRefOtherNode = 0, anOtherNode = 0;
977   // Check the presence of the previous edge <theEdgeIndex> :
978   BRepMesh_ListOfInteger::Iterator aLinkIt( myMeshData->LinkNeighboursOf( aStartNode ) );
979   for ( ; aLinkIt.More(); aLinkIt.Next() )
980   {
981     if ( aLinkIt.Value() != theEdgeIndex )
982     {
983       const BRepMesh_Edge& aNextEdge = GetEdge( aLinkIt.Value() );
984       anOtherNode = aNextEdge.LastNode();
985       if ( anOtherNode == aStartNode )
986         anOtherNode = aNextEdge.FirstNode();
987       break;
988     }
989   }
990   if ( anOtherNode == 0 )
991     return;
992
993
994   gp_XY aVEdge( anEndVertex.Coord() );
995   aVEdge.Subtract( aStartVertex.Coord() );
996   gp_XY aPrevVEdge( aVEdge );
997   gp_XY aRefCurrVEdge, aCurrVEdge;
998   
999   Standard_Integer aCurrEdgeId = theEdgeIndex;
1000   Standard_Integer aNextEdgeId;
1001
1002   // Find the nearest to <theEdgeIndex> closed aPolygonon :
1003   Standard_Boolean isInMesh, isNotInters;
1004   Standard_Real anAngle, aRefAngle;
1005
1006   NCollection_Vector <Bnd_Box2d> aBoxes;
1007   fillBndBox( aBoxes, aStartVertex, anEndVertex );
1008     
1009   while ( aPivotNode != aFirstNode )
1010   {
1011     aNextEdgeId = 0;
1012     if ( myPositiveOrientation )
1013       aRefAngle = RealFirst();
1014     else
1015       aRefAngle = RealLast();
1016
1017     const BRepMesh_Vertex& aPivotVertex = GetVertex( aPivotNode );
1018
1019     // Find the next edge with the greatest angle with <theEdgeIndex>
1020     // and non intersecting <theEdgeIndex> :
1021     
1022     aLinkIt.Init( myMeshData->LinkNeighboursOf( aPivotNode ) );
1023     for ( ; aLinkIt.More(); aLinkIt.Next() )
1024     {
1025       Standard_Integer aNextLink = aLinkIt.Value();
1026       Standard_Integer aNextLinkId = Abs( aNextLink );
1027       if ( aDealLinks.Contains( aNextLinkId ) )
1028         continue;
1029
1030       if ( aNextLinkId != aCurrEdgeId )
1031       {
1032         isNotInters = Standard_True;
1033         const BRepMesh_Edge& aNextEdge = GetEdge( aNextLinkId );
1034
1035         isInMesh = Standard_True;
1036         
1037         //define if link exist in mesh      
1038         if ( aNextEdge.Movability() == BRepMesh_Free )
1039         {
1040           if ( myMeshData->ElemConnectedTo( aLinkIt.Value() ).IsEmpty() ) 
1041             isInMesh = Standard_False;
1042         }
1043
1044         if ( isInMesh )
1045         {
1046           anOtherNode = aNextEdge.FirstNode();
1047           if ( anOtherNode == aPivotNode )
1048             anOtherNode = aNextEdge.LastNode();
1049
1050           aCurrVEdge = GetVertex( anOtherNode ).Coord();
1051           aCurrVEdge.Subtract( aPivotVertex.Coord() );
1052           
1053           if ( aCurrVEdge.Modulus() >= gp::Resolution() &&
1054                aPrevVEdge.Modulus() >= gp::Resolution() )
1055           {
1056             anAngle = gp_Vec2d( aPrevVEdge ).Angle( gp_Vec2d( aCurrVEdge ) );
1057
1058             if ( ( myPositiveOrientation && anAngle > aRefAngle ) ||
1059                 ( !myPositiveOrientation && anAngle < aRefAngle ) )
1060             {
1061               Bnd_Box2d aBox;
1062               aBox.Add( gp_Pnt2d( GetVertex( aNextEdge.FirstNode() ).Coord() ) );
1063               aBox.Add( gp_Pnt2d( GetVertex( aNextEdge.LastNode()  ).Coord() ) );
1064               
1065               for ( Standard_Integer k = 0, aLen = aPolygon.Length(); k < aLen; ++k )
1066               {
1067                 if ( !aBox.IsOut( aBoxes.Value( k ) ) )
1068                 {
1069                   // intersection is possible...
1070                   if ( IntSegSeg( aNextEdge, GetEdge( Abs( aPolygon( k + 1 ) ) ) ) )
1071                   {
1072                     isNotInters = Standard_False;
1073                     break;
1074                   }
1075                 }
1076               }
1077               
1078               if( isNotInters )
1079               {              
1080                 aRefAngle = anAngle;
1081                 aRefCurrVEdge = aCurrVEdge;
1082                 
1083                 if ( aNextEdge.FirstNode() == aPivotNode )
1084                   aNextEdgeId =  aLinkIt.Value();
1085                 else
1086                   aNextEdgeId = -aLinkIt.Value();
1087                   
1088                 aRefOtherNode = anOtherNode;
1089               }
1090             }
1091           }
1092         }
1093       }
1094     }
1095     if ( aNextEdgeId != 0 )
1096     {
1097       if ( Abs( aNextEdgeId ) != theEdgeIndex && Abs( aNextEdgeId ) != aCurrEdgeId )
1098       {
1099         aCurrEdgeId = Abs( aNextEdgeId );
1100
1101         if ( !anUsedEdges.Add( aCurrEdgeId ) )
1102         {
1103           //if this edge has already been added to the aPolygon, 
1104           //there is a risk of looping (attention to open contours)
1105           //remove last edge and continue
1106           
1107           aDealLinks.Add( aCurrEdgeId );
1108
1109           //roll back
1110           continue;
1111         }        
1112
1113         aPolygon.Append( aNextEdgeId );
1114
1115         const BRepMesh_Edge& aCurrEdge = GetEdge( aCurrEdgeId );
1116         Standard_Integer aVert1 = aCurrEdge.FirstNode();
1117         Standard_Integer aVert2 = aCurrEdge.LastNode();
1118         fillBndBox( aBoxes, GetVertex( aVert1 ), GetVertex( aVert2 ) );
1119
1120         RemovePivotTriangles( aNextEdgeId, aPivotNode,
1121           anInfectedEdges, aLoopEdges, (aPolygon.Length() == 2) );
1122       }
1123     }
1124     else
1125     {
1126       //hanging end
1127       if ( aPolygon.Length() == 1 )
1128         return;
1129
1130       Standard_Integer aDeadEdgeId = Abs( aPolygon.Last() );
1131       const BRepMesh_Edge& aDeadEdge = GetEdge( aDeadEdgeId );
1132
1133       aDealLinks.Add( aDeadEdgeId );
1134
1135       anUsedEdges.Remove( aDeadEdgeId );
1136       aPolygon.Remove( aPolygon.Length() );
1137
1138       // return to previous point
1139       Standard_Integer aLastValidEdge = aPolygon.Last();
1140       const BRepMesh_Edge& aLastEdge = GetEdge( Abs( aLastValidEdge ) );
1141
1142       if( aLastValidEdge > 0 )
1143       {
1144         aStartNode = aLastEdge.FirstNode();
1145         aPivotNode = aLastEdge.LastNode();
1146       }
1147       else
1148       {
1149         aStartNode = aLastEdge.LastNode();
1150         aPivotNode = aLastEdge.FirstNode();
1151       }
1152       
1153       const BRepMesh_Vertex& dV = GetVertex( aStartNode );
1154       const BRepMesh_Vertex& fV = GetVertex( aPivotNode );
1155       aPrevVEdge = fV.Coord() - dV.Coord();
1156       continue;
1157     }
1158     
1159     aStartNode = aPivotNode;
1160     aPivotNode = aRefOtherNode;
1161     aPrevVEdge = aRefCurrVEdge;
1162   }
1163
1164   CleanupPolygon( aPolygon, anInfectedEdges, aLoopEdges );
1165   MeshPolygon( aPolygon );
1166 }
1167
1168 //=======================================================================
1169 //function : MeshPolygon
1170 //purpose  : Triangulatiion of a closed aPolygonon described by the list of indexes of
1171 //           its edges in the structure. (negative index == reversed)
1172 //=======================================================================
1173 void BRepMesh_Delaun::MeshPolygon( TColStd_SequenceOfInteger& thePoly )
1174 {
1175   Standard_Integer aPivotNode, aVertex3 = 0;
1176   Standard_Integer aFirstNode, aLastNode;
1177   Standard_Integer aTriId;
1178
1179   if ( thePoly.Length() == 3 )
1180   {
1181     aTriId = myMeshData->AddElement( BRepMesh_Triangle( 
1182       Abs( thePoly(1) ), Abs( thePoly(2) ), Abs( thePoly(3) ), 
1183       thePoly(1) > 0,    thePoly(2) > 0,    thePoly(3) > 0,
1184       BRepMesh_Free ) );
1185       
1186     myCircles.MocAdd( aTriId );
1187     const BRepMesh_Edge& anEdge1 = GetEdge( Abs( thePoly(1) ) );
1188     const BRepMesh_Edge& anEdge2 = GetEdge( Abs( thePoly(2) ) );
1189     
1190     if ( thePoly(1) > 0)
1191     {
1192       aFirstNode = anEdge1.FirstNode();
1193       aLastNode  = anEdge1.LastNode();
1194     }
1195     else
1196     {
1197       aFirstNode = anEdge1.LastNode();
1198       aLastNode  = anEdge1.FirstNode();
1199     }
1200     
1201     if ( thePoly(2) > 0 ) 
1202       aVertex3 = anEdge2.LastNode();
1203     else
1204       aVertex3 = anEdge2.FirstNode();
1205
1206     Standard_Boolean isAdded = myCircles.Add( GetVertex( aFirstNode ).Coord(), 
1207       GetVertex( aLastNode ).Coord(), GetVertex( aVertex3 ).Coord(), aTriId );
1208       
1209     if ( !isAdded )
1210       myMeshData->RemoveElement( aTriId );
1211   }
1212   else if ( thePoly.Length() > 3 )
1213   {
1214     NCollection_Vector <Bnd_Box2d> aBoxes;
1215     Standard_Integer aPolyIdx, aUsedIdx = 0;
1216     Standard_Integer aPolyLen = thePoly.Length();
1217
1218     for ( aPolyIdx = 1; aPolyIdx <= aPolyLen; ++aPolyIdx )
1219     {
1220       const BRepMesh_Edge& anEdge = GetEdge( Abs( thePoly( aPolyIdx ) ) );
1221       aFirstNode = anEdge.FirstNode();
1222       aLastNode  = anEdge.LastNode();
1223       fillBndBox( aBoxes, GetVertex( aFirstNode ), GetVertex( aLastNode ) );
1224     }
1225     
1226     const BRepMesh_Edge& anEdge = GetEdge( Abs( thePoly(1) ) );
1227     Standard_Real aMinDist = RealLast();
1228
1229     if ( thePoly(1) > 0 )
1230     {
1231       aFirstNode = anEdge.FirstNode();
1232       aLastNode  = anEdge.LastNode();
1233     }
1234     else
1235     {
1236       aFirstNode = anEdge.LastNode();
1237       aLastNode  = anEdge.FirstNode();
1238     }
1239     
1240     gp_XY aVEdge( GetVertex( aLastNode  ).Coord() -
1241                   GetVertex( aFirstNode ).Coord() );
1242                   
1243     Standard_Real aVEdgeLen = aVEdge.Modulus();
1244     if ( aVEdgeLen > 0.)
1245     {
1246       aVEdge.SetCoord( aVEdge.X() / aVEdgeLen,
1247                        aVEdge.Y() / aVEdgeLen );
1248
1249       for ( aPolyIdx = 3; aPolyIdx <= aPolyLen; ++aPolyIdx )
1250       {
1251         const BRepMesh_Edge& aNextEdge = GetEdge( Abs( thePoly( aPolyIdx ) ) );
1252         if ( thePoly( aPolyIdx ) > 0)
1253           aPivotNode = aNextEdge.FirstNode();
1254         else
1255           aPivotNode = aNextEdge.LastNode();
1256           
1257         gp_XY aVEdgePivot( GetVertex( aPivotNode ).Coord() -
1258                            GetVertex( aLastNode  ).Coord() );
1259
1260         Standard_Real aDist = aVEdge ^ aVEdgePivot;
1261         if ( Abs( aDist ) > Precision::PConfusion() )
1262         {
1263           if ( ( aDist > 0. &&  myPositiveOrientation ) || 
1264                ( aDist < 0. && !myPositiveOrientation ) )
1265           { 
1266             if ( Abs( aDist ) < aMinDist )
1267             {
1268               Bnd_Box2d aBoxFirst, aBoxLast;
1269               aBoxFirst.Add( gp_Pnt2d( GetVertex( aPivotNode ).Coord() ) );
1270               aBoxFirst.Add( gp_Pnt2d( GetVertex( aLastNode  ).Coord() ) );
1271               
1272               aBoxLast.Add( gp_Pnt2d( GetVertex( aPivotNode ).Coord() ) );
1273               aBoxLast.Add( gp_Pnt2d( GetVertex( aFirstNode ).Coord() ) );
1274               
1275               BRepMesh_Edge aCheckE1( aLastNode,  aPivotNode, BRepMesh_Free );
1276               BRepMesh_Edge aCheckE2( aFirstNode, aPivotNode, BRepMesh_Free );
1277               
1278               Standard_Boolean isIntersect = Standard_False;
1279               for ( Standard_Integer aPolyIdx1 = 2; aPolyIdx1 <= aPolyLen; ++aPolyIdx1 )
1280               {
1281                 if( aPolyIdx1 == aPolyIdx )
1282                   continue;
1283                 
1284                 const BRepMesh_Edge& aNextEdge1 = GetEdge( Abs( thePoly( aPolyIdx1 ) ) );
1285                 if ( !aBoxFirst.IsOut( aBoxes.Value( aPolyIdx1 - 1 ) ) )
1286                 {                    
1287                   // intersection is possible...                  
1288                   if( IntSegSeg( aCheckE1, aNextEdge1 ) )
1289                   {
1290                     isIntersect = Standard_True;
1291                     break;
1292                   }
1293                 }
1294                 
1295                 if ( !aBoxLast.IsOut( aBoxes.Value( aPolyIdx1 - 1 ) ) &&
1296                      !aCheckE2.IsEqual( aNextEdge1 ) )
1297                 {
1298                   // intersection is possible...                  
1299                   if( IntSegSeg( aCheckE2, aNextEdge1 ) )
1300                   {
1301                     isIntersect = Standard_True;
1302                     break;
1303                   }
1304                 }
1305               }
1306               
1307               if( !isIntersect )
1308               {
1309                 aMinDist = aDist;
1310                 aVertex3 = aPivotNode;
1311                 aUsedIdx = aPolyIdx;
1312               }
1313             }
1314           }
1315         }
1316       }
1317     }
1318
1319     Standard_Integer aNewEdge2, aNewEdge3;
1320     if ( aMinDist < RealLast() )
1321     {
1322       aNewEdge2 = myMeshData->AddLink( BRepMesh_Edge( aLastNode, aVertex3,   BRepMesh_Free ) );
1323       aNewEdge3 = myMeshData->AddLink( BRepMesh_Edge( aVertex3,  aFirstNode, BRepMesh_Free ) );
1324       aTriId    = myMeshData->AddElement( BRepMesh_Triangle( 
1325         Abs( thePoly(1) ), Abs( aNewEdge2 ), Abs( aNewEdge3 ), 
1326         thePoly(1) > 0,    aNewEdge2 > 0,    aNewEdge3 > 0,
1327         BRepMesh_Free ) );
1328
1329       Standard_Boolean isAdded = myCircles.Add( GetVertex( aFirstNode ).Coord(), 
1330         GetVertex( aLastNode ).Coord(), GetVertex( aVertex3 ).Coord(), aTriId );
1331         
1332       if ( !isAdded )
1333         myMeshData->RemoveElement( aTriId );
1334
1335       if ( aUsedIdx < aPolyLen )
1336       {
1337         TColStd_SequenceOfInteger aSuitePoly;
1338         thePoly.Split( aUsedIdx, aSuitePoly );
1339         aSuitePoly.Prepend( -aNewEdge3 );
1340         MeshPolygon( aSuitePoly );
1341       }
1342       else 
1343         thePoly.Remove( aPolyLen );
1344
1345       if ( aUsedIdx > 3 )
1346       {
1347         thePoly.SetValue( 1, -aNewEdge2 );
1348         MeshPolygon( thePoly );
1349       }
1350     }
1351   }
1352 }
1353
1354 //=======================================================================
1355 //function : RemoveVertex
1356 //purpose  : Removes a vertex from the triangulation
1357 //=======================================================================
1358 void  BRepMesh_Delaun::RemoveVertex( const BRepMesh_Vertex& theVertex )
1359 {
1360   BRepMesh_SelectorOfDataStructureOfDelaun aSelector( myMeshData );
1361   aSelector.NeighboursOf( theVertex );
1362
1363   BRepMesh_MapOfIntegerInteger aLoopEdges( 10, myMeshData->Allocator() );
1364
1365   // Loop on triangles to be destroyed :
1366   BRepMesh_MapOfInteger::Iterator aTriangleIt( aSelector.Elements() );
1367   for ( ; aTriangleIt.More(); aTriangleIt.Next() )
1368     DeleteTriangle( aTriangleIt.Key(), aLoopEdges );
1369
1370   TColStd_SequenceOfInteger aPolygon;
1371   Standard_Integer aLoopEdgesCount = aLoopEdges.Extent();
1372   BRepMesh_MapOfIntegerInteger::Iterator aLoopEdgesIt( aLoopEdges );
1373
1374   if ( aLoopEdgesIt.More() )
1375   {
1376     const BRepMesh_Edge& anEdge = GetEdge( aLoopEdgesIt.Key() );
1377     Standard_Integer aFirstNode = anEdge.FirstNode();
1378     Standard_Integer aLastNode;
1379     Standard_Integer aPivotNode = anEdge.LastNode();
1380     Standard_Integer anEdgeId   = aLoopEdgesIt.Key();
1381     
1382     Standard_Boolean isPositive = (Standard_Boolean)aLoopEdges( anEdgeId );
1383     if ( !isPositive )
1384     {
1385       Standard_Integer aTmp;
1386       aTmp       = aFirstNode;
1387       aFirstNode = aPivotNode;
1388       aPivotNode = aTmp;
1389       
1390       aPolygon.Append( -anEdgeId );
1391     }
1392     else
1393       aPolygon.Append( anEdgeId );
1394
1395     aLoopEdges.UnBind( anEdgeId );
1396     
1397     aLastNode = aFirstNode;
1398     while ( aPivotNode != aLastNode )
1399     {
1400       BRepMesh_ListOfInteger::Iterator aLinkIt( myMeshData->LinkNeighboursOf( aPivotNode ) );
1401       for ( ; aLinkIt.More(); aLinkIt.Next() )
1402       {
1403         if ( aLinkIt.Value() != anEdgeId &&
1404              aLoopEdges.IsBound( aLinkIt.Value() ) )
1405         {
1406           Standard_Integer aCurrentNode;
1407           anEdgeId = aLinkIt.Value();
1408           const BRepMesh_Edge& anEdge1 = GetEdge( anEdgeId );
1409           
1410           aCurrentNode = anEdge1.LastNode();
1411           if ( aCurrentNode != aPivotNode )
1412           {
1413             aCurrentNode = anEdge1.FirstNode();
1414             aPolygon.Append( -anEdgeId );
1415           }
1416           else
1417             aPolygon.Append( anEdgeId );
1418             
1419           aPivotNode = aCurrentNode;
1420           aLoopEdges.UnBind( anEdgeId );
1421           break;
1422         }
1423       }
1424       
1425       if ( aLoopEdgesCount <= 0 )
1426         break;
1427       --aLoopEdgesCount;
1428     }
1429     
1430     MeshPolygon( aPolygon );
1431   }
1432 }
1433
1434
1435 //=======================================================================
1436 //function : AddVertices
1437 //purpose  : Adds some vertices in the triangulation.
1438 //=======================================================================
1439 void  BRepMesh_Delaun::AddVertices( BRepMesh_Array1OfVertexOfDelaun& theVertices )
1440 {
1441   BRepMesh_HeapSortVertexOfDelaun::Sort( theVertices, 
1442     BRepMesh_ComparatorOfVertexOfDelaun( SortingDirection, Precision::PConfusion() ) );
1443
1444   Standard_Integer aLower  = theVertices.Lower();
1445   Standard_Integer anUpper = theVertices.Upper();
1446     
1447   TColStd_Array1OfInteger aVertexIndexes( aLower, anUpper );
1448   for ( Standard_Integer i = aLower; i <= anUpper; ++i )     
1449     aVertexIndexes(i) = myMeshData->AddNode( theVertices(i) );
1450
1451   CreateTrianglesOnNewVertices( aVertexIndexes );
1452 }
1453
1454 //=======================================================================
1455 //function : UseEdge
1456 //purpose  : Modify mesh to use the edge. Return True if done
1457 //=======================================================================
1458 Standard_Boolean BRepMesh_Delaun::UseEdge( const Standard_Integer theIndex )
1459 {
1460   /*
1461   const BRepMesh_PairOfIndex& aPair = myMeshData->ElemConnectedTo( theIndex );
1462   if ( aPair.Extent() == 0 )
1463   {
1464     const BRepMesh_Edge& anEdge = GetEdge( theIndex );
1465     
1466     Standard_Integer aStartNode, aPivotNode, anOtherNode;
1467     aStartNode = anEdge.FirstNode();
1468     aPivotNode = anEdge.LastNode();
1469     
1470     const BRepMesh_ListOfInteger& aStartNodeNeighbors = myMeshData->LinkNeighboursOf( aStartNode );
1471     const BRepMesh_ListOfInteger& aPivotNodeNeighbors = myMeshData->LinkNeighboursOf( aPivotNode );
1472     
1473     if ( aStartNodeNeighbors.Extent() > 0 &&
1474          aPivotNodeNeighbors.Extent() > 0 )
1475     {
1476       const BRepMesh_Vertex& aStartVertex = GetVertex( aStartNode );
1477       const BRepMesh_Vertex& aPivotVertex = GetVertex( aPivotNode );
1478
1479       gp_XY aVEdge   ( aPivotVertex.Coord() );
1480       aVEdge.Subtract( aStartVertex.Coord() );
1481
1482       Standard_Real    anAngle    = 0.;
1483       Standard_Real    anAngleMin = RealLast();
1484       Standard_Real    anAngleMax = RealFirst();
1485       Standard_Integer aLeftEdge  = 0, aRightEdge = 0;
1486
1487       BRepMesh_ListOfInteger::Iterator aNeighborIt( aPivotNodeNeighbors );
1488       for ( ; aNeighborIt.More(); aNeighborIt.Next() )
1489       {
1490         Standard_Integer anEdgeId = aNeighborIt.Value();
1491         if ( anEdgeId != theIndex )
1492         {
1493           const BRepMesh_Edge& aNextEdge = GetEdge( anEdgeId );
1494
1495           Standard_Boolean isInMesh = Standard_True;
1496           if ( aNextEdge.Movability() == BRepMesh_Free )
1497           {
1498             if ( myMeshData->ElemConnectedTo( anEdgeId ).IsEmpty() ) 
1499               isInMesh = Standard_False;
1500           }
1501
1502           if ( isInMesh )
1503           {
1504             anOtherNode = aNextEdge.FirstNode();
1505             if ( anOtherNode == aPivotNode )
1506               anOtherNode = aNextEdge.LastNode();
1507
1508             gp_XY aVEdgeCur = GetVertex( anOtherNode ).Coord();
1509             aVEdgeCur.Subtract( aPivotVertex.Coord() );
1510
1511             anAngle = gp_Vec2d( aVEdge ).Angle( gp_Vec2d( aVEdgeCur ) );
1512           }
1513           
1514           if ( anAngle > anAngleMax )
1515           {
1516             anAngleMax = anAngle;
1517             aLeftEdge  = anEdgeId;
1518           }
1519           if ( anAngle < anAngleMin )
1520           {
1521             anAngleMin = anAngle;
1522             aRightEdge = anEdgeId;
1523           }
1524         }
1525       }
1526       
1527       if ( aLeftEdge > 0 )
1528       {
1529         if (aLeftEdge==aRightEdge)
1530         {
1531         }
1532         else
1533         {
1534         }
1535       }
1536     }
1537   }
1538   */
1539   return Standard_False;
1540 }
1541
1542 //=======================================================================
1543 //function : Result
1544 //purpose  : Gives the Mesh data structure
1545 //=======================================================================
1546 const Handle( BRepMesh_DataStructureOfDelaun )& BRepMesh_Delaun::Result() const
1547 {
1548   return myMeshData;
1549 }
1550
1551 //=======================================================================
1552 //function : Frontier
1553 //purpose  : Gives the list of frontier edges
1554 //=======================================================================
1555 const BRepMesh_MapOfInteger& BRepMesh_Delaun::Frontier()
1556 {
1557   BRepMesh_MapOfInteger::Iterator anEdgeIt( myMeshData->LinkOfDomain() );
1558
1559   myMapEdges.Clear();
1560   for ( ; anEdgeIt.More(); anEdgeIt.Next() )
1561   {
1562     Standard_Integer anEdge = anEdgeIt.Key();
1563     if ( GetEdge( anEdge ).Movability() == BRepMesh_Frontier )
1564       myMapEdges.Add( anEdge );
1565   }
1566   
1567   return myMapEdges;
1568 }
1569
1570 //=======================================================================
1571 //function : InternalEdges
1572 //purpose  : Gives the list of internal edges
1573 //=======================================================================
1574 const BRepMesh_MapOfInteger& BRepMesh_Delaun::InternalEdges()
1575 {
1576   BRepMesh_MapOfInteger::Iterator anEdgeIt( myMeshData->LinkOfDomain() );
1577
1578   myMapEdges.Clear();
1579   for ( ; anEdgeIt.More(); anEdgeIt.Next() )
1580   {
1581     Standard_Integer anEdge = anEdgeIt.Key();
1582     if ( GetEdge( anEdge ).Movability() == BRepMesh_Fixed )
1583       myMapEdges.Add( anEdge );
1584   }
1585   
1586   return myMapEdges;
1587 }
1588
1589 //=======================================================================
1590 //function : FreeEdges
1591 //purpose  : Gives the list of free edges used only one time
1592 //=======================================================================
1593 const BRepMesh_MapOfInteger& BRepMesh_Delaun::FreeEdges()
1594 {
1595   BRepMesh_MapOfInteger::Iterator anEdgeIt( myMeshData->LinkOfDomain() );
1596
1597   myMapEdges.Clear();
1598   for ( ; anEdgeIt.More(); anEdgeIt.Next() )
1599   {
1600     Standard_Integer anEdge = anEdgeIt.Key();
1601     if ( myMeshData->ElemConnectedTo( anEdge ).Extent() <= 1 )
1602       myMapEdges.Add( anEdge );
1603   }
1604   
1605   return myMapEdges;
1606 }
1607
1608 //=======================================================================
1609 //function : calculateDist
1610 //purpose  : Calculates distances between the given point and edges of
1611 //           triangle
1612 //=======================================================================
1613 static Standard_Real calculateDist( const gp_XY theVEdges[3],
1614                                     const gp_XY thePoints[3],
1615                                     const Standard_Integer theEdgesId[3],
1616                                     const BRepMesh_Vertex& theVertex,
1617                                     Standard_Real theDistance[3],
1618                                     Standard_Real theSqModulus[3],
1619                                     Standard_Integer& theEdgeOn )
1620 {
1621   Standard_Real aMinDist = -1;
1622   if ( !theVEdges || !thePoints || !theEdgesId || 
1623        !theDistance || !theSqModulus )
1624     return aMinDist;
1625     
1626   for( Standard_Integer i = 0; i < 3; ++i )
1627   {
1628     theSqModulus[i] = theVEdges[i].SquareModulus();
1629     if ( theSqModulus[i] <= EPSEPS )
1630       return -1;
1631       
1632     theDistance[i] = theVEdges[i] ^ ( theVertex.Coord() - thePoints[i] );
1633     
1634     Standard_Real aDist = theDistance[i] * theDistance[i];
1635     aDist /= theSqModulus[i];
1636     
1637     if ( aMinDist < 0 || aDist < aMinDist )
1638     {
1639       theEdgeOn = theEdgesId[i];
1640       aMinDist  = aDist;
1641     }
1642   }
1643   
1644   return aMinDist;
1645 }
1646
1647 //=======================================================================
1648 //function : Contains
1649 //purpose  : Test if triangle of index <TrianIndex> contains geometricaly
1650 //           <theVertex>. If <theEdgeOn> is != 0 then theVertex is on Edge 
1651 //           of  index <theEdgeOn>
1652 //=======================================================================
1653 Standard_Boolean BRepMesh_Delaun::Contains( const Standard_Integer theTriangleId,
1654                                             const BRepMesh_Vertex& theVertex,
1655                                             Standard_Integer& theEdgeOn ) const
1656 {
1657   theEdgeOn = 0;
1658   
1659   Standard_Integer e[3];
1660   Standard_Boolean o[3];
1661   Standard_Integer p[3];
1662
1663   GetTriangle( theTriangleId ).Edges( e[0], e[1], e[2],
1664                                       o[0], o[1], o[2] );
1665                                       
1666   const BRepMesh_Edge* anEdges[3] = { &GetEdge( e[0] ),
1667                                       &GetEdge( e[1] ),
1668                                       &GetEdge( e[2] ) };
1669   if ( o[0] )
1670   {
1671     p[0] = anEdges[0]->FirstNode();
1672     p[1] = anEdges[0]->LastNode();
1673   }
1674   else
1675   {
1676     p[1] = anEdges[0]->FirstNode();
1677     p[0] = anEdges[0]->LastNode();
1678   }
1679   
1680   if ( o[2] )
1681     p[2] = anEdges[2]->FirstNode();
1682   else
1683     p[2] = anEdges[2]->LastNode();
1684
1685   gp_XY aPoints[3];
1686   aPoints[0] = GetVertex( p[0] ).Coord();
1687   aPoints[1] = GetVertex( p[1] ).Coord();
1688   aPoints[2] = GetVertex( p[2] ).Coord();
1689   
1690   gp_XY aVEdges[3];
1691   aVEdges[0] = aPoints[1]; 
1692   aVEdges[0].Subtract( aPoints[0] );
1693   
1694   aVEdges[1] = aPoints[2]; 
1695   aVEdges[1].Subtract( aPoints[1] );
1696   
1697   aVEdges[2] = aPoints[0];
1698   aVEdges[2].Subtract( aPoints[2] );
1699
1700   Standard_Real aDistance[3];
1701   Standard_Real aSqModulus[3];
1702
1703   Standard_Real aMinDist;  
1704   aMinDist = calculateDist( aVEdges, aPoints, e, theVertex, aDistance, aSqModulus, theEdgeOn );
1705   if ( aMinDist < 0 )
1706     return Standard_False;
1707       
1708   if ( aMinDist > EPSEPS )
1709   {
1710     Standard_Integer anEdgeId = theEdgeOn;
1711     theEdgeOn = 0;
1712     
1713     if ( anEdgeId != 0 ) 
1714     {
1715       Standard_Integer i = 0;
1716       for ( ; i < 3; ++i )
1717       {
1718         if( e[i] == anEdgeId )
1719           break;
1720       }
1721       
1722       if( anEdges[i]->Movability() != BRepMesh_Free )
1723         if ( aDistance[i] < ( aSqModulus[i] / 5. ) )
1724           theEdgeOn = e[i];
1725     }
1726   }
1727
1728   return ( aDistance[0] + aDistance[1] + aDistance[2] != 0. &&
1729             ( ( aDistance[0] >= 0. && aDistance[1] >= 0. && aDistance[2] >= 0. ) ||
1730               ( aDistance[0] <= 0. && aDistance[1] <= 0. && aDistance[2] <= 0. ) ) );
1731 }
1732
1733
1734 //=============================================================================
1735 // Function: classifyPoint
1736 // This function is used for point classifying in case of coincidence of two 
1737 // vectors.
1738 // Returns zero value if point is out of segment and non zero value if point is
1739 // between the first and the second point of segment.
1740 //
1741 // thePoint1       - the start point of a segment (base point)
1742 // thePoint2       - the end point of a segment
1743 // thePointToCheck - the point to classify
1744 //=============================================================================
1745 static Standard_Integer classifyPoint( const gp_XY& thePoint1,
1746                                        const gp_XY& thePoint2,
1747                                        const gp_XY& thePointToCheck )
1748 {
1749   gp_XY aP1 = thePoint2       - thePoint1;
1750   gp_XY aP2 = thePointToCheck - thePoint1;
1751   
1752   Standard_Real aDist = Abs( aP1 ^ aP2 );
1753   if ( aDist >= Precision::PConfusion() )
1754   {
1755     aDist = ( aDist * aDist ) / aP1.SquareModulus();
1756     if ( aDist >= EPSEPS )
1757       return 0; //out
1758   }
1759     
1760   gp_XY aMult = aP1.Multiplied( aP2 );
1761   if ( aMult.X() < 0.0 || aMult.Y() < 0.0 )
1762     return 0; //out
1763     
1764   if ( aP1.SquareModulus() < aP2.SquareModulus() )
1765     return 0; //out
1766     
1767   if ( thePointToCheck.IsEqual( thePoint1, Precision::PConfusion() ) || 
1768        thePointToCheck.IsEqual( thePoint2, Precision::PConfusion() ) )
1769     return -1; //end point
1770     
1771   return 1;
1772 }
1773
1774 //=============================================================================
1775 // Function: IntSegSeg
1776 //=============================================================================
1777 Standard_Boolean BRepMesh_Delaun::IntSegSeg( const BRepMesh_Edge& theEdg1,
1778                                              const BRepMesh_Edge& theEdg2 )
1779 {
1780   gp_XY p1, p2, p3, p4;
1781   p1 = GetVertex( theEdg1.FirstNode() ).Coord();
1782   p2 = GetVertex( theEdg1.LastNode()  ).Coord();
1783   p3 = GetVertex( theEdg2.FirstNode() ).Coord();
1784   p4 = GetVertex( theEdg2.LastNode()  ).Coord();
1785   
1786   Standard_Integer aPoint1 = classifyPoint( p1, p2, p3 );
1787   Standard_Integer aPoint2 = classifyPoint( p1, p2, p4 );
1788   Standard_Integer aPoint3 = classifyPoint( p3, p4, p1 );
1789   Standard_Integer aPoint4 = classifyPoint( p3, p4, p2 );
1790   
1791   if ( aPoint1 > 0 || aPoint2 > 0 ||
1792        aPoint3 > 0 || aPoint4 > 0 )
1793     return Standard_True;
1794                     
1795   gp_XY aPl1 = p2 - p1;
1796   gp_XY aPl2 = p4 - p3;
1797   gp_XY aPl3 = p1 - p3;
1798     
1799   Standard_Real aCrossD1D2 = aPl1 ^ aPl2;
1800   Standard_Real aCrossD1D3 = aPl1 ^ aPl3;
1801   if ( Abs( aCrossD1D2 ) < Precision::PConfusion() )
1802   {
1803     if( Abs( aCrossD1D3 ) < Precision::PConfusion() )
1804     {
1805       Standard_Integer aPosHash = aPoint1 + aPoint2;
1806       if ( ( !aPosHash && aPoint3 ) ) //|| aPosHash < -1 )
1807         return Standard_True;
1808         
1809       return Standard_False;
1810     }
1811     else
1812       //parallel case
1813       return Standard_False;
1814   }
1815
1816   Standard_Real aPar = aCrossD1D3 / aCrossD1D2;
1817   // inrersects out of first segment range
1818   if( aPar < Precision::Angular() || aPar > 1 - Precision::Angular() )
1819     return Standard_False;
1820  
1821   Standard_Real aCrossD2D3 = aPl2 ^ aPl3;
1822   aPar = aCrossD2D3 / aCrossD1D2;
1823   // inrersects out of second segment range
1824   if( aPar < Precision::Angular() || aPar > 1 - Precision::Angular() )
1825     return Standard_False;
1826  
1827   return Standard_True;
1828 }