0026674: Performance regression in BRepExtrema_DistShapeShape in OCCT 6.9.0 in compar...
[occt.git] / src / math / math_GlobOptMin.hxx
1 // Created on: 2014-01-20
2 // Created by: Alexaner Malyshev
3 // Copyright (c) 2014-2015 OPEN CASCADE SAS
4 //
5 // This file is part of Open CASCADE Technology software library.
6 //
7 // This library is free software; you can redistribute it and/or modify it under
8 // the terms of the GNU Lesser General Public License version 2.1 as published
9 // by the Free Software Foundation, with special exception defined in the file
10 // OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT
11 // distribution for complete text of the license and disclaimer of any warranty.
12 //
13 // Alternatively, this file may be used under the terms of Open CASCADE
14 // commercial license or contractual agreement.
15
16 #ifndef _math_GlobOptMin_HeaderFile
17 #define _math_GlobOptMin_HeaderFile
18
19 #include <gp_Pnt.hxx>
20 #include <gp_Pnt2d.hxx>
21 #include <NCollection_CellFilter.hxx>
22 #include <math_MultipleVarFunction.hxx>
23 #include <NCollection_Sequence.hxx>
24 #include <Standard_Type.hxx>
25
26 class NCollection_CellFilter_Inspector
27 {
28 public:
29
30   //! Points and target type
31   typedef math_Vector Point;
32   typedef math_Vector Target;
33
34   NCollection_CellFilter_Inspector(const Standard_Integer theDim,
35                                    const Standard_Real theTol)
36   : myCurrent(1, theDim)
37   {
38     myTol = theTol * theTol;
39     myIsFind = Standard_False;
40     Dimension = theDim;
41   }
42
43   //! Access to co-ordinate
44   static Standard_Real Coord (int i, const Point &thePnt)
45   {
46     return thePnt(i + 1);
47   }
48
49   //! Auxiliary method to shift point by each coordinate on given value;
50   //! useful for preparing a points range for Inspect with tolerance
51   void Shift (const Point& thePnt,
52               const NCollection_Array1<Standard_Real> &theTol,
53               Point& theLowPnt,
54               Point& theUppPnt) const
55   {
56     for(Standard_Integer anIdx = 1; anIdx <= Dimension; anIdx++)
57     {
58       theLowPnt(anIdx) = thePnt(anIdx) - theTol(anIdx - 1);
59       theUppPnt(anIdx) = thePnt(anIdx) + theTol(anIdx - 1);
60     }
61   }
62
63   void ClearFind()
64   {
65     myIsFind = Standard_False;
66   }
67
68   Standard_Boolean isFind()
69   {
70     return myIsFind;
71   }
72
73   //! Set current point to search for coincidence
74   void SetCurrent (const math_Vector& theCurPnt)
75   { 
76     myCurrent = theCurPnt;
77   }
78
79   //! Implementation of inspection method
80   NCollection_CellFilter_Action Inspect (const Target& theObject)
81   {
82     Standard_Real aSqDist = (myCurrent - theObject).Norm2();
83
84     if(aSqDist < myTol)
85     {
86       myIsFind = Standard_True;
87     }
88
89     return CellFilter_Keep;
90   }
91
92 private:
93   Standard_Real myTol;
94   math_Vector myCurrent;
95   Standard_Boolean myIsFind;
96   Standard_Integer Dimension;
97 };
98
99 //! This class represents Evtushenko's algorithm of global optimization based on nonuniform mesh.<br>
100 //! Article: Yu. Evtushenko. Numerical methods for finding global extreme (case of a non-uniform mesh). <br>
101 //! U.S.S.R. Comput. Maths. Math. Phys., Vol. 11, N 6, pp. 38-54.
102
103 class math_GlobOptMin
104 {
105 public:
106
107   Standard_EXPORT math_GlobOptMin(math_MultipleVarFunction* theFunc,
108                                  const math_Vector& theLowerBorder,
109                                  const math_Vector& theUpperBorder,
110                                  const Standard_Real theC = 9,
111                                  const Standard_Real theDiscretizationTol = 1.0e-2,
112                                  const Standard_Real theSameTol = 1.0e-7);
113
114   Standard_EXPORT void SetGlobalParams(math_MultipleVarFunction* theFunc,
115                                        const math_Vector& theLowerBorder,
116                                        const math_Vector& theUpperBorder,
117                                        const Standard_Real theC = 9,
118                                        const Standard_Real theDiscretizationTol = 1.0e-2,
119                                        const Standard_Real theSameTol = 1.0e-7);
120
121   Standard_EXPORT void SetLocalParams(const math_Vector& theLocalA,
122                                       const math_Vector& theLocalB);
123
124   Standard_EXPORT void SetTol(const Standard_Real theDiscretizationTol,
125                               const Standard_Real theSameTol);
126
127   Standard_EXPORT void GetTol(Standard_Real& theDiscretizationTol,
128                               Standard_Real& theSameTol);
129
130   Standard_EXPORT ~math_GlobOptMin();
131
132   //! @param isFindSingleSolution - defines whether to find single solution or all solutions.
133   Standard_EXPORT void Perform(const Standard_Boolean isFindSingleSolution = Standard_False);
134
135   //! Get best functional value.
136   Standard_EXPORT Standard_Real GetF();
137
138   //! Return count of global extremas.
139   Standard_EXPORT Standard_Integer NbExtrema();
140
141   //! Return solution theIndex, 1 <= theIndex <= NbExtrema.
142   Standard_EXPORT void Points(const Standard_Integer theIndex, math_Vector& theSol);
143
144   Standard_EXPORT Standard_Boolean isDone();
145
146   //! Set functional minimal value.
147   Standard_EXPORT void SetFunctionalMinimalValue(const Standard_Real theMinimalValue);
148
149   //! Get functional minimal value.
150   Standard_EXPORT Standard_Real GetFunctionalMinimalValue();
151
152 private:
153
154   // Compute cell size.
155   void initCellSize();
156
157   math_GlobOptMin & operator = (const math_GlobOptMin & theOther);
158
159   Standard_Boolean computeLocalExtremum(const math_Vector& thePnt, Standard_Real& theVal, math_Vector& theOutPnt);
160
161   void computeGlobalExtremum(Standard_Integer theIndex);
162
163   //! Check possibility to stop computations.
164   //! Find single solution + in neighbourhood of best possible solution.
165   Standard_Boolean CheckFunctionalStopCriteria();
166
167   //! Computes starting value / approximation:
168   //! myF - initial best value.
169   //! myY - initial best point.
170   //! myC - approximation of Lipschitz constant.
171   //! to imporve convergence speed.
172   void computeInitialValues();
173
174   //! Check that myA <= thePnt <= myB
175   Standard_Boolean isInside(const math_Vector& thePnt);
176
177   //! Check presence of thePnt in GlobOpt sequence.
178   Standard_Boolean isStored(const math_Vector &thePnt);
179
180   // Input.
181   math_MultipleVarFunction* myFunc;
182   Standard_Integer myN;
183   math_Vector myA; // Left border on current C2 interval.
184   math_Vector myB; // Right border on current C2 interval.
185   math_Vector myGlobA; // Global left border.
186   math_Vector myGlobB; // Global right border.
187   Standard_Real myTol; // Discretization tolerance, default 1.0e-2.
188   Standard_Real mySameTol; // points with ||p1 - p2|| < mySameTol is equal,
189                            // function values |val1 - val2| * 0.01 < mySameTol is equal,
190                            // default value is 1.0e-7.
191   Standard_Real myC; //Lipschitz constant, default 9
192   Standard_Boolean myIsFindSingleSolution; // Default value is false.
193   Standard_Real myFunctionalMinimalValue; // Default value is -Precision::Infinite
194
195   // Output.
196   Standard_Boolean myDone;
197   NCollection_Sequence<Standard_Real> myY;// Current solutions.
198   Standard_Integer mySolCount; // Count of solutions.
199
200   // Algorithm data.
201   Standard_Real myZ;
202   Standard_Real myE1; // Border coeff.
203   Standard_Real myE2; // Minimum step size.
204   Standard_Real myE3; // Local extrema starting parameter.
205
206   math_Vector myX; // Current modified solution.
207   math_Vector myTmp; // Current modified solution.
208   math_Vector myV; // Steps array.
209   math_Vector myMaxV; // Max Steps array.
210   math_Vector myExpandCoeff; // Define expand coefficient between neighboring indiced dimensions.
211
212   NCollection_Array1<Standard_Real> myCellSize;
213   Standard_Integer myMinCellFilterSol;
214   Standard_Boolean isFirstCellFilterInvoke;
215   NCollection_CellFilter<NCollection_CellFilter_Inspector> myFilter;
216
217   Standard_Real myF; // Current value of Global optimum.
218 };
219
220 #endif