0030435: Improving performance of Approx_ComputeCLine
[occt.git] / 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 = 5;
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)
182         {
183           aStopCutting = Standard_True;
184         }
185       }
186       // is new decision better?
187       if (!Ok && (Abs(myfirstU - mylastU) <= TolU || aMaxSegments >= aMaxSegments1 || aStopCutting ))
188       {
189         Ok = Standard_True; // stop interval cutting, approx the rest part
190
191         if ((thetol3d + thetol2d) < (KeptT3d + KeptT2d))
192         {
193           KeptMultiCurve = TheMultiCurve;
194           KeptUfirst = myfirstU;
195           KeptUlast = mylastU;
196           KeptT3d = thetol3d;
197           KeptT2d = thetol2d;
198         }
199
200         mylastU = KeptUlast;
201
202         tolreached = Standard_False; // helas
203         myMultiCurves.Append(KeptMultiCurve);
204         aMaxSegments++;
205         Tolers3d.Append(KeptT3d);
206         Tolers2d.Append(KeptT2d);
207         myfirstparam.Append(KeptUfirst);
208         mylastparam.Append(KeptUlast);
209       }
210
211       begin = Standard_False;
212     } // while (!Finish)
213   }
214 }
215
216 //=======================================================================
217 //function : NbMultiCurves
218 //purpose  : Returns the number of MultiCurve doing the approximation
219 //           of the MultiLine.
220 //=======================================================================
221
222 Standard_Integer Approx_ComputeCLine::NbMultiCurves()const
223 {
224   return myMultiCurves.Length();
225 }
226
227 //=======================================================================
228 //function : Value
229 //purpose  : returns the approximation MultiCurve of range <Index>.
230 //=======================================================================
231
232 AppParCurves_MultiCurve Approx_ComputeCLine::Value(const Standard_Integer Index)
233 const
234 {
235   return myMultiCurves.Value(Index);
236 }
237
238 //=======================================================================
239 //function : Compute
240 //purpose  : is internally used by the algorithms.
241 //=======================================================================
242
243 Standard_Boolean Approx_ComputeCLine::Compute(const MultiLine& Line,
244   const Standard_Real Ufirst,
245   const Standard_Real Ulast,
246   Standard_Real&   TheTol3d,
247   Standard_Real&   TheTol2d)
248 {
249
250
251   const Standard_Integer NbPointsMax = 24;
252   const Standard_Real aMinRatio = 0.05;
253   const Standard_Integer aMaxDeg = 8;
254   //
255   Standard_Integer deg, NbPoints;
256   Standard_Boolean mydone;
257   Standard_Real Fv;
258
259   AppParCurves_MultiCurve aPrevCurve;
260   Standard_Real aPrevTol3d = RealLast(), aPrevTol2d = RealLast();
261   Standard_Boolean aPrevIsOk = Standard_False;
262   Standard_Boolean anInvOrder = myInvOrder;
263   if (anInvOrder && mydegremax > aMaxDeg)
264   {
265     if ((Ulast - Ufirst) / (Line.LastParameter() - Line.FirstParameter()) < aMinRatio)
266     {
267       anInvOrder = Standard_False;
268     }
269   }
270   if (anInvOrder)
271   {
272     for (deg = mydegremax; deg >= mydegremin; deg--) {
273       NbPoints = Min(2 * deg + 1, NbPointsMax);
274       AppCont_LeastSquare LSquare(Line, Ufirst, Ulast, myfirstC, mylastC, deg, NbPoints);
275       mydone = LSquare.IsDone();
276       if (mydone)
277       {
278         LSquare.Error(Fv, TheTol3d, TheTol2d);
279         if (TheTol3d <= mytol3d && TheTol2d <= mytol2d)
280         {
281           if (deg == mydegremin)
282           {
283             // Stockage de la multicurve approximee.
284             tolreached = Standard_True;
285             myMultiCurves.Append(LSquare.Value());
286             myfirstparam.Append(Ufirst);
287             mylastparam.Append(Ulast);
288             Tolers3d.Append(TheTol3d);
289             Tolers2d.Append(TheTol2d);
290             return Standard_True;
291           }
292           aPrevTol3d = TheTol3d;
293           aPrevTol2d = TheTol2d;
294           aPrevCurve = LSquare.Value();
295           aPrevIsOk = Standard_True;
296           continue;
297         }
298         else if (aPrevIsOk)
299         {
300           // Stockage de la multicurve approximee.
301           tolreached = Standard_True;
302           TheTol3d = aPrevTol3d;
303           TheTol2d = aPrevTol2d;
304           myMultiCurves.Append(aPrevCurve);
305           myfirstparam.Append(Ufirst);
306           mylastparam.Append(Ulast);
307           Tolers3d.Append(aPrevTol3d);
308           Tolers2d.Append(aPrevTol2d);
309           return Standard_True;
310         }
311       }
312       else if (aPrevIsOk)
313       {
314         // Stockage de la multicurve approximee.
315         tolreached = Standard_True;
316         TheTol3d = aPrevTol3d;
317         TheTol2d = aPrevTol2d;
318         myMultiCurves.Append(aPrevCurve);
319         myfirstparam.Append(Ufirst);
320         mylastparam.Append(Ulast);
321         Tolers3d.Append(aPrevTol3d);
322         Tolers2d.Append(aPrevTol2d);
323         return Standard_True;
324       }
325       if (!aPrevIsOk && deg == mydegremax)
326       {
327         TheMultiCurve = LSquare.Value();
328         currenttol3d = TheTol3d;
329         currenttol2d = TheTol2d;
330         aPrevTol3d = TheTol3d;
331         aPrevTol2d = TheTol2d;
332         aPrevCurve = TheMultiCurve;
333         break;
334       }
335     }
336   }
337   else
338   {
339     for (deg = mydegremin; deg <= mydegremax; deg++) {
340       NbPoints = Min(2 * deg + 1, NbPointsMax);
341       AppCont_LeastSquare LSquare(Line, Ufirst, Ulast, myfirstC, mylastC, deg, NbPoints);
342       mydone = LSquare.IsDone();
343       if (mydone) {
344         LSquare.Error(Fv, TheTol3d, TheTol2d);
345         if (TheTol3d <= mytol3d && TheTol2d <= mytol2d) {
346           // Stockage de la multicurve approximee.
347           tolreached = Standard_True;
348           myMultiCurves.Append(LSquare.Value());
349           myfirstparam.Append(Ufirst);
350           mylastparam.Append(Ulast);
351           Tolers3d.Append(TheTol3d);
352           Tolers2d.Append(TheTol2d);
353           return Standard_True;
354         }
355       }
356       if (deg == mydegremax) {
357         TheMultiCurve = LSquare.Value();
358         currenttol3d = TheTol3d;
359         currenttol2d = TheTol2d;
360       }
361     }
362   }
363   return Standard_False;
364 }
365
366 //=======================================================================
367 //function : Parameters
368 //purpose  : returns the first and last parameters of the 
369 //           <Index> MultiCurve.
370 //=======================================================================
371
372 void Approx_ComputeCLine::Parameters(const Standard_Integer Index,
373   Standard_Real& firstpar,
374   Standard_Real& lastpar) const
375 {
376   firstpar = myfirstparam.Value(Index);
377   lastpar = mylastparam.Value(Index);
378 }
379
380 //=======================================================================
381 //function : SetDegrees
382 //purpose  : changes the degrees of the approximation.
383 //=======================================================================
384
385 void Approx_ComputeCLine::SetDegrees(const Standard_Integer degreemin,
386   const Standard_Integer degreemax)
387 {
388   mydegremin = degreemin;
389   mydegremax = degreemax;
390 }
391
392 //=======================================================================
393 //function : SetTolerances
394 //purpose  : Changes the tolerances of the approximation.
395 //=======================================================================
396
397 void Approx_ComputeCLine::SetTolerances(const Standard_Real Tolerance3d,
398   const Standard_Real Tolerance2d)
399 {
400   mytol3d = Tolerance3d;
401   mytol2d = Tolerance2d;
402 }
403
404 //=======================================================================
405 //function : SetConstraints
406 //purpose  : Changes the constraints of the approximation.
407 //=======================================================================
408
409 void Approx_ComputeCLine::SetConstraints(const AppParCurves_Constraint FirstC,
410   const AppParCurves_Constraint LastC)
411 {
412   myfirstC = FirstC;
413   mylastC = LastC;
414 }
415
416 //=======================================================================
417 //function : SetMaxSegments
418 //purpose  : Changes the max number of segments, which is allowed for cutting.
419 //=======================================================================
420
421 void Approx_ComputeCLine::SetMaxSegments(const Standard_Integer theMaxSegments)
422 {
423   myMaxSegments = theMaxSegments;
424 }
425
426 //=======================================================================
427 //function : SetInvOrder
428 //purpose  : 
429 //=======================================================================
430 void Approx_ComputeCLine::SetInvOrder(const Standard_Boolean theInvOrder)
431 {
432   myInvOrder = theInvOrder;
433 }
434
435 //=======================================================================
436 //function : IsAllApproximated
437 //purpose  : returns False if at a moment of the approximation,
438 //           the status NoApproximation has been sent by the user
439 //           when more points were needed.
440 //=======================================================================
441
442 Standard_Boolean Approx_ComputeCLine::IsAllApproximated()
443 const {
444   return alldone;
445 }
446
447 //=======================================================================
448 //function : IsToleranceReached
449 //purpose  : returns False if the status NoPointsAdded has been sent.
450 //=======================================================================
451
452 Standard_Boolean Approx_ComputeCLine::IsToleranceReached()
453 const {
454   return tolreached;
455 }
456
457 //=======================================================================
458 //function : Error
459 //purpose  : returns the tolerances 2d and 3d of the <Index> MultiCurve.
460 //=======================================================================
461
462 void Approx_ComputeCLine::Error(const Standard_Integer Index,
463   Standard_Real& tol3d,
464   Standard_Real& tol2d) const
465 {
466   tol3d = Tolers3d.Value(Index);
467   tol2d = Tolers2d.Value(Index);
468 }