1 // Copyright (c) 1995-1999 Matra Datavision
2 // Copyright (c) 1999-2014 OPEN CASCADE SAS
4 // This file is part of Open CASCADE Technology software library.
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.
12 // Alternatively, this file may be used under the terms of Open CASCADE
13 // commercial license or contractual agreement.
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
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>
28 const static Standard_Integer MAXSEGM = 1000;
30 //=======================================================================
31 //function : Approx_ComputeCLine
32 //purpose : The MultiLine <Line> will be approximated until tolerances
34 // The approximation will be done from degreemin to degreemax
35 // with a cutting if the corresponding boolean is True.
36 //=======================================================================
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)
48 mydegremin = degreemin;
49 mydegremax = degreemax;
50 mytol3d = Tolerance3d;
51 mytol2d = Tolerance2d;
55 myMaxSegments = MAXSEGM;
56 myInvOrder = Standard_True;
57 myHangChecking = Standard_True;
58 alldone = Standard_False;
59 tolreached = Standard_False;
65 //=======================================================================
66 //function : Approx_ComputeCLine
67 //purpose : Initializes the fields of the algorithm.
68 //=======================================================================
70 Approx_ComputeCLine::Approx_ComputeCLine
71 (const Standard_Integer degreemin,
72 const Standard_Integer degreemax,
73 const Standard_Real Tolerance3d,
74 const Standard_Real Tolerance2d,
75 const Standard_Boolean cutting,
76 const AppParCurves_Constraint FirstC,
77 const AppParCurves_Constraint LastC)
79 alldone = Standard_False;
80 mydegremin = degreemin;
81 mydegremax = degreemax;
82 mytol3d = Tolerance3d;
83 mytol2d = Tolerance2d;
87 myMaxSegments = MAXSEGM;
88 myInvOrder = Standard_True;
89 myHangChecking = Standard_True;
90 tolreached = Standard_False;
95 //=======================================================================
97 //purpose : runs the algorithm after having initialized the fields.
98 //=======================================================================
100 void Approx_ComputeCLine::Perform(const MultiLine& Line)
102 Standard_Real UFirst, ULast;
103 Standard_Boolean Finish = Standard_False,
104 begin = Standard_True, Ok = Standard_False;
105 Standard_Real thetol3d = Precision::Confusion(), thetol2d = Precision::Confusion();
106 UFirst = Line.FirstParameter();
107 ULast = Line.LastParameter();
108 Standard_Real TolU = 0.;
111 TolU = Max((ULast - UFirst)*1.e-03, Precision::Confusion());
115 TolU = Max((ULast - UFirst)*1.e-05, Precision::PApproximation());
117 Standard_Real myfirstU = UFirst;
118 Standard_Real mylastU = ULast;
119 Standard_Integer aMaxSegments = 0;
120 Standard_Integer aMaxSegments1 = myMaxSegments - 1;
121 Standard_Integer aNbCut = 0, aNbImp = 0, aNbComp = 10;
125 alldone = Compute(Line, UFirst, ULast, thetol3d, thetol2d);
128 tolreached = Standard_False;
129 myfirstparam.Append(UFirst);
130 mylastparam.Append(ULast);
131 myMultiCurves.Append(TheMultiCurve);
132 Tolers3d.Append(currenttol3d);
133 Tolers2d.Append(currenttol2d);
139 // previous decision to be taken if we get worse with next cut (eap)
140 AppParCurves_MultiCurve KeptMultiCurve;
141 Standard_Real KeptUfirst = 0., KeptUlast = 0., KeptT3d = RealLast(), KeptT2d = 0.;
146 // Gestion du decoupage de la multiline pour approximer:
151 // Calcul de la partie a approximer.
156 if (Abs(ULast - myfirstU) <= RealEpsilon()
157 || aMaxSegments >= myMaxSegments)
159 Finish = Standard_True;
160 alldone = Standard_True;
163 KeptT3d = RealLast(); KeptT2d = 0;
164 KeptUfirst = myfirstU;
169 // keep best decision
170 if ((thetol3d + thetol2d) < (KeptT3d + KeptT2d))
172 KeptMultiCurve = TheMultiCurve;
173 KeptUfirst = myfirstU;
181 mylastU = (myfirstU + mylastU) / 2;
186 // Calcul des parametres sur ce nouvel intervalle.
187 Ok = Compute(Line, myfirstU, mylastU, thetol3d, thetol2d);
193 //cout << myfirstU << " - " << mylastU << " tol : " << thetol3d << " " << thetol2d << endl;
194 Standard_Boolean aStopCutting = Standard_False;
195 if (myHangChecking && aNbCut >= aNbComp)
197 if (aNbCut > aNbImp + 1)
199 aStopCutting = Standard_True;
204 // is new decision better?
205 if (!Ok && (Abs(myfirstU - mylastU) <= TolU || aMaxSegments >= aMaxSegments1 || aStopCutting ))
207 Ok = Standard_True; // stop interval cutting, approx the rest part
209 if ((thetol3d + thetol2d) < (KeptT3d + KeptT2d))
211 KeptMultiCurve = TheMultiCurve;
212 KeptUfirst = myfirstU;
220 tolreached = Standard_False; // helas
221 myMultiCurves.Append(KeptMultiCurve);
223 Tolers3d.Append(KeptT3d);
224 Tolers2d.Append(KeptT2d);
225 myfirstparam.Append(KeptUfirst);
226 mylastparam.Append(KeptUlast);
229 begin = Standard_False;
234 //=======================================================================
235 //function : NbMultiCurves
236 //purpose : Returns the number of MultiCurve doing the approximation
238 //=======================================================================
240 Standard_Integer Approx_ComputeCLine::NbMultiCurves()const
242 return myMultiCurves.Length();
245 //=======================================================================
247 //purpose : returns the approximation MultiCurve of range <Index>.
248 //=======================================================================
250 AppParCurves_MultiCurve Approx_ComputeCLine::Value(const Standard_Integer Index)
253 return myMultiCurves.Value(Index);
256 //=======================================================================
258 //purpose : is internally used by the algorithms.
259 //=======================================================================
261 Standard_Boolean Approx_ComputeCLine::Compute(const MultiLine& Line,
262 const Standard_Real Ufirst,
263 const Standard_Real Ulast,
264 Standard_Real& TheTol3d,
265 Standard_Real& TheTol2d)
269 const Standard_Integer NbPointsMax = 24;
270 const Standard_Real aMinRatio = 0.05;
271 const Standard_Integer aMaxDeg = 8;
273 Standard_Integer deg, NbPoints;
274 Standard_Boolean mydone;
277 AppParCurves_MultiCurve aPrevCurve;
278 Standard_Real aPrevTol3d = RealLast(), aPrevTol2d = RealLast();
279 Standard_Boolean aPrevIsOk = Standard_False;
280 Standard_Boolean anInvOrder = myInvOrder;
281 if (anInvOrder && mydegremax > aMaxDeg)
283 if ((Ulast - Ufirst) / (Line.LastParameter() - Line.FirstParameter()) < aMinRatio)
285 anInvOrder = Standard_False;
290 for (deg = mydegremax; deg >= mydegremin; deg--) {
291 NbPoints = Min(2 * deg + 1, NbPointsMax);
292 AppCont_LeastSquare LSquare(Line, Ufirst, Ulast, myfirstC, mylastC, deg, NbPoints);
293 mydone = LSquare.IsDone();
296 LSquare.Error(Fv, TheTol3d, TheTol2d);
297 if (TheTol3d <= mytol3d && TheTol2d <= mytol2d)
299 if (deg == mydegremin)
301 // Stockage de la multicurve approximee.
302 tolreached = Standard_True;
303 myMultiCurves.Append(LSquare.Value());
304 myfirstparam.Append(Ufirst);
305 mylastparam.Append(Ulast);
306 Tolers3d.Append(TheTol3d);
307 Tolers2d.Append(TheTol2d);
308 return Standard_True;
310 aPrevTol3d = TheTol3d;
311 aPrevTol2d = TheTol2d;
312 aPrevCurve = LSquare.Value();
313 aPrevIsOk = Standard_True;
318 // Stockage de la multicurve approximee.
319 tolreached = Standard_True;
320 TheTol3d = aPrevTol3d;
321 TheTol2d = aPrevTol2d;
322 myMultiCurves.Append(aPrevCurve);
323 myfirstparam.Append(Ufirst);
324 mylastparam.Append(Ulast);
325 Tolers3d.Append(aPrevTol3d);
326 Tolers2d.Append(aPrevTol2d);
327 return Standard_True;
332 // Stockage de la multicurve approximee.
333 tolreached = Standard_True;
334 TheTol3d = aPrevTol3d;
335 TheTol2d = aPrevTol2d;
336 myMultiCurves.Append(aPrevCurve);
337 myfirstparam.Append(Ufirst);
338 mylastparam.Append(Ulast);
339 Tolers3d.Append(aPrevTol3d);
340 Tolers2d.Append(aPrevTol2d);
341 return Standard_True;
343 if (!aPrevIsOk && deg == mydegremax)
345 TheMultiCurve = LSquare.Value();
346 currenttol3d = TheTol3d;
347 currenttol2d = TheTol2d;
348 aPrevTol3d = TheTol3d;
349 aPrevTol2d = TheTol2d;
350 aPrevCurve = TheMultiCurve;
357 for (deg = mydegremin; deg <= mydegremax; deg++) {
358 NbPoints = Min(2 * deg + 1, NbPointsMax);
359 AppCont_LeastSquare LSquare(Line, Ufirst, Ulast, myfirstC, mylastC, deg, NbPoints);
360 mydone = LSquare.IsDone();
362 LSquare.Error(Fv, TheTol3d, TheTol2d);
363 if (TheTol3d <= mytol3d && TheTol2d <= mytol2d) {
364 // Stockage de la multicurve approximee.
365 tolreached = Standard_True;
366 myMultiCurves.Append(LSquare.Value());
367 myfirstparam.Append(Ufirst);
368 mylastparam.Append(Ulast);
369 Tolers3d.Append(TheTol3d);
370 Tolers2d.Append(TheTol2d);
371 return Standard_True;
374 if (deg == mydegremax) {
375 TheMultiCurve = LSquare.Value();
376 currenttol3d = TheTol3d;
377 currenttol2d = TheTol2d;
381 return Standard_False;
384 //=======================================================================
385 //function : Parameters
386 //purpose : returns the first and last parameters of the
387 // <Index> MultiCurve.
388 //=======================================================================
390 void Approx_ComputeCLine::Parameters(const Standard_Integer Index,
391 Standard_Real& firstpar,
392 Standard_Real& lastpar) const
394 firstpar = myfirstparam.Value(Index);
395 lastpar = mylastparam.Value(Index);
398 //=======================================================================
399 //function : SetDegrees
400 //purpose : changes the degrees of the approximation.
401 //=======================================================================
403 void Approx_ComputeCLine::SetDegrees(const Standard_Integer degreemin,
404 const Standard_Integer degreemax)
406 mydegremin = degreemin;
407 mydegremax = degreemax;
410 //=======================================================================
411 //function : SetTolerances
412 //purpose : Changes the tolerances of the approximation.
413 //=======================================================================
415 void Approx_ComputeCLine::SetTolerances(const Standard_Real Tolerance3d,
416 const Standard_Real Tolerance2d)
418 mytol3d = Tolerance3d;
419 mytol2d = Tolerance2d;
422 //=======================================================================
423 //function : SetConstraints
424 //purpose : Changes the constraints of the approximation.
425 //=======================================================================
427 void Approx_ComputeCLine::SetConstraints(const AppParCurves_Constraint FirstC,
428 const AppParCurves_Constraint LastC)
434 //=======================================================================
435 //function : SetMaxSegments
436 //purpose : Changes the max number of segments, which is allowed for cutting.
437 //=======================================================================
439 void Approx_ComputeCLine::SetMaxSegments(const Standard_Integer theMaxSegments)
441 myMaxSegments = theMaxSegments;
444 //=======================================================================
445 //function : SetInvOrder
447 //=======================================================================
448 void Approx_ComputeCLine::SetInvOrder(const Standard_Boolean theInvOrder)
450 myInvOrder = theInvOrder;
453 //=======================================================================
454 //function : SetHangChecking
456 //=======================================================================
457 void Approx_ComputeCLine::SetHangChecking(const Standard_Boolean theHangChecking)
459 myHangChecking = theHangChecking;
462 //=======================================================================
463 //function : IsAllApproximated
464 //purpose : returns False if at a moment of the approximation,
465 // the status NoApproximation has been sent by the user
466 // when more points were needed.
467 //=======================================================================
469 Standard_Boolean Approx_ComputeCLine::IsAllApproximated()
474 //=======================================================================
475 //function : IsToleranceReached
476 //purpose : returns False if the status NoPointsAdded has been sent.
477 //=======================================================================
479 Standard_Boolean Approx_ComputeCLine::IsToleranceReached()
484 //=======================================================================
486 //purpose : returns the tolerances 2d and 3d of the <Index> MultiCurve.
487 //=======================================================================
489 void Approx_ComputeCLine::Error(const Standard_Integer Index,
490 Standard_Real& tol3d,
491 Standard_Real& tol2d) const
493 tol3d = Tolers3d.Value(Index);
494 tol2d = Tolers2d.Value(Index);