31308b24631c0522ea8d473ae3032c60f1bac16f
[occt.git] / src / IntCurve / IntCurve_IntPolyPolyGen.gxx
1 // Created on: 1992-10-13
2 // Created by: Laurent BUCHARD
3 // Copyright (c) 1992-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 //  Modified by skv - Tue Mar  1 14:22:09 2005 OCC8169
18
19
20 #ifndef OCCT_DEBUG
21 #define No_Standard_RangeError
22 #define No_Standard_OutOfRange
23 #endif
24
25
26 #include <Standard_ConstructionError.hxx>
27
28 #include <IntRes2d_Domain.hxx>
29 #include <IntRes2d_Position.hxx>
30 #include <IntRes2d_Transition.hxx>
31 #include <IntRes2d_IntersectionPoint.hxx>
32 #include <IntRes2d_IntersectionSegment.hxx>
33
34
35 #include <IntImpParGen.hxx>
36
37 #include <Intf_SectionPoint.hxx>
38 #include <Intf_SectionLine.hxx>
39 #include <Intf_TangentZone.hxx>
40 #include <Intf_InterferencePolygon2d.hxx>
41
42 #include <gp_Vec2d.hxx>
43
44 #include <math_Vector.hxx>
45 #include <math_FunctionSetRoot.hxx>
46 #include <math_NewtonFunctionSetRoot.hxx>
47 #include <NCollection_Handle.hxx>
48 #include <Bnd_Box2d.hxx>
49 #include <Precision.hxx>
50
51 //======================================================================
52
53 //  Modified by skv - Tue Mar  1 14:22:09 2005 OCC8169 Begin
54 // #define NBITER_MAX_POLYGON 3
55 #define NBITER_MAX_POLYGON 10
56 //  Modified by skv - Tue Mar  1 14:22:09 2005 OCC8169 End
57 #define TOL_CONF_MINI   0.0000000001
58 #define TOL_MINI        0.0000000001
59
60 //----------------------------------------------------------------------
61
62
63 void GetIntersection(const TheCurve& theC1, const Standard_Real theT1f, const Standard_Real theT1l,
64                      const TheCurve& theC2, const Standard_Real theT2f, const Standard_Real theT2l, 
65                      const Standard_Real theTolConf,
66                      const Standard_Integer theMaxCount,
67                      IntRes2d_IntersectionPoint& thePInt, Standard_Real& theDist,
68                      Standard_Integer& theCount);
69
70
71 Standard_Boolean HeadOrEndPoint( const IntRes2d_Domain& D1
72                                 ,const TheCurve& C1
73                                 ,const Standard_Real u
74                                 ,const IntRes2d_Domain& D2
75                                 ,const TheCurve& C2
76                                 ,const Standard_Real v
77                                 ,const Standard_Real TolConf
78                                 ,IntRes2d_IntersectionPoint& IntPt
79                                 ,Standard_Boolean& HeadOn1
80                                 ,Standard_Boolean& HeadOn2
81                                 ,Standard_Boolean& EndOn1
82                                 ,Standard_Boolean& EndOn2
83                                 ,Standard_Integer  PosSegment);
84
85
86 //======================================================================
87 IntCurve_IntPolyPolyGen::IntCurve_IntPolyPolyGen(void) {
88   done = Standard_False;
89 }
90 //======================================================================
91 void IntCurve_IntPolyPolyGen::Perform( const TheCurve& C1
92                                       ,const IntRes2d_Domain& D1
93                                       ,const TheCurve& C2
94                                       ,const IntRes2d_Domain& D2
95                                       ,const Standard_Real TheTolConf
96                                       ,const Standard_Real TheTol)
97 {
98   this->ResetFields();
99   DomainOnCurve1=D1;
100   DomainOnCurve2=D2; 
101   Standard_Real DU = D1.LastParameter()-D1.FirstParameter();
102   Standard_Real DV = D2.LastParameter()-D2.FirstParameter();
103   Standard_Real Tl=(TheTol < TOL_MINI)? TOL_MINI : TheTol;
104   Standard_Real TlConf=(TheTolConf < TOL_CONF_MINI)? TOL_CONF_MINI : TheTolConf;
105   Perform(C1,D1,C2,D2,TlConf,Tl,0,DU,DV);
106   //----------------------------------------------------------------------
107   //-- Processing of end points
108   //----------------------------------------------------------------------
109   Standard_Boolean HeadOn1 = Standard_False;
110   Standard_Boolean HeadOn2 = Standard_False;
111   Standard_Boolean EndOn1  = Standard_False;
112   Standard_Boolean EndOn2  = Standard_False;
113   Standard_Integer i;
114   Standard_Integer n=this->NbPoints();
115
116
117   //--------------------------------------------------------------------
118   //-- The points Head Head ... End End are not rejected if
119   //-- they are already present at the end of segment 
120   //-- ( It is not possible to test the equities on the parameters)
121   //-- ( these points are not found at EpsX precision    )
122   //-- PosSegment =            1    if Head Head
123   //--                       2      if Head End
124   //--                     4        if End  Head
125   //--                   8          if End  End
126   //--------------------------------------------------------------------
127   Standard_Integer PosSegment = 0;
128
129   for(i=1;i<=n;i++) { 
130     IntRes2d_Position Pos1 = this->Point(i).TransitionOfFirst().PositionOnCurve();
131     if(Pos1 == IntRes2d_Head) HeadOn1 = Standard_True;
132     else if(Pos1 == IntRes2d_End) EndOn1 = Standard_True;
133
134     IntRes2d_Position Pos2 =  this->Point(i).TransitionOfSecond().PositionOnCurve();
135     if(Pos2 == IntRes2d_Head) HeadOn2 = Standard_True;
136     else if(Pos2 == IntRes2d_End) EndOn2 = Standard_True;
137
138     if(Pos1 == IntRes2d_Head) { 
139       if(Pos2 == IntRes2d_Head)     PosSegment|=1;
140       else if(Pos2 == IntRes2d_End) PosSegment|=2;
141     }
142     else if(Pos1 == IntRes2d_End) { 
143       if(Pos2 == IntRes2d_Head)     PosSegment|=4;
144       else if(Pos2 == IntRes2d_End) PosSegment|=8;
145     }
146   }
147   
148   n=this->NbSegments();
149   for(i=1;i<=n;i++) { 
150     IntRes2d_Position Pos1 = this->Segment(i).FirstPoint().TransitionOfFirst().PositionOnCurve();
151     if(Pos1 == IntRes2d_Head)     HeadOn1 = Standard_True;
152     else if(Pos1 == IntRes2d_End) EndOn1  = Standard_True;
153     
154     IntRes2d_Position Pos2 =  this->Segment(i).FirstPoint().TransitionOfSecond().PositionOnCurve();
155     if(Pos2 == IntRes2d_Head)      HeadOn2 = Standard_True;
156     else if(Pos2 == IntRes2d_End)  EndOn2  = Standard_True;
157
158     if(Pos1 == IntRes2d_Head) { 
159       if(Pos2 == IntRes2d_Head)     PosSegment|=1;
160       else if(Pos2 == IntRes2d_End) PosSegment|=2;
161     }
162     else if(Pos1 == IntRes2d_End) { 
163       if(Pos2 == IntRes2d_Head)     PosSegment|=4;
164       else if(Pos2 == IntRes2d_End) PosSegment|=8;
165     }
166
167     Pos1 = this->Segment(i).LastPoint().TransitionOfFirst().PositionOnCurve();
168     if(Pos1 == IntRes2d_Head)     HeadOn1 = Standard_True;
169     else if(Pos1 == IntRes2d_End) EndOn1  = Standard_True;
170     
171     Pos2 =  this->Segment(i).LastPoint().TransitionOfSecond().PositionOnCurve();
172     if(Pos2 == IntRes2d_Head)     HeadOn2 = Standard_True;
173     else if(Pos2 == IntRes2d_End) EndOn2  = Standard_True;
174
175     if(Pos1 == IntRes2d_Head) { 
176       if(Pos2 == IntRes2d_Head)     PosSegment|=1;
177       else if(Pos2 == IntRes2d_End) PosSegment|=2;
178     }
179     else if(Pos1 == IntRes2d_End) { 
180       if(Pos2 == IntRes2d_Head)     PosSegment|=4;
181       else if(Pos2 == IntRes2d_End) PosSegment|=8;
182     }
183   }
184
185   Standard_Real U0 = D1.FirstParameter();
186   Standard_Real U1 = D1.LastParameter();
187   Standard_Real V0 = D2.FirstParameter();
188   Standard_Real V1 = D2.LastParameter();
189   IntRes2d_IntersectionPoint IntPt;
190   
191   if(D1.FirstTolerance() || D2.FirstTolerance()) { 
192     if(HeadOrEndPoint(D1,C1,U0,D2,C2,V0,TheTolConf,IntPt,HeadOn1,HeadOn2,EndOn1,EndOn2,PosSegment)) 
193       this->Insert(IntPt);
194   }
195   if(D1.FirstTolerance() || D2.LastTolerance()) { 
196     if(HeadOrEndPoint(D1,C1,U0,D2,C2,V1,TheTolConf,IntPt,HeadOn1,HeadOn2,EndOn1,EndOn2,PosSegment)) 
197       this->Insert(IntPt);
198   }
199   if(D1.LastTolerance() || D2.FirstTolerance()) {
200     if(HeadOrEndPoint(D1,C1,U1,D2,C2,V0,TheTolConf,IntPt,HeadOn1,HeadOn2,EndOn1,EndOn2,PosSegment)) 
201       this->Insert(IntPt);
202   }
203   if(D1.LastTolerance() ||  D2.LastTolerance()) { 
204     if(HeadOrEndPoint(D1,C1,U1,D2,C2,V1,TheTolConf,IntPt,HeadOn1,HeadOn2,EndOn1,EndOn2,PosSegment)) 
205       this->Insert(IntPt);
206   }
207 }
208
209
210 //======================================================================
211 //==      A u t o   I n t e r s e c t i o  n 
212 //======================================================================
213 void IntCurve_IntPolyPolyGen::Perform( const TheCurve& C1
214                                       ,const IntRes2d_Domain& D1
215                                       ,const Standard_Real TheTolConf
216                                       ,const Standard_Real TheTol)
217 {
218
219   this->ResetFields();
220   DomainOnCurve1=D1;
221   DomainOnCurve2=D1; 
222   Standard_Real DU = D1.LastParameter()-D1.FirstParameter();
223   Standard_Real Tl=(TheTol < TOL_MINI)? TOL_MINI : TheTol;
224   Standard_Real TlConf=(TheTolConf < TOL_CONF_MINI)? TOL_CONF_MINI : TheTolConf;
225   Perform(C1,D1,TlConf,Tl,0,DU,DU);
226   Standard_Integer i;
227   Standard_Integer n=this->NbPoints();
228
229   //--------------------------------------------------------------------
230    //-- The points Head Head ... End End are not rejected if
231   //-- they are already present at the end of segment 
232   //-- ( It is not possible to test the equities on the parameters)
233   //-- ( these points are not found at EpsX precision    )
234   //-- PosSegment =            1    if Head Head
235   //--                       2      if Head End
236   //--                     4        if End  Head
237   //--                   8          if End  End
238   //--------------------------------------------------------------------
239   Standard_Integer PosSegment = 0;
240
241   for(i=1;i<=n;i++) { 
242     IntRes2d_Position Pos1 = this->Point(i).TransitionOfFirst().PositionOnCurve();
243     IntRes2d_Position Pos2 =  this->Point(i).TransitionOfSecond().PositionOnCurve();
244
245     if(Pos1 == IntRes2d_Head) { 
246       if(Pos2 == IntRes2d_Head)     PosSegment|=1;
247       else if(Pos2 == IntRes2d_End) PosSegment|=2;
248     }
249     else if(Pos1 == IntRes2d_End) { 
250       if(Pos2 == IntRes2d_Head)     PosSegment|=4;
251       else if(Pos2 == IntRes2d_End) PosSegment|=8;
252     }
253   }
254   
255   n=this->NbSegments();
256   for(i=1;i<=n;i++) { 
257     IntRes2d_Position Pos1 = this->Segment(i).FirstPoint().TransitionOfFirst().PositionOnCurve();
258     IntRes2d_Position Pos2 =  this->Segment(i).FirstPoint().TransitionOfSecond().PositionOnCurve();
259
260     if(Pos1 == IntRes2d_Head) { 
261       if(Pos2 == IntRes2d_Head)     PosSegment|=1;
262       else if(Pos2 == IntRes2d_End) PosSegment|=2;
263     }
264     else if(Pos1 == IntRes2d_End) { 
265       if(Pos2 == IntRes2d_Head)     PosSegment|=4;
266       else if(Pos2 == IntRes2d_End) PosSegment|=8;
267     }
268
269     Pos1 = this->Segment(i).LastPoint().TransitionOfFirst().PositionOnCurve();
270     Pos2 =  this->Segment(i).LastPoint().TransitionOfSecond().PositionOnCurve();
271
272     if(Pos1 == IntRes2d_Head) { 
273       if(Pos2 == IntRes2d_Head)     PosSegment|=1;
274       else if(Pos2 == IntRes2d_End) PosSegment|=2;
275     }
276     else if(Pos1 == IntRes2d_End) { 
277       if(Pos2 == IntRes2d_Head)     PosSegment|=4;
278       else if(Pos2 == IntRes2d_End) PosSegment|=8;
279     }
280   }
281 }
282 //======================================================================
283
284 void IntCurve_IntPolyPolyGen::Perform( const TheCurve& C1
285                                       ,const IntRes2d_Domain& D1
286                                       ,const Standard_Real TolConf
287                                       ,const Standard_Real Tol
288                                       ,const Standard_Integer NbIter
289                                       ,const Standard_Real /*DeltaU*/
290                                       ,const Standard_Real) {
291   
292   gp_Vec2d Tan1,Tan2,Norm1,Norm2;
293   gp_Pnt2d P1,P2;
294   Standard_Integer nbsamples;
295   done = Standard_False;
296   
297   nbsamples = TheCurveTool::NbSamples(C1,D1.FirstParameter(),D1.LastParameter());
298
299   if(NbIter>3 || (NbIter>2 && nbsamples>100)) return;
300
301   nbsamples*=2;   //---  We take systematically two times more points 
302                   //--   than on a normal curve.  
303                   //--   Auto-intersecting curves often produce  
304                   //--   polygons rather far from the curve with parameter ct.
305
306   if(NbIter>0) { 
307     nbsamples=(3*(nbsamples*NbIter))/2;
308   }
309   IntCurve_ThePolygon2d Poly1(C1,nbsamples,D1,Tol);
310   if(!Poly1.AutoIntersectionIsPossible()) { 
311     done = Standard_True;
312     return;
313   }
314   //-- Poly1.Dump();
315   //----------------------------------------------------------------------
316   //-- If the deflection is less than the Tolerance of Confusion
317   //-- then the deflection of the polygon is set in TolConf
318   //-- (Detection of Tangency Zones)
319   //----------------------------------------------------------------------
320   if(Poly1.DeflectionOverEstimation() < TolConf) { 
321     Poly1.SetDeflectionOverEstimation(TolConf);
322   }
323
324   Intf_InterferencePolygon2d InterPP(Poly1);  
325   IntCurve_ExactIntersectionPoint  EIP(C1,C1,TolConf);
326   Standard_Real U,V;
327   
328   //----------------------------------------------------------------------
329   //-- Processing of SectionPoint 
330   //----------------------------------------------------------------------
331   Standard_Integer Nbsp = InterPP.NbSectionPoints();
332   if(Nbsp>=1) {
333     
334     //-- ---------------------------------------------------------------------
335     //-- filtering, filtering, filtering ...
336     //-- 
337     Standard_Integer* TriIndex     = new Standard_Integer [Nbsp+1];
338     Standard_Integer* PtrSegIndex1 = new Standard_Integer [Nbsp+1];
339     Standard_Integer* PtrSegIndex2 = new Standard_Integer [Nbsp+1];
340     Standard_Boolean Triok;
341     Standard_Integer SegIndex1,SegIndex2,SegIndex_1,SegIndex_2;
342 //    Standard_Real    ParamOn1,ParamOn2,ParamOn_1,ParamOn_2;
343     Standard_Real    ParamOn1,ParamOn2;
344     Intf_PIType      Type; 
345     Standard_Integer i ;
346     for( i=1;i<=Nbsp;i++) { 
347       TriIndex[i]=i;
348       const Intf_SectionPoint& SPnt1 = InterPP.PntValue(i);
349       SPnt1.InfoFirst(Type,PtrSegIndex1[i],ParamOn1);
350       SPnt1.InfoSecond(Type,PtrSegIndex2[i],ParamOn2);
351     }
352  
353
354     do { 
355       Triok=Standard_True;
356
357       for(Standard_Integer tr=1;tr<Nbsp;tr++) { 
358               SegIndex1=PtrSegIndex1[TriIndex[tr]];
359               SegIndex_1=PtrSegIndex1[TriIndex[tr+1]];
360
361               SegIndex2=PtrSegIndex2[TriIndex[tr]];
362               SegIndex_2=PtrSegIndex2[TriIndex[tr+1]];
363
364               if(SegIndex1 > SegIndex_1) { 
365                 Standard_Integer q=TriIndex[tr]; 
366                 TriIndex[tr]=TriIndex[tr+1];
367                 TriIndex[tr+1]=q;
368                 Triok=Standard_False;
369               }
370               else if(SegIndex1 == SegIndex_1) { 
371                 if(SegIndex2 > SegIndex_2) { 
372                   Standard_Integer q=TriIndex[tr]; 
373                   TriIndex[tr]=TriIndex[tr+1];
374                   TriIndex[tr+1]=q;
375                   Triok=Standard_False;
376                 }
377               }
378       }
379     }
380     while(Triok==Standard_False);
381
382     //-- supression des doublons Si Si !
383     for(i=1; i<Nbsp;i++) { 
384       if(   (PtrSegIndex1[TriIndex[i]] == PtrSegIndex1[TriIndex[i+1]])
385                 && (PtrSegIndex2[TriIndex[i]] == PtrSegIndex2[TriIndex[i+1]])) { 
386               TriIndex[i]=-i;
387       }
388     }
389
390     Standard_Integer Nelarg=(Poly1.NbSegments()/20);
391     if(Nelarg<2) Nelarg=2;
392
393     for(Standard_Integer sp=1; sp <= Nbsp; sp++) {
394       if(TriIndex[sp]>0) { 
395               const Intf_SectionPoint& SPnt = InterPP.PntValue(TriIndex[sp]);
396         
397               SPnt.InfoFirst(Type,SegIndex1,ParamOn1);
398               SPnt.InfoSecond(Type,SegIndex2,ParamOn2);
399         
400               if(Abs(SegIndex1-SegIndex2)>1) { 
401           
402                 EIP.Perform(Poly1,Poly1,SegIndex1,SegIndex2,ParamOn1,ParamOn2);
403                 if(EIP.NbRoots()==0) {
404                   //-- All neighbor segments are removed 
405                   for(Standard_Integer k=sp+1;k<=Nbsp;k++) { 
406                     Standard_Integer kk=TriIndex[k];
407                     // --- avoid negative indicies as well as in outer done
408                     if( kk > 0 ) {
409                             if(   Abs(SegIndex1-PtrSegIndex1[kk])< Nelarg
410                                && Abs(SegIndex2-PtrSegIndex2[kk])< Nelarg) { 
411                               TriIndex[k]=-k;
412                             }
413               }
414                   }
415                 }         
416                 else if(EIP.NbRoots()>=1) { 
417                   //--------------------------------------------------------------------
418                   //-- It is checked if the found point is a root
419                   //--------------------------------------------------------------------
420                   EIP.Roots(U,V);
421
422                   TheCurveTool::D1(C1,U,P1,Tan1);
423                   TheCurveTool::D1(C1,V,P2,Tan2);
424                   Standard_Real Dist = P1.Distance(P2);
425                   Standard_Real EpsX1 = 10.0*TheCurveTool::EpsX(C1);
426             
427                   if(Abs(U-V)<=EpsX1) { 
428                     //-----------------------------------------
429                     //-- Solution not valid 
430                     //-- The maths should have converged in a 
431                     //-- trivial solution  ( point U = V )
432                     //-----------------------------------------
433                     Dist = TolConf+1.0;
434                   }
435             
436                   //-----------------------------------------------------------------
437                   //-- It is checked if the point (u,v) already exists  
438                   //--
439                   done = Standard_True;
440                   Standard_Integer nbp=NbPoints();
441             
442                   for(Standard_Integer p=1; p<=nbp; p++) { 
443                     const IntRes2d_IntersectionPoint& P=Point(p);
444                     if(Abs(U-P.ParamOnFirst()) <= EpsX1) { 
445                             if(Abs(V-P.ParamOnSecond()) <= EpsX1) { 
446                               Dist = TolConf+1.0;  p+=nbp;
447                             }
448                     }
449                   }
450             
451                   if(Dist <= TolConf) {    //-- Or the point is already present
452                     IntRes2d_Position Pos1 = IntRes2d_Middle;
453                     IntRes2d_Position Pos2 = IntRes2d_Middle;
454                     IntRes2d_Transition  Trans1,Trans2;
455                     //-----------------------------------------------------------------
456                     //-- Calculate Positions of Points on the curve
457                     //--
458                     if(P1.Distance(DomainOnCurve1.FirstPoint())<=DomainOnCurve1.FirstTolerance())    
459                             Pos1 = IntRes2d_Head;
460                     else if(P1.Distance(DomainOnCurve1.LastPoint())<=DomainOnCurve1.LastTolerance()) 
461                             Pos1 = IntRes2d_End;
462               
463                     if(P2.Distance(DomainOnCurve2.FirstPoint())<=DomainOnCurve2.FirstTolerance())    
464                             Pos2 = IntRes2d_Head;
465                     else if(P2.Distance(DomainOnCurve2.LastPoint())<=DomainOnCurve2.LastTolerance()) 
466                             Pos2 = IntRes2d_End;
467                     //-----------------------------------------------------------------
468                     if(IntImpParGen::DetermineTransition( Pos1,Tan1,Trans1
469                                                          ,Pos2,Tan2,Trans2
470                                                          ,TolConf) == Standard_False) 
471               {
472                             TheCurveTool::D2(C1,U,P1,Tan1,Norm1);
473                             TheCurveTool::D2(C1,V,P2,Tan2,Norm2);
474                             IntImpParGen::DetermineTransition( Pos1,Tan1,Norm1,Trans1
475                                                               ,Pos2,Tan2,Norm2,Trans2
476                                                               ,TolConf);
477                     }
478                     IntRes2d_IntersectionPoint IP(P1,U,V,Trans1,Trans2,Standard_False);
479                     Insert(IP);
480                   }
481                 }
482               }
483       }
484     }
485     delete [] TriIndex;
486     delete [] PtrSegIndex1;
487     delete [] PtrSegIndex2;
488   }
489  done = Standard_True;
490 }
491
492
493 Standard_Boolean HeadOrEndPoint( const IntRes2d_Domain& D1
494                                 ,const TheCurve& C1
495                                 ,const Standard_Real tu
496                                 ,const IntRes2d_Domain& D2
497                                 ,const TheCurve& C2
498                                 ,const Standard_Real tv
499                                 ,const Standard_Real TolConf
500                                 ,IntRes2d_IntersectionPoint& IntPt
501                                 ,Standard_Boolean& HeadOn1
502                                 ,Standard_Boolean& HeadOn2
503                                 ,Standard_Boolean& EndOn1
504                                 ,Standard_Boolean& EndOn2
505                                 ,Standard_Integer PosSegment) { 
506
507   gp_Pnt2d P1,P2,SP1,SP2;
508   gp_Vec2d T1,T2,N1,N2;
509   Standard_Real u=tu;
510   Standard_Real v=tv;
511   Standard_Real svu = u;
512   Standard_Real svv = v;
513
514   TheCurveTool::D1(C1,u,P1,T1);
515   TheCurveTool::D1(C2,v,P2,T2);
516   
517   IntRes2d_Position Pos1 = IntRes2d_Middle; 
518   IntRes2d_Position Pos2 = IntRes2d_Middle;
519   IntRes2d_Transition Trans1,Trans2;
520
521   //----------------------------------------------------------------------
522   //-- Head On 1   :        Head1 <-> P2
523   if(P2.Distance(D1.FirstPoint())<=D1.FirstTolerance())    { 
524     Pos1 = IntRes2d_Head; 
525     HeadOn1 = Standard_True; 
526     SP1 = D1.FirstPoint();
527     u = D1.FirstParameter();
528   }
529   //----------------------------------------------------------------------
530   //-- End On 1   :         End1 <-> P2
531   else if(P2.Distance(D1.LastPoint())<=D1.LastTolerance()) { 
532     Pos1 = IntRes2d_End; 
533     EndOn1 = Standard_True;
534     SP1 = D1.LastPoint();
535     u = D1.LastParameter();
536   }
537
538   //----------------------------------------------------------------------
539   //-- Head On 2   :        Head2 <-> P1
540   else if(P1.Distance(D2.FirstPoint())<=D2.FirstTolerance())    { 
541     Pos2 = IntRes2d_Head; 
542     HeadOn2 = Standard_True; 
543     SP2 = D2.FirstPoint();
544     v = D2.FirstParameter();
545   }
546   //----------------------------------------------------------------------
547   //-- End On 2   :        End2 <-> P1
548   else if(P1.Distance(D2.LastPoint())<=D2.LastTolerance()) { 
549     Pos2 = IntRes2d_End; 
550     EndOn2 = Standard_True;
551     SP2 = D2.LastPoint();
552     v = D2.LastParameter();
553   }
554
555   Standard_Real EpsX1 = TheCurveTool::EpsX(C1);
556   Standard_Real EpsX2 = TheCurveTool::EpsX(C2);
557
558   if((Pos1 != IntRes2d_Middle)||(Pos2 !=  IntRes2d_Middle)) { 
559     if(Pos1 == IntRes2d_Middle) {
560       if(Abs(u-D1.FirstParameter()) <= EpsX1) { 
561               Pos1 = IntRes2d_Head;
562               P1 = D1.FirstPoint();
563               HeadOn1 = Standard_True;
564       }
565       else if(Abs(u-D1.LastParameter()) <= EpsX1) { 
566               Pos1 = IntRes2d_End;
567               P1 = D1.LastPoint();
568               EndOn1 = Standard_True;
569       }
570     }
571     else if(u!=tu) {
572       P1 = SP1; 
573     }
574       
575     
576     if(Pos2 == IntRes2d_Middle) { 
577       if(Abs(v-D2.FirstParameter()) <= EpsX2) { 
578               Pos2 = IntRes2d_Head;
579               HeadOn2 = Standard_True;
580               P2 = D2.FirstPoint();     
581               if(Pos1 != IntRes2d_Middle) {
582                 P1.SetCoord(0.5*(P1.X()+P2.X()),0.5*(P1.Y()+P2.Y()));
583               }
584               else { 
585                 P2 = P1; 
586               }
587       }
588       else if(Abs(v-D2.LastParameter()) <= EpsX2) { 
589               Pos2 = IntRes2d_End;
590               EndOn2 = Standard_True;
591               P2 = D2.LastPoint();
592               if(Pos1 != IntRes2d_Middle) {
593                 P1.SetCoord(0.5*(P1.X()+P2.X()),0.5*(P1.Y()+P2.Y()));
594               }
595               else { 
596                 P2 = P1; 
597               }
598       }
599     }
600
601     //--------------------------------------------------------------------
602     //-- It is tested if a point at the end of segment already has its transitions
603     //-- If Yes, the new point is not created
604     //-- 
605     //-- PosSegment =            1    if Head Head
606     //--                       2      if Head End
607     //--                     4        if End  Head
608     //--                   8          if End  End
609     //--------------------------------------------------------------------
610     if(Pos1 == IntRes2d_Head) { 
611       if((Pos2 == IntRes2d_Head)&&(PosSegment & 1)) return(Standard_False);
612       if((Pos2 == IntRes2d_End )&&(PosSegment & 2)) return(Standard_False);
613     }
614     else if(Pos1 == IntRes2d_End) { 
615       if((Pos2 == IntRes2d_Head)&&(PosSegment & 4)) return(Standard_False);
616       if((Pos2 == IntRes2d_End )&&(PosSegment & 8)) return(Standard_False);
617     }
618
619
620     if(IntImpParGen::DetermineTransition( Pos1,T1,Trans1,Pos2,T2,Trans2,TolConf)
621        == Standard_False) { 
622       TheCurveTool::D2(C1,svu,P1,T1,N1);
623       TheCurveTool::D2(C2,svv,P2,T2,N2);
624       IntImpParGen::DetermineTransition(Pos1,T1,N1,Trans1,
625                                         Pos2,T2,N2,Trans2,TolConf);
626     }
627     IntPt.SetValues(P1,u,v,Trans1,Trans2,Standard_False);
628     return(Standard_True);
629   }
630   else 
631     return(Standard_False);
632 }
633
634
635 //======================================================================
636 void IntCurve_IntPolyPolyGen::Perform( const TheCurve& C1
637                                       ,const IntRes2d_Domain& D1
638                                       ,const TheCurve& C2
639                                       ,const IntRes2d_Domain& D2
640                                       ,const Standard_Real TolConf
641                                       ,const Standard_Real Tol
642                                       ,const Standard_Integer NbIter
643                                       ,const Standard_Real DeltaU
644                                       ,const Standard_Real DeltaV) {
645
646   Standard_Integer nbsamplesOnC1,nbsamplesOnC2;
647   done = Standard_False;
648
649   if(NbIter>NBITER_MAX_POLYGON) return;
650
651   nbsamplesOnC1 = TheCurveTool::NbSamples(C1,D1.FirstParameter(),D1.LastParameter());      
652
653   if (NbIter == 0) // first time
654   {
655     if (nbsamplesOnC1 < 20)
656       nbsamplesOnC1 = 20;
657   }
658   else // NbIter > 0
659   {
660     nbsamplesOnC1=(5*(nbsamplesOnC1*NbIter))/4;
661   }
662   /////////////////////////////////////////////
663
664   nbsamplesOnC2 = TheCurveTool::NbSamples(C2,D2.FirstParameter(),D2.LastParameter());
665   
666   if (NbIter == 0) // first time
667   {
668     if (nbsamplesOnC2 < 20)
669       nbsamplesOnC2 = 20;
670   }
671   else // NbIter > 0
672   {
673     nbsamplesOnC2=(5*(nbsamplesOnC2*NbIter))/4;
674   }
675   /////////////////////////////////////////////
676
677   
678   NCollection_Handle<IntCurve_ThePolygon2d>
679     aPoly1 = new IntCurve_ThePolygon2d(C1,nbsamplesOnC1,D1,Tol),
680     aPoly2 = new IntCurve_ThePolygon2d(C2,nbsamplesOnC2,D2,Tol);
681
682   if( (aPoly1->DeflectionOverEstimation() > TolConf) &&
683       (aPoly2->DeflectionOverEstimation() > TolConf))
684   {
685     const Standard_Real aDeflectionSum = 
686       Max(aPoly1->DeflectionOverEstimation(), TolConf) + 
687       Max(aPoly2->DeflectionOverEstimation(), TolConf);
688
689     if (nbsamplesOnC2 > nbsamplesOnC1)
690     {
691       aPoly2->ComputeWithBox(C2, aPoly1->Bounding());
692       aPoly1->SetDeflectionOverEstimation(aDeflectionSum);
693       aPoly1->ComputeWithBox(C1, aPoly2->Bounding());
694     }
695     else
696     {
697       aPoly1->ComputeWithBox(C1, aPoly2->Bounding());
698       aPoly2->SetDeflectionOverEstimation(aDeflectionSum);
699       aPoly2->ComputeWithBox(C2, aPoly1->Bounding());
700     }
701   }
702
703   //----------------------------------------------------------------------
704   //-- if the deflection less then the Tolerance of Confusion
705   //-- Then the deflection of the polygon is set in TolConf
706   //-- (Detection of Tangency Zones)
707   //----------------------------------------------------------------------
708
709   if(aPoly1->DeflectionOverEstimation() < TolConf) { 
710     aPoly1->SetDeflectionOverEstimation(TolConf);
711   }
712   if(aPoly2->DeflectionOverEstimation() < TolConf) { 
713     aPoly2->SetDeflectionOverEstimation(TolConf);
714   }
715   // for case when a few polygon points were replaced by line
716   // if exact solution was not found 
717   // then search of precise solution will be repeated 
718   // for polygon contains all initial points
719   // secondary search will be performed only for case when initial points
720   // were dropped
721   Standard_Boolean isFullRepresentation = ( aPoly1->NbSegments() == nbsamplesOnC1 && 
722             aPoly2->NbSegments() == nbsamplesOnC2 );
723   
724   if( !findIntersect( C1, D1, C2, D2, TolConf, Tol, NbIter,
725           DeltaU, DeltaV, *aPoly1, *aPoly2, isFullRepresentation ) && !isFullRepresentation ) 
726   {
727     if(aPoly1->NbSegments() < nbsamplesOnC1)
728     {
729       aPoly1 = new IntCurve_ThePolygon2d(C1,nbsamplesOnC1,D1,Tol);
730     }
731     if(aPoly2->NbSegments() < nbsamplesOnC2)
732     {
733       aPoly2 = new IntCurve_ThePolygon2d(C2,nbsamplesOnC2,D2,Tol);
734     }
735
736     findIntersect( C1, D1, C2, D2, TolConf, Tol, NbIter,
737       DeltaU, DeltaV, *aPoly1, *aPoly2, 
738       Standard_True);   
739
740   }
741  
742   done = Standard_True;
743 }
744
745 //======================================================================
746 // Purpose : findIntersect
747 //======================================================================
748
749 Standard_Boolean IntCurve_IntPolyPolyGen::findIntersect( 
750     const TheCurve& C1,
751           const IntRes2d_Domain& D1,
752           const TheCurve& C2,
753           const IntRes2d_Domain& D2,
754           const Standard_Real TolConf,
755           const Standard_Real Tol,
756           const Standard_Integer NbIter,
757           const Standard_Real DeltaU,
758           const Standard_Real DeltaV,
759           const IntCurve_ThePolygon2d& thePoly1,
760           const IntCurve_ThePolygon2d& thePoly2,
761           Standard_Boolean isFullPolygon )
762 {
763
764   gp_Vec2d Tan1,Tan2,Norm1,Norm2;
765   gp_Pnt2d P1,P2;
766   Intf_InterferencePolygon2d InterPP(thePoly1,thePoly2);  
767   IntCurve_ExactIntersectionPoint  EIP(C1,C2,TolConf);
768   Standard_Real U = 0., V = 0.;
769   Standard_Boolean AnErrorOccurred = Standard_False;
770   done = Standard_True; // To prevent exception in nbp=NbPoints();
771   //----------------------------------------------------------------------
772   //-- Processing of SectionPoint 
773   //----------------------------------------------------------------------
774   Standard_Integer Nbsp = InterPP.NbSectionPoints();
775   for(Standard_Integer sp=1; sp <= Nbsp; sp++) {
776     const Intf_SectionPoint& SPnt = InterPP.PntValue(sp);
777     Standard_Integer SegIndex1,SegIndex2;
778     Standard_Real    ParamOn1,ParamOn2;
779     Intf_PIType      Type;
780
781     SPnt.InfoFirst(Type,SegIndex1,ParamOn1);
782     SPnt.InfoSecond(Type,SegIndex2,ParamOn2);
783     EIP.Perform(thePoly1,thePoly2,SegIndex1,SegIndex2,ParamOn1,ParamOn2);
784     AnErrorOccurred = EIP.AnErrorOccurred();
785
786     if( !EIP.NbRoots() && !isFullPolygon)
787       return Standard_False;
788
789     if(AnErrorOccurred) 
790     {
791       continue;
792     }
793
794     //--------------------------------------------------------------------
795     //-- It is checked if the found point is really a root
796     //--------------------------------------------------------------------
797
798     EIP.Roots(U,V);
799     TheCurveTool::D1(C1,U,P1,Tan1);
800     TheCurveTool::D1(C2,V,P2,Tan2);
801     Standard_Real Dist = P1.Distance(P2);
802     if(EIP.NbRoots() == 0 && Dist > TolConf)
803     {
804       IntRes2d_Transition aTrans;
805       IntRes2d_IntersectionPoint aPInt(P1, U, V, aTrans, aTrans, Standard_False);
806       Standard_Real aT1f, aT1l, aT2f, aT2l;
807       aT1f= thePoly1.ApproxParamOnCurve(SegIndex1, 0.0); 
808       aT1l= thePoly1.ApproxParamOnCurve(SegIndex1, 1.0); 
809       aT2f= thePoly2.ApproxParamOnCurve(SegIndex2, 0.0); 
810       aT2l= thePoly2.ApproxParamOnCurve(SegIndex2, 1.0); 
811       //
812       Standard_Integer aMaxCount = 16, aCount = 0;
813       GetIntersection(C1, aT1f, aT1l, C2, aT2f, aT2l, TolConf, aMaxCount, 
814                       aPInt, Dist, aCount); 
815       U = aPInt.ParamOnFirst();
816       V = aPInt.ParamOnSecond();
817       TheCurveTool::D1(C1,U,P1,Tan1);
818       TheCurveTool::D1(C2,V,P2,Tan2);
819       Dist = P1.Distance(P2);
820     }
821     //-----------------------------------------------------------------
822     //-- It is checked if the point (u,v) does not exist already 
823     //--
824     Standard_Integer nbp=NbPoints();
825     Standard_Real EpsX1 = 10.0*TheCurveTool::EpsX(C1);
826     Standard_Real EpsX2 = 10.0*TheCurveTool::EpsX(C2);
827     for(Standard_Integer p=1; p<=nbp; p++) { 
828       const IntRes2d_IntersectionPoint& P=Point(p);
829       if(Abs(U-P.ParamOnFirst()) <= EpsX1) { 
830         if(Abs(V-P.ParamOnSecond()) <= EpsX2) { 
831           Dist = TolConf+1.0;  p+=nbp;
832         }
833       }
834     }
835
836     if(Dist <= TolConf) {    //-- Or the point is already present
837       IntRes2d_Position Pos1 = IntRes2d_Middle;
838       IntRes2d_Position Pos2 = IntRes2d_Middle;
839       IntRes2d_Transition  Trans1,Trans2;
840       //-----------------------------------------------------------------
841       //-- Calculate the Positions of Points on the curve
842       //--
843       if(P1.Distance(DomainOnCurve1.FirstPoint())<=DomainOnCurve1.FirstTolerance())    
844         Pos1 = IntRes2d_Head;
845       else if(P1.Distance(DomainOnCurve1.LastPoint())<=DomainOnCurve1.LastTolerance()) 
846         Pos1 = IntRes2d_End;
847
848       if(P2.Distance(DomainOnCurve2.FirstPoint())<=DomainOnCurve2.FirstTolerance())    
849         Pos2 = IntRes2d_Head;
850       else if(P2.Distance(DomainOnCurve2.LastPoint())<=DomainOnCurve2.LastTolerance()) 
851         Pos2 = IntRes2d_End;
852       //-----------------------------------------------------------------
853       //-- Calculate the Transitions (see IntImpParGen.cxx)
854       //--
855       if(IntImpParGen::DetermineTransition (Pos1, Tan1, Trans1, Pos2, Tan2, Trans2, TolConf) == Standard_False) { 
856         TheCurveTool::D2(C1,U,P1,Tan1,Norm1);
857         TheCurveTool::D2(C2,V,P2,Tan2,Norm2);
858         IntImpParGen::DetermineTransition (Pos1, Tan1, Norm1, Trans1, Pos2, Tan2, Norm2, Trans2, TolConf);
859       }
860       IntRes2d_IntersectionPoint IP(P1,U,V,Trans1,Trans2,Standard_False);
861       Insert(IP);
862     }
863   }
864   
865   //----------------------------------------------------------------------
866   //-- Processing of TangentZone
867   //----------------------------------------------------------------------
868   Standard_Integer Nbtz = InterPP.NbTangentZones();
869   for(Standard_Integer tz=1; tz <= Nbtz; tz++) {
870     Standard_Integer NbPnts = InterPP.ZoneValue(tz).NumberOfPoints();
871     //====================================================================
872     //== Find the first and the last point in the tangency zone.
873     //====================================================================
874     Standard_Real ParamSupOnCurve2,ParamInfOnCurve2;
875     Standard_Real ParamSupOnCurve1,ParamInfOnCurve1;
876 //    Standard_Integer SegIndex,SegIndex1onP1,SegIndex1onP2,SegIndex2onP1,SegIndex2onP2;
877     Standard_Integer SegIndex1onP1,SegIndex1onP2;
878     Intf_PIType Type;
879     Standard_Real ParamOnLine;
880     Standard_Real PolyUInf,PolyUSup,PolyVInf,PolyVSup;
881     ParamSupOnCurve2=ParamSupOnCurve1=PolyUSup=PolyVSup=-RealLast();
882     ParamInfOnCurve2=ParamInfOnCurve1=PolyUInf=PolyVInf= RealLast();
883     for(Standard_Integer qq=1;qq<=NbPnts;qq++) { 
884       const Intf_SectionPoint& SPnt1 = InterPP.ZoneValue(tz).GetPoint(qq);
885       //====================================================================
886       //== The zones of tangency are discretized 
887       //== Test of stop : Check if 
888       //==     (Deflection  < Tolerance)
889       //==  Or (Sample < EpsX)   (normally the first condition is 
890       //==                           more strict)
891       //====================================================================
892 //      Standard_Real _PolyUInf,_PolyUSup,_PolyVInf,_PolyVSup;
893       Standard_Real _PolyUInf,_PolyVInf;
894
895       SPnt1.InfoFirst(Type,SegIndex1onP1,ParamOnLine);
896       if(SegIndex1onP1 > thePoly1.NbSegments()) { SegIndex1onP1--; ParamOnLine = 1.0; }
897       if(SegIndex1onP1 <= 0) { SegIndex1onP1=1; ParamOnLine = 0.0; }
898       _PolyUInf = thePoly1.ApproxParamOnCurve(SegIndex1onP1,ParamOnLine);
899       
900       SPnt1.InfoSecond(Type,SegIndex1onP2,ParamOnLine);
901       if(SegIndex1onP2 > thePoly2.NbSegments()) { SegIndex1onP2--; ParamOnLine = 1.0; }
902       if(SegIndex1onP2 <= 0) { SegIndex1onP2=1; ParamOnLine = 0.0; }
903       _PolyVInf = thePoly2.ApproxParamOnCurve(SegIndex1onP2,ParamOnLine);
904       
905       //----------------------------------------------------------------------
906
907       if(ParamInfOnCurve1 > _PolyUInf) ParamInfOnCurve1=_PolyUInf;
908       if(ParamInfOnCurve2 > _PolyVInf) ParamInfOnCurve2=_PolyVInf;
909
910       if(ParamSupOnCurve1 < _PolyUInf) ParamSupOnCurve1=_PolyUInf;
911       if(ParamSupOnCurve2 < _PolyVInf) ParamSupOnCurve2=_PolyVInf;
912     }
913
914     PolyUInf= ParamInfOnCurve1;
915     PolyUSup= ParamSupOnCurve1;
916     PolyVInf= ParamInfOnCurve2;
917     PolyVSup= ParamSupOnCurve2;
918     
919     TheCurveTool::D0(C1,PolyUInf,P1);
920     TheCurveTool::D0(C2,PolyVInf,P2);
921     Standard_Real distmemesens = P1.SquareDistance(P2);
922     TheCurveTool::D0(C2,PolyVSup,P2);
923     Standard_Real distdiffsens = P1.SquareDistance(P2);
924     if(distmemesens > distdiffsens) { 
925       Standard_Real qwerty=PolyVInf; PolyVInf=PolyVSup; PolyVSup=qwerty;
926     }
927
928     if(  (  (thePoly1.DeflectionOverEstimation() > TolConf)
929             ||(thePoly2.DeflectionOverEstimation() > TolConf))
930             &&(NbIter<NBITER_MAX_POLYGON)) {
931       
932       IntRes2d_Domain RecursD1( TheCurveTool::Value(C1,ParamInfOnCurve1)
933                                ,ParamInfOnCurve1,TolConf
934                                ,TheCurveTool::Value(C1,ParamSupOnCurve1)
935                                ,ParamSupOnCurve1,TolConf);
936       IntRes2d_Domain RecursD2( TheCurveTool::Value(C2,ParamInfOnCurve2)
937                                ,ParamInfOnCurve2,TolConf
938                                ,TheCurveTool::Value(C2,ParamSupOnCurve2)
939                                ,ParamSupOnCurve2,TolConf);
940       //-- thePoly1(2) are not deleted,
941       //-- finally they are destroyed. 
942       //-- !! No untimely return !!
943       Perform(C1,RecursD1,C2,RecursD2,Tol,TolConf,NbIter+1,DeltaU,DeltaV);
944     }
945     else { 
946       //-----------------------------------------------------------------
947       //-- Calculate Positions of Points on the curve and  
948       //-- Transitions on each limit of the segment
949       
950       IntRes2d_Position Pos1 = IntRes2d_Middle;
951       IntRes2d_Position Pos2 = IntRes2d_Middle;
952       IntRes2d_Transition  Trans1,Trans2;
953       
954       TheCurveTool::D1(C1,PolyUInf,P1,Tan1);
955       TheCurveTool::D1(C2,PolyVInf,P2,Tan2);
956       
957       if(P1.Distance(DomainOnCurve1.FirstPoint())<=DomainOnCurve1.FirstTolerance())    { 
958               Pos1 = IntRes2d_Head;
959       }
960       else if(P1.Distance(DomainOnCurve1.LastPoint())<=DomainOnCurve1.LastTolerance()) { 
961               Pos1 = IntRes2d_End;  
962       }
963       if(P2.Distance(DomainOnCurve2.FirstPoint())<=DomainOnCurve2.FirstTolerance())    { 
964               Pos2 = IntRes2d_Head; 
965       }
966       else if(P2.Distance(DomainOnCurve2.LastPoint())<=DomainOnCurve2.LastTolerance()) { 
967               Pos2 = IntRes2d_End;  
968       }
969
970       if(Pos1==IntRes2d_Middle && Pos2!=IntRes2d_Middle) { 
971               PolyUInf=TheProjPCur::FindParameter( C1,P2,D1.FirstParameter(),D1.LastParameter(),TheCurveTool::EpsX(C1));
972       }
973       else if(Pos1!=IntRes2d_Middle && Pos2==IntRes2d_Middle) { 
974               PolyVInf=TheProjPCur::FindParameter( C2,P1,D2.FirstParameter(),D2.LastParameter(),TheCurveTool::EpsX(C2));
975       }
976       else if(Abs(ParamInfOnCurve1-ParamSupOnCurve1) > Abs(ParamInfOnCurve2-ParamSupOnCurve2)) { 
977               PolyVInf=TheProjPCur::FindParameter( C2,P1,D2.FirstParameter(),D2.LastParameter(),TheCurveTool::EpsX(C2));
978       }
979       else { 
980               PolyUInf=TheProjPCur::FindParameter( C1,P2,D1.FirstParameter(),D1.LastParameter(),TheCurveTool::EpsX(C1));
981       }
982       
983
984
985       if(IntImpParGen::DetermineTransition( Pos1,Tan1,Trans1,Pos2,Tan2,Trans2,TolConf) 
986                == Standard_False)
987       {
988               TheCurveTool::D2(C1,PolyUInf,P1,Tan1,Norm1);
989               TheCurveTool::D2(C2,PolyVInf,P2,Tan2,Norm2);
990               IntImpParGen::DetermineTransition(Pos1,Tan1,Norm1,Trans1,
991                                                 Pos2,Tan2,Norm2,Trans2,TolConf);
992       }
993       IntRes2d_IntersectionPoint PtSeg1(P1,PolyUInf,PolyVInf
994                                         ,Trans1,Trans2,Standard_False);
995       //----------------------------------------------------------------------
996       
997       if((Abs(PolyUInf-PolyUSup) <= TheCurveTool::EpsX(C1)) 
998               || (Abs(PolyVInf-PolyVSup) <= TheCurveTool::EpsX(C2)))
999       { 
1000               Insert(PtSeg1);
1001       }
1002       else 
1003       { 
1004               TheCurveTool::D1(C1,PolyUSup,P1,Tan1);
1005               TheCurveTool::D1(C2,PolyVSup,P2,Tan2);
1006               Pos1 = IntRes2d_Middle; Pos2 = IntRes2d_Middle;
1007           
1008               if(P1.Distance(DomainOnCurve1.FirstPoint())<=DomainOnCurve1.FirstTolerance())    { 
1009                 Pos1 = IntRes2d_Head; 
1010               }
1011               else if(P1.Distance(DomainOnCurve1.LastPoint())<=DomainOnCurve1.LastTolerance()) { 
1012                 Pos1 = IntRes2d_End;  
1013               }
1014               if(P2.Distance(DomainOnCurve2.FirstPoint())<=DomainOnCurve2.FirstTolerance())    { 
1015                 Pos2 = IntRes2d_Head; 
1016               }
1017               else if(P2.Distance(DomainOnCurve2.LastPoint())<=DomainOnCurve2.LastTolerance()) { 
1018                 Pos2 = IntRes2d_End;  
1019               }
1020
1021
1022               if(Pos1==IntRes2d_Middle && Pos2!=IntRes2d_Middle) { 
1023                 PolyUSup=TheProjPCur::FindParameter( C1,P2,D1.FirstParameter(),D1.LastParameter(),TheCurveTool::EpsX(C1));
1024               }
1025               else if(Pos1!=IntRes2d_Middle && Pos2==IntRes2d_Middle) { 
1026                 PolyVSup=TheProjPCur::FindParameter( C2,P1,D2.FirstParameter(),D2.LastParameter(),TheCurveTool::EpsX(C2));
1027               }
1028               else if(Abs(ParamInfOnCurve1-ParamSupOnCurve1) > Abs(ParamInfOnCurve2-ParamSupOnCurve2)) { 
1029                 PolyVSup=TheProjPCur::FindParameter( C2,P1,D2.FirstParameter(),D2.LastParameter(),TheCurveTool::EpsX(C2));
1030               }
1031               else { 
1032                 PolyUSup=TheProjPCur::FindParameter( C1,P2,D1.FirstParameter(),D1.LastParameter(),TheCurveTool::EpsX(C1));
1033               }
1034         
1035         if(IntImpParGen::DetermineTransition( Pos1,Tan1,Trans1,Pos2,Tan2,Trans2,TolConf)
1036            ==Standard_False) { 
1037           TheCurveTool::D2(C1,PolyUSup,P1,Tan1,Norm1);
1038           TheCurveTool::D2(C2,PolyVSup,P2,Tan2,Norm2);
1039           IntImpParGen::DetermineTransition(Pos1,Tan1,Norm1,Trans1,
1040                                             Pos2,Tan2,Norm2,Trans2,TolConf);
1041         }
1042         IntRes2d_IntersectionPoint PtSeg2(P1,PolyUSup,PolyVSup
1043                                           ,Trans1,Trans2,Standard_False);
1044         
1045               Standard_Boolean Oppos = (Tan1.Dot(Tan2) > 0.0)? Standard_False : Standard_True;
1046               if(ParamInfOnCurve1 > ParamSupOnCurve1) {
1047                 IntRes2d_IntersectionSegment Seg(PtSeg2,PtSeg1,Oppos,Standard_False);
1048                 Append(Seg);
1049               }
1050               else { 
1051                 IntRes2d_IntersectionSegment Seg(PtSeg1,PtSeg2,Oppos,Standard_False);
1052                 Append(Seg);
1053               }
1054       }
1055     }
1056   }
1057  return Standard_True;
1058 }
1059
1060 //======================================================================
1061 //  GetIntersection
1062 //======================================================================
1063
1064 void GetIntersection(const TheCurve& theC1, const Standard_Real theT1f, const Standard_Real theT1l,
1065                      const TheCurve& theC2, const Standard_Real theT2f, const Standard_Real theT2l, 
1066                      const Standard_Real theTolConf,
1067                      const Standard_Integer theMaxCount,
1068                      IntRes2d_IntersectionPoint& thePInt, Standard_Real& theDist,
1069                      Standard_Integer& theCount)
1070 {
1071   theCount++;
1072   //
1073   Standard_Real aTol2 = theTolConf*theTolConf;
1074   Standard_Real aPTol1 = Max(100.*Epsilon(Max(Abs(theT1f), Abs(theT1l))), Precision::PConfusion());
1075   Standard_Real aPTol2 = Max(100.*Epsilon(Max(Abs(theT2f), Abs(theT2l))), Precision::PConfusion());
1076   gp_Pnt2d aP1f, aP1l, aP2f, aP2l;
1077   Bnd_Box2d aB1, aB2;
1078   //
1079   TheCurveTool::D0(theC1, theT1f, aP1f);
1080   TheCurveTool::D0(theC1, theT1l, aP1l);
1081   aB1.Add(aP1f);
1082   aB1.Add(aP1l);
1083   aB1.Enlarge(theTolConf);
1084   //
1085   TheCurveTool::D0(theC2, theT2f, aP2f);
1086   TheCurveTool::D0(theC2, theT2l, aP2l);
1087   aB2.Add(aP2f);
1088   aB2.Add(aP2l);
1089   aB2.Enlarge(theTolConf);
1090   //
1091   if(aB1.IsOut(aB2))
1092   {
1093     theCount--;
1094     return;
1095   }
1096   //
1097   Standard_Boolean isSmall1 = (theT1l - theT1f) <= aPTol1 || aP1f.SquareDistance(aP1l) / 4. <= aTol2;
1098   Standard_Boolean isSmall2 = (theT2l - theT2f) <= aPTol2 || aP2f.SquareDistance(aP2l) / 4. <= aTol2;
1099
1100   if((isSmall1 && isSmall2) || (theCount > theMaxCount))
1101   {
1102     //Seems to be intersection
1103     //Simple treatment of segment intersection
1104     gp_XY aPnts1[3] = {aP1f.XY(), (aP1f.XY() + aP1l.XY()) / 2., aP1l.XY()};
1105     gp_XY aPnts2[3] = {aP2f.XY(), (aP2f.XY() + aP2l.XY()) / 2., aP2l.XY()};
1106     Standard_Integer i, j, imin = -1, jmin = -1;
1107     Standard_Real dmin = RealLast(), d;
1108     for(i = 0; i < 3; i++)
1109     {
1110       for(j = 0; j < 3; j++)
1111       {
1112         d = (aPnts1[i] - aPnts2[j]).SquareModulus();
1113         if(d < dmin)
1114         {
1115           dmin=d;
1116           imin = i;
1117           jmin = j;
1118         }
1119       }
1120     }
1121     //
1122     dmin = Sqrt(dmin);
1123     if(theDist > dmin)
1124     {
1125       theDist = dmin;
1126       //
1127       Standard_Real t1;
1128       if(imin == 0)
1129       {
1130         t1 = theT1f;
1131       }
1132       else if(imin == 1)
1133       {
1134         t1 = (theT1f + theT1l) / 2.;
1135       }
1136       else
1137       {
1138         t1 = theT1l;
1139       }
1140       //
1141       Standard_Real t2;
1142       if(jmin == 0)
1143       {
1144         t2 = theT2f;
1145       }
1146       else if(jmin == 1)
1147       {
1148         t2 = (theT2f + theT2l) / 2.;
1149       }
1150       else
1151       {
1152         t2 = theT2l;
1153       }
1154       //
1155       gp_Pnt2d aPint((aPnts1[imin] + aPnts2[jmin])/2.);
1156       //
1157       IntRes2d_Transition aTrans1, aTrans2;
1158       thePInt.SetValues(aPint, t1, t2, aTrans1, aTrans2, Standard_False);
1159     }
1160     theCount--;
1161     return;
1162   }
1163
1164   if(isSmall1)
1165   {
1166     Standard_Real aT2m = (theT2l + theT2f) / 2.;
1167     GetIntersection(theC1, theT1f, theT1l, theC2, theT2f, aT2m, theTolConf, theMaxCount, thePInt, theDist, theCount);
1168     GetIntersection(theC1, theT1f, theT1l, theC2, aT2m, theT2l, theTolConf, theMaxCount, thePInt, theDist, theCount);
1169   }
1170   else if(isSmall2)
1171   {
1172     Standard_Real aT1m = (theT1l + theT1f) / 2.;
1173     GetIntersection(theC1, theT1f, aT1m, theC2, theT2f, theT2l, theTolConf, theMaxCount, thePInt, theDist, theCount);
1174     GetIntersection(theC1, aT1m, theT1l, theC2, theT2f, theT2l, theTolConf, theMaxCount, thePInt, theDist, theCount);
1175   }
1176   else
1177   {
1178     Standard_Real aT1m = (theT1l + theT1f) / 2.;
1179     Standard_Real aT2m = (theT2l + theT2f) / 2.;
1180     GetIntersection(theC1, theT1f, aT1m, theC2, theT2f, aT2m, theTolConf, theMaxCount, thePInt, theDist, theCount);
1181     GetIntersection(theC1, theT1f, aT1m, theC2, aT2m, theT2l, theTolConf, theMaxCount, thePInt, theDist, theCount);
1182     GetIntersection(theC1, aT1m, theT1l, theC2, theT2f, aT2m, theTolConf, theMaxCount, thePInt, theDist, theCount);
1183     GetIntersection(theC1, aT1m, theT1l, theC2, aT2m, theT2l, theTolConf, theMaxCount, thePInt, theDist, theCount);
1184   }
1185
1186 }