0022887: Request to make Intf_InterferencePolygon2d class thread-safe.
[occt.git] / src / IntCurve / IntCurve_IntPolyPolyGen.gxx
1 // File:        IntCurve_IntPolyPolyGen.gxx
2 // Created:     Tue Oct 13 11:12:26 1992
3 // Author:      Laurent BUCHARD
4
5 //  Modified by skv - Tue Mar  1 14:22:09 2005 OCC8169
6
7
8 #ifndef DEB
9 #define No_Standard_RangeError
10 #define No_Standard_OutOfRange
11 #endif
12
13
14 #include <Standard_ConstructionError.hxx>
15
16 #include <IntRes2d_Domain.hxx>
17 #include <IntRes2d_Position.hxx>
18 #include <IntRes2d_Transition.hxx>
19 #include <IntRes2d_IntersectionPoint.hxx>
20 #include <IntRes2d_IntersectionSegment.hxx>
21
22
23 #include <IntImpParGen.hxx>
24
25 #include <Intf_SectionPoint.hxx>
26 #include <Intf_SectionLine.hxx>
27 #include <Intf_TangentZone.hxx>
28 #include <Intf_InterferencePolygon2d.hxx>
29
30 #include <gp_Vec2d.hxx>
31
32 #include <math_Vector.hxx>
33 #include <math_FunctionSetRoot.hxx>
34 #include <math_NewtonFunctionSetRoot.hxx>
35
36 //======================================================================
37
38 //  Modified by skv - Tue Mar  1 14:22:09 2005 OCC8169 Begin
39 // #define NBITER_MAX_POLYGON 3
40 #define NBITER_MAX_POLYGON 10
41 //  Modified by skv - Tue Mar  1 14:22:09 2005 OCC8169 End
42 #define TOL_CONF_MINI   0.0000000001
43 #define TOL_MINI        0.0000000001
44
45 //----------------------------------------------------------------------
46
47
48
49
50
51 Standard_Boolean HeadOrEndPoint( const IntRes2d_Domain& D1
52                                 ,const TheCurve& C1
53                                 ,const Standard_Real u
54                                 ,const IntRes2d_Domain& D2
55                                 ,const TheCurve& C2
56                                 ,const Standard_Real v
57                                 ,const Standard_Real TolConf
58                                 ,IntRes2d_IntersectionPoint& IntPt
59                                 ,Standard_Boolean& HeadOn1
60                                 ,Standard_Boolean& HeadOn2
61                                 ,Standard_Boolean& EndOn1
62                                 ,Standard_Boolean& EndOn2
63                                 ,Standard_Integer  PosSegment);
64
65
66 //======================================================================
67 IntCurve_IntPolyPolyGen::IntCurve_IntPolyPolyGen(void) {
68   done = Standard_False;
69 }
70 //======================================================================
71 void IntCurve_IntPolyPolyGen::Perform( const TheCurve& C1
72                                       ,const IntRes2d_Domain& D1
73                                       ,const TheCurve& C2
74                                       ,const IntRes2d_Domain& D2
75                                       ,const Standard_Real TheTolConf
76                                       ,const Standard_Real TheTol)
77 {
78
79   Standard_Boolean AnErrorOccurred = Standard_False;
80
81   this->ResetFields();
82   DomainOnCurve1=D1;
83   DomainOnCurve2=D2; 
84   Standard_Real DU = D1.LastParameter()-D1.FirstParameter();
85   Standard_Real DV = D2.LastParameter()-D2.FirstParameter();
86   Standard_Real Tl=(TheTol < TOL_MINI)? TOL_MINI : TheTol;
87   Standard_Real TlConf=(TheTolConf < TOL_CONF_MINI)? TOL_CONF_MINI : TheTolConf;
88   Perform(C1,D1,C2,D2,TlConf,Tl,0,DU,DV);
89   //----------------------------------------------------------------------
90   //-- Traitement des points en bouts 
91   //----------------------------------------------------------------------
92   Standard_Boolean HeadOn1 = Standard_False;
93   Standard_Boolean HeadOn2 = Standard_False;
94   Standard_Boolean EndOn1  = Standard_False;
95   Standard_Boolean EndOn2  = Standard_False;
96   Standard_Integer i;
97   Standard_Integer n=this->NbPoints();
98
99
100   //--------------------------------------------------------------------
101   //-- On ne rejette les points Head Head ... End End 
102   //-- si ils figurent deja dans un bout de segment 
103   //-- ( On ne peut pas tester les egalites sur les parametres)
104   //-- ( ces points n etant pas trouves a EpsX pres           )
105   //-- PosSegment =            1    si Head Head
106   //--                       2      si Head End
107   //--                     4        si End  Head
108   //--                   8          si End  End
109   //--------------------------------------------------------------------
110   Standard_Integer PosSegment = 0;
111
112
113
114   for(i=1;i<=n;i++) { 
115     IntRes2d_Position Pos1 = this->Point(i).TransitionOfFirst().PositionOnCurve();
116     if(Pos1 == IntRes2d_Head) HeadOn1 = Standard_True;
117     else if(Pos1 == IntRes2d_End) EndOn1 = Standard_True;
118
119     IntRes2d_Position Pos2 =  this->Point(i).TransitionOfSecond().PositionOnCurve();
120     if(Pos2 == IntRes2d_Head) HeadOn2 = Standard_True;
121     else if(Pos2 == IntRes2d_End) EndOn2 = Standard_True;
122
123     if(Pos1 == IntRes2d_Head) { 
124       if(Pos2 == IntRes2d_Head)     PosSegment|=1;
125       else if(Pos2 == IntRes2d_End) PosSegment|=2;
126     }
127     else if(Pos1 == IntRes2d_End) { 
128       if(Pos2 == IntRes2d_Head)     PosSegment|=4;
129       else if(Pos2 == IntRes2d_End) PosSegment|=8;
130     }
131   }
132   
133   n=this->NbSegments();
134   for(i=1;i<=n;i++) { 
135     IntRes2d_Position Pos1 = this->Segment(i).FirstPoint().TransitionOfFirst().PositionOnCurve();
136     if(Pos1 == IntRes2d_Head)     HeadOn1 = Standard_True;
137     else if(Pos1 == IntRes2d_End) EndOn1  = Standard_True;
138     
139     IntRes2d_Position Pos2 =  this->Segment(i).FirstPoint().TransitionOfSecond().PositionOnCurve();
140     if(Pos2 == IntRes2d_Head)      HeadOn2 = Standard_True;
141     else if(Pos2 == IntRes2d_End)  EndOn2  = Standard_True;
142
143     if(Pos1 == IntRes2d_Head) { 
144       if(Pos2 == IntRes2d_Head)     PosSegment|=1;
145       else if(Pos2 == IntRes2d_End) PosSegment|=2;
146     }
147     else if(Pos1 == IntRes2d_End) { 
148       if(Pos2 == IntRes2d_Head)     PosSegment|=4;
149       else if(Pos2 == IntRes2d_End) PosSegment|=8;
150     }
151
152     Pos1 = this->Segment(i).LastPoint().TransitionOfFirst().PositionOnCurve();
153     if(Pos1 == IntRes2d_Head)     HeadOn1 = Standard_True;
154     else if(Pos1 == IntRes2d_End) EndOn1  = Standard_True;
155     
156     Pos2 =  this->Segment(i).LastPoint().TransitionOfSecond().PositionOnCurve();
157     if(Pos2 == IntRes2d_Head)     HeadOn2 = Standard_True;
158     else if(Pos2 == IntRes2d_End) EndOn2  = Standard_True;
159
160     if(Pos1 == IntRes2d_Head) { 
161       if(Pos2 == IntRes2d_Head)     PosSegment|=1;
162       else if(Pos2 == IntRes2d_End) PosSegment|=2;
163     }
164     else if(Pos1 == IntRes2d_End) { 
165       if(Pos2 == IntRes2d_Head)     PosSegment|=4;
166       else if(Pos2 == IntRes2d_End) PosSegment|=8;
167     }
168   }
169
170
171
172   Standard_Real U0 = D1.FirstParameter();
173   Standard_Real U1 = D1.LastParameter();
174   Standard_Real V0 = D2.FirstParameter();
175   Standard_Real V1 = D2.LastParameter();
176   Standard_Real v,u;
177   Standard_Real EpsX1 = TheCurveTool::EpsX(C1);
178   Standard_Real EpsX2 = TheCurveTool::EpsX(C2);
179   IntRes2d_IntersectionPoint IntPt;
180   
181   if(D1.FirstTolerance() || D2.FirstTolerance()) { 
182     if(HeadOrEndPoint(D1,C1,U0,D2,C2,V0,TheTolConf,IntPt,HeadOn1,HeadOn2,EndOn1,EndOn2,PosSegment)) 
183       this->Insert(IntPt);
184   }
185   if(D1.FirstTolerance() || D2.LastTolerance()) { 
186     if(HeadOrEndPoint(D1,C1,U0,D2,C2,V1,TheTolConf,IntPt,HeadOn1,HeadOn2,EndOn1,EndOn2,PosSegment)) 
187       this->Insert(IntPt);
188   }
189   if(D1.LastTolerance() || D2.FirstTolerance()) {
190     if(HeadOrEndPoint(D1,C1,U1,D2,C2,V0,TheTolConf,IntPt,HeadOn1,HeadOn2,EndOn1,EndOn2,PosSegment)) 
191       this->Insert(IntPt);
192   }
193   if(D1.LastTolerance() ||  D2.LastTolerance()) { 
194     if(HeadOrEndPoint(D1,C1,U1,D2,C2,V1,TheTolConf,IntPt,HeadOn1,HeadOn2,EndOn1,EndOn2,PosSegment)) 
195       this->Insert(IntPt);
196   }
197   if(AnErrorOccurred) {
198     //----------------------------------------------------------------------------------
199     //-- On a donne un point approche a la recherche du point exact, et cette recherche 
200     //-- a echoue. 
201     //-- Soit le point n'existe pas, soit c'est un point en bout dont un des parameteres
202     //-- est en dehors du domaine de la courbe. 
203     //--
204     //-- Dans le cas contraire, on suppose que les points en bouts ont ete trouves par 
205     //-- les interferences des polygones
206     //--
207     if(!HeadOn1)  {
208       u = U0;
209       v = TheProjPCur::FindParameter( C2,D1.FirstPoint(),V0,V1,EpsX2);
210       if(HeadOrEndPoint(D1,C1,u,D2,C2,v,TheTolConf,IntPt,HeadOn1,HeadOn2,EndOn1,EndOn2,PosSegment))
211         this->Insert(IntPt);
212     }
213     
214     if(!EndOn1)  {  
215       u = U1;
216       v = TheProjPCur::FindParameter( C2,D1.LastPoint(),V0,V1,EpsX2);
217       if(HeadOrEndPoint(D1,C1,u,D2,C2,v,TheTolConf,IntPt,HeadOn1,HeadOn2,EndOn1,EndOn2,PosSegment))
218         this->Insert(IntPt);
219     }
220     
221     if(!HeadOn2)  {  
222       u = TheProjPCur::FindParameter( C1,D2.FirstPoint(),U0,U1,EpsX1);
223       v = V0;
224       if(HeadOrEndPoint(D1,C1,u,D2,C2,v,TheTolConf,IntPt,HeadOn1,HeadOn2,EndOn1,EndOn2,PosSegment))
225         this->Insert(IntPt);
226     }
227     
228     if(!EndOn2)  {  
229       u = TheProjPCur::FindParameter( C1,D2.LastPoint(),U0,U1,EpsX1);
230       v = V1;
231       if(HeadOrEndPoint(D1,C1,u,D2,C2,v,TheTolConf,IntPt,HeadOn1,HeadOn2,EndOn1,EndOn2,PosSegment))
232         this->Insert(IntPt);
233     } 
234   }
235 }
236
237
238
239
240
241 //======================================================================
242 //==      A u t o   I n t e r s e c t i o  n 
243 //======================================================================
244 void IntCurve_IntPolyPolyGen::Perform( const TheCurve& C1
245                                       ,const IntRes2d_Domain& D1
246                                       ,const Standard_Real TheTolConf
247                                       ,const Standard_Real TheTol)
248 {
249
250   this->ResetFields();
251   DomainOnCurve1=D1;
252   DomainOnCurve2=D1; 
253   Standard_Real DU = D1.LastParameter()-D1.FirstParameter();
254   Standard_Real Tl=(TheTol < TOL_MINI)? TOL_MINI : TheTol;
255   Standard_Real TlConf=(TheTolConf < TOL_CONF_MINI)? TOL_CONF_MINI : TheTolConf;
256   Perform(C1,D1,TlConf,Tl,0,DU,DU);
257   //----------------------------------------------------------------------
258   //-- Traitement des points en bouts 
259   //----------------------------------------------------------------------
260   Standard_Boolean HeadOn1 = Standard_False;
261   Standard_Boolean HeadOn2 = Standard_False;
262   Standard_Boolean EndOn1  = Standard_False;
263   Standard_Boolean EndOn2  = Standard_False;
264   Standard_Integer i;
265   Standard_Integer n=this->NbPoints();
266
267
268   //--------------------------------------------------------------------
269   //-- On ne rejette les points Head Head ... End End 
270   //-- si ils figurent deja dans un bout de segment 
271   //-- ( On ne peut pas tester les egalites sur les parametres)
272   //-- ( ces points n etant pas trouves a EpsX pres           )
273   //-- PosSegment =            1    si Head Head
274   //--                       2      si Head End
275   //--                     4        si End  Head
276   //--                   8          si End  End
277   //--------------------------------------------------------------------
278   Standard_Integer PosSegment = 0;
279
280
281
282   for(i=1;i<=n;i++) { 
283     IntRes2d_Position Pos1 = this->Point(i).TransitionOfFirst().PositionOnCurve();
284     if(Pos1 == IntRes2d_Head) HeadOn1 = Standard_True;
285     else if(Pos1 == IntRes2d_End) EndOn1 = Standard_True;
286
287     IntRes2d_Position Pos2 =  this->Point(i).TransitionOfSecond().PositionOnCurve();
288     if(Pos2 == IntRes2d_Head) HeadOn2 = Standard_True;
289     else if(Pos2 == IntRes2d_End) EndOn2 = Standard_True;
290
291     if(Pos1 == IntRes2d_Head) { 
292       if(Pos2 == IntRes2d_Head)     PosSegment|=1;
293       else if(Pos2 == IntRes2d_End) PosSegment|=2;
294     }
295     else if(Pos1 == IntRes2d_End) { 
296       if(Pos2 == IntRes2d_Head)     PosSegment|=4;
297       else if(Pos2 == IntRes2d_End) PosSegment|=8;
298     }
299   }
300   
301   n=this->NbSegments();
302   for(i=1;i<=n;i++) { 
303     IntRes2d_Position Pos1 = this->Segment(i).FirstPoint().TransitionOfFirst().PositionOnCurve();
304     if(Pos1 == IntRes2d_Head)     HeadOn1 = Standard_True;
305     else if(Pos1 == IntRes2d_End) EndOn1  = Standard_True;
306     
307     IntRes2d_Position Pos2 =  this->Segment(i).FirstPoint().TransitionOfSecond().PositionOnCurve();
308     if(Pos2 == IntRes2d_Head)      HeadOn2 = Standard_True;
309     else if(Pos2 == IntRes2d_End)  EndOn2  = Standard_True;
310
311     if(Pos1 == IntRes2d_Head) { 
312       if(Pos2 == IntRes2d_Head)     PosSegment|=1;
313       else if(Pos2 == IntRes2d_End) PosSegment|=2;
314     }
315     else if(Pos1 == IntRes2d_End) { 
316       if(Pos2 == IntRes2d_Head)     PosSegment|=4;
317       else if(Pos2 == IntRes2d_End) PosSegment|=8;
318     }
319
320     Pos1 = this->Segment(i).LastPoint().TransitionOfFirst().PositionOnCurve();
321     if(Pos1 == IntRes2d_Head)     HeadOn1 = Standard_True;
322     else if(Pos1 == IntRes2d_End) EndOn1  = Standard_True;
323     
324     Pos2 =  this->Segment(i).LastPoint().TransitionOfSecond().PositionOnCurve();
325     if(Pos2 == IntRes2d_Head)     HeadOn2 = Standard_True;
326     else if(Pos2 == IntRes2d_End) EndOn2  = Standard_True;
327
328     if(Pos1 == IntRes2d_Head) { 
329       if(Pos2 == IntRes2d_Head)     PosSegment|=1;
330       else if(Pos2 == IntRes2d_End) PosSegment|=2;
331     }
332     else if(Pos1 == IntRes2d_End) { 
333       if(Pos2 == IntRes2d_Head)     PosSegment|=4;
334       else if(Pos2 == IntRes2d_End) PosSegment|=8;
335     }
336   }
337 }
338 //======================================================================
339
340
341
342 void IntCurve_IntPolyPolyGen::Perform( const TheCurve& C1
343                                       ,const IntRes2d_Domain& D1
344                                       ,const Standard_Real TolConf
345                                       ,const Standard_Real Tol
346                                       ,const Standard_Integer NbIter
347                                       ,const Standard_Real DeltaU
348                                       ,const Standard_Real) {
349   
350   gp_Vec2d Tan1,Tan2,Norm1,Norm2;
351   gp_Pnt2d P1,P2;
352   Standard_Integer nbsamples;
353   done = Standard_False;
354   Standard_Boolean AnErrorOccurred = Standard_False;
355   
356   
357   nbsamples = TheCurveTool::NbSamples(C1,D1.FirstParameter(),D1.LastParameter());
358
359   if(NbIter>3 || (NbIter>2 && nbsamples>100)) return;
360
361   nbsamples*=2;   //---  On prend systematiquement 2 fois plus de points que 
362                   //--   sur une courbe normale.  
363                   //--   Les courbes auto-intersectantes donne souvent des 
364                   //--   polygones assez loin de la courbe a parametre ct.
365
366   if(NbIter>0) {
367     if((D1.LastParameter()-D1.FirstParameter())
368        >0.5*(DeltaU)) { 
369       nbsamples=(3*(nbsamples*NbIter)/2);
370     }
371     else { 
372       nbsamples=(3*(nbsamples*NbIter))/2;
373     }
374   }
375   IntCurve_ThePolygon2d Poly1(C1,nbsamples,D1,Tol);
376   if(!Poly1.AutoIntersectionIsPossible()) { 
377     done = Standard_True;
378     return;
379   }
380   //-- Poly1.Dump();
381   //----------------------------------------------------------------------
382   //-- Si la deflection est inferieure a la Tolerance de Confusion
383   //-- Alors la deflection du polygone est fixee a TolConf
384   //-- (Detection des Zones de Tangence)
385   //----------------------------------------------------------------------
386   if(Poly1.DeflectionOverEstimation() < TolConf) { 
387     Poly1.SetDeflectionOverEstimation(TolConf);
388   }
389
390   Intf_InterferencePolygon2d InterPP(Poly1);  
391   IntCurve_ExactIntersectionPoint  EIP(C1,C1,TolConf);
392   Standard_Real U,V;
393   
394   //----------------------------------------------------------------------
395   //-- Traitement des SectionPoint 
396   //----------------------------------------------------------------------
397   Standard_Integer Nbsp = InterPP.NbSectionPoints();
398   if(Nbsp>=1) {
399     
400     //-- ---------------------------------------------------------------------
401     //-- tri  tri  tri  tri  tri  tri  tri  tri  tri  tri  tri  tri  tri  tri 
402     //-- 
403     Standard_Integer* TriIndex     = new Standard_Integer [Nbsp+1];
404     Standard_Integer* PtrSegIndex1 = new Standard_Integer [Nbsp+1];
405     Standard_Integer* PtrSegIndex2 = new Standard_Integer [Nbsp+1];
406     Standard_Boolean Triok;
407     Standard_Integer SegIndex1,SegIndex2,SegIndex_1,SegIndex_2;
408 //    Standard_Real    ParamOn1,ParamOn2,ParamOn_1,ParamOn_2;
409     Standard_Real    ParamOn1,ParamOn2;
410     Intf_PIType      Type; 
411     Standard_Integer i ;
412     for( i=1;i<=Nbsp;i++) { 
413       TriIndex[i]=i;
414       const Intf_SectionPoint& SPnt1 = InterPP.PntValue(i);
415       SPnt1.InfoFirst(Type,PtrSegIndex1[i],ParamOn1);
416       SPnt1.InfoSecond(Type,PtrSegIndex2[i],ParamOn2);
417     }
418  
419
420     do { 
421       Triok=Standard_True;
422
423       for(Standard_Integer tr=1;tr<Nbsp;tr++) { 
424         SegIndex1=PtrSegIndex1[TriIndex[tr]];
425         SegIndex_1=PtrSegIndex1[TriIndex[tr+1]];
426
427         SegIndex2=PtrSegIndex2[TriIndex[tr]];
428         SegIndex_2=PtrSegIndex2[TriIndex[tr+1]];
429
430         if(SegIndex1 > SegIndex_1) { 
431           Standard_Integer q=TriIndex[tr]; 
432           TriIndex[tr]=TriIndex[tr+1];
433           TriIndex[tr+1]=q;
434           Triok=Standard_False;
435         }
436         else if(SegIndex1 == SegIndex_1) { 
437           if(SegIndex2 > SegIndex_2) { 
438             Standard_Integer q=TriIndex[tr]; 
439             TriIndex[tr]=TriIndex[tr+1];
440             TriIndex[tr+1]=q;
441             Triok=Standard_False;
442           }
443         }
444       }
445     }
446     while(Triok==Standard_False);
447
448     //-- supression des doublons Si Si !
449     for(i=1; i<Nbsp;i++) { 
450       if(   (PtrSegIndex1[TriIndex[i]] == PtrSegIndex1[TriIndex[i+1]])
451          && (PtrSegIndex2[TriIndex[i]] == PtrSegIndex2[TriIndex[i+1]])) { 
452         TriIndex[i]=-i;
453
454       }
455     }
456
457     Standard_Integer Nelarg=(Poly1.NbSegments()/20);
458     if(Nelarg<2) Nelarg=2;
459
460     for(Standard_Integer sp=1; sp <= Nbsp; sp++) {
461       if(TriIndex[sp]>0) { 
462         const Intf_SectionPoint& SPnt = InterPP.PntValue(TriIndex[sp]);
463         
464         SPnt.InfoFirst(Type,SegIndex1,ParamOn1);
465         SPnt.InfoSecond(Type,SegIndex2,ParamOn2);
466         
467         if(Abs(SegIndex1-SegIndex2)>1) { 
468           
469           EIP.Perform(Poly1,Poly1,SegIndex1,SegIndex2,ParamOn1,ParamOn2);
470           AnErrorOccurred = EIP.AnErrorOccurred();
471           if(EIP.NbRoots()==0) {
472             //-- On supprime tous les segments voisins 
473             for(Standard_Integer k=sp+1;k<=Nbsp;k++) { 
474               Standard_Integer kk=TriIndex[k];
475               // modified by OFV OCC2502  Tue Apr 29 15:07:45 2003 .Begin
476               // --- avoid negative indicies as well as in outer done
477               if( kk > 0 ) {
478                 if(   Abs(SegIndex1-PtrSegIndex1[kk])< Nelarg
479                    && Abs(SegIndex2-PtrSegIndex2[kk])< Nelarg) { 
480                   TriIndex[k]=-k;
481                 }
482               }
483               // modified by OFV OCC2502  Tue Apr 29 15:11:34 2003 .End
484             }
485           }       
486           else if(EIP.NbRoots()>=1) { 
487             //--------------------------------------------------------------------
488             //-- On verifie que le point trouve est bien une racine
489             //--------------------------------------------------------------------
490             EIP.Roots(U,V);
491
492             TheCurveTool::D1(C1,U,P1,Tan1);
493             TheCurveTool::D1(C1,V,P2,Tan2);
494             Standard_Real Dist = P1.Distance(P2);
495             Standard_Real EpsX1 = 10.0*TheCurveTool::EpsX(C1);
496             
497             if(Abs(U-V)<=EpsX1) { 
498               //-----------------------------------------
499               //-- Solution non valide 
500               //-- Les maths ont du converger vers une 
501               //-- solution triviale ( point U = V )
502               //-----------------------------------------
503               Dist = TolConf+1.0;
504             }
505             
506             //-----------------------------------------------------------------
507             //-- On verifie que le point (u,v) n existe pas deja 
508             //--
509             done = Standard_True;
510             Standard_Integer nbp=NbPoints();
511             
512             for(Standard_Integer p=1; p<=nbp; p++) { 
513               const IntRes2d_IntersectionPoint& P=Point(p);
514               if(Abs(U-P.ParamOnFirst()) <= EpsX1) { 
515                 if(Abs(V-P.ParamOnSecond()) <= EpsX1) { 
516                   Dist = TolConf+1.0;  p+=nbp;
517                 }
518               }
519             }
520             
521             if(Dist <= TolConf) {    //-- Ou le point est deja present
522               IntRes2d_Position Pos1 = IntRes2d_Middle;
523               IntRes2d_Position Pos2 = IntRes2d_Middle;
524               IntRes2d_Transition  Trans1,Trans2;
525               //-----------------------------------------------------------------
526               //-- Calcul des Positions des Points sur la courbe
527               //--
528               if(P1.Distance(DomainOnCurve1.FirstPoint())<=DomainOnCurve1.FirstTolerance())    
529                 Pos1 = IntRes2d_Head;
530               else if(P1.Distance(DomainOnCurve1.LastPoint())<=DomainOnCurve1.LastTolerance()) 
531                 Pos1 = IntRes2d_End;
532               
533               if(P2.Distance(DomainOnCurve2.FirstPoint())<=DomainOnCurve2.FirstTolerance())    
534                 Pos2 = IntRes2d_Head;
535               else if(P2.Distance(DomainOnCurve2.LastPoint())<=DomainOnCurve2.LastTolerance()) 
536                 Pos2 = IntRes2d_End;
537               //-----------------------------------------------------------------
538               if(IntImpParGen::DetermineTransition( Pos1,Tan1,Trans1
539                                                    ,Pos2,Tan2,Trans2
540                                                    ,TolConf) == Standard_False) {
541                 TheCurveTool::D2(C1,U,P1,Tan1,Norm1);
542                 TheCurveTool::D2(C1,V,P2,Tan2,Norm2);
543                 IntImpParGen::DetermineTransition( Pos1,Tan1,Norm1,Trans1
544                                                   ,Pos2,Tan2,Norm2,Trans2
545                                                   ,TolConf);
546               }
547               IntRes2d_IntersectionPoint IP(P1,U,V,Trans1,Trans2,Standard_False);
548               Insert(IP);
549             }
550           }
551         }
552       }
553     }
554     delete [] TriIndex;
555     delete [] PtrSegIndex1;
556     delete [] PtrSegIndex2;
557   }
558   
559   
560   //----------------------------------------------------------------------
561   //-- Traitement des TangentZone
562   //----------------------------------------------------------------------
563   Standard_Integer Nbtz = InterPP.NbTangentZones();
564   Nbtz=0;
565   if(Nbtz) { 
566     Standard_Real ParamInf=D1.FirstParameter();
567     Standard_Real ParamSup=D1.LastParameter();
568     ParamSup=-RealLast();
569     ParamInf=RealLast();
570     for(Standard_Integer tz=1; tz <= Nbtz; tz++) {
571       Standard_Integer NbPnts = InterPP.ZoneValue(tz).NumberOfPoints();
572       //====================================================================
573       //== Recherche du premier et du dernier point dans la zone de tg.
574       //== ATTENTION LA LISTE N EST PAS TRIEE
575       //====================================================================
576       for(Standard_Integer tzz=1; tzz<=NbPnts; tzz++) {
577         const Intf_SectionPoint& SPnt1 = InterPP.ZoneValue(tz).GetPoint(tzz);
578         
579 //      Standard_Integer SegIndex,SegIndex1onP1,SegIndex1onP2;
580         Standard_Integer SegIndex1onP1;
581         Intf_PIType Type;
582         Standard_Real ParamOnLine;
583         
584         SPnt1.InfoFirst(Type,SegIndex1onP1,ParamOnLine);
585         if(SegIndex1onP1 >= Poly1.NbSegments()) { SegIndex1onP1--; ParamOnLine = 1.0; }
586         if(SegIndex1onP1 <= 0) { SegIndex1onP1=1; ParamOnLine = 0.0; }
587         Standard_Real Par = Poly1.ApproxParamOnCurve(SegIndex1onP1,ParamOnLine);
588         if(ParamSup<Par) ParamSup=Par;
589         if(ParamInf>Par) ParamInf=Par;
590       }
591     }
592     if(ParamSup > ParamInf) { 
593       //-- printf("\n %g -> %g     %g -> %g ",D1.FirstParameter(),ParamInf,D1.LastParameter(),ParamSup);
594       IntRes2d_Domain RecursD1( TheCurveTool::Value(C1,ParamInf)
595                                ,ParamInf,TolConf
596                                ,TheCurveTool::Value(C1,ParamSup)
597                                ,ParamSup,TolConf);
598       Perform(C1,RecursD1,TolConf,Tol,NbIter+1,ParamSup-ParamInf,0.0);
599     }
600   }
601   //----------------------------------------------------------------------
602   done = Standard_True;
603 }
604
605
606 Standard_Boolean HeadOrEndPoint( const IntRes2d_Domain& D1
607                                 ,const TheCurve& C1
608                                 ,const Standard_Real tu
609                                 ,const IntRes2d_Domain& D2
610                                 ,const TheCurve& C2
611                                 ,const Standard_Real tv
612                                 ,const Standard_Real TolConf
613                                 ,IntRes2d_IntersectionPoint& IntPt
614                                 ,Standard_Boolean& HeadOn1
615                                 ,Standard_Boolean& HeadOn2
616                                 ,Standard_Boolean& EndOn1
617                                 ,Standard_Boolean& EndOn2
618                                 ,Standard_Integer PosSegment) { 
619
620   gp_Pnt2d P1,P2,SP1,SP2;
621   gp_Vec2d T1,T2,N1,N2;
622   Standard_Real u=tu;
623   Standard_Real v=tv;
624   Standard_Real svu = u;
625   Standard_Real svv = v;
626
627   TheCurveTool::D1(C1,u,P1,T1);
628   TheCurveTool::D1(C2,v,P2,T2);
629   
630   IntRes2d_Position Pos1 = IntRes2d_Middle; 
631   IntRes2d_Position Pos2 = IntRes2d_Middle;
632   IntRes2d_Transition Trans1,Trans2;
633
634   //----------------------------------------------------------------------
635   //-- Head On 1   :        Head1 <-> P2
636   if(P2.Distance(D1.FirstPoint())<=D1.FirstTolerance())    { 
637     Pos1 = IntRes2d_Head; 
638     HeadOn1 = Standard_True; 
639     SP1 = D1.FirstPoint();
640     u = D1.FirstParameter();
641   }
642   //----------------------------------------------------------------------
643   //-- End On 1   :         End1 <-> P2
644   else if(P2.Distance(D1.LastPoint())<=D1.LastTolerance()) { 
645     Pos1 = IntRes2d_End; 
646     EndOn1 = Standard_True;
647     SP1 = D1.LastPoint();
648     u = D1.LastParameter();
649   }
650
651
652   //----------------------------------------------------------------------
653   //-- Head On 2   :        Head2 <-> P1
654   else if(P1.Distance(D2.FirstPoint())<=D2.FirstTolerance())    { 
655     Pos2 = IntRes2d_Head; 
656     HeadOn2 = Standard_True; 
657     SP2 = D2.FirstPoint();
658     v = D2.FirstParameter();
659   }
660   //----------------------------------------------------------------------
661   //-- End On 2   :        End2 <-> P1
662   else if(P1.Distance(D2.LastPoint())<=D2.LastTolerance()) { 
663     Pos2 = IntRes2d_End; 
664     EndOn2 = Standard_True;
665     SP2 = D2.LastPoint();
666     v = D2.LastParameter();
667   }
668
669   Standard_Real EpsX1 = TheCurveTool::EpsX(C1);
670   Standard_Real EpsX2 = TheCurveTool::EpsX(C2);
671
672   
673   if((Pos1 != IntRes2d_Middle)||(Pos2 !=  IntRes2d_Middle)) { 
674     if(Pos1 == IntRes2d_Middle) {
675       if(Abs(u-D1.FirstParameter()) <= EpsX1) { 
676         Pos1 = IntRes2d_Head;
677         P1 = D1.FirstPoint();
678         HeadOn1 = Standard_True;
679       }
680       else if(Abs(u-D1.LastParameter()) <= EpsX1) { 
681         Pos1 = IntRes2d_End;
682         P1 = D1.LastPoint();
683         EndOn1 = Standard_True;
684       }
685     }
686     else if(u!=tu) {
687       P1 = SP1; 
688     }
689       
690     
691     if(Pos2 == IntRes2d_Middle) { 
692       if(Abs(v-D2.FirstParameter()) <= EpsX2) { 
693         Pos2 = IntRes2d_Head;
694         HeadOn2 = Standard_True;
695         P2 = D2.FirstPoint();   
696         if(Pos1 != IntRes2d_Middle) {
697           P1.SetCoord(0.5*(P1.X()+P2.X()),0.5*(P1.Y()+P2.Y()));
698         }
699         else { 
700           P2 = P1; 
701         }
702       }
703       else if(Abs(v-D2.LastParameter()) <= EpsX2) { 
704         Pos2 = IntRes2d_End;
705         EndOn2 = Standard_True;
706         P2 = D2.LastPoint();
707         if(Pos1 != IntRes2d_Middle) {
708           P1.SetCoord(0.5*(P1.X()+P2.X()),0.5*(P1.Y()+P2.Y()));
709         }
710         else { 
711           P2 = P1; 
712         }
713       }
714     }
715
716
717     //--------------------------------------------------------------------
718     //-- On Teste si un point de bout de segment a deja ces trnasitions 
719     //-- Si Oui, on ne cree pas de nouveau point
720     //-- 
721     //-- PosSegment =            1    si Head Head
722     //--                       2      si Head End
723     //--                     4        si End  Head
724     //--                   8          si End  End
725     //--------------------------------------------------------------------
726     if(Pos1 == IntRes2d_Head) { 
727       if((Pos2 == IntRes2d_Head)&&(PosSegment & 1)) return(Standard_False);
728       if((Pos2 == IntRes2d_End )&&(PosSegment & 2)) return(Standard_False);
729     }
730     else if(Pos1 == IntRes2d_End) { 
731       if((Pos2 == IntRes2d_Head)&&(PosSegment & 4)) return(Standard_False);
732       if((Pos2 == IntRes2d_End )&&(PosSegment & 8)) return(Standard_False);
733     }
734
735
736     if(IntImpParGen::DetermineTransition( Pos1,T1,Trans1,Pos2,T2,Trans2,TolConf)
737        == Standard_False) { 
738       TheCurveTool::D2(C1,svu,P1,T1,N1);
739       TheCurveTool::D2(C2,svv,P2,T2,N2);
740       IntImpParGen::DetermineTransition(Pos1,T1,N1,Trans1,
741                                         Pos2,T2,N2,Trans2,TolConf);
742     }
743     IntPt.SetValues(P1,u,v,Trans1,Trans2,Standard_False);
744     return(Standard_True);
745   }
746   else 
747     return(Standard_False);
748 }
749
750
751
752
753
754
755
756 //======================================================================
757 void IntCurve_IntPolyPolyGen::Perform( const TheCurve& C1
758                                       ,const IntRes2d_Domain& D1
759                                       ,const TheCurve& C2
760                                       ,const IntRes2d_Domain& D2
761                                       ,const Standard_Real TolConf
762                                       ,const Standard_Real Tol
763                                       ,const Standard_Integer NbIter
764                                       ,const Standard_Real DeltaU
765                                       ,const Standard_Real DeltaV) {
766
767   gp_Vec2d Tan1,Tan2,Norm1,Norm2;
768   gp_Pnt2d P1,P2;
769   Standard_Integer nbsamplesOnC1,nbsamplesOnC2;
770   done = Standard_False;
771   Standard_Boolean AnErrorOccurred = Standard_False;
772
773   if(NbIter>NBITER_MAX_POLYGON) return;
774
775   nbsamplesOnC1 = TheCurveTool::NbSamples(C1,D1.FirstParameter(),D1.LastParameter());      
776
777   //// modified by jgv, 5.12.02 for OCC935 ////
778   if (NbIter == 0) // first time
779     {
780       if (nbsamplesOnC1 < 20)
781         nbsamplesOnC1 = 20;
782     }
783   else // NbIter > 0
784     {
785       if ((D1.LastParameter()-D1.FirstParameter()) > 0.5*(DeltaU))
786         nbsamplesOnC1=(5*(nbsamplesOnC1*NbIter))/4;
787       else
788         nbsamplesOnC1=(5*(nbsamplesOnC1*NbIter))/4;
789     }
790   /////////////////////////////////////////////
791
792   nbsamplesOnC2 = TheCurveTool::NbSamples(C2,D2.FirstParameter(),D2.LastParameter());
793   
794   //// modified by jgv, 5.12.02 for OCC935 ////
795   if (NbIter == 0) // first time
796     {
797       if (nbsamplesOnC2 < 20)
798         nbsamplesOnC2 = 20;
799     }
800   else // NbIter > 0
801     {
802       if ((D2.LastParameter()-D2.FirstParameter()) > 0.5*(DeltaV))
803         nbsamplesOnC2=(5*(nbsamplesOnC2*NbIter))/4;
804       else
805         nbsamplesOnC2=(5*(nbsamplesOnC2*NbIter))/4;
806     }
807   /////////////////////////////////////////////
808
809   IntCurve_ThePolygon2d *PtrPoly1,*PtrPoly2;
810   if(nbsamplesOnC2 > nbsamplesOnC1) { 
811     PtrPoly1 = new IntCurve_ThePolygon2d(C1,nbsamplesOnC1,D1,Tol);  
812     if(PtrPoly1->DeflectionOverEstimation() < TolConf) { 
813       PtrPoly2 = new IntCurve_ThePolygon2d(C2,nbsamplesOnC2,D2,Tol);
814     }
815     else { 
816       PtrPoly2 = new IntCurve_ThePolygon2d(C2,nbsamplesOnC2,D2,Tol,PtrPoly1->Bounding());
817       PtrPoly1->SetDeflectionOverEstimation( PtrPoly2->DeflectionOverEstimation()
818                                             +PtrPoly1->DeflectionOverEstimation());
819       PtrPoly1->ComputeWithBox(C1,PtrPoly2->Bounding());
820     }
821   }
822   else { 
823     PtrPoly2 = new IntCurve_ThePolygon2d(C2,nbsamplesOnC2,D2,Tol);  
824     if(PtrPoly2->DeflectionOverEstimation() < TolConf) {
825       PtrPoly1 = new IntCurve_ThePolygon2d(C1,nbsamplesOnC1,D1,Tol);
826     }
827     else { 
828       PtrPoly1 = new IntCurve_ThePolygon2d(C1,nbsamplesOnC1,D1,Tol,PtrPoly2->Bounding());
829       PtrPoly2->SetDeflectionOverEstimation( PtrPoly2->DeflectionOverEstimation()
830                                             +PtrPoly1->DeflectionOverEstimation());
831       PtrPoly2->ComputeWithBox(C2,PtrPoly1->Bounding());
832     }
833   }
834   //----------------------------------------------------------------------
835   //-- Si la deflection est inferieure a la Tolerance de Confusion
836   //-- Alors la deflection du polygone est fixee a TolConf
837   //-- (Detection des Zones de Tangence)
838   //----------------------------------------------------------------------
839
840   if(PtrPoly1->DeflectionOverEstimation() < TolConf) { 
841     PtrPoly1->SetDeflectionOverEstimation(TolConf);
842   }
843   if(PtrPoly2->DeflectionOverEstimation() < TolConf) { 
844     PtrPoly2->SetDeflectionOverEstimation(TolConf);
845   }
846   Intf_InterferencePolygon2d InterPP(*PtrPoly1,*PtrPoly2);  
847   IntCurve_ExactIntersectionPoint  EIP(C1,C2,TolConf);
848   Standard_Real U,V;
849   
850   //----------------------------------------------------------------------
851   //-- Traitement des SectionPoint 
852   //----------------------------------------------------------------------
853   Standard_Integer Nbsp = InterPP.NbSectionPoints();
854
855   if(Nbsp>=1) {
856     for(Standard_Integer sp=1; sp <= Nbsp; sp++) {
857       const Intf_SectionPoint& SPnt = InterPP.PntValue(sp);
858       Standard_Integer SegIndex1,SegIndex2;
859       Standard_Real    ParamOn1,ParamOn2;
860       Intf_PIType      Type;
861
862       SPnt.InfoFirst(Type,SegIndex1,ParamOn1);
863       SPnt.InfoSecond(Type,SegIndex2,ParamOn2);
864       EIP.Perform(*PtrPoly1,*PtrPoly2,SegIndex1,SegIndex2,ParamOn1,ParamOn2);
865       AnErrorOccurred = EIP.AnErrorOccurred();
866       if(EIP.NbRoots()>=1) { 
867         //--------------------------------------------------------------------
868         //-- On verifie que le point trouve est bien une racine
869         //--------------------------------------------------------------------
870         EIP.Roots(U,V);
871         TheCurveTool::D1(C1,U,P1,Tan1);
872         TheCurveTool::D1(C2,V,P2,Tan2);
873         Standard_Real Dist = P1.Distance(P2);
874         //-----------------------------------------------------------------
875         //-- On verifie que le point (u,v) n existe pas deja 
876         //--
877         done = Standard_True;
878         Standard_Integer nbp=NbPoints();
879         Standard_Real EpsX1 = 10.0*TheCurveTool::EpsX(C1);
880         Standard_Real EpsX2 = 10.0*TheCurveTool::EpsX(C2);
881
882         for(Standard_Integer p=1; p<=nbp; p++) { 
883           const IntRes2d_IntersectionPoint& P=Point(p);
884           if(Abs(U-P.ParamOnFirst()) <= EpsX1) { 
885             if(Abs(V-P.ParamOnSecond()) <= EpsX2) { 
886               Dist = TolConf+1.0;  p+=nbp;
887             }
888           }
889         }
890
891         if(Dist <= TolConf) {    //-- Ou le point est deja present
892           IntRes2d_Position Pos1 = IntRes2d_Middle;
893           IntRes2d_Position Pos2 = IntRes2d_Middle;
894           IntRes2d_Transition  Trans1,Trans2;
895           //-----------------------------------------------------------------
896           //-- Calcul des Positions des Points sur la courbe
897           //--
898           if(P1.Distance(DomainOnCurve1.FirstPoint())<=DomainOnCurve1.FirstTolerance())    
899             Pos1 = IntRes2d_Head;
900           else if(P1.Distance(DomainOnCurve1.LastPoint())<=DomainOnCurve1.LastTolerance()) 
901             Pos1 = IntRes2d_End;
902           
903           if(P2.Distance(DomainOnCurve2.FirstPoint())<=DomainOnCurve2.FirstTolerance())    
904             Pos2 = IntRes2d_Head;
905           else if(P2.Distance(DomainOnCurve2.LastPoint())<=DomainOnCurve2.LastTolerance()) 
906             Pos2 = IntRes2d_End;
907           //-----------------------------------------------------------------
908           //-- Calcul des Transitions (Voir IntImpParGen.cxx)
909           //--
910           if(IntImpParGen::DetermineTransition( Pos1,Tan1,Trans1
911                                                ,Pos2,Tan2,Trans2
912                                                ,TolConf)==Standard_False) { 
913             
914             TheCurveTool::D2(C1,U,P1,Tan1,Norm1);
915             TheCurveTool::D2(C2,V,P2,Tan2,Norm2);
916             IntImpParGen::DetermineTransition( Pos1,Tan1,Norm1,Trans1
917                                               ,Pos2,Tan2,Norm2,Trans2
918                                               ,TolConf);
919           }
920           IntRes2d_IntersectionPoint IP(P1,U,V,Trans1,Trans2,Standard_False);
921           Insert(IP);
922         }
923       } //-- if(EIP.NbRoots()>=1)
924     }
925   }
926   
927
928   //----------------------------------------------------------------------
929   //-- Traitement des TangentZone
930   //----------------------------------------------------------------------
931   Standard_Integer Nbtz = InterPP.NbTangentZones();
932   for(Standard_Integer tz=1; tz <= Nbtz; tz++) {
933     Standard_Integer NbPnts = InterPP.ZoneValue(tz).NumberOfPoints();
934     //====================================================================
935     //== Recherche du premier et du dernier point dans la zone de tg.
936     //====================================================================
937     Standard_Real ParamSupOnCurve2,ParamInfOnCurve2;
938     Standard_Real ParamSupOnCurve1,ParamInfOnCurve1;
939 //    Standard_Integer SegIndex,SegIndex1onP1,SegIndex1onP2,SegIndex2onP1,SegIndex2onP2;
940     Standard_Integer SegIndex1onP1,SegIndex1onP2;
941     Intf_PIType Type;
942     Standard_Real ParamOnLine;
943     Standard_Real PolyUInf,PolyUSup,PolyVInf,PolyVSup;
944     ParamSupOnCurve2=ParamSupOnCurve1=PolyUSup=PolyVSup=-RealLast();
945     ParamInfOnCurve2=ParamInfOnCurve1=PolyUInf=PolyVInf= RealLast();
946     for(Standard_Integer qq=1;qq<=NbPnts;qq++) { 
947       const Intf_SectionPoint& SPnt1 = InterPP.ZoneValue(tz).GetPoint(qq);
948       //====================================================================
949       //== On discretise sur les zones de tangence 
950       //== Test d arret : 
951       //==      Compteur 
952       //==     Deflection  < Tolerance 
953       //==  OU Echantillon < EpsX   (normalement la premiere condition est 
954       //==                           plus severe)
955       //====================================================================
956 //      Standard_Real _PolyUInf,_PolyUSup,_PolyVInf,_PolyVSup;
957       Standard_Real _PolyUInf,_PolyVInf;
958
959       SPnt1.InfoFirst(Type,SegIndex1onP1,ParamOnLine);
960       if(SegIndex1onP1 >= PtrPoly1->NbSegments()) { SegIndex1onP1--; ParamOnLine = 1.0; }
961       if(SegIndex1onP1 <= 0) { SegIndex1onP1=1; ParamOnLine = 0.0; }
962       _PolyUInf = PtrPoly1->ApproxParamOnCurve(SegIndex1onP1,ParamOnLine);
963       
964       SPnt1.InfoSecond(Type,SegIndex1onP2,ParamOnLine);
965       if(SegIndex1onP2 >= PtrPoly2->NbSegments()) { SegIndex1onP2--; ParamOnLine = 1.0; }
966       if(SegIndex1onP2 <= 0) { SegIndex1onP2=1; ParamOnLine = 0.0; }
967       _PolyVInf = PtrPoly2->ApproxParamOnCurve(SegIndex1onP2,ParamOnLine);
968       
969       //----------------------------------------------------------------------
970
971       if(ParamInfOnCurve1 > _PolyUInf) ParamInfOnCurve1=_PolyUInf;
972       if(ParamInfOnCurve2 > _PolyVInf) ParamInfOnCurve2=_PolyVInf;
973
974       if(ParamSupOnCurve1 < _PolyUInf) ParamSupOnCurve1=_PolyUInf;
975       if(ParamSupOnCurve2 < _PolyVInf) ParamSupOnCurve2=_PolyVInf;
976
977     }
978
979     PolyUInf= ParamInfOnCurve1;
980     PolyUSup= ParamSupOnCurve1;
981     PolyVInf= ParamInfOnCurve2;
982     PolyVSup= ParamSupOnCurve2;
983     
984     TheCurveTool::D0(C1,PolyUInf,P1);
985     TheCurveTool::D0(C2,PolyVInf,P2);
986     Standard_Real distmemesens = P1.SquareDistance(P2);
987     TheCurveTool::D0(C2,PolyVSup,P2);
988     Standard_Real distdiffsens = P1.SquareDistance(P2);
989     if(distmemesens > distdiffsens) { 
990       Standard_Real qwerty=PolyVInf; PolyVInf=PolyVSup; PolyVSup=qwerty;
991     }
992
993     
994
995     if(  (  (PtrPoly1->DeflectionOverEstimation() > TolConf)
996             ||(PtrPoly2->DeflectionOverEstimation() > TolConf))
997          &&(NbIter<NBITER_MAX_POLYGON)) {
998       
999       IntRes2d_Domain RecursD1( TheCurveTool::Value(C1,ParamInfOnCurve1)
1000                                ,ParamInfOnCurve1,TolConf
1001                                ,TheCurveTool::Value(C1,ParamSupOnCurve1)
1002                                ,ParamSupOnCurve1,TolConf);
1003       IntRes2d_Domain RecursD2( TheCurveTool::Value(C2,ParamInfOnCurve2)
1004                                ,ParamInfOnCurve2,TolConf
1005                                ,TheCurveTool::Value(C2,ParamSupOnCurve2)
1006                                ,ParamSupOnCurve2,TolConf);
1007       //-- On ne delete pas PtrPoly1(2) ,
1008       //-- ils sont detruits enfin de fct. 
1009       //-- !! Pas de return intempestif !!
1010       Perform(C1,RecursD1,C2,RecursD2,Tol,TolConf,NbIter+1,DeltaU,DeltaV);
1011     }
1012     else { 
1013       //-----------------------------------------------------------------
1014       //-- Calcul des Positions des Points sur la courbe et des 
1015       //-- Transitions sur chaque borne du segment
1016       
1017       IntRes2d_Position Pos1 = IntRes2d_Middle;
1018       IntRes2d_Position Pos2 = IntRes2d_Middle;
1019       IntRes2d_Transition  Trans1,Trans2;
1020       
1021       TheCurveTool::D1(C1,PolyUInf,P1,Tan1);
1022       TheCurveTool::D1(C2,PolyVInf,P2,Tan2);
1023       
1024       if(P1.Distance(DomainOnCurve1.FirstPoint())<=DomainOnCurve1.FirstTolerance())    { 
1025         Pos1 = IntRes2d_Head;
1026       }
1027       else if(P1.Distance(DomainOnCurve1.LastPoint())<=DomainOnCurve1.LastTolerance()) { 
1028         Pos1 = IntRes2d_End;  
1029       }
1030       if(P2.Distance(DomainOnCurve2.FirstPoint())<=DomainOnCurve2.FirstTolerance())    { 
1031         Pos2 = IntRes2d_Head; 
1032       }
1033       else if(P2.Distance(DomainOnCurve2.LastPoint())<=DomainOnCurve2.LastTolerance()) { 
1034         Pos2 = IntRes2d_End;  
1035       }
1036
1037       if(Pos1==IntRes2d_Middle && Pos2!=IntRes2d_Middle) { 
1038         PolyUInf=TheProjPCur::FindParameter( C1,P2,D1.FirstParameter(),D1.LastParameter(),TheCurveTool::EpsX(C1));
1039       }
1040       else if(Pos1!=IntRes2d_Middle && Pos2==IntRes2d_Middle) { 
1041         PolyVInf=TheProjPCur::FindParameter( C2,P1,D2.FirstParameter(),D2.LastParameter(),TheCurveTool::EpsX(C2));
1042       }
1043       else if(Abs(ParamInfOnCurve1-ParamSupOnCurve1) > Abs(ParamInfOnCurve2-ParamSupOnCurve2)) { 
1044         PolyVInf=TheProjPCur::FindParameter( C2,P1,D2.FirstParameter(),D2.LastParameter(),TheCurveTool::EpsX(C2));
1045       }
1046       else { 
1047         PolyUInf=TheProjPCur::FindParameter( C1,P2,D1.FirstParameter(),D1.LastParameter(),TheCurveTool::EpsX(C1));
1048       }
1049       
1050
1051
1052       if(IntImpParGen::DetermineTransition( Pos1,Tan1,Trans1,Pos2,Tan2,Trans2,TolConf) 
1053          == Standard_False) {
1054         TheCurveTool::D2(C1,PolyUInf,P1,Tan1,Norm1);
1055         TheCurveTool::D2(C2,PolyVInf,P2,Tan2,Norm2);
1056         IntImpParGen::DetermineTransition(Pos1,Tan1,Norm1,Trans1,
1057                                           Pos2,Tan2,Norm2,Trans2,TolConf);
1058       }
1059       IntRes2d_IntersectionPoint PtSeg1(P1,PolyUInf,PolyVInf
1060                                         ,Trans1,Trans2,Standard_False);
1061       //----------------------------------------------------------------------
1062       
1063       if((Abs(PolyUInf-PolyUSup) <= TheCurveTool::EpsX(C1)) 
1064          || (Abs(PolyVInf-PolyVSup) <= TheCurveTool::EpsX(C2))) { 
1065         Insert(PtSeg1);
1066       }
1067       else { 
1068         TheCurveTool::D1(C1,PolyUSup,P1,Tan1);
1069         TheCurveTool::D1(C2,PolyVSup,P2,Tan2);
1070         Pos1 = IntRes2d_Middle; Pos2 = IntRes2d_Middle;
1071           
1072         if(P1.Distance(DomainOnCurve1.FirstPoint())<=DomainOnCurve1.FirstTolerance())    { 
1073           Pos1 = IntRes2d_Head; 
1074         }
1075         else if(P1.Distance(DomainOnCurve1.LastPoint())<=DomainOnCurve1.LastTolerance()) { 
1076           Pos1 = IntRes2d_End;  
1077         }
1078         if(P2.Distance(DomainOnCurve2.FirstPoint())<=DomainOnCurve2.FirstTolerance())    { 
1079           Pos2 = IntRes2d_Head; 
1080         }
1081         else if(P2.Distance(DomainOnCurve2.LastPoint())<=DomainOnCurve2.LastTolerance()) { 
1082           Pos2 = IntRes2d_End;  
1083         }
1084
1085
1086         if(Pos1==IntRes2d_Middle && Pos2!=IntRes2d_Middle) { 
1087           PolyUInf=TheProjPCur::FindParameter( C1,P2,D1.FirstParameter(),D1.LastParameter(),TheCurveTool::EpsX(C1));
1088         }
1089         else if(Pos1!=IntRes2d_Middle && Pos2==IntRes2d_Middle) { 
1090           PolyVInf=TheProjPCur::FindParameter( C2,P1,D2.FirstParameter(),D2.LastParameter(),TheCurveTool::EpsX(C2));
1091         }
1092         else if(Abs(ParamInfOnCurve1-ParamSupOnCurve1) > Abs(ParamInfOnCurve2-ParamSupOnCurve2)) { 
1093           PolyVInf=TheProjPCur::FindParameter( C2,P1,D2.FirstParameter(),D2.LastParameter(),TheCurveTool::EpsX(C2));
1094         }
1095         else { 
1096           PolyUInf=TheProjPCur::FindParameter( C1,P2,D1.FirstParameter(),D1.LastParameter(),TheCurveTool::EpsX(C1));
1097         }
1098         
1099         if(IntImpParGen::DetermineTransition( Pos1,Tan1,Trans1,Pos2,Tan2,Trans2,TolConf)
1100            ==Standard_False) { 
1101           TheCurveTool::D2(C1,PolyUSup,P1,Tan1,Norm1);
1102           TheCurveTool::D2(C2,PolyVSup,P2,Tan2,Norm2);
1103           IntImpParGen::DetermineTransition(Pos1,Tan1,Norm1,Trans1,
1104                                             Pos2,Tan2,Norm2,Trans2,TolConf);
1105         }
1106         IntRes2d_IntersectionPoint PtSeg2(P1,PolyUSup,PolyVSup
1107                                           ,Trans1,Trans2,Standard_False);
1108         
1109         
1110         
1111         Standard_Boolean Oppos = (Tan1.Dot(Tan2) > 0.0)? Standard_False : Standard_True;
1112         if(ParamInfOnCurve1 > ParamSupOnCurve1) {
1113           IntRes2d_IntersectionSegment Seg(PtSeg2,PtSeg1,Oppos,Standard_False);
1114           Append(Seg);
1115         }
1116         else { 
1117           IntRes2d_IntersectionSegment Seg(PtSeg1,PtSeg2,Oppos,Standard_False);
1118           Append(Seg);
1119         }
1120       }
1121     }
1122   }
1123   //----------------------------------------------------------------------
1124   delete PtrPoly1;
1125   delete PtrPoly2;
1126   done = Standard_True;
1127 }
1128