0027341: Incorrect exact HLR results
[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 #define NBITER_MAX_POLYGON 10
54 #define TOL_CONF_MINI   0.0000000001
55 #define TOL_MINI        0.0000000001
56
57 //----------------------------------------------------------------------
58
59
60 void GetIntersection(const TheCurve& theC1, const Standard_Real theT1f, const Standard_Real theT1l,
61                      const TheCurve& theC2, const Standard_Real theT2f, const Standard_Real theT2l, 
62                      const Standard_Real theTolConf,
63                      const Standard_Integer theMaxCount,
64                      IntRes2d_IntersectionPoint& thePInt, Standard_Real& theDist,
65                      Standard_Integer& theCount);
66
67
68 Standard_Boolean HeadOrEndPoint( const IntRes2d_Domain& D1
69                                 ,const TheCurve& C1
70                                 ,const Standard_Real u
71                                 ,const IntRes2d_Domain& D2
72                                 ,const TheCurve& C2
73                                 ,const Standard_Real v
74                                 ,const Standard_Real TolConf
75                                 ,IntRes2d_IntersectionPoint& IntPt
76                                 ,Standard_Boolean& HeadOn1
77                                 ,Standard_Boolean& HeadOn2
78                                 ,Standard_Boolean& EndOn1
79                                 ,Standard_Boolean& EndOn2
80                                 ,Standard_Integer  PosSegment);
81
82
83 //======================================================================
84 IntCurve_IntPolyPolyGen::IntCurve_IntPolyPolyGen()
85 {
86   const Standard_Integer aMinPntNb = 20; // Minimum number of samples.
87   myMinPntNb = aMinPntNb;
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 //function : Perform
636 //purpose  : Base method to perform polyline / polyline intersection for
637 //           pair of curves.
638 //=======================================================================
639 void IntCurve_IntPolyPolyGen::Perform(const TheCurve& C1,
640                                       const IntRes2d_Domain& D1,
641                                       const TheCurve& C2,
642                                       const IntRes2d_Domain& D2,
643                                       const Standard_Real TolConf,
644                                       const Standard_Real Tol,
645                                       const Standard_Integer NbIter,
646                                       const Standard_Real DeltaU,
647                                       const Standard_Real DeltaV)
648 {
649   Standard_Integer nbsamplesOnC1,nbsamplesOnC2;
650   done = Standard_False;
651
652   if(NbIter>NBITER_MAX_POLYGON) return;
653
654   // Number of samples tunning.
655   nbsamplesOnC1 = TheCurveTool::NbSamples(C1,D1.FirstParameter(),D1.LastParameter());
656   nbsamplesOnC2 = TheCurveTool::NbSamples(C2,D2.FirstParameter(),D2.LastParameter());
657
658   if (NbIter == 0)
659   {
660     // Minimal number of points.
661     nbsamplesOnC1 = Max(nbsamplesOnC1, myMinPntNb);
662     nbsamplesOnC2 = Max(nbsamplesOnC2, myMinPntNb);
663   }
664   else
665   {
666     // Increase number of samples in second and next iterations.
667     nbsamplesOnC1=(5 * (nbsamplesOnC1 * NbIter)) / 4;
668     nbsamplesOnC2=(5 * (nbsamplesOnC2 * NbIter)) / 4;
669   }
670
671   NCollection_Handle<IntCurve_ThePolygon2d>
672     aPoly1 = new IntCurve_ThePolygon2d(C1,nbsamplesOnC1,D1,Tol),
673     aPoly2 = new IntCurve_ThePolygon2d(C2,nbsamplesOnC2,D2,Tol);
674
675   if( (aPoly1->DeflectionOverEstimation() > TolConf) &&
676       (aPoly2->DeflectionOverEstimation() > TolConf))
677   {
678     const Standard_Real aDeflectionSum = 
679       Max(aPoly1->DeflectionOverEstimation(), TolConf) + 
680       Max(aPoly2->DeflectionOverEstimation(), TolConf);
681
682     if (nbsamplesOnC2 > nbsamplesOnC1)
683     {
684       aPoly2->ComputeWithBox(C2, aPoly1->Bounding());
685       aPoly1->SetDeflectionOverEstimation(aDeflectionSum);
686       aPoly1->ComputeWithBox(C1, aPoly2->Bounding());
687     }
688     else
689     {
690       aPoly1->ComputeWithBox(C1, aPoly2->Bounding());
691       aPoly2->SetDeflectionOverEstimation(aDeflectionSum);
692       aPoly2->ComputeWithBox(C2, aPoly1->Bounding());
693     }
694   }
695
696   //----------------------------------------------------------------------
697   //-- if the deflection less then the Tolerance of Confusion
698   //-- Then the deflection of the polygon is set in TolConf
699   //-- (Detection of Tangency Zones)
700   //----------------------------------------------------------------------
701
702   if(aPoly1->DeflectionOverEstimation() < TolConf) { 
703     aPoly1->SetDeflectionOverEstimation(TolConf);
704   }
705   if(aPoly2->DeflectionOverEstimation() < TolConf) { 
706     aPoly2->SetDeflectionOverEstimation(TolConf);
707   }
708   // for case when a few polygon points were replaced by line
709   // if exact solution was not found 
710   // then search of precise solution will be repeated 
711   // for polygon contains all initial points
712   // secondary search will be performed only for case when initial points
713   // were dropped
714   Standard_Boolean isFullRepresentation = ( aPoly1->NbSegments() == nbsamplesOnC1 && 
715             aPoly2->NbSegments() == nbsamplesOnC2 );
716   
717   if( !findIntersect( C1, D1, C2, D2, TolConf, Tol, NbIter,
718           DeltaU, DeltaV, *aPoly1, *aPoly2, isFullRepresentation ) && !isFullRepresentation ) 
719   {
720     if(aPoly1->NbSegments() < nbsamplesOnC1)
721     {
722       aPoly1 = new IntCurve_ThePolygon2d(C1,nbsamplesOnC1,D1,Tol);
723     }
724     if(aPoly2->NbSegments() < nbsamplesOnC2)
725     {
726       aPoly2 = new IntCurve_ThePolygon2d(C2,nbsamplesOnC2,D2,Tol);
727     }
728
729     findIntersect( C1, D1, C2, D2, TolConf, Tol, NbIter,
730       DeltaU, DeltaV, *aPoly1, *aPoly2, 
731       Standard_True);   
732
733   }
734  
735   done = Standard_True;
736 }
737
738 //======================================================================
739 // Purpose : findIntersect
740 //======================================================================
741
742 Standard_Boolean IntCurve_IntPolyPolyGen::findIntersect( 
743     const TheCurve& C1,
744           const IntRes2d_Domain& D1,
745           const TheCurve& C2,
746           const IntRes2d_Domain& D2,
747           const Standard_Real TolConf,
748           const Standard_Real Tol,
749           const Standard_Integer NbIter,
750           const Standard_Real DeltaU,
751           const Standard_Real DeltaV,
752           const IntCurve_ThePolygon2d& thePoly1,
753           const IntCurve_ThePolygon2d& thePoly2,
754           Standard_Boolean isFullPolygon )
755 {
756
757   gp_Vec2d Tan1,Tan2,Norm1,Norm2;
758   gp_Pnt2d P1,P2;
759   Intf_InterferencePolygon2d InterPP(thePoly1,thePoly2);  
760   IntCurve_ExactIntersectionPoint  EIP(C1,C2,TolConf);
761   Standard_Real U = 0., V = 0.;
762   Standard_Boolean AnErrorOccurred = Standard_False;
763   done = Standard_True; // To prevent exception in nbp=NbPoints();
764   //----------------------------------------------------------------------
765   //-- Processing of SectionPoint 
766   //----------------------------------------------------------------------
767   Standard_Integer Nbsp = InterPP.NbSectionPoints();
768   for(Standard_Integer sp=1; sp <= Nbsp; sp++) {
769     const Intf_SectionPoint& SPnt = InterPP.PntValue(sp);
770     Standard_Integer SegIndex1,SegIndex2;
771     Standard_Real    ParamOn1,ParamOn2;
772     Intf_PIType      Type;
773
774     SPnt.InfoFirst(Type,SegIndex1,ParamOn1);
775     SPnt.InfoSecond(Type,SegIndex2,ParamOn2);
776     EIP.Perform(thePoly1,thePoly2,SegIndex1,SegIndex2,ParamOn1,ParamOn2);
777     AnErrorOccurred = EIP.AnErrorOccurred();
778
779     if( !EIP.NbRoots() && !isFullPolygon)
780       return Standard_False;
781
782     if(AnErrorOccurred) 
783     {
784       continue;
785     }
786
787     //--------------------------------------------------------------------
788     //-- It is checked if the found point is really a root
789     //--------------------------------------------------------------------
790
791     EIP.Roots(U,V);
792     TheCurveTool::D1(C1,U,P1,Tan1);
793     TheCurveTool::D1(C2,V,P2,Tan2);
794     Standard_Real Dist = P1.Distance(P2);
795     if(EIP.NbRoots() == 0 && Dist > TolConf)
796     {
797       IntRes2d_Transition aTrans;
798       IntRes2d_IntersectionPoint aPInt(P1, U, V, aTrans, aTrans, Standard_False);
799       Standard_Real aT1f, aT1l, aT2f, aT2l;
800       aT1f= thePoly1.ApproxParamOnCurve(SegIndex1, 0.0); 
801       aT1l= thePoly1.ApproxParamOnCurve(SegIndex1, 1.0); 
802       aT2f= thePoly2.ApproxParamOnCurve(SegIndex2, 0.0); 
803       aT2l= thePoly2.ApproxParamOnCurve(SegIndex2, 1.0); 
804       //
805       Standard_Integer aMaxCount = 16, aCount = 0;
806       GetIntersection(C1, aT1f, aT1l, C2, aT2f, aT2l, TolConf, aMaxCount, 
807                       aPInt, Dist, aCount); 
808       U = aPInt.ParamOnFirst();
809       V = aPInt.ParamOnSecond();
810       TheCurveTool::D1(C1,U,P1,Tan1);
811       TheCurveTool::D1(C2,V,P2,Tan2);
812       Dist = P1.Distance(P2);
813     }
814     //-----------------------------------------------------------------
815     //-- It is checked if the point (u,v) does not exist already 
816     //--
817     Standard_Integer nbp=NbPoints();
818     Standard_Real EpsX1 = 10.0*TheCurveTool::EpsX(C1);
819     Standard_Real EpsX2 = 10.0*TheCurveTool::EpsX(C2);
820     for(Standard_Integer p=1; p<=nbp; p++) { 
821       const IntRes2d_IntersectionPoint& P=Point(p);
822       if(Abs(U-P.ParamOnFirst()) <= EpsX1) { 
823         if(Abs(V-P.ParamOnSecond()) <= EpsX2) { 
824           Dist = TolConf+1.0;  p+=nbp;
825         }
826       }
827     }
828
829     if(Dist <= TolConf) {    //-- Or the point is already present
830       IntRes2d_Position Pos1 = IntRes2d_Middle;
831       IntRes2d_Position Pos2 = IntRes2d_Middle;
832       IntRes2d_Transition  Trans1,Trans2;
833       //-----------------------------------------------------------------
834       //-- Calculate the Positions of Points on the curve
835       //--
836       if(P1.Distance(DomainOnCurve1.FirstPoint())<=DomainOnCurve1.FirstTolerance())    
837         Pos1 = IntRes2d_Head;
838       else if(P1.Distance(DomainOnCurve1.LastPoint())<=DomainOnCurve1.LastTolerance()) 
839         Pos1 = IntRes2d_End;
840
841       if(P2.Distance(DomainOnCurve2.FirstPoint())<=DomainOnCurve2.FirstTolerance())    
842         Pos2 = IntRes2d_Head;
843       else if(P2.Distance(DomainOnCurve2.LastPoint())<=DomainOnCurve2.LastTolerance()) 
844         Pos2 = IntRes2d_End;
845       //-----------------------------------------------------------------
846       //-- Calculate the Transitions (see IntImpParGen.cxx)
847       //--
848       if(IntImpParGen::DetermineTransition (Pos1, Tan1, Trans1, Pos2, Tan2, Trans2, TolConf) == Standard_False) { 
849         TheCurveTool::D2(C1,U,P1,Tan1,Norm1);
850         TheCurveTool::D2(C2,V,P2,Tan2,Norm2);
851         IntImpParGen::DetermineTransition (Pos1, Tan1, Norm1, Trans1, Pos2, Tan2, Norm2, Trans2, TolConf);
852       }
853       IntRes2d_IntersectionPoint IP(P1,U,V,Trans1,Trans2,Standard_False);
854       Insert(IP);
855     }
856   }
857   
858   //----------------------------------------------------------------------
859   //-- Processing of TangentZone
860   //----------------------------------------------------------------------
861   Standard_Integer Nbtz = InterPP.NbTangentZones();
862   for(Standard_Integer tz=1; tz <= Nbtz; tz++) {
863     Standard_Integer NbPnts = InterPP.ZoneValue(tz).NumberOfPoints();
864     //====================================================================
865     //== Find the first and the last point in the tangency zone.
866     //====================================================================
867     Standard_Real ParamSupOnCurve2,ParamInfOnCurve2;
868     Standard_Real ParamSupOnCurve1,ParamInfOnCurve1;
869 //    Standard_Integer SegIndex,SegIndex1onP1,SegIndex1onP2,SegIndex2onP1,SegIndex2onP2;
870     Standard_Integer SegIndex1onP1,SegIndex1onP2;
871     Intf_PIType Type;
872     Standard_Real ParamOnLine;
873     Standard_Real PolyUInf,PolyUSup,PolyVInf,PolyVSup;
874     ParamSupOnCurve2=ParamSupOnCurve1=PolyUSup=PolyVSup=-RealLast();
875     ParamInfOnCurve2=ParamInfOnCurve1=PolyUInf=PolyVInf= RealLast();
876     for(Standard_Integer qq=1;qq<=NbPnts;qq++) { 
877       const Intf_SectionPoint& SPnt1 = InterPP.ZoneValue(tz).GetPoint(qq);
878       //====================================================================
879       //== The zones of tangency are discretized 
880       //== Test of stop : Check if 
881       //==     (Deflection  < Tolerance)
882       //==  Or (Sample < EpsX)   (normally the first condition is 
883       //==                           more strict)
884       //====================================================================
885 //      Standard_Real _PolyUInf,_PolyUSup,_PolyVInf,_PolyVSup;
886       Standard_Real _PolyUInf,_PolyVInf;
887
888       SPnt1.InfoFirst(Type,SegIndex1onP1,ParamOnLine);
889       if(SegIndex1onP1 > thePoly1.NbSegments()) { SegIndex1onP1--; ParamOnLine = 1.0; }
890       if(SegIndex1onP1 <= 0) { SegIndex1onP1=1; ParamOnLine = 0.0; }
891       _PolyUInf = thePoly1.ApproxParamOnCurve(SegIndex1onP1,ParamOnLine);
892       
893       SPnt1.InfoSecond(Type,SegIndex1onP2,ParamOnLine);
894       if(SegIndex1onP2 > thePoly2.NbSegments()) { SegIndex1onP2--; ParamOnLine = 1.0; }
895       if(SegIndex1onP2 <= 0) { SegIndex1onP2=1; ParamOnLine = 0.0; }
896       _PolyVInf = thePoly2.ApproxParamOnCurve(SegIndex1onP2,ParamOnLine);
897       
898       //----------------------------------------------------------------------
899
900       if(ParamInfOnCurve1 > _PolyUInf) ParamInfOnCurve1=_PolyUInf;
901       if(ParamInfOnCurve2 > _PolyVInf) ParamInfOnCurve2=_PolyVInf;
902
903       if(ParamSupOnCurve1 < _PolyUInf) ParamSupOnCurve1=_PolyUInf;
904       if(ParamSupOnCurve2 < _PolyVInf) ParamSupOnCurve2=_PolyVInf;
905     }
906
907     PolyUInf= ParamInfOnCurve1;
908     PolyUSup= ParamSupOnCurve1;
909     PolyVInf= ParamInfOnCurve2;
910     PolyVSup= ParamSupOnCurve2;
911     
912     TheCurveTool::D0(C1,PolyUInf,P1);
913     TheCurveTool::D0(C2,PolyVInf,P2);
914     Standard_Real distmemesens = P1.SquareDistance(P2);
915     TheCurveTool::D0(C2,PolyVSup,P2);
916     Standard_Real distdiffsens = P1.SquareDistance(P2);
917     if(distmemesens > distdiffsens) { 
918       Standard_Real qwerty=PolyVInf; PolyVInf=PolyVSup; PolyVSup=qwerty;
919     }
920
921     if(  (  (thePoly1.DeflectionOverEstimation() > TolConf)
922             ||(thePoly2.DeflectionOverEstimation() > TolConf))
923             &&(NbIter<NBITER_MAX_POLYGON)) {
924       
925       IntRes2d_Domain RecursD1( TheCurveTool::Value(C1,ParamInfOnCurve1)
926                                ,ParamInfOnCurve1,TolConf
927                                ,TheCurveTool::Value(C1,ParamSupOnCurve1)
928                                ,ParamSupOnCurve1,TolConf);
929       IntRes2d_Domain RecursD2( TheCurveTool::Value(C2,ParamInfOnCurve2)
930                                ,ParamInfOnCurve2,TolConf
931                                ,TheCurveTool::Value(C2,ParamSupOnCurve2)
932                                ,ParamSupOnCurve2,TolConf);
933       //-- thePoly1(2) are not deleted,
934       //-- finally they are destroyed. 
935       //-- !! No untimely return !!
936       Perform(C1,RecursD1,C2,RecursD2,Tol,TolConf,NbIter+1,DeltaU,DeltaV);
937     }
938     else { 
939       //-----------------------------------------------------------------
940       //-- Calculate Positions of Points on the curve and  
941       //-- Transitions on each limit of the segment
942       
943       IntRes2d_Position Pos1 = IntRes2d_Middle;
944       IntRes2d_Position Pos2 = IntRes2d_Middle;
945       IntRes2d_Transition  Trans1,Trans2;
946       
947       TheCurveTool::D1(C1,PolyUInf,P1,Tan1);
948       TheCurveTool::D1(C2,PolyVInf,P2,Tan2);
949       
950       if(P1.Distance(DomainOnCurve1.FirstPoint())<=DomainOnCurve1.FirstTolerance())    { 
951               Pos1 = IntRes2d_Head;
952       }
953       else if(P1.Distance(DomainOnCurve1.LastPoint())<=DomainOnCurve1.LastTolerance()) { 
954               Pos1 = IntRes2d_End;  
955       }
956       if(P2.Distance(DomainOnCurve2.FirstPoint())<=DomainOnCurve2.FirstTolerance())    { 
957               Pos2 = IntRes2d_Head; 
958       }
959       else if(P2.Distance(DomainOnCurve2.LastPoint())<=DomainOnCurve2.LastTolerance()) { 
960               Pos2 = IntRes2d_End;  
961       }
962
963       if(Pos1==IntRes2d_Middle && Pos2!=IntRes2d_Middle) { 
964               PolyUInf=TheProjPCur::FindParameter( C1,P2,D1.FirstParameter(),D1.LastParameter(),TheCurveTool::EpsX(C1));
965       }
966       else if(Pos1!=IntRes2d_Middle && Pos2==IntRes2d_Middle) { 
967               PolyVInf=TheProjPCur::FindParameter( C2,P1,D2.FirstParameter(),D2.LastParameter(),TheCurveTool::EpsX(C2));
968       }
969       else if(Abs(ParamInfOnCurve1-ParamSupOnCurve1) > Abs(ParamInfOnCurve2-ParamSupOnCurve2)) { 
970               PolyVInf=TheProjPCur::FindParameter( C2,P1,D2.FirstParameter(),D2.LastParameter(),TheCurveTool::EpsX(C2));
971       }
972       else { 
973               PolyUInf=TheProjPCur::FindParameter( C1,P2,D1.FirstParameter(),D1.LastParameter(),TheCurveTool::EpsX(C1));
974       }
975       
976
977
978       if(IntImpParGen::DetermineTransition( Pos1,Tan1,Trans1,Pos2,Tan2,Trans2,TolConf) 
979                == Standard_False)
980       {
981               TheCurveTool::D2(C1,PolyUInf,P1,Tan1,Norm1);
982               TheCurveTool::D2(C2,PolyVInf,P2,Tan2,Norm2);
983               IntImpParGen::DetermineTransition(Pos1,Tan1,Norm1,Trans1,
984                                                 Pos2,Tan2,Norm2,Trans2,TolConf);
985       }
986       IntRes2d_IntersectionPoint PtSeg1(P1,PolyUInf,PolyVInf
987                                         ,Trans1,Trans2,Standard_False);
988       //----------------------------------------------------------------------
989       
990       if((Abs(PolyUInf-PolyUSup) <= TheCurveTool::EpsX(C1)) 
991               || (Abs(PolyVInf-PolyVSup) <= TheCurveTool::EpsX(C2)))
992       { 
993               Insert(PtSeg1);
994       }
995       else 
996       { 
997               TheCurveTool::D1(C1,PolyUSup,P1,Tan1);
998               TheCurveTool::D1(C2,PolyVSup,P2,Tan2);
999               Pos1 = IntRes2d_Middle; Pos2 = IntRes2d_Middle;
1000           
1001               if(P1.Distance(DomainOnCurve1.FirstPoint())<=DomainOnCurve1.FirstTolerance())    { 
1002                 Pos1 = IntRes2d_Head; 
1003               }
1004               else if(P1.Distance(DomainOnCurve1.LastPoint())<=DomainOnCurve1.LastTolerance()) { 
1005                 Pos1 = IntRes2d_End;  
1006               }
1007               if(P2.Distance(DomainOnCurve2.FirstPoint())<=DomainOnCurve2.FirstTolerance())    { 
1008                 Pos2 = IntRes2d_Head; 
1009               }
1010               else if(P2.Distance(DomainOnCurve2.LastPoint())<=DomainOnCurve2.LastTolerance()) { 
1011                 Pos2 = IntRes2d_End;  
1012               }
1013
1014
1015               if(Pos1==IntRes2d_Middle && Pos2!=IntRes2d_Middle) { 
1016                 PolyUSup=TheProjPCur::FindParameter( C1,P2,D1.FirstParameter(),D1.LastParameter(),TheCurveTool::EpsX(C1));
1017               }
1018               else if(Pos1!=IntRes2d_Middle && Pos2==IntRes2d_Middle) { 
1019                 PolyVSup=TheProjPCur::FindParameter( C2,P1,D2.FirstParameter(),D2.LastParameter(),TheCurveTool::EpsX(C2));
1020               }
1021               else if(Abs(ParamInfOnCurve1-ParamSupOnCurve1) > Abs(ParamInfOnCurve2-ParamSupOnCurve2)) { 
1022                 PolyVSup=TheProjPCur::FindParameter( C2,P1,D2.FirstParameter(),D2.LastParameter(),TheCurveTool::EpsX(C2));
1023               }
1024               else { 
1025                 PolyUSup=TheProjPCur::FindParameter( C1,P2,D1.FirstParameter(),D1.LastParameter(),TheCurveTool::EpsX(C1));
1026               }
1027         
1028         if(IntImpParGen::DetermineTransition( Pos1,Tan1,Trans1,Pos2,Tan2,Trans2,TolConf)
1029            ==Standard_False) { 
1030           TheCurveTool::D2(C1,PolyUSup,P1,Tan1,Norm1);
1031           TheCurveTool::D2(C2,PolyVSup,P2,Tan2,Norm2);
1032           IntImpParGen::DetermineTransition(Pos1,Tan1,Norm1,Trans1,
1033                                             Pos2,Tan2,Norm2,Trans2,TolConf);
1034         }
1035         IntRes2d_IntersectionPoint PtSeg2(P1,PolyUSup,PolyVSup
1036                                           ,Trans1,Trans2,Standard_False);
1037         
1038               Standard_Boolean Oppos = (Tan1.Dot(Tan2) > 0.0)? Standard_False : Standard_True;
1039               if(ParamInfOnCurve1 > ParamSupOnCurve1) {
1040                 IntRes2d_IntersectionSegment Seg(PtSeg2,PtSeg1,Oppos,Standard_False);
1041                 Append(Seg);
1042               }
1043               else { 
1044                 IntRes2d_IntersectionSegment Seg(PtSeg1,PtSeg2,Oppos,Standard_False);
1045                 Append(Seg);
1046               }
1047       }
1048     }
1049   }
1050  return Standard_True;
1051 }
1052
1053 //======================================================================
1054 //  GetIntersection
1055 //======================================================================
1056
1057 void GetIntersection(const TheCurve& theC1, const Standard_Real theT1f, const Standard_Real theT1l,
1058                      const TheCurve& theC2, const Standard_Real theT2f, const Standard_Real theT2l, 
1059                      const Standard_Real theTolConf,
1060                      const Standard_Integer theMaxCount,
1061                      IntRes2d_IntersectionPoint& thePInt, Standard_Real& theDist,
1062                      Standard_Integer& theCount)
1063 {
1064   theCount++;
1065   //
1066   Standard_Real aTol2 = theTolConf*theTolConf;
1067   Standard_Real aPTol1 = Max(100.*Epsilon(Max(Abs(theT1f), Abs(theT1l))), Precision::PConfusion());
1068   Standard_Real aPTol2 = Max(100.*Epsilon(Max(Abs(theT2f), Abs(theT2l))), Precision::PConfusion());
1069   gp_Pnt2d aP1f, aP1l, aP2f, aP2l;
1070   Bnd_Box2d aB1, aB2;
1071   //
1072   TheCurveTool::D0(theC1, theT1f, aP1f);
1073   TheCurveTool::D0(theC1, theT1l, aP1l);
1074   aB1.Add(aP1f);
1075   aB1.Add(aP1l);
1076   aB1.Enlarge(theTolConf);
1077   //
1078   TheCurveTool::D0(theC2, theT2f, aP2f);
1079   TheCurveTool::D0(theC2, theT2l, aP2l);
1080   aB2.Add(aP2f);
1081   aB2.Add(aP2l);
1082   aB2.Enlarge(theTolConf);
1083   //
1084   if(aB1.IsOut(aB2))
1085   {
1086     theCount--;
1087     return;
1088   }
1089   //
1090   Standard_Boolean isSmall1 = (theT1l - theT1f) <= aPTol1 || aP1f.SquareDistance(aP1l) / 4. <= aTol2;
1091   Standard_Boolean isSmall2 = (theT2l - theT2f) <= aPTol2 || aP2f.SquareDistance(aP2l) / 4. <= aTol2;
1092
1093   if((isSmall1 && isSmall2) || (theCount > theMaxCount))
1094   {
1095     //Seems to be intersection
1096     //Simple treatment of segment intersection
1097     gp_XY aPnts1[3] = {aP1f.XY(), (aP1f.XY() + aP1l.XY()) / 2., aP1l.XY()};
1098     gp_XY aPnts2[3] = {aP2f.XY(), (aP2f.XY() + aP2l.XY()) / 2., aP2l.XY()};
1099     Standard_Integer i, j, imin = -1, jmin = -1;
1100     Standard_Real dmin = RealLast(), d;
1101     for(i = 0; i < 3; i++)
1102     {
1103       for(j = 0; j < 3; j++)
1104       {
1105         d = (aPnts1[i] - aPnts2[j]).SquareModulus();
1106         if(d < dmin)
1107         {
1108           dmin=d;
1109           imin = i;
1110           jmin = j;
1111         }
1112       }
1113     }
1114     //
1115     dmin = Sqrt(dmin);
1116     if(theDist > dmin)
1117     {
1118       theDist = dmin;
1119       //
1120       Standard_Real t1;
1121       if(imin == 0)
1122       {
1123         t1 = theT1f;
1124       }
1125       else if(imin == 1)
1126       {
1127         t1 = (theT1f + theT1l) / 2.;
1128       }
1129       else
1130       {
1131         t1 = theT1l;
1132       }
1133       //
1134       Standard_Real t2;
1135       if(jmin == 0)
1136       {
1137         t2 = theT2f;
1138       }
1139       else if(jmin == 1)
1140       {
1141         t2 = (theT2f + theT2l) / 2.;
1142       }
1143       else
1144       {
1145         t2 = theT2l;
1146       }
1147       //
1148       gp_Pnt2d aPint((aPnts1[imin] + aPnts2[jmin])/2.);
1149       //
1150       IntRes2d_Transition aTrans1, aTrans2;
1151       thePInt.SetValues(aPint, t1, t2, aTrans1, aTrans2, Standard_False);
1152     }
1153     theCount--;
1154     return;
1155   }
1156
1157   if(isSmall1)
1158   {
1159     Standard_Real aT2m = (theT2l + theT2f) / 2.;
1160     GetIntersection(theC1, theT1f, theT1l, theC2, theT2f, aT2m, theTolConf, theMaxCount, thePInt, theDist, theCount);
1161     GetIntersection(theC1, theT1f, theT1l, theC2, aT2m, theT2l, theTolConf, theMaxCount, thePInt, theDist, theCount);
1162   }
1163   else if(isSmall2)
1164   {
1165     Standard_Real aT1m = (theT1l + theT1f) / 2.;
1166     GetIntersection(theC1, theT1f, aT1m, theC2, theT2f, theT2l, theTolConf, theMaxCount, thePInt, theDist, theCount);
1167     GetIntersection(theC1, aT1m, theT1l, theC2, theT2f, theT2l, theTolConf, theMaxCount, thePInt, theDist, theCount);
1168   }
1169   else
1170   {
1171     Standard_Real aT1m = (theT1l + theT1f) / 2.;
1172     Standard_Real aT2m = (theT2l + theT2f) / 2.;
1173     GetIntersection(theC1, theT1f, aT1m, theC2, theT2f, aT2m, theTolConf, theMaxCount, thePInt, theDist, theCount);
1174     GetIntersection(theC1, theT1f, aT1m, theC2, aT2m, theT2l, theTolConf, theMaxCount, thePInt, theDist, theCount);
1175     GetIntersection(theC1, aT1m, theT1l, theC2, theT2f, aT2m, theTolConf, theMaxCount, thePInt, theDist, theCount);
1176     GetIntersection(theC1, aT1m, theT1l, theC2, aT2m, theT2l, theTolConf, theMaxCount, thePInt, theDist, theCount);
1177   }
1178
1179 }
1180
1181 //=======================================================================
1182 //function : GetMinNbPoints
1183 //purpose  : 
1184 //=======================================================================
1185 Standard_Integer IntCurve_IntPolyPolyGen::GetMinNbSamples() const
1186 {
1187   return myMinPntNb;
1188 }
1189
1190 //=======================================================================
1191 //function : SetMinNbPoints
1192 //purpose  : 
1193 //=======================================================================
1194 void IntCurve_IntPolyPolyGen::SetMinNbSamples(const Standard_Integer theMinNbSamples)
1195 {
1196   myMinPntNb = theMinNbSamples;
1197 }