b311480e |
1 | // Created on: 1995-07-18 |
2 | // Created by: Modelistation |
3 | // Copyright (c) 1995-1999 Matra Datavision |
973c2be1 |
4 | // Copyright (c) 1999-2014 OPEN CASCADE SAS |
b311480e |
5 | // |
973c2be1 |
6 | // This file is part of Open CASCADE Technology software library. |
b311480e |
7 | // |
d5f74e42 |
8 | // This library is free software; you can redistribute it and/or modify it under |
9 | // the terms of the GNU Lesser General Public License version 2.1 as published |
973c2be1 |
10 | // by the Free Software Foundation, with special exception defined in the file |
11 | // OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT |
12 | // distribution for complete text of the license and disclaimer of any warranty. |
b311480e |
13 | // |
973c2be1 |
14 | // Alternatively, this file may be used under the terms of Open CASCADE |
15 | // commercial license or contractual agreement. |
7fd59977 |
16 | |
20a216fe |
17 | #include <algorithm> |
18 | |
4bbaf12b |
19 | #include <Extrema_GlobOptFuncCC.hxx> |
20 | #include <math_GlobOptMin.hxx> |
7fd59977 |
21 | #include <Standard_NullObject.hxx> |
22 | #include <Standard_OutOfRange.hxx> |
4bbaf12b |
23 | #include <StdFail_NotDone.hxx> |
24 | #include <TColStd_Array1OfReal.hxx> |
7fd59977 |
25 | #include <Precision.hxx> |
20a216fe |
26 | #include <NCollection_Vector.hxx> |
27 | #include <NCollection_CellFilter.hxx> |
28 | |
29 | // Comparator, used in std::sort. |
30 | static Standard_Boolean comp(const gp_XY& theA, |
31 | const gp_XY& theB) |
32 | { |
33 | if (theA.X() < theB.X()) |
34 | { |
35 | return Standard_True; |
36 | } |
37 | else |
38 | { |
39 | if (theA.X() == theB.X()) |
40 | { |
afb27815 |
41 | if (theA.Y() < theB.Y()) |
20a216fe |
42 | return Standard_True; |
43 | } |
44 | } |
45 | |
46 | return Standard_False; |
47 | } |
48 | |
49 | class Extrema_CCPointsInspector : public NCollection_CellFilter_InspectorXY |
50 | { |
51 | public: |
52 | typedef gp_XY Target; |
53 | //! Constructor; remembers the tolerance |
54 | Extrema_CCPointsInspector (const Standard_Real theTol) |
55 | { |
56 | myTol = theTol * theTol; |
57 | myIsFind = Standard_False; |
58 | } |
59 | |
60 | void ClearFind() |
61 | { |
62 | myIsFind = Standard_False; |
63 | } |
64 | |
65 | Standard_Boolean isFind() |
66 | { |
67 | return myIsFind; |
68 | } |
69 | |
70 | //! Set current point to search for coincidence |
71 | void SetCurrent (const gp_XY& theCurPnt) |
72 | { |
73 | myCurrent = theCurPnt; |
74 | } |
75 | |
76 | //! Implementation of inspection method |
77 | NCollection_CellFilter_Action Inspect (const Target& theObject) |
78 | { |
79 | gp_XY aPt = myCurrent.Subtracted(theObject); |
80 | const Standard_Real aSQDist = aPt.SquareModulus(); |
81 | if(aSQDist < myTol) |
82 | { |
83 | myIsFind = Standard_True; |
84 | } |
85 | |
86 | return CellFilter_Keep; |
87 | } |
88 | |
89 | private: |
90 | Standard_Real myTol; |
91 | gp_XY myCurrent; |
92 | Standard_Boolean myIsFind; |
93 | }; |
7fd59977 |
94 | |
5493d334 |
95 | //======================================================================= |
96 | //function : Extrema_GenExtCC |
97 | //purpose : |
98 | //======================================================================= |
4bbaf12b |
99 | Extrema_GenExtCC::Extrema_GenExtCC() |
836d7b64 |
100 | : myIsFindSingleSolution(Standard_False), |
101 | myParallel(Standard_False), |
20a216fe |
102 | myCurveMinTol(Precision::PConfusion()), |
6ca1fa70 |
103 | myLowBorder(1,2), |
4bbaf12b |
104 | myUppBorder(1,2), |
105 | myDone(Standard_False) |
7fd59977 |
106 | { |
6ca1fa70 |
107 | myC[0] = myC[1] = 0; |
7fd59977 |
108 | } |
109 | |
5493d334 |
110 | //======================================================================= |
111 | //function : Extrema_GenExtCC |
112 | //purpose : |
113 | //======================================================================= |
114 | Extrema_GenExtCC::Extrema_GenExtCC(const Curve1& C1, |
115 | const Curve2& C2) |
836d7b64 |
116 | : myIsFindSingleSolution(Standard_False), |
117 | myParallel(Standard_False), |
20a216fe |
118 | myCurveMinTol(Precision::PConfusion()), |
6ca1fa70 |
119 | myLowBorder(1,2), |
4bbaf12b |
120 | myUppBorder(1,2), |
121 | myDone(Standard_False) |
7fd59977 |
122 | { |
4bbaf12b |
123 | myC[0] = (Standard_Address)&C1; |
124 | myC[1] = (Standard_Address)&C2; |
125 | myLowBorder(1) = C1.FirstParameter(); |
126 | myLowBorder(2) = C2.FirstParameter(); |
127 | myUppBorder(1) = C1.LastParameter(); |
128 | myUppBorder(2) = C2.LastParameter(); |
7fd59977 |
129 | } |
130 | |
5493d334 |
131 | //======================================================================= |
132 | //function : Extrema_GenExtCC |
133 | //purpose : |
134 | //======================================================================= |
135 | Extrema_GenExtCC::Extrema_GenExtCC(const Curve1& C1, |
136 | const Curve2& C2, |
137 | const Standard_Real Uinf, |
138 | const Standard_Real Usup, |
139 | const Standard_Real Vinf, |
140 | const Standard_Real Vsup) |
836d7b64 |
141 | : myIsFindSingleSolution(Standard_False), |
142 | myParallel(Standard_False), |
20a216fe |
143 | myCurveMinTol(Precision::PConfusion()), |
6ca1fa70 |
144 | myLowBorder(1,2), |
4bbaf12b |
145 | myUppBorder(1,2), |
146 | myDone(Standard_False) |
7fd59977 |
147 | { |
4bbaf12b |
148 | myC[0] = (Standard_Address)&C1; |
149 | myC[1] = (Standard_Address)&C2; |
150 | myLowBorder(1) = Uinf; |
151 | myLowBorder(2) = Vinf; |
152 | myUppBorder(1) = Usup; |
153 | myUppBorder(2) = Vsup; |
7fd59977 |
154 | } |
155 | |
5493d334 |
156 | //======================================================================= |
157 | //function : SetParams |
158 | //purpose : |
159 | //======================================================================= |
160 | void Extrema_GenExtCC::SetParams(const Curve1& C1, |
161 | const Curve2& C2, |
162 | const Standard_Real Uinf, |
163 | const Standard_Real Usup, |
164 | const Standard_Real Vinf, |
165 | const Standard_Real Vsup) |
7fd59977 |
166 | { |
4bbaf12b |
167 | myC[0] = (Standard_Address)&C1; |
168 | myC[1] = (Standard_Address)&C2; |
169 | myLowBorder(1) = Uinf; |
170 | myLowBorder(2) = Vinf; |
171 | myUppBorder(1) = Usup; |
172 | myUppBorder(2) = Vsup; |
7fd59977 |
173 | } |
174 | |
5493d334 |
175 | //======================================================================= |
176 | //function : SetTolerance |
177 | //purpose : |
178 | //======================================================================= |
179 | void Extrema_GenExtCC::SetTolerance(Standard_Real theTol) |
180 | { |
181 | myCurveMinTol = theTol; |
182 | } |
183 | |
184 | //======================================================================= |
185 | //function : Perform |
186 | //purpose : |
187 | //======================================================================= |
188 | void Extrema_GenExtCC::Perform() |
7fd59977 |
189 | { |
190 | myDone = Standard_False; |
20a216fe |
191 | myParallel = Standard_False; |
7fd59977 |
192 | |
4bbaf12b |
193 | Curve1 &C1 = *(Curve1*)myC[0]; |
194 | Curve2 &C2 = *(Curve2*)myC[1]; |
195 | |
196 | Standard_Integer aNbInter[2]; |
197 | aNbInter[0] = C1.NbIntervals(GeomAbs_C2); |
198 | aNbInter[1] = C2.NbIntervals(GeomAbs_C2); |
199 | TColStd_Array1OfReal anIntervals1(1, aNbInter[0] + 1); |
200 | TColStd_Array1OfReal anIntervals2(1, aNbInter[1] + 1); |
201 | C1.Intervals(anIntervals1, GeomAbs_C2); |
202 | C2.Intervals(anIntervals2, GeomAbs_C2); |
203 | |
1907fb9a |
204 | // Lipchitz constant approximation. |
205 | Standard_Real aLC = 9.0; // Default value. |
206 | Standard_Boolean isConstLockedFlag = Standard_False; |
207 | if (C1.GetType() == GeomAbs_Line) |
208 | { |
209 | Standard_Real aMaxDer = 1.0 / C2.Resolution(1.0); |
210 | if (aLC > aMaxDer) |
211 | { |
212 | isConstLockedFlag = Standard_True; |
213 | aLC = aMaxDer; |
214 | } |
215 | } |
216 | if (C2.GetType() == GeomAbs_Line) |
217 | { |
218 | Standard_Real aMaxDer = 1.0 / C1.Resolution(1.0); |
219 | if (aLC > aMaxDer) |
220 | { |
221 | isConstLockedFlag = Standard_True; |
222 | aLC = aMaxDer; |
223 | } |
224 | } |
225 | |
6ca1fa70 |
226 | Extrema_GlobOptFuncCCC2 aFunc (C1, C2); |
1907fb9a |
227 | math_GlobOptMin aFinder(&aFunc, myLowBorder, myUppBorder, aLC); |
228 | aFinder.SetLipConstState(isConstLockedFlag); |
5493d334 |
229 | Standard_Real aDiscTol = 1.0e-2; |
230 | Standard_Real aValueTol = 1.0e-2; |
231 | Standard_Real aSameTol = myCurveMinTol / (aDiscTol); |
232 | aFinder.SetTol(aDiscTol, aSameTol); |
1907fb9a |
233 | aFinder.SetFunctionalMinimalValue(0.0); // Best distance cannot be lower than 0.0. |
4bbaf12b |
234 | |
20a216fe |
235 | // Size computed to have cell index inside of int32 value. |
236 | const Standard_Real aCellSize = Max(anIntervals1.Upper() - anIntervals1.Lower(), |
237 | anIntervals2.Upper() - anIntervals2.Lower()) |
238 | * Precision::PConfusion() / (2.0 * Sqrt(2.0)); |
239 | Extrema_CCPointsInspector anInspector(Precision::PConfusion()); |
a7653f4f |
240 | NCollection_CellFilter<Extrema_CCPointsInspector> aFilter(aCellSize); |
20a216fe |
241 | NCollection_Vector<gp_XY> aPnts; |
6ca1fa70 |
242 | |
4bbaf12b |
243 | Standard_Integer i,j,k; |
244 | math_Vector aFirstBorderInterval(1,2); |
245 | math_Vector aSecondBorderInterval(1,2); |
20a216fe |
246 | Standard_Real aF = RealLast(); // Best functional value. |
247 | Standard_Real aCurrF = RealLast(); // Current functional value computed on current interval. |
4bbaf12b |
248 | for(i = 1; i <= aNbInter[0]; i++) |
249 | { |
250 | for(j = 1; j <= aNbInter[1]; j++) |
251 | { |
252 | aFirstBorderInterval(1) = anIntervals1(i); |
253 | aFirstBorderInterval(2) = anIntervals2(j); |
254 | aSecondBorderInterval(1) = anIntervals1(i + 1); |
255 | aSecondBorderInterval(2) = anIntervals2(j + 1); |
256 | |
257 | aFinder.SetLocalParams(aFirstBorderInterval, aSecondBorderInterval); |
836d7b64 |
258 | aFinder.Perform(GetSingleSolutionFlag()); |
4bbaf12b |
259 | |
20a216fe |
260 | // Check that solution found on current interval is not worse than previous. |
4bbaf12b |
261 | aCurrF = aFinder.GetF(); |
6ca1fa70 |
262 | if (aCurrF >= aF + aSameTol * aValueTol) |
4bbaf12b |
263 | { |
6ca1fa70 |
264 | continue; |
265 | } |
266 | |
20a216fe |
267 | // Clean previously computed solution if current one is better. |
6ca1fa70 |
268 | if (aCurrF > aF - aSameTol * aValueTol) |
269 | { |
270 | if (aCurrF < aF) |
4bbaf12b |
271 | aF = aCurrF; |
6ca1fa70 |
272 | } |
273 | else |
274 | { |
275 | aF = aCurrF; |
20a216fe |
276 | aFilter.Reset(aCellSize); |
277 | aPnts.Clear(); |
6ca1fa70 |
278 | } |
7fd59977 |
279 | |
20a216fe |
280 | // Save found solutions avoiding repetitions. |
6ca1fa70 |
281 | math_Vector sol(1,2); |
282 | for(k = 1; k <= aFinder.NbExtrema(); k++) |
4bbaf12b |
283 | { |
6ca1fa70 |
284 | aFinder.Points(k, sol); |
20a216fe |
285 | gp_XY aPnt2d(sol(1), sol(2)); |
6ca1fa70 |
286 | |
20a216fe |
287 | gp_XY aXYmin = anInspector.Shift(aPnt2d, -aCellSize); |
288 | gp_XY aXYmax = anInspector.Shift(aPnt2d, aCellSize); |
289 | |
290 | anInspector.ClearFind(); |
291 | anInspector.SetCurrent(aPnt2d); |
292 | aFilter.Inspect(aXYmin, aXYmax, anInspector); |
293 | if (!anInspector.isFind()) |
6ca1fa70 |
294 | { |
20a216fe |
295 | // Point is out of close cells, add new one. |
296 | aFilter.Add(aPnt2d, aPnt2d); |
297 | aPnts.Append(gp_XY(sol(1), sol(2))); |
6ca1fa70 |
298 | } |
4bbaf12b |
299 | } |
7fd59977 |
300 | } |
4bbaf12b |
301 | } |
7fd59977 |
302 | |
20a216fe |
303 | if (aPnts.Size() == 0) |
304 | { |
305 | // No solutions. |
306 | myDone = Standard_False; |
307 | return; |
308 | } |
309 | |
310 | // Check for infinity solutions case, for this: |
311 | // Sort points lexicographically and check midpoint between each two neighboring points. |
312 | // If all midpoints functional value is acceptable |
1907fb9a |
313 | // then set myParallel flag to true and return one solution. |
20a216fe |
314 | std::sort(aPnts.begin(), aPnts.end(), comp); |
315 | Standard_Boolean isParallel = Standard_False; |
316 | Standard_Real aVal = 0.0; |
317 | math_Vector aVec(1,2, 0.0); |
318 | |
319 | // Avoid mark parallel case when have duplicates out of tolerance. |
320 | // Bad conditioned task: bug25635_1, bug23706_10, bug23706_13. |
321 | const Standard_Integer aMinNbInfSol = 100; |
322 | if (aPnts.Size() >= aMinNbInfSol) |
323 | { |
324 | isParallel = Standard_True; |
325 | for(Standard_Integer anIdx = aPnts.Lower(); anIdx <= aPnts.Upper() - 1; anIdx++) |
326 | { |
327 | const gp_XY& aCurrent = aPnts(anIdx); |
328 | const gp_XY& aNext = aPnts(anIdx + 1); |
329 | |
330 | aVec(1) = (aCurrent.X() + aNext.X()) * 0.5; |
331 | aVec(2) = (aCurrent.Y() + aNext.Y()) * 0.5; |
332 | |
333 | aFunc.Value(aVec, aVal); |
334 | |
335 | if (Abs(aVal - aF) > Precision::Confusion()) |
336 | { |
337 | isParallel = Standard_False; |
338 | break; |
339 | } |
340 | } |
341 | } |
342 | |
343 | if (isParallel) |
344 | { |
345 | const gp_XY& aCurrent = aPnts.First(); |
346 | myPoints1.Append(aCurrent.X()); |
347 | myPoints2.Append(aCurrent.Y()); |
348 | myParallel = Standard_True; |
349 | } |
350 | else |
351 | { |
352 | for(Standard_Integer anIdx = aPnts.Lower(); anIdx <= aPnts.Upper(); anIdx++) |
353 | { |
354 | const gp_XY& aCurrent = aPnts(anIdx); |
355 | myPoints1.Append(aCurrent.X()); |
356 | myPoints2.Append(aCurrent.Y()); |
357 | } |
358 | } |
359 | |
7fd59977 |
360 | myDone = Standard_True; |
361 | } |
7fd59977 |
362 | |
5493d334 |
363 | //======================================================================= |
364 | //function : IsDone |
365 | //purpose : |
366 | //======================================================================= |
367 | Standard_Boolean Extrema_GenExtCC::IsDone() const |
4bbaf12b |
368 | { |
369 | return myDone; |
370 | } |
7fd59977 |
371 | |
20a216fe |
372 | //======================================================================= |
373 | //function : IsParallel |
374 | //purpose : |
375 | //======================================================================= |
376 | Standard_Boolean Extrema_GenExtCC::IsParallel() const |
377 | { |
378 | return myParallel; |
379 | } |
380 | |
5493d334 |
381 | //======================================================================= |
382 | //function : NbExt |
383 | //purpose : |
384 | //======================================================================= |
385 | Standard_Integer Extrema_GenExtCC::NbExt() const |
7fd59977 |
386 | { |
387 | StdFail_NotDone_Raise_if (!myDone, "Extrema_GenExtCC::NbExt()") |
4bbaf12b |
388 | |
6ca1fa70 |
389 | return myPoints1.Length(); |
7fd59977 |
390 | } |
7fd59977 |
391 | |
5493d334 |
392 | //======================================================================= |
393 | //function : SquareDistance |
394 | //purpose : |
395 | //======================================================================= |
396 | Standard_Real Extrema_GenExtCC::SquareDistance(const Standard_Integer N) const |
7fd59977 |
397 | { |
398 | StdFail_NotDone_Raise_if (!myDone, "Extrema_GenExtCC::SquareDistance()") |
399 | Standard_OutOfRange_Raise_if ((N < 1 || N > NbExt()), "Extrema_GenExtCC::SquareDistance()") |
4bbaf12b |
400 | |
401 | return Tool1::Value(*((Curve1*)myC[0]), myPoints1(N)).SquareDistance(Tool2::Value(*((Curve2*)myC[1]), myPoints2(N))); |
7fd59977 |
402 | } |
7fd59977 |
403 | |
5493d334 |
404 | //======================================================================= |
405 | //function : Points |
406 | //purpose : |
407 | //======================================================================= |
408 | void Extrema_GenExtCC::Points(const Standard_Integer N, |
409 | POnC& P1, |
410 | POnC& P2) const |
7fd59977 |
411 | { |
4bbaf12b |
412 | StdFail_NotDone_Raise_if (!myDone, "Extrema_GenExtCC::Points()") |
413 | Standard_OutOfRange_Raise_if ((N < 1 || N > NbExt()), "Extrema_GenExtCC::Points()") |
414 | |
415 | P1.SetValues(myPoints1(N), Tool1::Value(*((Curve1*)myC[0]), myPoints1(N))); |
416 | P2.SetValues(myPoints2(N), Tool2::Value(*((Curve2*)myC[1]), myPoints2(N))); |
20a216fe |
417 | } |
836d7b64 |
418 | |
419 | //======================================================================= |
420 | //function : SetSingleSolutionFlag |
421 | //purpose : |
422 | //======================================================================= |
423 | void Extrema_GenExtCC::SetSingleSolutionFlag(const Standard_Boolean theFlag) |
424 | { |
425 | myIsFindSingleSolution = theFlag; |
426 | } |
427 | |
428 | //======================================================================= |
429 | //function : GetSingleSolutionFlag |
430 | //purpose : |
431 | //======================================================================= |
432 | Standard_Boolean Extrema_GenExtCC::GetSingleSolutionFlag() const |
433 | { |
434 | return myIsFindSingleSolution; |
435 | } |