b311480e |
1 | // Created on: 1995-07-18 |
2 | // Created by: Modelistation |
3 | // Copyright (c) 1995-1999 Matra Datavision |
4 | // Copyright (c) 1999-2012 OPEN CASCADE SAS |
5 | // |
6 | // The content of this file is subject to the Open CASCADE Technology Public |
7 | // License Version 6.5 (the "License"). You may not use the content of this file |
8 | // except in compliance with the License. Please obtain a copy of the License |
9 | // at http://www.opencascade.org and read it completely before using this file. |
10 | // |
11 | // The Initial Developer of the Original Code is Open CASCADE S.A.S., having its |
12 | // main offices at: 1, place des Freres Montgolfier, 78280 Guyancourt, France. |
13 | // |
14 | // The Original Code and all software distributed under the License is |
15 | // distributed on an "AS IS" basis, without warranty of any kind, and the |
16 | // Initial Developer hereby disclaims all such warranties, including without |
17 | // limitation, any warranties of merchantability, fitness for a particular |
18 | // purpose or non-infringement. Please see the License for the specific terms |
19 | // and conditions governing the rights and limitations under the License. |
20 | |
7fd59977 |
21 | |
22 | #include <StdFail_NotDone.hxx> |
23 | #include <math_FunctionSetRoot.hxx> |
24 | #include <math_NewtonFunctionSetRoot.hxx> |
25 | #include <TColStd_Array2OfInteger.hxx> |
26 | #include <TColStd_Array2OfReal.hxx> |
27 | #include <Standard_NullObject.hxx> |
28 | #include <Standard_OutOfRange.hxx> |
29 | #include <Precision.hxx> |
30 | |
31 | Extrema_GenExtCC::Extrema_GenExtCC () : myDone (Standard_False) |
32 | { |
33 | } |
34 | |
35 | Extrema_GenExtCC::Extrema_GenExtCC (const Curve1& C1, |
36 | const Curve2& C2, |
37 | const Standard_Integer NbU, |
38 | const Standard_Integer NbV, |
39 | const Standard_Real TolU, |
40 | const Standard_Real TolV) : myF (C1,C2, Min(TolU, TolV)), myDone (Standard_False) |
41 | { |
42 | SetCurveCache (1, new Cache (C1, C1.FirstParameter(), C1.LastParameter(), NbU, Standard_True)); |
43 | SetCurveCache (2, new Cache (C2, C2.FirstParameter(), C2.LastParameter(), NbV, Standard_True)); |
44 | Perform(); |
45 | } |
46 | |
47 | |
48 | Extrema_GenExtCC::Extrema_GenExtCC (const Curve1& C1, |
49 | const Curve2& C2, |
50 | const Standard_Real Uinf, |
51 | const Standard_Real Usup, |
52 | const Standard_Real Vinf, |
53 | const Standard_Real Vsup, |
54 | const Standard_Integer NbU, |
55 | const Standard_Integer NbV, |
35e08fe8 |
56 | const Standard_Real /*TolU*/, |
57 | const Standard_Real /*TolV*/) : myF (C1,C2), myDone (Standard_False) |
7fd59977 |
58 | { |
59 | SetCurveCache (1, new Cache (C1, Uinf, Usup, NbU, Standard_True)); |
60 | SetCurveCache (2, new Cache (C2, Vinf, Vsup, NbV, Standard_True)); |
61 | Perform(); |
62 | } |
63 | |
64 | void Extrema_GenExtCC::SetCurveCache (const Standard_Integer theRank, |
65 | const Handle(Cache)& theCache) |
66 | { |
67 | Standard_OutOfRange_Raise_if (theRank < 1 || theRank > 2, "Extrema_GenExtCC::SetCurveCache()") |
68 | myF.SetCurve (theRank, *(Curve1*)theCache->CurvePtr()); |
69 | Standard_Integer anInd = theRank - 1; |
70 | myCache[anInd] = theCache; |
71 | } |
72 | |
73 | void Extrema_GenExtCC::SetTolerance (const Standard_Real Tol) |
74 | { |
75 | myF.SetTolerance (Tol); |
76 | } |
77 | |
78 | |
79 | //============================================================================= |
80 | void Extrema_GenExtCC::Perform () |
81 | /*----------------------------------------------------------------------------- |
82 | Fonction: |
83 | Recherche de toutes les distances extremales entre les courbes C1 et C2. |
84 | a partir de 2 echantillonnages (NbU,NbV). |
85 | |
86 | Methode: |
87 | L'algorithme part de l'hypothese que les echantillonnages sont suffisamment |
88 | fins pour que, s'il existe N distances extremales entre les 2 courbes, |
89 | alors il existe aussi N extrema entre les 2 ensembles de points. |
90 | Ainsi, l'algorithme consiste a partir des extrema des echantillons |
91 | pour trouver les extrema des courbes. |
92 | Les extrema sont calcules par l'algorithme math_FunctionSetRoot avec les |
93 | arguments suivants: |
94 | - myF: Extrema_FuncExtCC cree a partir de C1 et C2, |
95 | - UV: math_Vector dont les composantes sont les parametres des points de |
96 | l'extremum sur les ensembles de points, |
97 | - Tol: Min(TolU,TolV), (Prov.:math_FunctionSetRoot n'autorise pas un vecteur) |
98 | - UVinf: math_Vector dont les composantes sont les bornes inferieures de u et |
99 | v, |
100 | - UVsup: math_Vector dont les composantes sont les bornes superieures de u et |
101 | v. |
102 | |
103 | Traitement: |
104 | a- Constitution du tableau des square distances (TbDist2(0,NbU+1,0,NbV+1)): |
105 | Le tableau est volontairement etendu; les lignes 0 et NbU+1 et les |
106 | colonnes 0 et NbV+1 seront initialisees a RealFirst() ou RealLast() |
107 | pour simplifier les tests effectues dans l'etape b |
108 | (on n'a pas besoin de tester si le point est sur une extremite). |
109 | b- Calcul des extrema: |
110 | On recherche d'abord les minima et ensuite les maxima. Ces 2 traitements |
111 | se passent de facon similaire: |
112 | b.a- Initialisations: |
113 | - des 'bords' du tableau TbDist2 (a RealLast() dans le cas des minima |
114 | et a RealLast() dans le cas des maxima), |
115 | - du tableau TbSel(0,NbU+1,0,NbV+1) de selection des points pour un |
116 | calcul d'extremum local (a 0). Lorsqu'un couple de points sera |
117 | selectionne, il ne sera plus selectionnable, ainsi que les couples |
118 | adjacents (8 au maximum). |
119 | Les adresses correspondantes seront mises a 1. |
120 | b.b- Calcul des minima (ou maxima): |
121 | On boucle sur toutes les square distances du tableau TbDist2: |
122 | - recherche d'un minimum (ou maximum) sur les echantillons, |
123 | - calcul de l'extremum sur les courbes, |
124 | - mise a jour du tableau TbSel. |
125 | -----------------------------------------------------------------------------*/ |
126 | { |
127 | myDone = Standard_False; |
128 | |
129 | const Handle(Cache)& aCache1 = myCache[0]; |
130 | const Handle(Cache)& aCache2 = myCache[1]; |
131 | Standard_NullObject_Raise_if ((aCache1.IsNull() || aCache2.IsNull()), |
132 | "Extrema_GenExtCC::Perform()") |
133 | |
134 | Standard_Integer aNbU = aCache1->NbSamples(), aNbV = aCache2->NbSamples(); |
135 | Standard_OutOfRange_Raise_if ((aNbU < 2 ||aNbV < 2), "Extrema_GenExtCC::Perform()") |
136 | |
137 | /* |
138 | a- Constitution du tableau des distances (TbDist2(0,NbU+1,0,NbV+1)): |
139 | --------------------------------------------------------------- |
140 | */ |
141 | |
142 | //ensure that caches have been calculated |
143 | if (!aCache1->IsValid()) |
144 | aCache1->CalculatePoints(); |
145 | if (!aCache2->IsValid()) |
146 | aCache2->CalculatePoints(); |
147 | |
148 | // Calcul des distances |
7fd59977 |
149 | const Handle(ArrayOfPnt)& aPntArray1 = aCache1->Points(); |
150 | const Handle(ArrayOfPnt)& aPntArray2 = aCache2->Points(); |
151 | Standard_Integer NoU, NoV; |
152 | TColStd_Array2OfReal TbDist2(0, aNbU + 1, 0, aNbV + 1); |
153 | for (NoU = 1; NoU <= aNbU; NoU++) { |
154 | const Pnt& P1 = aPntArray1->Value (NoU); |
155 | for (NoV = 1; NoV <= aNbV; NoV++) { |
156 | const Pnt& P2 = aPntArray2->Value (NoV); |
157 | TbDist2(NoU,NoV) = P1.SquareDistance(P2); |
158 | } |
159 | } |
160 | |
161 | /* |
162 | b- Calcul des minima: |
163 | ----------------- |
164 | b.a) Initialisations: |
165 | */ |
166 | // - generales |
167 | math_Vector Tol(1, 2); |
168 | Tol(1) = myF.Tolerance(); |
169 | Tol(2) = myF.Tolerance(); |
170 | math_Vector UV(1,2), UVinf(1,2), UVsup(1,2); |
171 | UVinf(1) = aCache1->TrimFirstParameter(); |
172 | UVinf(2) = aCache2->TrimFirstParameter(); |
173 | UVsup(1) = aCache1->TrimLastParameter(); |
174 | UVsup(2) = aCache2->TrimLastParameter(); |
32ca7a51 |
175 | |
176 | myF.SubIntervalInitialize(UVinf,UVsup); |
7fd59977 |
177 | |
178 | // - des 'bords' du tableau TbDist2 |
179 | for (NoV = 0; NoV <= aNbV+1; NoV++) { |
180 | TbDist2(0,NoV) = RealLast(); |
181 | TbDist2(aNbU+1,NoV) = RealLast(); |
182 | } |
183 | for (NoU = 1; NoU <= aNbU; NoU++) { |
184 | TbDist2(NoU,0) = RealLast(); |
185 | TbDist2(NoU,aNbV+1) = RealLast(); |
186 | } |
187 | |
188 | // - du tableau TbSel(0,aNbU+1,0,aNbV+1) de selection des points |
189 | TColStd_Array2OfInteger TbSel(0,aNbU+1,0,aNbV+1); |
190 | TbSel.Init(0); |
191 | |
192 | /* |
193 | b.b) Calcul des minima: |
194 | */ |
195 | // - recherche d un minimum sur la grille |
196 | Standard_Integer Nu, Nv; |
197 | Standard_Real Dist2; |
afed7fd7 |
198 | const Handle(TColStd_HArray1OfReal)& aParamArray1 = aCache1->Parameters(); |
199 | const Handle(TColStd_HArray1OfReal)& aParamArray2 = aCache2->Parameters(); |
7fd59977 |
200 | for (NoU = 1; NoU <= aNbU; NoU++) { |
201 | for (NoV = 1; NoV <= aNbV; NoV++) { |
202 | if (TbSel(NoU,NoV) == 0) { |
203 | Dist2 = TbDist2(NoU,NoV); |
204 | if ((TbDist2(NoU-1,NoV-1) >= Dist2) && |
205 | (TbDist2(NoU-1,NoV ) >= Dist2) && |
206 | (TbDist2(NoU-1,NoV+1) >= Dist2) && |
207 | (TbDist2(NoU ,NoV-1) >= Dist2) && |
208 | (TbDist2(NoU ,NoV+1) >= Dist2) && |
209 | (TbDist2(NoU+1,NoV-1) >= Dist2) && |
210 | (TbDist2(NoU+1,NoV ) >= Dist2) && |
211 | (TbDist2(NoU+1,NoV+1) >= Dist2)) { |
212 | |
213 | // - calcul de l extremum sur la surface: |
afed7fd7 |
214 | |
215 | UV(1) = aParamArray1->Value(NoU); |
216 | UV(2) = aParamArray2->Value(NoV); |
7fd59977 |
217 | |
218 | math_FunctionSetRoot S (myF,UV,Tol,UVinf,UVsup); |
219 | |
220 | |
221 | // - mise a jour du tableau TbSel |
222 | for (Nu = NoU-1; Nu <= NoU+1; Nu++) { |
223 | for (Nv = NoV-1; Nv <= NoV+1; Nv++) { |
224 | TbSel(Nu,Nv) = 1; |
225 | } |
226 | } |
227 | } |
228 | } // if (TbSel(NoU,NoV) |
229 | } // for (NoV = 1; ... |
230 | } // for (NoU = 1; ... |
231 | /* |
232 | c- Calcul des maxima: |
233 | ----------------- |
234 | c.a) Initialisations: |
235 | */ |
236 | // - des 'bords' du tableau TbDist2 |
237 | for (NoV = 0; NoV <= aNbV+1; NoV++) { |
238 | TbDist2(0,NoV) = RealFirst(); |
239 | TbDist2(aNbU+1,NoV) = RealFirst(); |
240 | } |
241 | for (NoU = 1; NoU <= aNbU; NoU++) { |
242 | TbDist2(NoU,0) = RealFirst(); |
243 | TbDist2(NoU,aNbV+1) = RealFirst(); |
244 | } |
245 | |
246 | // - du tableau TbSel(0,aNbU+1,0,aNbV+1) de selection des points |
247 | TbSel.Init(0); |
248 | /*for (NoU = 0; NoU <= aNbU+1; NoU++) { |
249 | for (NoV = 0; NoV <= aNbV+1; NoV++) { |
250 | TbSel(NoU,NoV) = 0; |
251 | } |
252 | }*/ |
253 | /* |
254 | c.b) Calcul des maxima: |
255 | */ |
256 | // - recherche d un maximum sur la grille |
257 | for (NoU = 1; NoU <= aNbU; NoU++) { |
258 | for (NoV = 1; NoV <= aNbV; NoV++) { |
259 | if (TbSel(NoU,NoV) == 0) { |
260 | Dist2 = TbDist2(NoU,NoV); |
261 | if ((TbDist2(NoU-1,NoV-1) <= Dist2) && |
262 | (TbDist2(NoU-1,NoV ) <= Dist2) && |
263 | (TbDist2(NoU-1,NoV+1) <= Dist2) && |
264 | (TbDist2(NoU ,NoV-1) <= Dist2) && |
265 | (TbDist2(NoU ,NoV+1) <= Dist2) && |
266 | (TbDist2(NoU+1,NoV-1) <= Dist2) && |
267 | (TbDist2(NoU+1,NoV ) <= Dist2) && |
268 | (TbDist2(NoU+1,NoV+1) <= Dist2)) { |
269 | |
270 | // - calcul de l extremum sur la surface: |
afed7fd7 |
271 | |
272 | UV(1) = aParamArray1->Value(NoU); |
273 | UV(2) = aParamArray2->Value(NoV); |
7fd59977 |
274 | |
275 | math_FunctionSetRoot S (myF,UV,Tol,UVinf,UVsup); |
276 | |
277 | // - mise a jour du tableau TbSel |
278 | for (Nu = NoU-1; Nu <= NoU+1; Nu++) { |
279 | for (Nv = NoV-1; Nv <= NoV+1; Nv++) { |
280 | TbSel(Nu,Nv) = 1; |
281 | } |
282 | } |
283 | } |
284 | } // if (TbSel(NoU,NoV)) |
285 | } // for (NoV = 1; ...) |
286 | } // for (NoU = 1; ...) |
287 | myDone = Standard_True; |
288 | } |
289 | //============================================================================= |
290 | |
291 | Standard_Boolean Extrema_GenExtCC::IsDone () const { return myDone; } |
292 | //============================================================================= |
293 | |
294 | Standard_Integer Extrema_GenExtCC::NbExt () const |
295 | { |
296 | StdFail_NotDone_Raise_if (!myDone, "Extrema_GenExtCC::NbExt()") |
297 | return myF.NbExt(); |
298 | } |
299 | //============================================================================= |
300 | |
301 | Standard_Real Extrema_GenExtCC::SquareDistance (const Standard_Integer N) const |
302 | { |
303 | StdFail_NotDone_Raise_if (!myDone, "Extrema_GenExtCC::SquareDistance()") |
304 | Standard_OutOfRange_Raise_if ((N < 1 || N > NbExt()), "Extrema_GenExtCC::SquareDistance()") |
305 | return myF.SquareDistance(N); |
306 | } |
307 | //============================================================================= |
308 | |
309 | void Extrema_GenExtCC::Points (const Standard_Integer N, |
310 | POnC& P1, POnC& P2) const |
311 | { |
312 | StdFail_NotDone_Raise_if (!myDone, "Extrema_GenExtCC::SquareDistance()") |
313 | Standard_OutOfRange_Raise_if ((N < 1 || N > NbExt()), "Extrema_GenExtCC::SquareDistance()") |
314 | myF.Points(N,P1,P2); |
315 | } |