src/IntWalk/IntWalk_IWalking_2.gxx

   1 // Copyright (c) 1995-1999 Matra Datavision
   2 // Copyright (c) 1999-2014 OPEN CASCADE SAS
   3 //
   4 // This file is part of Open CASCADE Technology software library.
   5 //
   6 // This library is free software; you can redistribute it and/or modify it under
   7 // the terms of the GNU Lesser General Public License version 2.1 as published
   8 // by the Free Software Foundation, with special exception defined in the file
   9 // OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT
  10 // distribution for complete text of the license and disclaimer of any warranty.
  11 //
  12 // Alternatively, this file may be used under the terms of Open CASCADE
  13 // commercial license or contractual agreement.
  14
  15 //-- IntWalk_IWalking_2.gxx
  16
  17 #include <Bnd_Range.hxx>
  18 #include <TColStd_MapOfInteger.hxx>
  19
  20 #ifndef OCCT_DEBUG
  21 #define No_Standard_RangeError
  22 #define No_Standard_OutOfRange
  23 #endif
  24
  25 static void CutVectorByTolerances (gp_Vec2d&          theVector,
  26                                    const math_Vector& theTolerance)
  27 {
  28   if (Abs(theVector.X()) < theTolerance(1))
  29     theVector.SetX (0.);
  30   if (Abs(theVector.Y()) < theTolerance(2))
  31     theVector.SetY (0.);
  32 }
  33
  34 // _______________________________________________
  35 //
  36 // Location of point (u, v) in the natural domain of a surface AND update
  37 // of couple (u, v) for the calculation of the next point.
  38 //
  39 Standard_Boolean IntWalk_IWalking::Cadrage
  40   (math_Vector& BornInf,
  41    math_Vector& BornSup,
  42    math_Vector& UVap,
  43    Standard_Real& Step,
  44 //   Standard_Real& StepV,
  45    const Standard_Integer StepSign) const
  46
  47 // there are always :
  48 // BorInf(1) <= UVap(1) <= BornSup(1) et BorInf(2) <= UVap(2) <= BornSup(2)
  49 // 1) check if the process point is out of the natural domain of the surface.
  50 // 2) if yes the approximated point is located on border taking the best direction
  51 // the step and a limit blocating one of the parameters during the recent call of
  52 // FunctionSetRoot are modified;
  53 // 3) couple (u, v) is recomputed by approximation for the calculation of the next point.
  54 // 4) return Standard_True if location, Standard_False if no location.
  55 {
  56   Standard_Real Duvx = previousd2d.X();
  57   Standard_Real Duvy = previousd2d.Y();
  58
  59   if (!reversed) {
  60     previousPoint.ParametersOnS2(UVap(1),UVap(2));
  61   }
  62   else {
  63     previousPoint.ParametersOnS1(UVap(1),UVap(2));
  64   }
  65
  66   Standard_Real U1 = UVap(1) + Step * Duvx * StepSign;
  67   Standard_Real V1 = UVap(2) + Step * Duvy * StepSign;
  68
  69
  70   Standard_Boolean infu = (U1 <= BornInf(1)+Precision::PConfusion());
  71   Standard_Boolean supu = (U1 >= BornSup(1)-Precision::PConfusion());
  72   Standard_Boolean infv = (V1 <= BornInf(2)+Precision::PConfusion());
  73   Standard_Boolean supv = (V1 >= BornSup(2)-Precision::PConfusion());
  74
  75   Standard_Real theStepU,theStepV;
  76
  77   if (!infu && !supu && !infv && !supv) {
  78     UVap(1) = U1;
  79     UVap(2) = V1;
  80     return Standard_False;
  81   }
  82
  83   if ((infu || supu) && (infv || supv)) {
  84     if (infu) { // jag 940616
  85       if(Duvx) {
  86         theStepU = Abs((BornInf(1) - UVap(1)) / Duvx);  // iso U =BornInf(1)
  87       }
  88       else {
  89         theStepU = Step;
  90       }
  91     }
  92     else {
  93       if(Duvx) {
  94         theStepU = Abs((BornSup(1) - UVap(1)) / Duvx);  // iso U =BornSup(1)
  95       }
  96       else {
  97         theStepU = Step;
  98       }
  99     }
 100     if (infv) { // jag 940616
 101       if(Duvy) {
 102         theStepV = Abs((BornInf(2) - UVap(2)) / Duvy);  // iso V =BornInf(2)
 103       }
 104       else {
 105         theStepV = Step;
 106       }
 107     }
 108     else {
 109       if(Duvy) {
 110         theStepV = Abs((BornSup(2) - UVap(2)) / Duvy);  // iso V =BornSup(2)
 111       }
 112       else {
 113         theStepV = Step;
 114       }
 115     }
 116
 117
 118     if (theStepU <= theStepV) {
 119       Step = theStepU;
 120       if (infu) {
 121         UVap(1) = BornInf(1);
 122         BornSup(1) = BornInf(1);
 123       }
 124       else {
 125         UVap(1) = BornSup(1);
 126         BornInf(1) = BornSup(1);
 127       }
 128       UVap(2) += Step*Duvy*StepSign;
 129     }
 130     else {
 131       Step = theStepV;
 132       if (infv) {
 133         UVap(2) = BornInf(2);
 134         BornSup(2) = BornInf(2);
 135       }
 136       else {
 137         UVap(2) = BornSup(2);
 138         BornInf(2) = BornSup(2);
 139       }
 140       UVap(1) += Step*Duvx*StepSign;
 141     }
 142     return Standard_True;
 143   }
 144
 145   else if (infu) { // jag 940616
 146     if(Duvx) {
 147       Standard_Real aStep = Abs((BornInf(1) - UVap(1)) / Duvx);  // iso U =BornInf(1)
 148       if(aStep<Step) Step=aStep;
 149     }
 150     BornSup(1) = BornInf(1);                     // limit the parameter
 151     UVap(1) = BornInf(1);
 152     UVap(2) += Step*Duvy*StepSign;
 153     return Standard_True;
 154   }
 155   else if (supu) { // jag 940616
 156     if(Duvx) {
 157       Standard_Real aStep = Abs((BornSup(1) - UVap(1)) / Duvx);  // iso U =BornSup(1)
 158       if(aStep<Step) Step=aStep;
 159     }
 160     BornInf(1) = BornSup(1);                    // limit the parameter
 161     UVap(1) = BornSup(1);
 162     UVap(2) += Step*Duvy*StepSign;
 163     return Standard_True;
 164   }
 165   else if (infv) { // jag 940616
 166     if(Duvy) {
 167       Standard_Real aStep = Abs((BornInf(2) - UVap(2)) / Duvy);  // iso V =BornInf(2)
 168       if(aStep<Step) Step=aStep;
 169     }
 170     BornSup(2) = BornInf(2);
 171     UVap(1) += Step*Duvx*StepSign;
 172     UVap(2) = BornInf(2);
 173     return Standard_True;
 174   }
 175   else if (supv) { // jag 940616
 176     if(Duvy) {
 177       Standard_Real aStep = Abs((BornSup(2) - UVap(2)) / Duvy);  // iso V =BornSup(2)
 178       if(aStep<Step) Step=aStep;
 179     }
 180     BornInf(2) = BornSup(2);
 181     UVap(1) += Step*Duvx*StepSign;
 182     UVap(2) = BornSup(2);
 183     return Standard_True;
 184   }
 185   return Standard_True;
 186 }
 187
 188
 189 Standard_Boolean IntWalk_IWalking::TestArretPassage
 190   (const TColStd_SequenceOfReal& Umult,
 191    const TColStd_SequenceOfReal& Vmult,
 192    TheIWFunction& sp,
 193    math_Vector& UV,
 194    Standard_Integer& Irang)
 195
 196 // Umult et Vmult : table of stop (or crossing) points on border,
 197 //         here only the crossing points are taken into account.
 198 // UV     : the current point.
 199 // Irang  : at exit : give index of the stop point in uvstart1 or 0.
 200 //          consider that there is no risk of crossing only if there is one crossing point.
 201
 202
 203 // test of stop for an OPEN intersection line
 204 // 1) crossing test on all interior points
 205 // 2) stop test on all start points
 206 // if a stop is detected, the index of the stop point (Irang) is returned
 207 // in the iterator of start points and the associated parameters in UV space.
 208 {
 209   Standard_Real Up, Vp, Du, Dv, Dup, Dvp, Utest,Vtest;
 210   Standard_Integer j, N, ind;
 211   Standard_Real tolu = tolerance(1);
 212   Standard_Real tolv = tolerance(2);
 213   Standard_Real tolu2 = 10.*tolerance(1);
 214   Standard_Real tolv2 = 10.*tolerance(2);
 215
 216   Standard_Boolean Arrive = Standard_False;
 217
 218   // crossing test  on point that can start a loop; mark
 219   // as processed if passes through an open line
 220
 221   if (!reversed) {
 222     previousPoint.ParametersOnS2(Up,Vp);
 223   }
 224   else {
 225     previousPoint.ParametersOnS1(Up,Vp);
 226   }
 227
 228   for (size_t i = 1; i < wd2.size(); i++) {
 229     if (wd2[i].etat > 0) {
 230       // debug jag 05.04.94
 231
 232 //      if ((Up-wd2[i].ustart)*(UV(1)-wd2[i].ustart) +
 233 //        (Vp-wd2[i].vstart)*(UV(2)-wd2[i].vstart) <= 0)
 234       Utest = wd2[i].ustart;
 235       Vtest = wd2[i].vstart;
 236
 237       Du  = UV(1)-Utest;
 238       Dv  = UV(2)-Vtest;
 239       Dup = Up - Utest;
 240       Dvp = Vp - Vtest;
 241
 242 //-- lbr le 30 oct 97
 243
 244       //IFV for OCC20285
 245
 246       if ((Abs(Du) < tolu2 && Abs(Dv) < tolv2) ||
 247           (Abs(Dup) < tolu2 && Abs(Dvp) < tolv2)) {
 248
 249         wd2[i].etat = -wd2[i].etat;
 250       }
 251       else {
 252         Standard_Real DDu = (UV(1)-Up);
 253         Standard_Real DDv = (UV(2)-Vp);
 254         Standard_Real DDD = DDu*DDu+DDv*DDv;
 255         Standard_Real DD1 = Du*Du+Dv*Dv;
 256         if(DD1<=DDD) {
 257           Standard_Real DD2 = Dup*Dup+Dvp*Dvp;
 258           if(DD2<=DDD && ((Du*Dup) + (Dv*Dvp*tolu/tolv) <= 0.)) {
 259             wd2[i].etat = -wd2[i].etat;
 260           }
 261         }
 262       }
 263     }
 264   }
 265
 266   // stop test on point given at input and not yet processed
 267
 268 //  Modified by Sergey KHROMOV - Tue Nov 20 10:55:01 2001 Begin
 269 // Check of all path points in the following order:
 270 //   * First check all not treated points;
 271 //   * After that check of already treated ones.
 272   Standard_Integer l;
 273
 274   //// Modified by jgv, 28.07.2010 for OCC21914 ////
 275   // There are several path points between (Up,Vp) and UV
 276   // So several path points satisfy the condition
 277   // Dup*UV1mUtest + Dvp*UV2mVtest) < 0
 278   // We choose from them the path point with
 279   // minimum distance to (Up,Vp)
 280   TColStd_SequenceOfInteger i_candidates;
 281   TColStd_SequenceOfReal    SqDist_candidates;
 282
 283   for (l = 1; l <= 2 && !Arrive; l++) {
 284     Standard_Boolean isToCheck;
 285
 286     for (size_t i = 1; i < wd1.size(); i++) {
 287       if (l == 1)
 288         isToCheck = (wd1[i].etat > 0);
 289       else
 290         isToCheck = (wd1[i].etat < 0);
 291
 292       if (isToCheck) {
 293 //  Modified by Sergey KHROMOV - Tue Nov 20 11:03:16 2001 End
 294
 295         // debug jag voir avec isg
 296
 297         Utest = wd1[i].ustart;
 298         Vtest = wd1[i].vstart;
 299         Dup = Up - Utest;
 300         Dvp = Vp - Vtest;
 301         if (Abs(Dup) >= tolu || Abs(Dvp) >= tolv) {
 302           Standard_Real UV1mUtest = UV(1)-Utest;
 303           Standard_Real UV2mVtest = UV(2)-Vtest;
 304           if(( (Dup*UV1mUtest + Dvp*UV2mVtest) < 0) ||
 305              (   Abs(UV1mUtest) < tolu
 306               && Abs(UV2mVtest) < tolv)) {
 307             i_candidates.Append((Standard_Integer)i);
 308             SqDist_candidates.Append(Dup*Dup + Dvp*Dvp);
 309             /*
 310             Irang=i;
 311             Arrive = Standard_True;
 312             UV(1) = Utest;
 313             UV(2) = Vtest;
 314             */
 315           }
 316           else if (nbMultiplicities[i] > 0 && i_candidates.IsEmpty()) {
 317             N=0;
 318             for (size_t k = 1; k < i; k++) {
 319               N+=nbMultiplicities[k];
 320             }
 321             for (j = N + 1; j <= N + nbMultiplicities[i]; j++) {
 322               if (((Up-Umult(j))*(UV(1)-Umult(j)) +
 323                    (Vp-Vmult(j))*(UV(2)-Vmult(j)) < 0) ||
 324                   (Abs(UV(1)-Umult(j)) < tolu &&
 325                    Abs(UV(2)-Vmult(j)) < tolv)) {
 326                 Irang=(Standard_Integer)i;
 327                 Arrive = Standard_True;
 328                 UV(1) = Utest;
 329                 UV(2) = Vtest;
 330                 break;
 331               }
 332             }
 333           }
 334           if (Arrive) {
 335             Standard_Real abidF[1], abidD[1][2];
 336             math_Vector bidF(abidF,1,1);
 337             math_Matrix bidD(abidD,1,1,1,2);
 338         sp.Values(UV,bidF,bidD);
 339             break;
 340           }
 341         }
 342       }
 343     } //end of for (i = 1; i < wd1.size(); i++)
 344     if (!i_candidates.IsEmpty())
 345       {
 346         Standard_Real MinSqDist = RealLast();
 347         for (ind = 1; ind <= i_candidates.Length(); ind++)
 348           if (SqDist_candidates(ind) < MinSqDist)
 349             {
 350               MinSqDist = SqDist_candidates(ind);
 351               Irang = i_candidates(ind);
 352             }
 353         Arrive = Standard_True;
 354         UV(1) = wd1[Irang].ustart;
 355         UV(2) = wd1[Irang].vstart;
 356       }
 357   } //end of for (l = 1; l <= 2 && !Arrive; l++)
 358   return  Arrive;
 359 }
 360
 361 Standard_Boolean IntWalk_IWalking::TestArretPassage
 362   (const TColStd_SequenceOfReal& Umult,
 363    const TColStd_SequenceOfReal& Vmult,
 364    const math_Vector& UV,
 365    const Standard_Integer Index,
 366    Standard_Integer& Irang)
 367 {
 368 // Umult, Vmult : table of stop (or crossing) points on border, here
 369 //          only crossing points are taken into account.
 370 // UV     : the current point.
 371 // Index  : index of the start point in uvstart2 of the current line
 372 //          (this is an interior point).
 373 // Irang  : at output : gives the index of the point passing in uvstart1 or 0.
 374 //          consider that there is risk to cross only one crossing point.
 375
 376 // test of stop for a CLOSED intersection line.
 377 // 1) test of crossing on all interior points.
 378 // 2) test of crossing on all crossing points.
 379
 380   Standard_Real Up, Vp, Scal;
 381   Standard_Boolean Arrive = Standard_False;
 382   Standard_Integer N, k, i;
 383   Standard_Real Utest,Vtest;
 384   Standard_Real tolu = tolerance(1);
 385   Standard_Real tolv = tolerance(2);
 386
 387
 388   // tests of stop and of crossing on all interior points.
 389
 390   if (!reversed) {
 391     previousPoint.ParametersOnS2(Up,Vp);
 392   }
 393   else {
 394     previousPoint.ParametersOnS1(Up,Vp);
 395   }
 396
 397   Standard_Real UV1=UV(1);
 398   Standard_Real UV2=UV(2);
 399
 400
 401   //Normalizing factor. If it is less than 1.0 then the range will be expanded.
 402   //This is no good for computation. Therefore, it is limited.
 403   //Do not limit this factor in case of highly anisotropic parametrization
 404   //(parametric space is considerably larger in one direction than another).
 405   const Standard_Boolean isHighlyAnisotropic = Max(tolu, tolv) > 1000. * Min(tolu, tolv);
 406   const Standard_Real deltau = mySRangeU.IsVoid() ? UM - Um
 407                                                   : (isHighlyAnisotropic ? mySRangeU.Delta()
 408                                                                          : Max(mySRangeU.Delta(), 1.0));
 409   const Standard_Real deltav = mySRangeV.IsVoid() ? VM - Vm
 410                                                   : (isHighlyAnisotropic ? mySRangeV.Delta()
 411                                                                          : Max(mySRangeV.Delta(), 1.0));
 412
 413   Up/=deltau; UV1/=deltau;
 414   Vp/=deltav; UV2/=deltav;
 415
 416   tolu/=deltau;
 417   tolv/=deltav;
 418
 419   Standard_Real tolu2=tolu+tolu;
 420   Standard_Real tolv2=tolv+tolv;
 421
 422
 423   Standard_Real dPreviousCurrent = (Up-UV1)*(Up-UV1)+(Vp-UV2)*(Vp-UV2);
 424   for (k = 1; k < (int)wd2.size(); k++) {
 425     if (wd2[k].etat > 0) {
 426       Utest = wd2[k].ustart;
 427       Vtest = wd2[k].vstart;
 428
 429       Utest/=deltau;
 430       Vtest/=deltav;
 431
 432       Standard_Real UV1mUtest=UV1-Utest;
 433       Standard_Real UV2mVtest=UV2-Vtest;
 434       if(   (UV1mUtest<tolu2 && UV1mUtest>-tolu2)
 435          && (UV2mVtest<tolv2 && UV2mVtest>-tolv2)) {
 436         if(Index!=k) {
 437           //-- cout<<"* etat2 : ("<<k<<")"<<endl;
 438           wd2[k].etat=-wd2[k].etat; //-- mark the point as a crossing point
 439         }
 440         else {  //-- Index == k
 441           //-- cout<<"* Arrive"<<endl;
 442           Arrive=Standard_True;
 443         }
 444       }
 445       else {
 446         Standard_Real UpmUtest = (Up-Utest);
 447         Standard_Real VpmVtest = (Vp-Vtest);
 448         Standard_Real dPreviousStart = (UpmUtest)*(UpmUtest)+(VpmVtest)*(VpmVtest);
 449         Standard_Real dCurrentStart  = UV1mUtest * UV1mUtest + UV2mVtest * UV2mVtest;
 450
 451         Scal=(UpmUtest)*(UV1mUtest)+(VpmVtest)*(UV2mVtest);
 452         if( (Abs(UpmUtest)<tolu && Abs(VpmVtest)<tolv)) {
 453           if(Index != k ) {
 454             //-- cout<<"** etat2 : ("<<k<<")"<<endl;
 455             wd2[k].etat = -wd2[k].etat;
 456           }
 457         }
 458         else if(Scal<0 && (dPreviousStart+dCurrentStart < dPreviousCurrent)) {
 459           if (Index == k ) { // on a boucle.
 460             Arrive = Standard_True;
 461             //-- cout<<"** Arrive  : k="<<k<<endl;
 462           }
 463           else {
 464             //-- cout<<"*** etat2 : ("<<k<<")"<<endl;
 465             wd2[k].etat = -wd2[k].etat; // mark the point as a crossing point
 466           }
 467         }
 468         else if(k!=Index) {
 469           if(dPreviousStart < dPreviousCurrent*0.25) {
 470             wd2[k].etat = -wd2[k].etat; // mark the point as a crossing point
 471             //-- cout<<"**** etat2 : ("<<k<<")"<<endl;
 472           }
 473           else {
 474             if(dCurrentStart < dPreviousCurrent*0.25) {
 475               //-- cout<<"***** etat2 : ("<<k<<")"<<endl;
 476               wd2[k].etat = -wd2[k].etat; // mark the point as a crossing point
 477             }
 478             else {
 479               Standard_Real UMidUtest = 0.5*(UV1+Up)-Utest;
 480               Standard_Real VMidVtest = 0.5*(UV2+Vp)-Vtest;
 481               Standard_Real dMiddleStart =  UMidUtest* UMidUtest+VMidVtest*VMidVtest;
 482
 483               if(dMiddleStart < dPreviousCurrent*0.5) {
 484                 //-- cout<<"*********** etat2 : ("<<k<<")"<<endl;
 485                 wd2[k].etat = -wd2[k].etat; // mark the point as a crossing point
 486               }
 487             }
 488           }
 489         }
 490       }
 491     }
 492   }
 493
 494   // crossing test on crossing points.
 495
 496   Irang =0;
 497   for (i = 1; i < (int)wd1.size(); i++) {
 498     if (wd1[i].etat > 0 && wd1[i].etat < 11) { //test of crossing points
 499       Utest = wd1[i].ustart;
 500       Vtest = wd1[i].vstart;
 501       Utest/=deltau;
 502       Vtest/=deltav;
 503
 504       if (((Up-Utest) * (UV1-Utest) + (Vp-Vtest) * (UV2-Vtest) < 0) ||
 505           (Abs(UV1-Utest) < tolu &&  Abs(UV2-Vtest) < tolv))
 506         Irang = i;
 507       else if (nbMultiplicities[i] > 0) {
 508         N=0;
 509         for (k = 1; k < i; k++) N = N + nbMultiplicities[k];
 510         for (Standard_Integer j = N + 1; j <= N + nbMultiplicities[i]; j++) {
 511           Standard_Real Umultj = Umult(j)/deltau;
 512           Standard_Real Vmultj = Vmult(j)/deltav;
 513           if (((Up-Umultj)*(UV1-Umultj) +
 514                (Vp-Vmultj)*(UV2-Vmultj) < 0) ||
 515               (Abs(UV1-Umultj) < tolu &&
 516                Abs(UV2-Vmultj) < tolv)) {
 517             Irang=i;
 518             break;
 519           }
 520         }
 521       }
 522     }
 523   }
 524   return Arrive;
 525 }
 526
 527
 528 Standard_Boolean IntWalk_IWalking::TestArretAjout
 529   (TheIWFunction& sp,
 530    math_Vector& UV,
 531    Standard_Integer& Irang,
 532    IntSurf_PntOn2S& Psol)
 533
 534 // test of stop on added points
 535 // these are the points on the natural biorder that were not given at input
 536 // return : Psol,  the added point.
 537 //          Irang, index in the iterator of added points.
 538 //          UV,    parameter of the added point.
 539 //
 540 {
 541   Standard_Boolean Arrive = Standard_False;
 542   Standard_Real U1,V1;
 543   Standard_Real Up,Vp;
 544
 545   if (!reversed) {
 546     previousPoint.ParametersOnS2(Up,Vp);
 547   }
 548   else {
 549     previousPoint.ParametersOnS1(Up,Vp);
 550   }
 551
 552   Standard_Integer nbAjout = seqAjout.Length();
 553   for (Standard_Integer i = 1; i <= nbAjout; i++) {
 554     Irang = seqAjout.Value(i);
 555
 556 // add test Abs(Irang) <= lines.Length() for the case when
 557 // a closed line is opened by adding a  1 point on this same
 558 // line. Anyway there is a huge problem as 2 points will be
 559 // added on this line...
 560
 561     if (Abs(Irang) <= lines.Length()) {
 562
 563       const Handle(IntWalk_TheIWLine)& Line = lines.Value(Abs(Irang));
 564       if (Irang>0)
 565         Psol = Line->Value(Line->NbPoints());
 566       else
 567         Psol = Line->Value(1);
 568       if (!reversed) {
 569         Psol.ParametersOnS2(U1, V1);
 570       }
 571       else {
 572         Psol.ParametersOnS1(U1, V1);
 573       }
 574       if (((Up-U1) * (UV(1)-U1) +
 575            (Vp-V1) * (UV(2)-V1)) < 0 ||
 576           (Abs(UV(1)-U1) < tolerance(1) &&
 577            Abs(UV(2)-V1) < tolerance(2))) {
 578 //jag 940615    Irang= -Abs(Irang);
 579         Arrive = Standard_True;
 580         UV(1) = U1;
 581         UV(2) = V1;
 582         Standard_Real abidF[1], abidD[1][2];
 583         math_Vector bidF(abidF,1,1);
 584         math_Matrix bidD(abidD,1,1,1,2);
 585     sp.Values(UV,bidF,bidD);
 586         break;
 587       }
 588     }
 589   }
 590   return Arrive;
 591 }
 592
 593 void IntWalk_IWalking::FillPntsInHoles(TheIWFunction& sp,
 594                                        TColStd_SequenceOfInteger& CopySeqAlone,
 595                                        IntSurf_SequenceOfInteriorPoint& PntsInHoles)
 596 {
 597   math_Vector BornInf(1,2), BornSup(1,2);
 598   BornInf(1) = Um;
 599   BornSup(1) = UM;
 600   BornInf(2) = Vm;
 601   BornSup(2) = VM;
 602   PointLineLine.Clear();
 603   TColStd_SequenceOfInteger SeqToRemove;
 604   TColStd_MapOfInteger BadSolutions;
 605
 606   for (Standard_Integer i = 1; i < CopySeqAlone.Length(); i++)
 607   {
 608     Standard_Integer Irang1 = CopySeqAlone(i);
 609     if (Irang1 == 0)
 610       continue;
 611     Standard_Boolean ToRemove = Standard_False;
 612     IntSurf_PntOn2S PointAlone1, PointAlone2;
 613     const Handle(IntWalk_TheIWLine)& Line1 = lines.Value(Abs(Irang1));
 614     if (Irang1 > 0)
 615       PointAlone1 = Line1->Value(Line1->NbPoints());
 616     else
 617       PointAlone1 = Line1->Value(1);
 618     gp_Pnt2d P2d1 = PointAlone1.ValueOnSurface(reversed), P2d2;
 619     Standard_Real MinSqDist = RealLast();
 620     Standard_Integer MinRang = 0, MinIndex = 0;
 621     for (Standard_Integer j = i+1; j <= CopySeqAlone.Length(); j++)
 622     {
 623       Standard_Integer Irang2 = CopySeqAlone(j);
 624       if (Irang2 == 0 ||
 625           BadSolutions.Contains(Irang2))
 626         continue;
 627       const Handle(IntWalk_TheIWLine)& Line2 = lines.Value(Abs(Irang2));
 628       if (Irang2 > 0)
 629         PointAlone2 = Line2->Value(Line2->NbPoints());
 630       else
 631         PointAlone2 = Line2->Value(1);
 632       P2d2 = PointAlone2.ValueOnSurface(reversed);
 633       Standard_Real aSqDist = P2d1.SquareDistance(P2d2);
 634       if (aSqDist < MinSqDist)
 635       {
 636         MinSqDist = aSqDist;
 637         MinRang = Irang2;
 638         MinIndex = j;
 639       }
 640     }
 641     //processing points from Irang1 and MinRang
 642     if (MinRang == 0)
 643     {
 644       SeqToRemove.Append(Irang1);
 645       BadSolutions.Clear();
 646       continue;
 647     }
 648     //Ends of same line
 649     if (Abs(Irang1) == Abs(MinRang) &&
 650         lines.Value(Abs(Irang1))->NbPoints() == 2)
 651     {
 652       SeqToRemove.Append(Irang1);
 653       SeqToRemove.Append(MinRang);
 654       CopySeqAlone(i) = 0;
 655       CopySeqAlone(MinIndex) = 0;
 656       BadSolutions.Clear();
 657       continue;
 658     }
 659     ///////////////////
 660     const Handle(IntWalk_TheIWLine)& Line2 = lines.Value(Abs(MinRang));
 661     if (MinRang > 0)
 662       PointAlone2 = Line2->Value(Line2->NbPoints());
 663     else
 664       PointAlone2 = Line2->Value(1);
 665     gp_Pnt Pnt1 = PointAlone1.Value();
 666     gp_Pnt Pnt2 = PointAlone2.Value();
 667     P2d2 = PointAlone2.ValueOnSurface(reversed);
 668     Standard_Real MinSqDist3d = Pnt1.SquareDistance(Pnt2);
 669     if (MinSqDist3d <= epsilon ||
 670         (Abs(P2d1.X() - P2d2.X()) <= tolerance(1) &&
 671          Abs(P2d1.Y() - P2d2.Y()) <= tolerance(2))) //close points
 672       ToRemove = Standard_True;
 673     else //real curve
 674     {
 675       math_Vector UVap(1,2), UV(1,2);
 676       UVap(1) = (P2d1.X() + P2d2.X())/2;
 677       UVap(2) = (P2d1.Y() + P2d2.Y())/2;
 678       math_FunctionSetRoot Rsnld(sp, tolerance);
 679       Rsnld.Perform(sp, UVap, BornInf, BornSup);
 680       if (Rsnld.IsDone() &&
 681           Abs(sp.Root()) <= sp.Tolerance() &&
 682           !sp.IsTangent())
 683       {
 684         Rsnld.Root(UV);
 685         gp_Pnt2d Pmid(UV(1),UV(2));
 686         gp_Vec2d P1P2(P2d1, P2d2);
 687         gp_Vec2d P1Pmid(P2d1, Pmid);
 688         gp_Vec2d P2Pmid(P2d2, Pmid);
 689         Standard_Real ScalProd1 = P1P2 * P1Pmid;
 690         Standard_Real ScalProd2 = P1P2 * P2Pmid;
 691         Standard_Boolean IsPmidValid = (ScalProd1 > 0. && ScalProd2 < 0); //Pmid is in the middle
 692         if (IsPmidValid)
 693         {
 694           for (Standard_Integer iline = 1; iline <= lines.Length(); iline++)
 695             if (IsPointOnLine(Pmid,iline))
 696             {
 697               IsPmidValid = Standard_False;
 698               break;
 699             }
 700         }
 701         if (IsPmidValid)
 702         {
 703           IntSurf_InteriorPoint aPoint(sp.Point(), UV(1), UV(2),
 704                                        sp.Direction3d(),
 705                                        sp.Direction2d());
 706           PntsInHoles.Append(aPoint);
 707           TColStd_ListOfInteger LineLine;
 708           LineLine.Append(Irang1);
 709           LineLine.Append(MinRang);
 710           PointLineLine.Bind(PntsInHoles.Length(), LineLine);
 711         }
 712         else
 713         {
 714           BadSolutions.Add(MinRang);
 715           i--;
 716           continue;
 717         }
 718       }
 719       else
 720       {
 721         BadSolutions.Add(MinRang);
 722         i--;
 723         continue;
 724       }
 725     }
 726     CopySeqAlone(i) = 0;
 727     CopySeqAlone(MinIndex) = 0;
 728     if (ToRemove)
 729     {
 730       SeqToRemove.Append(Irang1);
 731       SeqToRemove.Append(MinRang);
 732     }
 733     BadSolutions.Clear();
 734   }
 735
 736   for (Standard_Integer i = 1; i <= SeqToRemove.Length(); i++)
 737     for (Standard_Integer j = 1; j <= seqAlone.Length(); j++)
 738       if (seqAlone(j) == SeqToRemove(i))
 739       {
 740         seqAlone.Remove(j);
 741         break;
 742       }
 743 }
 744
 745 void IntWalk_IWalking::TestArretCadre
 746   (const TColStd_SequenceOfReal& Umult,
 747    const TColStd_SequenceOfReal& Vmult,
 748    const Handle(IntWalk_TheIWLine)& Line,
 749    TheIWFunction& sp,
 750    math_Vector& UV,
 751    Standard_Integer& Irang)
 752
 753 // test of stop when located on border.
 754 // tried all tests of stop and arrived.
 755 // test of stop on all given departure points already marked and on the entire current line.
 756 // This line can be shortened if the stop point is found.
 757 // Abs(Irang) = index in the iterator of departure points or 0
 758 //  if Irang <0 , it is necessary to add this point on the line (no Line->Cut)
 759 // UV = parameter of the departure point
 760 {
 761   Standard_Real Scal, Up, Vp, Uc, Vc;
 762   Standard_Integer N;
 763   Standard_Boolean Found = Standard_False;
 764
 765
 766   Irang =0;
 767   for (Standard_Integer i = 1; i < (int)wd1.size(); i++) {
 768     if (wd1[i].etat < 0) {
 769       N=0; // range in UVMult.
 770       if (nbMultiplicities[i] > 0) {
 771         for (Standard_Integer k = 1; k < i; k++)
 772           N+=nbMultiplicities[k];
 773       }
 774       if (!reversed) {
 775         Line->Value(1).ParametersOnS2(Up,Vp);
 776       }
 777       else {
 778         Line->Value(1).ParametersOnS1(Up,Vp);
 779       }
 780       Standard_Integer nbp= Line->NbPoints();
 781       for (Standard_Integer j = 2; j <= nbp; j++) {
 782         if (!reversed) {
 783           Line->Value(j).ParametersOnS2(Uc,Vc);
 784         }
 785         else {
 786           Line->Value(j).ParametersOnS1(Uc,Vc);
 787         }
 788
 789         gp_Vec2d aVec1 (Up-wd1[i].ustart, Vp-wd1[i].vstart),
 790           aVec2 (Uc-wd1[i].ustart, Vc-wd1[i].vstart);
 791         CutVectorByTolerances (aVec1, tolerance);
 792         CutVectorByTolerances (aVec2, tolerance);
 793
 794         Scal = aVec1 * aVec2;
 795
 796         // if a stop point is found: stop the line on this point.
 797         if (Scal < 0) {
 798           Line->Cut(j);  nbp= Line->NbPoints();
 799           Irang = i;
 800           UV(1) = wd1[Irang].ustart;
 801           UV(2) = wd1[Irang].vstart;
 802           Found = Standard_True;
 803         }
 804         else if (Abs(Uc-wd1[i].ustart) < tolerance(1) &&
 805                  Abs(Vc-wd1[i].vstart) < tolerance(2) ) {
 806           Line->Cut(j);  nbp= Line->NbPoints();
 807           Irang=i;
 808           UV(1) = wd1[Irang].ustart;
 809           UV(2) = wd1[Irang].vstart;
 810           Found = Standard_True;
 811         }
 812         else if (nbMultiplicities[i] > 0) {
 813           for (Standard_Integer k = N+1; k <= N + nbMultiplicities[i]; k++) {
 814
 815             aVec1.SetCoord (Up-Umult(k), Vp-Vmult(k)),
 816             aVec2.SetCoord (Uc-Umult(k), Vc-Vmult(k));
 817             CutVectorByTolerances (aVec1, tolerance);
 818             CutVectorByTolerances (aVec2, tolerance);
 819
 820             Scal = aVec1 * aVec2;
 821
 822             if (Scal < 0) {
 823               Line->Cut(j);  nbp= Line->NbPoints();
 824               Irang=i;
 825               UV(1) = wd1[Irang].ustart;
 826               UV(2) = wd1[Irang].vstart;
 827               Found = Standard_True;
 828               break;
 829             }
 830             else if (Abs(Uc-Umult(k)) < tolerance(1) &&
 831                      Abs(Vc-Vmult(k)) < tolerance(2)) {
 832               Line->Cut(j);  nbp= Line->NbPoints();
 833               Irang=i;
 834               UV(1) = wd1[Irang].ustart;
 835               UV(2) = wd1[Irang].vstart;
 836               Found = Standard_True;
 837               break;
 838             }
 839           }
 840         }
 841         if (Found) {
 842           Standard_Real abidF[1], abidD[1][2];
 843           math_Vector bidF(abidF,1,1);
 844           math_Matrix bidD(abidD,1,1,1,2);
 845       sp.Values(UV,bidF,bidD);
 846           Standard_Integer NBP =  Line->NbPoints();
 847           Standard_Integer Indextg;
 848           Line->TangentVector(Indextg);
 849           if(Indextg > NBP) {
 850             if(j>3 && j<=NBP+1) {
 851               gp_Vec Dir3d = sp.Direction3d();
 852               gp_Vec Dir3d1 = gp_Vec(Line->Value(j-2).Value(),Line->Value(j-1).Value());
 853               Standard_Real dot = Dir3d.Dot(Dir3d1);
 854               if(dot<0.0) { // Normally this Function should not be used often !!!
 855                 Dir3d.Reverse();
 856                 //-- cout<<" IntWalk_IWalking_2.gxx REVERSE "<<endl;
 857               }
 858               Line->SetTangentVector(previousd3d,j-1);
 859             }
 860 #ifdef OCCT_DEBUG
 861             else {
 862               std::cout<<" IntWalk_IWalking_2.gxx : bizarrerie 30 10 97 "<<std::endl;
 863             }
 864 #endif
 865           }
 866
 867           return;
 868         }
 869         Up = Uc;
 870         Vp = Vc;
 871       }
 872
 873       // now the last point of the line and the last calculated point are compated.
 874       // there will be no need to "Cut"
 875
 876       gp_Vec2d aVec1 (Up-wd1[i].ustart, Vp-wd1[i].vstart),
 877         aVec2 (UV(1)-wd1[i].ustart, UV(2)-wd1[i].vstart);
 878       CutVectorByTolerances (aVec1, tolerance);
 879       CutVectorByTolerances (aVec2, tolerance);
 880
 881       Scal = aVec1 * aVec2;
 882
 883       if (Scal < 0) {
 884         Irang = i;
 885         UV(1) = wd1[Irang].ustart;
 886         UV(2) = wd1[Irang].vstart;
 887         Found = Standard_True;
 888       }
 889       else if (Abs(UV(1)-wd1[i].ustart) < tolerance(1) &&
 890                Abs(UV(2)-wd1[i].vstart) < tolerance(2)) {
 891         Irang=i;
 892         UV(1) = wd1[Irang].ustart;
 893         UV(2) = wd1[Irang].vstart;
 894         Found = Standard_True;
 895       }
 896       else if (nbMultiplicities[i] > 0) {
 897         for (Standard_Integer j = N+1; j <= N+nbMultiplicities[i]; j++) {
 898
 899           aVec1.SetCoord (Up-Umult(j), Vp-Vmult(j));
 900           aVec2.SetCoord (UV(1)-Umult(j), UV(2)-Vmult(j));
 901           CutVectorByTolerances (aVec1, tolerance);
 902           CutVectorByTolerances (aVec2, tolerance);
 903
 904           Scal = aVec1 * aVec2;
 905
 906           if (Scal < 0) {
 907             Irang=i;
 908             UV(1) = wd1[Irang].ustart;
 909             UV(2) = wd1[Irang].vstart;
 910             Found = Standard_True;
 911             break;
 912           }
 913           else if (Abs(UV(1)-Umult(j)) < tolerance(1) &&
 914                    Abs(UV(2)-Vmult(j)) < tolerance(2)) {
 915             Irang=i;
 916             UV(1) = wd1[Irang].ustart;
 917             UV(2) = wd1[Irang].vstart;
 918             Found = Standard_True;
 919             break;
 920           }
 921         }
 922       }
 923       if (Found) {
 924         Irang = -Irang; // jag 941017
 925         Standard_Real abidF[1], abidD[1][2];
 926         math_Vector bidF(abidF,1,1);
 927         math_Matrix bidD(abidD,1,1,1,2);
 928     sp.Values(UV,bidF,bidD);
 929         return;
 930       }
 931     }
 932   }
 933 }
 934
 935