src/Approx/Approx_ComputeCLine.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 //  modified by Edward AGAPOV (eap) Tue Apr 2 2002 (occ265)
  16 //  -- stop cutting an interval to approximate if next decisions
  17 //  -- get worse on and on
  18
  19
  20
  21 #include <Approx_ParametrizationType.hxx>
  22 #include <AppCont_LeastSquare.hxx>
  23 #include <TColStd_Array1OfReal.hxx>
  24 #include <AppParCurves_Constraint.hxx>
  25 #include <Approx_Status.hxx>
  26 #include <Precision.hxx>
  27
  28 const static Standard_Integer MAXSEGM = 1000;
  29
  30 //=======================================================================
  31 //function : Approx_ComputeCLine
  32 //purpose  : The MultiLine <Line> will be approximated until tolerances
  33 //           will be reached.
  34 //           The approximation will be done from degreemin to degreemax
  35 //           with a cutting if the corresponding boolean is True.
  36 //=======================================================================
  37
  38 Approx_ComputeCLine::Approx_ComputeCLine
  39 (const MultiLine& Line,
  40 const Standard_Integer degreemin,
  41 const Standard_Integer degreemax,
  42 const Standard_Real Tolerance3d,
  43 const Standard_Real Tolerance2d,
  44 const Standard_Boolean cutting,
  45 const AppParCurves_Constraint FirstC,
  46 const AppParCurves_Constraint LastC)
  47 {
  48   mydegremin = degreemin;
  49   mydegremax = degreemax;
  50   mytol3d = Tolerance3d;
  51   mytol2d = Tolerance2d;
  52   mycut = cutting;
  53   myfirstC = FirstC;
  54   mylastC = LastC;
  55   myMaxSegments = MAXSEGM;
  56   myInvOrder = Standard_True;
  57   alldone = Standard_False;
  58   Perform(Line);
  59 }
  60
  61 //=======================================================================
  62 //function : Approx_ComputeCLine
  63 //purpose  : Initializes the fields of the algorithm.
  64 //=======================================================================
  65
  66 Approx_ComputeCLine::Approx_ComputeCLine
  67 (const Standard_Integer degreemin,
  68 const Standard_Integer degreemax,
  69 const Standard_Real Tolerance3d,
  70 const Standard_Real Tolerance2d,
  71 const Standard_Boolean cutting,
  72 const AppParCurves_Constraint FirstC,
  73 const AppParCurves_Constraint LastC)
  74 {
  75   alldone = Standard_False;
  76   mydegremin = degreemin;
  77   mydegremax = degreemax;
  78   mytol3d = Tolerance3d;
  79   mytol2d = Tolerance2d;
  80   mycut = cutting;
  81   myfirstC = FirstC;
  82   mylastC = LastC;
  83   myMaxSegments = MAXSEGM;
  84   myInvOrder = Standard_True;
  85 }
  86
  87 //=======================================================================
  88 //function : Perform
  89 //purpose  : runs the algorithm after having initialized the fields.
  90 //=======================================================================
  91
  92 void Approx_ComputeCLine::Perform(const MultiLine& Line)
  93 {
  94   Standard_Real UFirst, ULast;
  95   Standard_Boolean Finish = Standard_False,
  96     begin = Standard_True, Ok = Standard_False;
  97   Standard_Real thetol3d = Precision::Confusion(), thetol2d = Precision::Confusion();
  98   UFirst = Line.FirstParameter();
  99   ULast = Line.LastParameter();
 100   Standard_Real TolU = Max((ULast - UFirst)*1.e-03, Precision::Confusion());
 101   Standard_Real myfirstU = UFirst;
 102   Standard_Real mylastU = ULast;
 103   Standard_Integer aMaxSegments = 0;
 104   Standard_Integer aMaxSegments1 = myMaxSegments - 1;
 105   Standard_Integer aNbCut = 0, aNbImp = 0, aNbComp = 10;
 106
 107   if (!mycut)
 108   {
 109     alldone = Compute(Line, UFirst, ULast, thetol3d, thetol2d);
 110     if (!alldone)
 111     {
 112       tolreached = Standard_False;
 113       myfirstparam.Append(UFirst);
 114       mylastparam.Append(ULast);
 115       myMultiCurves.Append(TheMultiCurve);
 116       Tolers3d.Append(currenttol3d);
 117       Tolers2d.Append(currenttol2d);
 118     }
 119   }
 120   else
 121   {
 122
 123     // previous decision to be taken if we get worse with next cut (eap)
 124     AppParCurves_MultiCurve KeptMultiCurve;
 125     Standard_Real KeptUfirst = 0., KeptUlast = 0., KeptT3d = RealLast(), KeptT2d = 0.;
 126
 127     while (!Finish)
 128     {
 129
 130       // Gestion du decoupage de la multiline pour approximer:
 131       if (!begin)
 132       {
 133         if (Ok)
 134         {
 135           // Calcul de la partie a approximer.
 136           myfirstU = mylastU;
 137           mylastU = ULast;
 138           aNbCut = 0;
 139           aNbImp = 0;
 140           if (Abs(ULast - myfirstU) <= RealEpsilon()
 141               || aMaxSegments >= myMaxSegments)
 142           {
 143             Finish = Standard_True;
 144             alldone = Standard_True;
 145             return;
 146           }
 147           KeptT3d = RealLast(); KeptT2d = 0;
 148           KeptUfirst = myfirstU;
 149           KeptUlast = mylastU;
 150         }
 151         else
 152         {
 153           // keep best decison
 154           if ((thetol3d + thetol2d) < (KeptT3d + KeptT2d))
 155           {
 156             KeptMultiCurve = TheMultiCurve;
 157             KeptUfirst = myfirstU;
 158             KeptUlast = mylastU;
 159             KeptT3d = thetol3d;
 160             KeptT2d = thetol2d;
 161             aNbImp++;
 162           }
 163
 164           // cut an interval
 165           mylastU = (myfirstU + mylastU) / 2;
 166           aNbCut++;
 167         }
 168       }
 169
 170       // Calcul des parametres sur ce nouvel intervalle.
 171       Ok = Compute(Line, myfirstU, mylastU, thetol3d, thetol2d);
 172       if (Ok)
 173       {
 174         aMaxSegments++;
 175       }
 176
 177       //cout << myfirstU << " - " << mylastU << "  tol : " << thetol3d << " " << thetol2d << endl;
 178       Standard_Boolean aStopCutting = Standard_False;
 179       if (aNbCut >= aNbComp)
 180       {
 181         if (aNbCut > aNbImp + 1)
 182         {
 183           aStopCutting = Standard_True;
 184         }
 185         aNbCut = 0;
 186         aNbImp = 0;
 187       }
 188       // is new decision better?
 189       if (!Ok && (Abs(myfirstU - mylastU) <= TolU || aMaxSegments >= aMaxSegments1 || aStopCutting ))
 190       {
 191         Ok = Standard_True; // stop interval cutting, approx the rest part
 192
 193         if ((thetol3d + thetol2d) < (KeptT3d + KeptT2d))
 194         {
 195           KeptMultiCurve = TheMultiCurve;
 196           KeptUfirst = myfirstU;
 197           KeptUlast = mylastU;
 198           KeptT3d = thetol3d;
 199           KeptT2d = thetol2d;
 200         }
 201
 202         mylastU = KeptUlast;
 203
 204         tolreached = Standard_False; // helas
 205         myMultiCurves.Append(KeptMultiCurve);
 206         aMaxSegments++;
 207         Tolers3d.Append(KeptT3d);
 208         Tolers2d.Append(KeptT2d);
 209         myfirstparam.Append(KeptUfirst);
 210         mylastparam.Append(KeptUlast);
 211       }
 212
 213       begin = Standard_False;
 214     } // while (!Finish)
 215   }
 216 }
 217
 218 //=======================================================================
 219 //function : NbMultiCurves
 220 //purpose  : Returns the number of MultiCurve doing the approximation
 221 //           of the MultiLine.
 222 //=======================================================================
 223
 224 Standard_Integer Approx_ComputeCLine::NbMultiCurves()const
 225 {
 226   return myMultiCurves.Length();
 227 }
 228
 229 //=======================================================================
 230 //function : Value
 231 //purpose  : returns the approximation MultiCurve of range <Index>.
 232 //=======================================================================
 233
 234 AppParCurves_MultiCurve Approx_ComputeCLine::Value(const Standard_Integer Index)
 235 const
 236 {
 237   return myMultiCurves.Value(Index);
 238 }
 239
 240 //=======================================================================
 241 //function : Compute
 242 //purpose  : is internally used by the algorithms.
 243 //=======================================================================
 244
 245 Standard_Boolean Approx_ComputeCLine::Compute(const MultiLine& Line,
 246   const Standard_Real Ufirst,
 247   const Standard_Real Ulast,
 248   Standard_Real&   TheTol3d,
 249   Standard_Real&   TheTol2d)
 250 {
 251
 252
 253   const Standard_Integer NbPointsMax = 24;
 254   const Standard_Real aMinRatio = 0.05;
 255   const Standard_Integer aMaxDeg = 8;
 256   //
 257   Standard_Integer deg, NbPoints;
 258   Standard_Boolean mydone;
 259   Standard_Real Fv;
 260
 261   AppParCurves_MultiCurve aPrevCurve;
 262   Standard_Real aPrevTol3d = RealLast(), aPrevTol2d = RealLast();
 263   Standard_Boolean aPrevIsOk = Standard_False;
 264   Standard_Boolean anInvOrder = myInvOrder;
 265   if (anInvOrder && mydegremax > aMaxDeg)
 266   {
 267     if ((Ulast - Ufirst) / (Line.LastParameter() - Line.FirstParameter()) < aMinRatio)
 268     {
 269       anInvOrder = Standard_False;
 270     }
 271   }
 272   if (anInvOrder)
 273   {
 274     for (deg = mydegremax; deg >= mydegremin; deg--) {
 275       NbPoints = Min(2 * deg + 1, NbPointsMax);
 276       AppCont_LeastSquare LSquare(Line, Ufirst, Ulast, myfirstC, mylastC, deg, NbPoints);
 277       mydone = LSquare.IsDone();
 278       if (mydone)
 279       {
 280         LSquare.Error(Fv, TheTol3d, TheTol2d);
 281         if (TheTol3d <= mytol3d && TheTol2d <= mytol2d)
 282         {
 283           if (deg == mydegremin)
 284           {
 285             // Stockage de la multicurve approximee.
 286             tolreached = Standard_True;
 287             myMultiCurves.Append(LSquare.Value());
 288             myfirstparam.Append(Ufirst);
 289             mylastparam.Append(Ulast);
 290             Tolers3d.Append(TheTol3d);
 291             Tolers2d.Append(TheTol2d);
 292             return Standard_True;
 293           }
 294           aPrevTol3d = TheTol3d;
 295           aPrevTol2d = TheTol2d;
 296           aPrevCurve = LSquare.Value();
 297           aPrevIsOk = Standard_True;
 298           continue;
 299         }
 300         else if (aPrevIsOk)
 301         {
 302           // Stockage de la multicurve approximee.
 303           tolreached = Standard_True;
 304           TheTol3d = aPrevTol3d;
 305           TheTol2d = aPrevTol2d;
 306           myMultiCurves.Append(aPrevCurve);
 307           myfirstparam.Append(Ufirst);
 308           mylastparam.Append(Ulast);
 309           Tolers3d.Append(aPrevTol3d);
 310           Tolers2d.Append(aPrevTol2d);
 311           return Standard_True;
 312         }
 313       }
 314       else if (aPrevIsOk)
 315       {
 316         // Stockage de la multicurve approximee.
 317         tolreached = Standard_True;
 318         TheTol3d = aPrevTol3d;
 319         TheTol2d = aPrevTol2d;
 320         myMultiCurves.Append(aPrevCurve);
 321         myfirstparam.Append(Ufirst);
 322         mylastparam.Append(Ulast);
 323         Tolers3d.Append(aPrevTol3d);
 324         Tolers2d.Append(aPrevTol2d);
 325         return Standard_True;
 326       }
 327       if (!aPrevIsOk && deg == mydegremax)
 328       {
 329         TheMultiCurve = LSquare.Value();
 330         currenttol3d = TheTol3d;
 331         currenttol2d = TheTol2d;
 332         aPrevTol3d = TheTol3d;
 333         aPrevTol2d = TheTol2d;
 334         aPrevCurve = TheMultiCurve;
 335         break;
 336       }
 337     }
 338   }
 339   else
 340   {
 341     for (deg = mydegremin; deg <= mydegremax; deg++) {
 342       NbPoints = Min(2 * deg + 1, NbPointsMax);
 343       AppCont_LeastSquare LSquare(Line, Ufirst, Ulast, myfirstC, mylastC, deg, NbPoints);
 344       mydone = LSquare.IsDone();
 345       if (mydone) {
 346         LSquare.Error(Fv, TheTol3d, TheTol2d);
 347         if (TheTol3d <= mytol3d && TheTol2d <= mytol2d) {
 348           // Stockage de la multicurve approximee.
 349           tolreached = Standard_True;
 350           myMultiCurves.Append(LSquare.Value());
 351           myfirstparam.Append(Ufirst);
 352           mylastparam.Append(Ulast);
 353           Tolers3d.Append(TheTol3d);
 354           Tolers2d.Append(TheTol2d);
 355           return Standard_True;
 356         }
 357       }
 358       if (deg == mydegremax) {
 359         TheMultiCurve = LSquare.Value();
 360         currenttol3d = TheTol3d;
 361         currenttol2d = TheTol2d;
 362       }
 363     }
 364   }
 365   return Standard_False;
 366 }
 367
 368 //=======================================================================
 369 //function : Parameters
 370 //purpose  : returns the first and last parameters of the
 371 //           <Index> MultiCurve.
 372 //=======================================================================
 373
 374 void Approx_ComputeCLine::Parameters(const Standard_Integer Index,
 375   Standard_Real& firstpar,
 376   Standard_Real& lastpar) const
 377 {
 378   firstpar = myfirstparam.Value(Index);
 379   lastpar = mylastparam.Value(Index);
 380 }
 381
 382 //=======================================================================
 383 //function : SetDegrees
 384 //purpose  : changes the degrees of the approximation.
 385 //=======================================================================
 386
 387 void Approx_ComputeCLine::SetDegrees(const Standard_Integer degreemin,
 388   const Standard_Integer degreemax)
 389 {
 390   mydegremin = degreemin;
 391   mydegremax = degreemax;
 392 }
 393
 394 //=======================================================================
 395 //function : SetTolerances
 396 //purpose  : Changes the tolerances of the approximation.
 397 //=======================================================================
 398
 399 void Approx_ComputeCLine::SetTolerances(const Standard_Real Tolerance3d,
 400   const Standard_Real Tolerance2d)
 401 {
 402   mytol3d = Tolerance3d;
 403   mytol2d = Tolerance2d;
 404 }
 405
 406 //=======================================================================
 407 //function : SetConstraints
 408 //purpose  : Changes the constraints of the approximation.
 409 //=======================================================================
 410
 411 void Approx_ComputeCLine::SetConstraints(const AppParCurves_Constraint FirstC,
 412   const AppParCurves_Constraint LastC)
 413 {
 414   myfirstC = FirstC;
 415   mylastC = LastC;
 416 }
 417
 418 //=======================================================================
 419 //function : SetMaxSegments
 420 //purpose  : Changes the max number of segments, which is allowed for cutting.
 421 //=======================================================================
 422
 423 void Approx_ComputeCLine::SetMaxSegments(const Standard_Integer theMaxSegments)
 424 {
 425   myMaxSegments = theMaxSegments;
 426 }
 427
 428 //=======================================================================
 429 //function : SetInvOrder
 430 //purpose  :
 431 //=======================================================================
 432 void Approx_ComputeCLine::SetInvOrder(const Standard_Boolean theInvOrder)
 433 {
 434   myInvOrder = theInvOrder;
 435 }
 436
 437 //=======================================================================
 438 //function : IsAllApproximated
 439 //purpose  : returns False if at a moment of the approximation,
 440 //           the status NoApproximation has been sent by the user
 441 //           when more points were needed.
 442 //=======================================================================
 443
 444 Standard_Boolean Approx_ComputeCLine::IsAllApproximated()
 445 const {
 446   return alldone;
 447 }
 448
 449 //=======================================================================
 450 //function : IsToleranceReached
 451 //purpose  : returns False if the status NoPointsAdded has been sent.
 452 //=======================================================================
 453
 454 Standard_Boolean Approx_ComputeCLine::IsToleranceReached()
 455 const {
 456   return tolreached;
 457 }
 458
 459 //=======================================================================
 460 //function : Error
 461 //purpose  : returns the tolerances 2d and 3d of the <Index> MultiCurve.
 462 //=======================================================================
 463
 464 void Approx_ComputeCLine::Error(const Standard_Integer Index,
 465   Standard_Real& tol3d,
 466   Standard_Real& tol2d) const
 467 {
 468   tol3d = Tolers3d.Value(Index);
 469   tol2d = Tolers2d.Value(Index);
 470 }