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