| 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 | } |