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
 490   //----------------------------------------------------------------------
 491   //-- Processing of TangentZone
 492   //----------------------------------------------------------------------
 493   Standard_Integer Nbtz = InterPP.NbTangentZones();
 494   for(Standard_Integer tz=1; tz <= Nbtz; tz++) {
 495     Standard_Integer NbPnts = InterPP.ZoneValue(tz).NumberOfPoints();
 496     //====================================================================
 497     //== Find the first and the last point in the tangency zone.
 498     //====================================================================
 499     Standard_Real ParamSupOnCurve2,ParamInfOnCurve2;
 500     Standard_Real ParamSupOnCurve1,ParamInfOnCurve1;
 501 //    Standard_Integer SegIndex,SegIndex1onP1,SegIndex1onP2,SegIndex2onP1,SegIndex2onP2;
 502     Standard_Integer SegIndex1onP1,SegIndex1onP2;
 503     Intf_PIType Type;
 504     Standard_Real ParamOnLine;
 505     Standard_Real PolyUInf,PolyUSup,PolyVInf,PolyVSup;
 506     ParamSupOnCurve2=ParamSupOnCurve1=PolyUSup=PolyVSup=-RealLast();
 507     ParamInfOnCurve2=ParamInfOnCurve1=PolyUInf=PolyVInf= RealLast();
 508     for(Standard_Integer qq=1;qq<=NbPnts;qq++) {
 509       const Intf_SectionPoint& SPnt1 = InterPP.ZoneValue(tz).GetPoint(qq);
 510       //====================================================================
 511       //== The zones of tangency are discretized
 512       //== Test of stop : Check if
 513       //==     (Deflection  < Tolerance)
 514       //==  Or (Sample < EpsX)   (normally the first condition is
 515       //==                           more strict)
 516       //====================================================================
 517 //      Standard_Real _PolyUInf,_PolyUSup,_PolyVInf,_PolyVSup;
 518       Standard_Real _PolyUInf,_PolyVInf;
 519
 520       SPnt1.InfoFirst(Type,SegIndex1onP1,ParamOnLine);
 521       if(SegIndex1onP1 > Poly1.NbSegments()) { SegIndex1onP1--; ParamOnLine = 1.0; }
 522       if(SegIndex1onP1 <= 0) { SegIndex1onP1=1; ParamOnLine = 0.0; }
 523       _PolyUInf = Poly1.ApproxParamOnCurve(SegIndex1onP1,ParamOnLine);
 524
 525       SPnt1.InfoSecond(Type,SegIndex1onP2,ParamOnLine);
 526       if(SegIndex1onP2 > Poly1.NbSegments()) { SegIndex1onP2--; ParamOnLine = 1.0; }
 527       if(SegIndex1onP2 <= 0) { SegIndex1onP2=1; ParamOnLine = 0.0; }
 528       _PolyVInf = Poly1.ApproxParamOnCurve(SegIndex1onP2,ParamOnLine);
 529
 530       //----------------------------------------------------------------------
 531
 532       if(ParamInfOnCurve1 > _PolyUInf) ParamInfOnCurve1=_PolyUInf;
 533       if(ParamInfOnCurve2 > _PolyVInf) ParamInfOnCurve2=_PolyVInf;
 534
 535       if(ParamSupOnCurve1 < _PolyUInf) ParamSupOnCurve1=_PolyUInf;
 536       if(ParamSupOnCurve2 < _PolyVInf) ParamSupOnCurve2=_PolyVInf;
 537     }
 538
 539     PolyUInf= ParamInfOnCurve1;
 540     PolyUSup= ParamSupOnCurve1;
 541     PolyVInf= ParamInfOnCurve2;
 542     PolyVSup= ParamSupOnCurve2;
 543
 544     TheCurveTool::D0(C1,PolyUInf,P1);
 545     TheCurveTool::D0(C1,PolyVInf,P2);
 546     Standard_Real distmemesens = P1.SquareDistance(P2);
 547     TheCurveTool::D0(C1,PolyVSup,P2);
 548     Standard_Real distdiffsens = P1.SquareDistance(P2);
 549     if(distmemesens > distdiffsens) {
 550       Standard_Real qwerty=PolyVInf; PolyVInf=PolyVSup; PolyVSup=qwerty;
 551     }
 552
 553     //-----------------------------------------------------------------
 554     //-- Calculate Positions of Points on the curve and
 555     //-- Transitions on each limit of the segment
 556
 557     IntRes2d_Position Pos1 = IntRes2d_Middle;
 558     IntRes2d_Position Pos2 = IntRes2d_Middle;
 559     IntRes2d_Transition  Trans1,Trans2;
 560
 561     TheCurveTool::D1(C1,PolyUInf,P1,Tan1);
 562     TheCurveTool::D1(C1,PolyVInf,P2,Tan2);
 563
 564     if(P1.Distance(DomainOnCurve1.FirstPoint())<=DomainOnCurve1.FirstTolerance())    {
 565       Pos1 = IntRes2d_Head;
 566     }
 567     else if(P1.Distance(DomainOnCurve1.LastPoint())<=DomainOnCurve1.LastTolerance()) {
 568       Pos1 = IntRes2d_End;
 569     }
 570     if(P2.Distance(DomainOnCurve2.FirstPoint())<=DomainOnCurve2.FirstTolerance())    {
 571       Pos2 = IntRes2d_Head;
 572     }
 573     else if(P2.Distance(DomainOnCurve2.LastPoint())<=DomainOnCurve2.LastTolerance()) {
 574       Pos2 = IntRes2d_End;
 575     }
 576
 577     if(Pos1==IntRes2d_Middle && Pos2!=IntRes2d_Middle) {
 578       PolyUInf=TheProjPCur::FindParameter( C1,P2,D1.FirstParameter(),D1.LastParameter(),TheCurveTool::EpsX(C1));
 579     }
 580     else if(Pos1!=IntRes2d_Middle && Pos2==IntRes2d_Middle) {
 581       PolyVInf=TheProjPCur::FindParameter( C1,P1,D1.FirstParameter(),D1.LastParameter(),TheCurveTool::EpsX(C1));
 582     }
 583     else if(Abs(ParamInfOnCurve1-ParamSupOnCurve1) > Abs(ParamInfOnCurve2-ParamSupOnCurve2)) {
 584       PolyVInf=TheProjPCur::FindParameter( C1,P1,D1.FirstParameter(),D1.LastParameter(),TheCurveTool::EpsX(C1));
 585     }
 586     else {
 587       PolyUInf=TheProjPCur::FindParameter( C1,P2,D1.FirstParameter(),D1.LastParameter(),TheCurveTool::EpsX(C1));
 588     }
 589
 590
 591
 592     if(IntImpParGen::DetermineTransition( Pos1,Tan1,Trans1,Pos2,Tan2,Trans2,TolConf)
 593        == Standard_False)
 594     {
 595       TheCurveTool::D2(C1,PolyUInf,P1,Tan1,Norm1);
 596       TheCurveTool::D2(C1,PolyVInf,P2,Tan2,Norm2);
 597       IntImpParGen::DetermineTransition(Pos1,Tan1,Norm1,Trans1,
 598                                         Pos2,Tan2,Norm2,Trans2,TolConf);
 599     }
 600     IntRes2d_IntersectionPoint PtSeg1(P1,PolyUInf,PolyVInf
 601                                         ,Trans1,Trans2,Standard_False);
 602     //----------------------------------------------------------------------
 603
 604     if((Abs(PolyUInf-PolyUSup) <= TheCurveTool::EpsX(C1)) ||
 605        (Abs(PolyVInf-PolyVSup) <= TheCurveTool::EpsX(C1)))
 606     {
 607       //bad segment
 608     }
 609     else
 610     {
 611       TheCurveTool::D1(C1,PolyUSup,P1,Tan1);
 612       TheCurveTool::D1(C1,PolyVSup,P2,Tan2);
 613       Pos1 = IntRes2d_Middle; Pos2 = IntRes2d_Middle;
 614
 615       if(P1.Distance(DomainOnCurve1.FirstPoint())<=DomainOnCurve1.FirstTolerance())    {
 616         Pos1 = IntRes2d_Head;
 617       }
 618       else if(P1.Distance(DomainOnCurve1.LastPoint())<=DomainOnCurve1.LastTolerance()) {
 619         Pos1 = IntRes2d_End;
 620       }
 621       if(P2.Distance(DomainOnCurve2.FirstPoint())<=DomainOnCurve2.FirstTolerance())    {
 622         Pos2 = IntRes2d_Head;
 623       }
 624       else if(P2.Distance(DomainOnCurve2.LastPoint())<=DomainOnCurve2.LastTolerance()) {
 625         Pos2 = IntRes2d_End;
 626       }
 627
 628
 629       if(Pos1==IntRes2d_Middle && Pos2!=IntRes2d_Middle) {
 630         PolyUSup=TheProjPCur::FindParameter( C1,P2,D1.FirstParameter(),D1.LastParameter(),TheCurveTool::EpsX(C1));
 631       }
 632       else if(Pos1!=IntRes2d_Middle && Pos2==IntRes2d_Middle) {
 633         PolyVSup=TheProjPCur::FindParameter( C1,P1,D1.FirstParameter(),D1.LastParameter(),TheCurveTool::EpsX(C1));
 634       }
 635       else if(Abs(ParamInfOnCurve1-ParamSupOnCurve1) > Abs(ParamInfOnCurve2-ParamSupOnCurve2)) {
 636         PolyVSup=TheProjPCur::FindParameter( C1,P1,D1.FirstParameter(),D1.LastParameter(),TheCurveTool::EpsX(C1));
 637       }
 638       else {
 639         PolyUSup=TheProjPCur::FindParameter( C1,P2,D1.FirstParameter(),D1.LastParameter(),TheCurveTool::EpsX(C1));
 640       }
 641
 642       if(IntImpParGen::DetermineTransition( Pos1,Tan1,Trans1,Pos2,Tan2,Trans2,TolConf)
 643          ==Standard_False) {
 644         TheCurveTool::D2(C1,PolyUSup,P1,Tan1,Norm1);
 645         TheCurveTool::D2(C1,PolyVSup,P2,Tan2,Norm2);
 646         IntImpParGen::DetermineTransition(Pos1,Tan1,Norm1,Trans1,
 647                                           Pos2,Tan2,Norm2,Trans2,TolConf);
 648       }
 649       IntRes2d_IntersectionPoint PtSeg2(P1,PolyUSup,PolyVSup
 650                                         ,Trans1,Trans2,Standard_False);
 651
 652       Standard_Boolean Oppos = (Tan1.Dot(Tan2) > 0.0)? Standard_False : Standard_True;
 653       if(ParamInfOnCurve1 > ParamSupOnCurve1) {
 654         IntRes2d_IntersectionSegment Seg(PtSeg2,PtSeg1,Oppos,Standard_False);
 655         Append(Seg);
 656       }
 657       else {
 658         IntRes2d_IntersectionSegment Seg(PtSeg1,PtSeg2,Oppos,Standard_False);
 659         Append(Seg);
 660       }
 661     }
 662   } //end of processing of TangentZone
 663
 664  done = Standard_True;
 665 }
 666
 667
 668 Standard_Boolean HeadOrEndPoint( const IntRes2d_Domain& D1
 669                                 ,const TheCurve& C1
 670                                 ,const Standard_Real tu
 671                                 ,const IntRes2d_Domain& D2
 672                                 ,const TheCurve& C2
 673                                 ,const Standard_Real tv
 674                                 ,const Standard_Real TolConf
 675                                 ,IntRes2d_IntersectionPoint& IntPt
 676                                 ,Standard_Boolean& HeadOn1
 677                                 ,Standard_Boolean& HeadOn2
 678                                 ,Standard_Boolean& EndOn1
 679                                 ,Standard_Boolean& EndOn2
 680                                 ,Standard_Integer PosSegment) {
 681
 682   gp_Pnt2d P1,P2,SP1,SP2;
 683   gp_Vec2d T1,T2,N1,N2;
 684   Standard_Real u=tu;
 685   Standard_Real v=tv;
 686   Standard_Real svu = u;
 687   Standard_Real svv = v;
 688
 689   TheCurveTool::D1(C1,u,P1,T1);
 690   TheCurveTool::D1(C2,v,P2,T2);
 691
 692   IntRes2d_Position Pos1 = IntRes2d_Middle;
 693   IntRes2d_Position Pos2 = IntRes2d_Middle;
 694   IntRes2d_Transition Trans1,Trans2;
 695
 696   //----------------------------------------------------------------------
 697   //-- Head On 1   :        Head1 <-> P2
 698   if(P2.Distance(D1.FirstPoint())<=D1.FirstTolerance())    {
 699     Pos1 = IntRes2d_Head;
 700     HeadOn1 = Standard_True;
 701     SP1 = D1.FirstPoint();
 702     u = D1.FirstParameter();
 703   }
 704   //----------------------------------------------------------------------
 705   //-- End On 1   :         End1 <-> P2
 706   else if(P2.Distance(D1.LastPoint())<=D1.LastTolerance()) {
 707     Pos1 = IntRes2d_End;
 708     EndOn1 = Standard_True;
 709     SP1 = D1.LastPoint();
 710     u = D1.LastParameter();
 711   }
 712
 713   //----------------------------------------------------------------------
 714   //-- Head On 2   :        Head2 <-> P1
 715   else if(P1.Distance(D2.FirstPoint())<=D2.FirstTolerance())    {
 716     Pos2 = IntRes2d_Head;
 717     HeadOn2 = Standard_True;
 718     SP2 = D2.FirstPoint();
 719     v = D2.FirstParameter();
 720   }
 721   //----------------------------------------------------------------------
 722   //-- End On 2   :        End2 <-> P1
 723   else if(P1.Distance(D2.LastPoint())<=D2.LastTolerance()) {
 724     Pos2 = IntRes2d_End;
 725     EndOn2 = Standard_True;
 726     SP2 = D2.LastPoint();
 727     v = D2.LastParameter();
 728   }
 729
 730   Standard_Real EpsX1 = TheCurveTool::EpsX(C1);
 731   Standard_Real EpsX2 = TheCurveTool::EpsX(C2);
 732
 733   if((Pos1 != IntRes2d_Middle)||(Pos2 !=  IntRes2d_Middle)) {
 734     if(Pos1 == IntRes2d_Middle) {
 735       if(Abs(u-D1.FirstParameter()) <= EpsX1) {
 736               Pos1 = IntRes2d_Head;
 737               P1 = D1.FirstPoint();
 738               HeadOn1 = Standard_True;
 739       }
 740       else if(Abs(u-D1.LastParameter()) <= EpsX1) {
 741               Pos1 = IntRes2d_End;
 742               P1 = D1.LastPoint();
 743               EndOn1 = Standard_True;
 744       }
 745     }
 746     else if(u!=tu) {
 747       P1 = SP1;
 748     }
 749
 750
 751     if(Pos2 == IntRes2d_Middle) {
 752       if(Abs(v-D2.FirstParameter()) <= EpsX2) {
 753               Pos2 = IntRes2d_Head;
 754               HeadOn2 = Standard_True;
 755               P2 = D2.FirstPoint();
 756               if(Pos1 != IntRes2d_Middle) {
 757                 P1.SetCoord(0.5*(P1.X()+P2.X()),0.5*(P1.Y()+P2.Y()));
 758               }
 759               else {
 760                 P2 = P1;
 761               }
 762       }
 763       else if(Abs(v-D2.LastParameter()) <= EpsX2) {
 764               Pos2 = IntRes2d_End;
 765               EndOn2 = Standard_True;
 766               P2 = D2.LastPoint();
 767               if(Pos1 != IntRes2d_Middle) {
 768                 P1.SetCoord(0.5*(P1.X()+P2.X()),0.5*(P1.Y()+P2.Y()));
 769               }
 770               else {
 771                 P2 = P1;
 772               }
 773       }
 774     }
 775
 776     //--------------------------------------------------------------------
 777     //-- It is tested if a point at the end of segment already has its transitions
 778     //-- If Yes, the new point is not created
 779     //--
 780     //-- PosSegment =            1    if Head Head
 781     //--                       2      if Head End
 782     //--                     4        if End  Head
 783     //--                   8          if End  End
 784     //--------------------------------------------------------------------
 785     if(Pos1 == IntRes2d_Head) {
 786       if((Pos2 == IntRes2d_Head)&&(PosSegment & 1)) return(Standard_False);
 787       if((Pos2 == IntRes2d_End )&&(PosSegment & 2)) return(Standard_False);
 788     }
 789     else if(Pos1 == IntRes2d_End) {
 790       if((Pos2 == IntRes2d_Head)&&(PosSegment & 4)) return(Standard_False);
 791       if((Pos2 == IntRes2d_End )&&(PosSegment & 8)) return(Standard_False);
 792     }
 793
 794
 795     if(IntImpParGen::DetermineTransition( Pos1,T1,Trans1,Pos2,T2,Trans2,TolConf)
 796        == Standard_False) {
 797       TheCurveTool::D2(C1,svu,P1,T1,N1);
 798       TheCurveTool::D2(C2,svv,P2,T2,N2);
 799       IntImpParGen::DetermineTransition(Pos1,T1,N1,Trans1,
 800                                         Pos2,T2,N2,Trans2,TolConf);
 801     }
 802     IntPt.SetValues(P1,u,v,Trans1,Trans2,Standard_False);
 803     return(Standard_True);
 804   }
 805   else
 806     return(Standard_False);
 807 }
 808
 809 //=======================================================================
 810 //function : Perform
 811 //purpose  : Base method to perform polyline / polyline intersection for
 812 //           pair of curves.
 813 //=======================================================================
 814 void IntCurve_IntPolyPolyGen::Perform(const TheCurve& C1,
 815                                       const IntRes2d_Domain& D1,
 816                                       const TheCurve& C2,
 817                                       const IntRes2d_Domain& D2,
 818                                       const Standard_Real TolConf,
 819                                       const Standard_Real Tol,
 820                                       const Standard_Integer NbIter,
 821                                       const Standard_Real DeltaU,
 822                                       const Standard_Real DeltaV)
 823 {
 824   Standard_Integer nbsamplesOnC1,nbsamplesOnC2;
 825   done = Standard_False;
 826
 827   if(NbIter>NBITER_MAX_POLYGON) return;
 828
 829   // Number of samples tunning.
 830   nbsamplesOnC1 = TheCurveTool::NbSamples(C1,D1.FirstParameter(),D1.LastParameter());
 831   nbsamplesOnC2 = TheCurveTool::NbSamples(C2,D2.FirstParameter(),D2.LastParameter());
 832
 833   if (NbIter == 0)
 834   {
 835     // Minimal number of points.
 836     nbsamplesOnC1 = Max(nbsamplesOnC1, myMinPntNb);
 837     nbsamplesOnC2 = Max(nbsamplesOnC2, myMinPntNb);
 838   }
 839   else
 840   {
 841     // Increase number of samples in second and next iterations.
 842     nbsamplesOnC1=(5 * (nbsamplesOnC1 * NbIter)) / 4;
 843     nbsamplesOnC2=(5 * (nbsamplesOnC2 * NbIter)) / 4;
 844   }
 845
 846   NCollection_Handle<IntCurve_ThePolygon2d>
 847     aPoly1 = new IntCurve_ThePolygon2d(C1,nbsamplesOnC1,D1,Tol),
 848     aPoly2 = new IntCurve_ThePolygon2d(C2,nbsamplesOnC2,D2,Tol);
 849
 850   if( (aPoly1->DeflectionOverEstimation() > TolConf) &&
 851       (aPoly2->DeflectionOverEstimation() > TolConf))
 852   {
 853     const Standard_Real aDeflectionSum =
 854       Max(aPoly1->DeflectionOverEstimation(), TolConf) +
 855       Max(aPoly2->DeflectionOverEstimation(), TolConf);
 856
 857     if (nbsamplesOnC2 > nbsamplesOnC1)
 858     {
 859       aPoly2->ComputeWithBox(C2, aPoly1->Bounding());
 860       aPoly1->SetDeflectionOverEstimation(aDeflectionSum);
 861       aPoly1->ComputeWithBox(C1, aPoly2->Bounding());
 862     }
 863     else
 864     {
 865       aPoly1->ComputeWithBox(C1, aPoly2->Bounding());
 866       aPoly2->SetDeflectionOverEstimation(aDeflectionSum);
 867       aPoly2->ComputeWithBox(C2, aPoly1->Bounding());
 868     }
 869   }
 870
 871   //----------------------------------------------------------------------
 872   //-- if the deflection less then the Tolerance of Confusion
 873   //-- Then the deflection of the polygon is set in TolConf
 874   //-- (Detection of Tangency Zones)
 875   //----------------------------------------------------------------------
 876
 877   if(aPoly1->DeflectionOverEstimation() < TolConf) {
 878     aPoly1->SetDeflectionOverEstimation(TolConf);
 879   }
 880   if(aPoly2->DeflectionOverEstimation() < TolConf) {
 881     aPoly2->SetDeflectionOverEstimation(TolConf);
 882   }
 883   // for case when a few polygon points were replaced by line
 884   // if exact solution was not found
 885   // then search of precise solution will be repeated
 886   // for polygon contains all initial points
 887   // secondary search will be performed only for case when initial points
 888   // were dropped
 889   Standard_Boolean isFullRepresentation = ( aPoly1->NbSegments() == nbsamplesOnC1 &&
 890             aPoly2->NbSegments() == nbsamplesOnC2 );
 891
 892   if( !findIntersect( C1, D1, C2, D2, TolConf, Tol, NbIter,
 893           DeltaU, DeltaV, *aPoly1, *aPoly2, isFullRepresentation ) && !isFullRepresentation )
 894   {
 895     if(aPoly1->NbSegments() < nbsamplesOnC1)
 896     {
 897       aPoly1 = new IntCurve_ThePolygon2d(C1,nbsamplesOnC1,D1,Tol);
 898     }
 899     if(aPoly2->NbSegments() < nbsamplesOnC2)
 900     {
 901       aPoly2 = new IntCurve_ThePolygon2d(C2,nbsamplesOnC2,D2,Tol);
 902     }
 903
 904     findIntersect( C1, D1, C2, D2, TolConf, Tol, NbIter,
 905       DeltaU, DeltaV, *aPoly1, *aPoly2,
 906       Standard_True);
 907
 908   }
 909
 910   done = Standard_True;
 911 }
 912
 913 //======================================================================
 914 // Purpose : findIntersect
 915 //======================================================================
 916
 917 Standard_Boolean IntCurve_IntPolyPolyGen::findIntersect(
 918     const TheCurve& C1,
 919           const IntRes2d_Domain& D1,
 920           const TheCurve& C2,
 921           const IntRes2d_Domain& D2,
 922           const Standard_Real TolConf,
 923           const Standard_Real Tol,
 924           const Standard_Integer NbIter,
 925           const Standard_Real DeltaU,
 926           const Standard_Real DeltaV,
 927           const IntCurve_ThePolygon2d& thePoly1,
 928           const IntCurve_ThePolygon2d& thePoly2,
 929           Standard_Boolean isFullPolygon )
 930 {
 931
 932   gp_Vec2d Tan1,Tan2,Norm1,Norm2;
 933   gp_Pnt2d P1,P2;
 934   Intf_InterferencePolygon2d InterPP(thePoly1,thePoly2);
 935   IntCurve_ExactIntersectionPoint  EIP(C1,C2,TolConf);
 936   Standard_Real U = 0., V = 0.;
 937   Standard_Boolean AnErrorOccurred = Standard_False;
 938   done = Standard_True; // To prevent exception in nbp=NbPoints();
 939   //----------------------------------------------------------------------
 940   //-- Processing of SectionPoint
 941   //----------------------------------------------------------------------
 942   Standard_Integer Nbsp = InterPP.NbSectionPoints();
 943   for(Standard_Integer sp=1; sp <= Nbsp; sp++) {
 944     const Intf_SectionPoint& SPnt = InterPP.PntValue(sp);
 945     Standard_Integer SegIndex1,SegIndex2;
 946     Standard_Real    ParamOn1,ParamOn2;
 947     Intf_PIType      Type;
 948
 949     SPnt.InfoFirst(Type,SegIndex1,ParamOn1);
 950     SPnt.InfoSecond(Type,SegIndex2,ParamOn2);
 951     EIP.Perform(thePoly1,thePoly2,SegIndex1,SegIndex2,ParamOn1,ParamOn2);
 952     AnErrorOccurred = EIP.AnErrorOccurred();
 953
 954     if( !EIP.NbRoots() && !isFullPolygon)
 955       return Standard_False;
 956
 957     if(AnErrorOccurred)
 958     {
 959       continue;
 960     }
 961
 962     //--------------------------------------------------------------------
 963     //-- It is checked if the found point is really a root
 964     //--------------------------------------------------------------------
 965
 966     EIP.Roots(U,V);
 967     TheCurveTool::D1(C1,U,P1,Tan1);
 968     TheCurveTool::D1(C2,V,P2,Tan2);
 969     Standard_Real Dist = P1.Distance(P2);
 970     if(EIP.NbRoots() == 0 && Dist > TolConf)
 971     {
 972       IntRes2d_Transition aTrans;
 973       IntRes2d_IntersectionPoint aPInt(P1, U, V, aTrans, aTrans, Standard_False);
 974       Standard_Real aT1f, aT1l, aT2f, aT2l;
 975       aT1f= thePoly1.ApproxParamOnCurve(SegIndex1, 0.0);
 976       aT1l= thePoly1.ApproxParamOnCurve(SegIndex1, 1.0);
 977       aT2f= thePoly2.ApproxParamOnCurve(SegIndex2, 0.0);
 978       aT2l= thePoly2.ApproxParamOnCurve(SegIndex2, 1.0);
 979       //
 980       Standard_Integer aMaxCount = 16, aCount = 0;
 981       GetIntersection(C1, aT1f, aT1l, C2, aT2f, aT2l, TolConf, aMaxCount,
 982                       aPInt, Dist, aCount);
 983       U = aPInt.ParamOnFirst();
 984       V = aPInt.ParamOnSecond();
 985       TheCurveTool::D1(C1,U,P1,Tan1);
 986       TheCurveTool::D1(C2,V,P2,Tan2);
 987       Dist = P1.Distance(P2);
 988     }
 989     //-----------------------------------------------------------------
 990     //-- It is checked if the point (u,v) does not exist already
 991     //--
 992     Standard_Integer nbp=NbPoints();
 993     Standard_Real EpsX1 = 10.0*TheCurveTool::EpsX(C1);
 994     Standard_Real EpsX2 = 10.0*TheCurveTool::EpsX(C2);
 995     for(Standard_Integer p=1; p<=nbp; p++) {
 996       const IntRes2d_IntersectionPoint& P=Point(p);
 997       if(Abs(U-P.ParamOnFirst()) <= EpsX1) {
 998         if(Abs(V-P.ParamOnSecond()) <= EpsX2) {
 999           Dist = TolConf+1.0;  p+=nbp;
1000         }
1001       }
1002     }
1003
1004     if(Dist <= TolConf) {    //-- Or the point is already present
1005       IntRes2d_Position Pos1 = IntRes2d_Middle;
1006       IntRes2d_Position Pos2 = IntRes2d_Middle;
1007       IntRes2d_Transition  Trans1,Trans2;
1008       //-----------------------------------------------------------------
1009       //-- Calculate the Positions of Points on the curve
1010       //--
1011       if(P1.Distance(DomainOnCurve1.FirstPoint())<=DomainOnCurve1.FirstTolerance())
1012         Pos1 = IntRes2d_Head;
1013       else if(P1.Distance(DomainOnCurve1.LastPoint())<=DomainOnCurve1.LastTolerance())
1014         Pos1 = IntRes2d_End;
1015
1016       if(P2.Distance(DomainOnCurve2.FirstPoint())<=DomainOnCurve2.FirstTolerance())
1017         Pos2 = IntRes2d_Head;
1018       else if(P2.Distance(DomainOnCurve2.LastPoint())<=DomainOnCurve2.LastTolerance())
1019         Pos2 = IntRes2d_End;
1020       //-----------------------------------------------------------------
1021       //-- Calculate the Transitions (see IntImpParGen.cxx)
1022       //--
1023       if(IntImpParGen::DetermineTransition (Pos1, Tan1, Trans1, Pos2, Tan2, Trans2, TolConf) == Standard_False) {
1024         TheCurveTool::D2(C1,U,P1,Tan1,Norm1);
1025         TheCurveTool::D2(C2,V,P2,Tan2,Norm2);
1026         IntImpParGen::DetermineTransition (Pos1, Tan1, Norm1, Trans1, Pos2, Tan2, Norm2, Trans2, TolConf);
1027       }
1028       IntRes2d_IntersectionPoint IP(P1,U,V,Trans1,Trans2,Standard_False);
1029       Insert(IP);
1030     }
1031   }
1032
1033   //----------------------------------------------------------------------
1034   //-- Processing of TangentZone
1035   //----------------------------------------------------------------------
1036   Standard_Integer Nbtz = InterPP.NbTangentZones();
1037   for(Standard_Integer tz=1; tz <= Nbtz; tz++) {
1038     Standard_Integer NbPnts = InterPP.ZoneValue(tz).NumberOfPoints();
1039     //====================================================================
1040     //== Find the first and the last point in the tangency zone.
1041     //====================================================================
1042     Standard_Real ParamSupOnCurve2,ParamInfOnCurve2;
1043     Standard_Real ParamSupOnCurve1,ParamInfOnCurve1;
1044 //    Standard_Integer SegIndex,SegIndex1onP1,SegIndex1onP2,SegIndex2onP1,SegIndex2onP2;
1045     Standard_Integer SegIndex1onP1,SegIndex1onP2;
1046     Intf_PIType Type;
1047     Standard_Real ParamOnLine;
1048     Standard_Real PolyUInf,PolyUSup,PolyVInf,PolyVSup;
1049     ParamSupOnCurve2=ParamSupOnCurve1=PolyUSup=PolyVSup=-RealLast();
1050     ParamInfOnCurve2=ParamInfOnCurve1=PolyUInf=PolyVInf= RealLast();
1051     for(Standard_Integer qq=1;qq<=NbPnts;qq++) {
1052       const Intf_SectionPoint& SPnt1 = InterPP.ZoneValue(tz).GetPoint(qq);
1053       //====================================================================
1054       //== The zones of tangency are discretized
1055       //== Test of stop : Check if
1056       //==     (Deflection  < Tolerance)
1057       //==  Or (Sample < EpsX)   (normally the first condition is
1058       //==                           more strict)
1059       //====================================================================
1060 //      Standard_Real _PolyUInf,_PolyUSup,_PolyVInf,_PolyVSup;
1061       Standard_Real _PolyUInf,_PolyVInf;
1062
1063       SPnt1.InfoFirst(Type,SegIndex1onP1,ParamOnLine);
1064       if(SegIndex1onP1 > thePoly1.NbSegments()) { SegIndex1onP1--; ParamOnLine = 1.0; }
1065       if(SegIndex1onP1 <= 0) { SegIndex1onP1=1; ParamOnLine = 0.0; }
1066       _PolyUInf = thePoly1.ApproxParamOnCurve(SegIndex1onP1,ParamOnLine);
1067
1068       SPnt1.InfoSecond(Type,SegIndex1onP2,ParamOnLine);
1069       if(SegIndex1onP2 > thePoly2.NbSegments()) { SegIndex1onP2--; ParamOnLine = 1.0; }
1070       if(SegIndex1onP2 <= 0) { SegIndex1onP2=1; ParamOnLine = 0.0; }
1071       _PolyVInf = thePoly2.ApproxParamOnCurve(SegIndex1onP2,ParamOnLine);
1072
1073       //----------------------------------------------------------------------
1074
1075       if(ParamInfOnCurve1 > _PolyUInf) ParamInfOnCurve1=_PolyUInf;
1076       if(ParamInfOnCurve2 > _PolyVInf) ParamInfOnCurve2=_PolyVInf;
1077
1078       if(ParamSupOnCurve1 < _PolyUInf) ParamSupOnCurve1=_PolyUInf;
1079       if(ParamSupOnCurve2 < _PolyVInf) ParamSupOnCurve2=_PolyVInf;
1080     }
1081
1082     PolyUInf= ParamInfOnCurve1;
1083     PolyUSup= ParamSupOnCurve1;
1084     PolyVInf= ParamInfOnCurve2;
1085     PolyVSup= ParamSupOnCurve2;
1086
1087     TheCurveTool::D0(C1,PolyUInf,P1);
1088     TheCurveTool::D0(C2,PolyVInf,P2);
1089     Standard_Real distmemesens = P1.SquareDistance(P2);
1090     TheCurveTool::D0(C2,PolyVSup,P2);
1091     Standard_Real distdiffsens = P1.SquareDistance(P2);
1092     if(distmemesens > distdiffsens) {
1093       Standard_Real qwerty=PolyVInf; PolyVInf=PolyVSup; PolyVSup=qwerty;
1094     }
1095
1096     if(  (  (thePoly1.DeflectionOverEstimation() > TolConf)
1097             ||(thePoly2.DeflectionOverEstimation() > TolConf))
1098             &&(NbIter<NBITER_MAX_POLYGON)) {
1099
1100       IntRes2d_Domain RecursD1( TheCurveTool::Value(C1,ParamInfOnCurve1)
1101                                ,ParamInfOnCurve1,TolConf
1102                                ,TheCurveTool::Value(C1,ParamSupOnCurve1)
1103                                ,ParamSupOnCurve1,TolConf);
1104       IntRes2d_Domain RecursD2( TheCurveTool::Value(C2,ParamInfOnCurve2)
1105                                ,ParamInfOnCurve2,TolConf
1106                                ,TheCurveTool::Value(C2,ParamSupOnCurve2)
1107                                ,ParamSupOnCurve2,TolConf);
1108       //-- thePoly1(2) are not deleted,
1109       //-- finally they are destroyed.
1110       //-- !! No untimely return !!
1111       Perform(C1,RecursD1,C2,RecursD2,Tol,TolConf,NbIter+1,DeltaU,DeltaV);
1112     }
1113     else {
1114       //-----------------------------------------------------------------
1115       //-- Calculate Positions of Points on the curve and
1116       //-- Transitions on each limit of the segment
1117
1118       IntRes2d_Position Pos1 = IntRes2d_Middle;
1119       IntRes2d_Position Pos2 = IntRes2d_Middle;
1120       IntRes2d_Transition  Trans1,Trans2;
1121
1122       TheCurveTool::D1(C1,PolyUInf,P1,Tan1);
1123       TheCurveTool::D1(C2,PolyVInf,P2,Tan2);
1124
1125       if(P1.Distance(DomainOnCurve1.FirstPoint())<=DomainOnCurve1.FirstTolerance())    {
1126               Pos1 = IntRes2d_Head;
1127       }
1128       else if(P1.Distance(DomainOnCurve1.LastPoint())<=DomainOnCurve1.LastTolerance()) {
1129               Pos1 = IntRes2d_End;
1130       }
1131       if(P2.Distance(DomainOnCurve2.FirstPoint())<=DomainOnCurve2.FirstTolerance())    {
1132               Pos2 = IntRes2d_Head;
1133       }
1134       else if(P2.Distance(DomainOnCurve2.LastPoint())<=DomainOnCurve2.LastTolerance()) {
1135               Pos2 = IntRes2d_End;
1136       }
1137
1138       if(Pos1==IntRes2d_Middle && Pos2!=IntRes2d_Middle) {
1139               PolyUInf=TheProjPCur::FindParameter( C1,P2,D1.FirstParameter(),D1.LastParameter(),TheCurveTool::EpsX(C1));
1140       }
1141       else if(Pos1!=IntRes2d_Middle && Pos2==IntRes2d_Middle) {
1142               PolyVInf=TheProjPCur::FindParameter( C2,P1,D2.FirstParameter(),D2.LastParameter(),TheCurveTool::EpsX(C2));
1143       }
1144       else if(Abs(ParamInfOnCurve1-ParamSupOnCurve1) > Abs(ParamInfOnCurve2-ParamSupOnCurve2)) {
1145               PolyVInf=TheProjPCur::FindParameter( C2,P1,D2.FirstParameter(),D2.LastParameter(),TheCurveTool::EpsX(C2));
1146       }
1147       else {
1148               PolyUInf=TheProjPCur::FindParameter( C1,P2,D1.FirstParameter(),D1.LastParameter(),TheCurveTool::EpsX(C1));
1149       }
1150
1151
1152
1153       if(IntImpParGen::DetermineTransition( Pos1,Tan1,Trans1,Pos2,Tan2,Trans2,TolConf)
1154                == Standard_False)
1155       {
1156               TheCurveTool::D2(C1,PolyUInf,P1,Tan1,Norm1);
1157               TheCurveTool::D2(C2,PolyVInf,P2,Tan2,Norm2);
1158               IntImpParGen::DetermineTransition(Pos1,Tan1,Norm1,Trans1,
1159                                                 Pos2,Tan2,Norm2,Trans2,TolConf);
1160       }
1161       IntRes2d_IntersectionPoint PtSeg1(P1,PolyUInf,PolyVInf
1162                                         ,Trans1,Trans2,Standard_False);
1163       //----------------------------------------------------------------------
1164
1165       if((Abs(PolyUInf-PolyUSup) <= TheCurveTool::EpsX(C1))
1166               || (Abs(PolyVInf-PolyVSup) <= TheCurveTool::EpsX(C2)))
1167       {
1168               Insert(PtSeg1);
1169       }
1170       else
1171       {
1172               TheCurveTool::D1(C1,PolyUSup,P1,Tan1);
1173               TheCurveTool::D1(C2,PolyVSup,P2,Tan2);
1174               Pos1 = IntRes2d_Middle; Pos2 = IntRes2d_Middle;
1175
1176               if(P1.Distance(DomainOnCurve1.FirstPoint())<=DomainOnCurve1.FirstTolerance())    {
1177                 Pos1 = IntRes2d_Head;
1178               }
1179               else if(P1.Distance(DomainOnCurve1.LastPoint())<=DomainOnCurve1.LastTolerance()) {
1180                 Pos1 = IntRes2d_End;
1181               }
1182               if(P2.Distance(DomainOnCurve2.FirstPoint())<=DomainOnCurve2.FirstTolerance())    {
1183                 Pos2 = IntRes2d_Head;
1184               }
1185               else if(P2.Distance(DomainOnCurve2.LastPoint())<=DomainOnCurve2.LastTolerance()) {
1186                 Pos2 = IntRes2d_End;
1187               }
1188
1189
1190               if(Pos1==IntRes2d_Middle && Pos2!=IntRes2d_Middle) {
1191                 PolyUSup=TheProjPCur::FindParameter( C1,P2,D1.FirstParameter(),D1.LastParameter(),TheCurveTool::EpsX(C1));
1192               }
1193               else if(Pos1!=IntRes2d_Middle && Pos2==IntRes2d_Middle) {
1194                 PolyVSup=TheProjPCur::FindParameter( C2,P1,D2.FirstParameter(),D2.LastParameter(),TheCurveTool::EpsX(C2));
1195               }
1196               else if(Abs(ParamInfOnCurve1-ParamSupOnCurve1) > Abs(ParamInfOnCurve2-ParamSupOnCurve2)) {
1197                 PolyVSup=TheProjPCur::FindParameter( C2,P1,D2.FirstParameter(),D2.LastParameter(),TheCurveTool::EpsX(C2));
1198               }
1199               else {
1200                 PolyUSup=TheProjPCur::FindParameter( C1,P2,D1.FirstParameter(),D1.LastParameter(),TheCurveTool::EpsX(C1));
1201               }
1202
1203         if(IntImpParGen::DetermineTransition( Pos1,Tan1,Trans1,Pos2,Tan2,Trans2,TolConf)
1204            ==Standard_False) {
1205           TheCurveTool::D2(C1,PolyUSup,P1,Tan1,Norm1);
1206           TheCurveTool::D2(C2,PolyVSup,P2,Tan2,Norm2);
1207           IntImpParGen::DetermineTransition(Pos1,Tan1,Norm1,Trans1,
1208                                             Pos2,Tan2,Norm2,Trans2,TolConf);
1209         }
1210         IntRes2d_IntersectionPoint PtSeg2(P1,PolyUSup,PolyVSup
1211                                           ,Trans1,Trans2,Standard_False);
1212
1213               Standard_Boolean Oppos = (Tan1.Dot(Tan2) > 0.0)? Standard_False : Standard_True;
1214               if(ParamInfOnCurve1 > ParamSupOnCurve1) {
1215                 IntRes2d_IntersectionSegment Seg(PtSeg2,PtSeg1,Oppos,Standard_False);
1216                 Append(Seg);
1217               }
1218               else {
1219                 IntRes2d_IntersectionSegment Seg(PtSeg1,PtSeg2,Oppos,Standard_False);
1220                 Append(Seg);
1221               }
1222       }
1223     }
1224   }
1225  return Standard_True;
1226 }
1227
1228 //======================================================================
1229 //  GetIntersection
1230 //======================================================================
1231
1232 void GetIntersection(const TheCurve& theC1, const Standard_Real theT1f, const Standard_Real theT1l,
1233                      const TheCurve& theC2, const Standard_Real theT2f, const Standard_Real theT2l,
1234                      const Standard_Real theTolConf,
1235                      const Standard_Integer theMaxCount,
1236                      IntRes2d_IntersectionPoint& thePInt, Standard_Real& theDist,
1237                      Standard_Integer& theCount)
1238 {
1239   theCount++;
1240   //
1241   Standard_Real aTol2 = theTolConf*theTolConf;
1242   Standard_Real aPTol1 = Max(100.*Epsilon(Max(Abs(theT1f), Abs(theT1l))), Precision::PConfusion());
1243   Standard_Real aPTol2 = Max(100.*Epsilon(Max(Abs(theT2f), Abs(theT2l))), Precision::PConfusion());
1244   gp_Pnt2d aP1f, aP1l, aP2f, aP2l;
1245   Bnd_Box2d aB1, aB2;
1246   //
1247   TheCurveTool::D0(theC1, theT1f, aP1f);
1248   TheCurveTool::D0(theC1, theT1l, aP1l);
1249   aB1.Add(aP1f);
1250   aB1.Add(aP1l);
1251   aB1.Enlarge(theTolConf);
1252   //
1253   TheCurveTool::D0(theC2, theT2f, aP2f);
1254   TheCurveTool::D0(theC2, theT2l, aP2l);
1255   aB2.Add(aP2f);
1256   aB2.Add(aP2l);
1257   aB2.Enlarge(theTolConf);
1258   //
1259   if(aB1.IsOut(aB2))
1260   {
1261     theCount--;
1262     return;
1263   }
1264   //
1265   Standard_Boolean isSmall1 = (theT1l - theT1f) <= aPTol1 || aP1f.SquareDistance(aP1l) / 4. <= aTol2;
1266   Standard_Boolean isSmall2 = (theT2l - theT2f) <= aPTol2 || aP2f.SquareDistance(aP2l) / 4. <= aTol2;
1267
1268   if((isSmall1 && isSmall2) || (theCount > theMaxCount))
1269   {
1270     //Seems to be intersection
1271     //Simple treatment of segment intersection
1272     gp_XY aPnts1[3] = {aP1f.XY(), (aP1f.XY() + aP1l.XY()) / 2., aP1l.XY()};
1273     gp_XY aPnts2[3] = {aP2f.XY(), (aP2f.XY() + aP2l.XY()) / 2., aP2l.XY()};
1274     Standard_Integer i, j, imin = -1, jmin = -1;
1275     Standard_Real dmin = RealLast(), d;
1276     for(i = 0; i < 3; i++)
1277     {
1278       for(j = 0; j < 3; j++)
1279       {
1280         d = (aPnts1[i] - aPnts2[j]).SquareModulus();
1281         if(d < dmin)
1282         {
1283           dmin=d;
1284           imin = i;
1285           jmin = j;
1286         }
1287       }
1288     }
1289     //
1290     dmin = Sqrt(dmin);
1291     if(theDist > dmin)
1292     {
1293       theDist = dmin;
1294       //
1295       Standard_Real t1;
1296       if(imin == 0)
1297       {
1298         t1 = theT1f;
1299       }
1300       else if(imin == 1)
1301       {
1302         t1 = (theT1f + theT1l) / 2.;
1303       }
1304       else
1305       {
1306         t1 = theT1l;
1307       }
1308       //
1309       Standard_Real t2;
1310       if(jmin == 0)
1311       {
1312         t2 = theT2f;
1313       }
1314       else if(jmin == 1)
1315       {
1316         t2 = (theT2f + theT2l) / 2.;
1317       }
1318       else
1319       {
1320         t2 = theT2l;
1321       }
1322       //
1323       gp_Pnt2d aPint((aPnts1[imin] + aPnts2[jmin])/2.);
1324       //
1325       IntRes2d_Transition aTrans1, aTrans2;
1326       thePInt.SetValues(aPint, t1, t2, aTrans1, aTrans2, Standard_False);
1327     }
1328     theCount--;
1329     return;
1330   }
1331
1332   if(isSmall1)
1333   {
1334     Standard_Real aT2m = (theT2l + theT2f) / 2.;
1335     GetIntersection(theC1, theT1f, theT1l, theC2, theT2f, aT2m, theTolConf, theMaxCount, thePInt, theDist, theCount);
1336     GetIntersection(theC1, theT1f, theT1l, theC2, aT2m, theT2l, theTolConf, theMaxCount, thePInt, theDist, theCount);
1337   }
1338   else if(isSmall2)
1339   {
1340     Standard_Real aT1m = (theT1l + theT1f) / 2.;
1341     GetIntersection(theC1, theT1f, aT1m, theC2, theT2f, theT2l, theTolConf, theMaxCount, thePInt, theDist, theCount);
1342     GetIntersection(theC1, aT1m, theT1l, theC2, theT2f, theT2l, theTolConf, theMaxCount, thePInt, theDist, theCount);
1343   }
1344   else
1345   {
1346     Standard_Real aT1m = (theT1l + theT1f) / 2.;
1347     Standard_Real aT2m = (theT2l + theT2f) / 2.;
1348     GetIntersection(theC1, theT1f, aT1m, theC2, theT2f, aT2m, theTolConf, theMaxCount, thePInt, theDist, theCount);
1349     GetIntersection(theC1, theT1f, aT1m, theC2, aT2m, theT2l, theTolConf, theMaxCount, thePInt, theDist, theCount);
1350     GetIntersection(theC1, aT1m, theT1l, theC2, theT2f, aT2m, theTolConf, theMaxCount, thePInt, theDist, theCount);
1351     GetIntersection(theC1, aT1m, theT1l, theC2, aT2m, theT2l, theTolConf, theMaxCount, thePInt, theDist, theCount);
1352   }
1353
1354 }
1355
1356 //=======================================================================
1357 //function : GetMinNbPoints
1358 //purpose  :
1359 //=======================================================================
1360 Standard_Integer IntCurve_IntPolyPolyGen::GetMinNbSamples() const
1361 {
1362   return myMinPntNb;
1363 }
1364
1365 //=======================================================================
1366 //function : SetMinNbPoints
1367 //purpose  :
1368 //=======================================================================
1369 void IntCurve_IntPolyPolyGen::SetMinNbSamples(const Standard_Integer theMinNbSamples)
1370 {
1371   myMinPntNb = theMinNbSamples;
1372 }