4a71206512ed54556dd3a6a5d717155abd724b4a
[occt.git] / src / BRepTools / BRepTools_WireExplorer.cxx
1 // Created on: 1993-01-21
2 // Created by: Remi LEQUETTE
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
18 #include <BRep_Tool.hxx>
19 #include <BRepAdaptor_Surface.hxx>
20 #include <BRepTools.hxx>
21 #include <BRepTools_WireExplorer.hxx>
22 #include <Geom2d_Curve.hxx>
23 #include <Geom_Surface.hxx>
24 #include <GeomAdaptor_Surface.hxx>
25 #include <gp_Pnt2d.hxx>
26 #include <Precision.hxx>
27 #include <Standard_DomainError.hxx>
28 #include <Standard_NoMoreObject.hxx>
29 #include <Standard_NoSuchObject.hxx>
30 #include <TopExp.hxx>
31 #include <TopExp_Explorer.hxx>
32 #include <TopoDS.hxx>
33 #include <TopoDS_Edge.hxx>
34 #include <TopoDS_Face.hxx>
35 #include <TopoDS_Iterator.hxx>
36 #include <TopoDS_Vertex.hxx>
37 #include <TopoDS_Wire.hxx>
38 #include <TopTools_DataMapIteratorOfDataMapOfShapeListOfShape.hxx>
39 #include <TopTools_ListIteratorOfListOfShape.hxx>
40 #include <TopTools_ListOfShape.hxx>
41 #include <TopTools_MapIteratorOfMapOfShape.hxx>
42 #include <TopTools_MapOfShape.hxx>
43
44 //=======================================================================
45 // forward declarations of aux functions
46 //=======================================================================
47 static Standard_Boolean SelectDouble(TopTools_MapOfShape& Doubles,
48                                      TopTools_ListOfShape& L,
49                                      TopoDS_Edge&          E);
50
51 static Standard_Boolean SelectDegenerated(TopTools_ListOfShape& L,
52                                           TopoDS_Edge&          E);
53
54 static Standard_Real GetNextParamOnPC(const Handle(Geom2d_Curve)& aPC,
55                                       const gp_Pnt2d& aPRef,
56                                       const Standard_Real& fP,
57                                       const Standard_Real& lP,
58                                       const Standard_Real& tolU,
59                                       const Standard_Real& tolV,
60                                       const Standard_Boolean& reverse);
61
62 //=======================================================================
63 //function : BRepTools_WireExplorer
64 //purpose  : 
65 //=======================================================================
66 BRepTools_WireExplorer::BRepTools_WireExplorer()
67 : myReverse(Standard_False),
68   myTolU(0.0),
69   myTolV(0.0)
70 {
71 }
72
73 //=======================================================================
74 //function : BRepTools_WireExplorer
75 //purpose  : 
76 //=======================================================================
77 BRepTools_WireExplorer::BRepTools_WireExplorer(const TopoDS_Wire& W)
78 {
79   TopoDS_Face F = TopoDS_Face();
80   Init(W,F);
81 }
82
83 //=======================================================================
84 //function : BRepTools_WireExplorer
85 //purpose  : 
86 //=======================================================================
87 BRepTools_WireExplorer::BRepTools_WireExplorer(const TopoDS_Wire& W,
88                                                const TopoDS_Face& F)
89 {
90   Init(W,F);
91 }
92
93 //=======================================================================
94 //function : Init
95 //purpose  : 
96 //=======================================================================
97 void  BRepTools_WireExplorer::Init(const TopoDS_Wire& W)
98 {  
99   TopoDS_Face F = TopoDS_Face();
100   Init(W,F);
101 }
102
103 //=======================================================================
104 //function : Init
105 //purpose  : 
106 //=======================================================================
107 void  BRepTools_WireExplorer::Init(const TopoDS_Wire& W,
108                                    const TopoDS_Face& F)
109 {
110   myEdge = TopoDS_Edge();
111   myVertex = TopoDS_Vertex();
112   myMap.Clear();
113   myDoubles.Clear();
114
115   if (W.IsNull())
116     return;
117
118   Standard_Real UMin(0.0), UMax(0.0), VMin(0.0), VMax(0.0);
119   if (!F.IsNull())
120   {
121     // For the faces based on Cone, BSpline and Bezier compute the
122     // UV bounds to precise the UV tolerance values
123     const GeomAbs_SurfaceType aSurfType = BRepAdaptor_Surface(F, Standard_False).GetType();
124     if (aSurfType == GeomAbs_Cone ||
125         aSurfType == GeomAbs_BSplineSurface ||
126         aSurfType == GeomAbs_BezierSurface)
127     {
128       BRepTools::UVBounds(F, UMin, UMax, VMin, VMax);
129     }
130   }
131
132   Init(W, F, UMin, UMax, VMin, VMax);
133 }
134
135 //=======================================================================
136 //function : Init
137 //purpose  : 
138 //=======================================================================
139 void  BRepTools_WireExplorer::Init(const TopoDS_Wire& W,
140                                    const TopoDS_Face& F,
141                                    const Standard_Real UMin,
142                                    const Standard_Real UMax,
143                                    const Standard_Real VMin,
144                                    const Standard_Real VMax)
145 {
146   myEdge = TopoDS_Edge();
147   myVertex = TopoDS_Vertex();
148   myMap.Clear();
149   myDoubles.Clear();
150
151   if (W.IsNull())
152     return;
153
154   myFace = F;
155   Standard_Real dfVertToler = 0.;
156   myReverse = Standard_False;
157
158   if (!myFace.IsNull())
159   {
160     TopLoc_Location aL;
161     const Handle(Geom_Surface)& aSurf = BRep_Tool::Surface(myFace, aL);
162     GeomAdaptor_Surface aGAS(aSurf);
163     TopExp_Explorer anExp(W, TopAbs_VERTEX);
164     for (; anExp.More(); anExp.Next())
165     {
166       const TopoDS_Vertex& aV = TopoDS::Vertex(anExp.Current());
167       dfVertToler = Max(BRep_Tool::Tolerance(aV), dfVertToler);
168     }
169     if (dfVertToler < Precision::Confusion())
170     {
171       // Use tolerance of edges
172       for (TopoDS_Iterator it(W); it.More(); it.Next())
173         dfVertToler = Max(BRep_Tool::Tolerance(TopoDS::Edge(it.Value())), dfVertToler);
174
175       if (dfVertToler < Precision::Confusion())
176         // empty wire
177         return;
178     }
179     myTolU = 2. * aGAS.UResolution(dfVertToler);
180     myTolV = 2. * aGAS.VResolution(dfVertToler);
181
182     // uresolution for cone with infinite vmin vmax is too small.
183     if (aGAS.GetType() == GeomAbs_Cone)
184     {
185       gp_Pnt aP;
186       gp_Vec aD1U, aD1V;
187       aGAS.D1(UMin, VMin, aP, aD1U, aD1V);
188       Standard_Real tol1, tol2, maxtol = .0005*(UMax - UMin);
189       Standard_Real a = aD1U.Magnitude();
190
191       if (a <= Precision::Confusion())
192         tol1 = maxtol;
193       else
194         tol1 = Min(maxtol, dfVertToler / a);
195
196       aGAS.D1(UMin, VMax, aP, aD1U, aD1V);
197       a = aD1U.Magnitude();
198       if (a <= Precision::Confusion())
199         tol2 = maxtol;
200       else
201         tol2 = Min(maxtol, dfVertToler / a);
202
203       myTolU = 2. * Max(tol1, tol2);
204     }
205
206     if (aGAS.GetType() == GeomAbs_BSplineSurface ||
207       aGAS.GetType() == GeomAbs_BezierSurface)
208     {
209       Standard_Real maxTol = Max(myTolU, myTolV);
210       gp_Pnt aP;
211       gp_Vec aDU, aDV;
212       aGAS.D1((UMax - UMin) / 2., (VMax - VMin) / 2., aP, aDU, aDV);
213       Standard_Real mod = Sqrt(aDU*aDU + aDV*aDV);
214       if (mod > gp::Resolution())
215       {
216         if (mod * maxTol / dfVertToler < 1.5)
217         {
218           maxTol = 1.5 * dfVertToler / mod;
219         }
220         myTolU = maxTol;
221         myTolV = maxTol;
222       }
223     }
224
225     myReverse = (myFace.Orientation() == TopAbs_REVERSED);
226   }
227
228   // map of vertices to know if the wire is open
229   TopTools_MapOfShape vmap;
230   //  map of infinite edges
231   TopTools_MapOfShape anInfEmap;
232
233   // list the vertices
234   TopoDS_Vertex V1, V2;
235   TopTools_ListOfShape empty;
236
237   TopoDS_Iterator it(W);
238   while (it.More())
239   {
240     const TopoDS_Edge& E = TopoDS::Edge(it.Value());
241     TopAbs_Orientation Eori = E.Orientation();
242     if (Eori == TopAbs_INTERNAL || Eori == TopAbs_EXTERNAL)
243     {
244       it.Next();
245       continue;
246     }
247     TopExp::Vertices(E, V1, V2, Standard_True);
248
249     if (!V1.IsNull())
250     {
251       if (!myMap.IsBound(V1))
252         myMap.Bind(V1, empty);
253       myMap(V1).Append(E);
254
255       // add or remove in the vertex map
256       V1.Orientation(TopAbs_FORWARD);
257       if (!vmap.Add(V1))
258         vmap.Remove(V1);
259     }
260
261     if (!V2.IsNull())
262     {
263       V2.Orientation(TopAbs_REVERSED);
264       if (!vmap.Add(V2))
265         vmap.Remove(V2);
266     }
267
268     if (V1.IsNull() || V2.IsNull())
269     {
270       Standard_Real aF = 0., aL = 0.;
271       BRep_Tool::Range(E, aF, aL);
272
273       if (Eori == TopAbs_FORWARD)
274       {
275         if (aF == -Precision::Infinite())
276           anInfEmap.Add(E);
277       }
278       else
279       { // Eori == TopAbs_REVERSED
280         if (aL == Precision::Infinite())
281           anInfEmap.Add(E);
282       }
283     }
284     it.Next();
285   }
286
287   //Construction of the set of double edges.
288   TopoDS_Iterator it2(W);
289   TopTools_MapOfShape emap;
290   while (it2.More()) {
291     if (!emap.Add(it2.Value()))
292       myDoubles.Add(it2.Value());
293     it2.Next();
294   }
295
296   // if vmap is not empty the wire is open, let us find the first vertex
297   if (!vmap.IsEmpty()) {
298     TopTools_MapIteratorOfMapOfShape itt(vmap);
299     while (itt.Key().Orientation() != TopAbs_FORWARD) {
300       itt.Next();
301       if (!itt.More()) break;
302     }
303     if (itt.More()) V1 = TopoDS::Vertex(itt.Key());
304   }
305   else {
306     //   The wire is infinite Try to find the first vertex. It may be NULL.
307     if (!anInfEmap.IsEmpty()) {
308       TopTools_MapIteratorOfMapOfShape itt(anInfEmap);
309
310       for (; itt.More(); itt.Next()) {
311         TopoDS_Edge        anEdge = TopoDS::Edge(itt.Key());
312         TopAbs_Orientation anOri = anEdge.Orientation();
313         Standard_Real      aF;
314         Standard_Real      aL;
315
316         BRep_Tool::Range(anEdge, aF, aL);
317         if ((anOri == TopAbs_FORWARD  && aF == -Precision::Infinite()) ||
318           (anOri == TopAbs_REVERSED && aL == Precision::Infinite())) {
319           myEdge = anEdge;
320           myVertex = TopoDS_Vertex();
321
322           return;
323         }
324       }
325     }
326
327     // use the first vertex in iterator
328     it.Initialize(W);
329     while (it.More()) {
330       const TopoDS_Edge& E = TopoDS::Edge(it.Value());
331       TopAbs_Orientation Eori = E.Orientation();
332       if (Eori == TopAbs_INTERNAL || Eori == TopAbs_EXTERNAL) {
333         // JYL 10-03-97 : waiting for correct processing 
334         // of INTERNAL/EXTERNAL edges
335         it.Next();
336         continue;
337       }
338       TopExp::Vertices(E, V1, V2, Standard_True);
339       break;
340     }
341   }
342
343   if (V1.IsNull()) return;
344   if (!myMap.IsBound(V1)) return;
345
346   TopTools_ListOfShape& l = myMap(V1);
347   myEdge = TopoDS::Edge(l.First());
348   l.RemoveFirst();
349   myVertex = TopExp::FirstVertex(myEdge, Standard_True);
350
351 }
352
353 //=======================================================================
354 //function : More
355 //purpose  : 
356 //=======================================================================
357 Standard_Boolean  BRepTools_WireExplorer::More()const 
358 {
359   return !myEdge.IsNull();
360 }
361
362 //=======================================================================
363 //function : Next
364 //purpose  : 
365 //=======================================================================
366 void  BRepTools_WireExplorer::Next()
367 {
368   myVertex = TopExp::LastVertex (myEdge, Standard_True);
369
370   if (myVertex.IsNull()) {
371      myEdge = TopoDS_Edge();
372      return;
373   }
374   if (!myMap.IsBound(myVertex)) {
375      myEdge = TopoDS_Edge();
376      return;
377   }
378
379   TopTools_ListOfShape& l = myMap(myVertex);
380
381   if (l.IsEmpty()) {
382     myEdge = TopoDS_Edge();
383   }
384   else if (l.Extent() == 1) {
385 //  Modified by Sergey KHROMOV - Fri Jun 21 10:28:01 2002 OCC325 Begin
386     TopoDS_Vertex aV1;
387     TopoDS_Vertex aV2;
388     TopoDS_Edge   aNextEdge = TopoDS::Edge(l.First());
389
390     TopExp::Vertices(aNextEdge, aV1, aV2, Standard_True);
391
392     if (!aV1.IsSame(myVertex)) {
393       myEdge = TopoDS_Edge();
394       return;
395     }
396     if (!myFace.IsNull() && aV1.IsSame(aV2)) {
397       Handle(Geom2d_Curve) aPrevPC;
398       Handle(Geom2d_Curve) aNextPC;
399       Standard_Real        aPar11, aPar12;
400       Standard_Real        aPar21, aPar22;
401       Standard_Real        aPrevPar;
402       Standard_Real        aNextFPar;
403       Standard_Real        aNextLPar;
404
405       aPrevPC = BRep_Tool::CurveOnSurface(myEdge, myFace, aPar11, aPar12);
406       aNextPC = BRep_Tool::CurveOnSurface(aNextEdge, myFace, aPar21, aPar22);
407
408       if (aPrevPC.IsNull() || aNextPC.IsNull()) {
409               myEdge = TopoDS_Edge();
410               return;
411       }
412
413       if (myEdge.Orientation() == TopAbs_FORWARD)
414               aPrevPar = aPar12;
415       else
416               aPrevPar = aPar11;
417
418       if (aNextEdge.Orientation() == TopAbs_FORWARD) {
419               aNextFPar = aPar21;
420               aNextLPar = aPar22;
421       } else {
422               aNextFPar = aPar22;
423               aNextLPar = aPar21;
424       }
425
426       gp_Pnt2d aPPrev  = aPrevPC->Value(aPrevPar);
427       gp_Pnt2d aPNextF = aNextPC->Value(aNextFPar);
428       gp_Pnt2d aPNextL = aNextPC->Value(aNextLPar);
429
430       if (aPPrev.SquareDistance(aPNextF) > aPPrev.SquareDistance(aPNextL)) {
431               myEdge = TopoDS_Edge();
432               return;
433       }
434     }
435 //  Modified by Sergey KHROMOV - Fri Jun 21 11:08:16 2002 End
436     myEdge = TopoDS::Edge(l.First());
437     l.Clear();
438   }
439   else {
440     if (myFace.IsNull()) {
441       // Without Face - try to return edges
442       // as logically as possible
443       // At first degenerated edges.
444       TopoDS_Edge E = myEdge;
445       if (SelectDegenerated(l,E)) {
446               myEdge = E;
447               return;
448       }
449       // At second double edges.
450       E = myEdge;
451       if (SelectDouble(myDoubles,l,E)) {
452               myEdge = E;
453               return;
454       }
455
456       TopTools_ListIteratorOfListOfShape it(l); 
457       Standard_Boolean notfound = Standard_True;
458       while (it.More()) {
459               if (!it.Value().IsSame(myEdge)) {
460                 myEdge = TopoDS::Edge(it.Value());
461                 l.Remove(it);
462                 notfound = Standard_False;
463                 break;
464               }
465               it.Next();
466       }
467       
468       if(notfound) {
469               myEdge = TopoDS_Edge();
470               return;
471       }
472
473     }
474     else
475     {
476       // If we have more than one edge attached to the list
477       // probably wire that we explore contains a loop or loops.
478       Standard_Real dfFPar = 0., dfLPar = 0.;
479       Handle(Geom2d_Curve) aPCurve = BRep_Tool::CurveOnSurface (myEdge, myFace, dfFPar, dfLPar);
480       if(aPCurve.IsNull())
481       {
482         myEdge = TopoDS_Edge();
483         return;
484       }
485       // Note: current < myVertex > which is last on < myEdge >
486       //       equals in 2D to following 2D points:
487       //       edge is FORWARD  - point with MAX parameter on PCurve;
488       //       edge is REVERSED - point with MIN parameter on PCurve.
489
490       // Get 2D point equals to < myVertex > in 2D for current edge.
491       gp_Pnt2d PRef;
492       if( myEdge.Orientation() == TopAbs_REVERSED )
493         aPCurve->D0(dfFPar, PRef);
494       else 
495         aPCurve->D0(dfLPar, PRef);
496
497       // Get next 2D point from current edge's PCurve with parameter
498       // F + dP (REV) or L - dP (FOR)
499       Standard_Boolean isrevese = ( myEdge.Orientation() == TopAbs_REVERSED );
500       Standard_Real dfMPar = GetNextParamOnPC(aPCurve,PRef,dfFPar,dfLPar,myTolU,myTolV,isrevese);
501
502       gp_Pnt2d PRefm;
503       aPCurve->D0(dfMPar, PRefm);
504       // Get vector from PRef to PRefm
505       gp_Vec2d anERefDir(PRef,PRefm);
506       if (anERefDir.SquareMagnitude() < gp::Resolution())
507       {
508         myEdge = TopoDS_Edge();
509         return;
510       }
511
512       // Search the list of edges looking for the edge having hearest
513       // 2D point of connected vertex to current one and smallest angle.
514       // First process all degenerated edges, then - all others.
515
516       TopTools_ListIteratorOfListOfShape it;
517       Standard_Integer k = 1, kMin = 0, iDone = 0;
518       Standard_Boolean isDegenerated = Standard_True;
519       Standard_Real dmin = RealLast();
520       Standard_Real dfMinAngle = 3.0*M_PI, dfCurAngle = 3.0*M_PI;
521
522       for(iDone = 0; iDone < 2; iDone++)
523       {
524         it.Initialize(l);
525         while( it.More() )
526         {
527                 const TopoDS_Edge& E = TopoDS::Edge(it.Value());
528                 if( E.IsSame(myEdge) )
529                 {
530                   it.Next();
531                   k++;
532                   continue;
533                 }
534                 
535                 TopoDS_Vertex aVert1, aVert2;
536                 TopExp::Vertices (E, aVert1, aVert2, Standard_True);
537                 if( aVert1.IsNull() || aVert2.IsNull() )
538           {
539             it.Next();
540             k++;
541             continue;
542           }
543                 
544                 aPCurve = BRep_Tool::CurveOnSurface (E, myFace, dfFPar, dfLPar);
545                 if( aPCurve.IsNull() )
546           {
547             it.Next();
548             k++;
549             continue;
550           }
551                 
552                 gp_Pnt2d aPEb, aPEe;
553                 if( aVert1.IsSame(aVert2) == isDegenerated )
554                 {
555                   if( E.Orientation() == TopAbs_REVERSED )
556                     aPCurve->D0(dfLPar, aPEb);
557                   else  
558                     aPCurve->D0(dfFPar, aPEb);
559
560                   if( Abs(dfLPar-dfFPar) > Precision::PConfusion() )
561                   {
562                           isrevese = ( E.Orientation() == TopAbs_REVERSED );
563                           isrevese = !isrevese;
564                           Standard_Real aEPm = GetNextParamOnPC(aPCurve,aPEb,dfFPar,dfLPar,myTolU,myTolV,isrevese);
565                                 
566                           aPCurve->D0 (aEPm, aPEe);
567               if(aPEb.SquareDistance(aPEe) <= gp::Resolution())
568               {
569                 //seems to be very short curve
570                 gp_Vec2d aD;
571                 aPCurve->D1(aEPm, aPEe, aD);
572                       if( E.Orientation() == TopAbs_REVERSED )
573                   aPEe.SetXY(aPEb.XY()-aD.XY());
574                       else      
575                   aPEe.SetXY(aPEb.XY()+aD.XY());
576
577                 if(aPEb.SquareDistance(aPEe) <= gp::Resolution())
578                 {
579                   it.Next();
580                   k++;
581                   continue;
582                 }
583               }
584                           gp_Vec2d anEDir(aPEb, aPEe);
585                           dfCurAngle = Abs( anEDir.Angle(anERefDir) );
586                   }
587
588                   if( dfCurAngle <= dfMinAngle )
589                   {
590                           Standard_Real d = PRef.SquareDistance(aPEb);
591                           if( d <= Precision::PConfusion() )
592                             d = 0.;
593                           if( Abs(aPEb.X()-PRef.X()) < myTolU  &&  Abs(aPEb.Y()-PRef.Y()) < myTolV )
594                           {
595                             if( d <= dmin )
596                             {
597                                     dfMinAngle = dfCurAngle;
598                                     kMin = k;
599                                     dmin = d;
600                             }
601                           }
602                   }
603                 }
604                 it.Next();
605                 k++;
606         }// while it
607
608         if( kMin == 0 )
609         {
610                 isDegenerated = Standard_False;
611                 k = 1;
612                 dmin = RealLast();
613         }
614         else
615           break;
616       }// for iDone
617
618       if(kMin == 0)
619       {
620         // probably unclosed in 2d space wire
621         myEdge = TopoDS_Edge();
622         return;
623       }
624
625       // Selection the edge.
626       it.Initialize(l);
627       k = 1;
628       while( it.More() )
629       {
630         if( k == kMin )
631         {
632           myEdge = TopoDS::Edge(it.Value());
633           l.Remove(it);
634           break;
635         }
636         it.Next();
637         k++;
638       }
639     }//else face != NULL && l > 1
640   }//else l > 1
641 }
642
643 //=======================================================================
644 //function : Current
645 //purpose  : 
646 //=======================================================================
647 const TopoDS_Edge&  BRepTools_WireExplorer::Current()const 
648 {
649   return myEdge;
650 }
651
652 //=======================================================================
653 //function : Orientation
654 //purpose  : 
655 //=======================================================================
656 TopAbs_Orientation BRepTools_WireExplorer::Orientation() const
657 {
658   if (myVertex.IsNull()
659   && !myEdge.IsNull())
660   {
661     // infinite edge
662     return TopAbs_FORWARD;
663   }
664
665   TopoDS_Iterator it(myEdge,Standard_False);
666   while (it.More()) {
667     if (myVertex.IsSame(it.Value()))
668       return it.Value().Orientation();
669     it.Next();
670   }
671   throw Standard_NoSuchObject("BRepTools_WireExplorer::Orientation");
672 }
673
674 //=======================================================================
675 //function : CurrentVertex
676 //purpose  : 
677 //=======================================================================
678 const TopoDS_Vertex& BRepTools_WireExplorer::CurrentVertex() const
679 {
680   return myVertex;
681 }
682
683 //=======================================================================
684 //function : Clear
685 //purpose  : 
686 //=======================================================================
687
688 void BRepTools_WireExplorer::Clear()
689 {
690   myMap.Clear();
691   myDoubles.Clear();
692   myEdge = TopoDS_Edge();
693   myFace = TopoDS_Face();
694   myVertex = TopoDS_Vertex();
695 }
696
697
698 //=======================================================================
699 //function : SelectDouble
700 //purpose  : 
701 //=======================================================================
702
703 Standard_Boolean SelectDouble(TopTools_MapOfShape& Doubles,
704                               TopTools_ListOfShape& L,
705                               TopoDS_Edge&          E)
706 {
707   TopTools_ListIteratorOfListOfShape it(L);
708   
709   for (; it.More(); it.Next()) {
710     const TopoDS_Shape& CE = it.Value();
711     if (Doubles.Contains(CE) && (!E.IsSame(CE))) {
712       E = TopoDS::Edge(CE);
713       L.Remove(it);
714       return 1;
715     }
716   }
717   return 0;
718 }
719
720 //=======================================================================
721 //function : SelectDegenerated
722 //purpose  : 
723 //=======================================================================
724
725 Standard_Boolean SelectDegenerated(TopTools_ListOfShape& L,
726                                    TopoDS_Edge&          E)
727 {
728   TopTools_ListIteratorOfListOfShape it(L);
729   while (it.More()) {
730     if (!it.Value().IsSame(E)) {
731       E = TopoDS::Edge(it.Value());
732       if (BRep_Tool::Degenerated(E)) {
733         L.Remove(it);
734         return 1;
735       }
736     }
737     it.Next();
738   } 
739   return 0;
740 }
741
742 //=======================================================================
743 //function : GetNextParamOnPC
744 //purpose  : 
745 //=======================================================================
746 Standard_Real GetNextParamOnPC(const Handle(Geom2d_Curve)& aPC,
747                                const gp_Pnt2d& aPRef,
748                                const Standard_Real& fP,
749                                const Standard_Real& lP,
750                                const Standard_Real& tolU,
751                                const Standard_Real& tolV,
752                                const Standard_Boolean& reverse)
753 {
754   Standard_Real result = ( reverse ) ? fP : lP;
755   Standard_Real dP = Abs( lP - fP ) / 1000.; // was / 16.;
756   if( reverse )
757     {
758       Standard_Real startPar = fP;
759       Standard_Boolean nextPntOnEdge = Standard_False;
760       while( !nextPntOnEdge && startPar < lP )
761         {
762           gp_Pnt2d pnt;
763           startPar += dP;
764           aPC->D0(startPar, pnt);
765           if( Abs( aPRef.X() - pnt.X() ) < tolU && Abs( aPRef.Y() - pnt.Y() ) < tolV )
766             continue;
767           else
768             {
769               result = startPar;
770               nextPntOnEdge = Standard_True;
771               break;
772             }
773         }
774       
775       if( !nextPntOnEdge )
776         result = lP;
777
778       if( result > lP )
779         result = lP;
780     }
781   else
782     {
783       Standard_Real startPar = lP;
784       Standard_Boolean nextPntOnEdge = Standard_False;
785       while( !nextPntOnEdge && startPar > fP )
786         {
787           gp_Pnt2d pnt;
788           startPar -= dP;
789           aPC->D0(startPar, pnt);
790           if( Abs( aPRef.X() - pnt.X() ) < tolU && Abs( aPRef.Y() - pnt.Y() ) < tolV )
791             continue;
792           else
793             {
794               result = startPar;
795               nextPntOnEdge = Standard_True;
796               break;
797             }
798         }
799       
800       if( !nextPntOnEdge )
801         result = fP;
802
803       if( result < fP )
804         result = fP;
805     }
806
807   return result;
808 }