0023024: Update headers of OCCT files
[occt.git] / src / Extrema / Extrema_GenExtPS.cxx
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
21
22 //  Modified by skv - Thu Sep 30 15:21:07 2004 OCC593
23
24
25 #include <Extrema_GenExtPS.ixx>
26 #include <StdFail_NotDone.hxx>
27 #include <Standard_OutOfRange.hxx>
28 #include <TColStd_Array2OfInteger.hxx>
29 #include <TColStd_Array2OfReal.hxx>
30 #include <TColgp_Array2OfPnt.hxx>
31 #include <math_FunctionSetRoot.hxx>
32 #include <math_Vector.hxx>
33 #include <math_NewtonFunctionSetRoot.hxx>
34 #include <GeomAbs_IsoType.hxx>
35 #include <Bnd_Sphere.hxx>
36 #include <Extrema_HUBTreeOfSphere.hxx>
37 #include <Extrema_ExtFlag.hxx>
38 #include <Bnd_Array1OfSphere.hxx>
39 #include <Bnd_HArray1OfSphere.hxx>
40
41 //IMPLEMENT_HARRAY1(Extrema_HArray1OfSphere)
42
43
44 class Bnd_SphereUBTreeSelector : public Extrema_UBTreeOfSphere::Selector
45 {
46  public:
47
48   Bnd_SphereUBTreeSelector (const Handle(Bnd_HArray1OfSphere)& theSphereArray,
49 Bnd_Sphere& theSol)
50     : myXYZ(0,0,0),
51       mySphereArray(theSphereArray),
52       mySol(theSol)
53   {
54     //myXYZ = gp_Pnt(0, 0, 0);    
55   }
56
57   void DefineCheckPoint( const gp_Pnt& theXYZ )
58   { myXYZ = theXYZ; }
59
60   Bnd_Sphere& Sphere() const
61   { return mySol; }
62
63   virtual Standard_Boolean Reject( const Bnd_Sphere &theBnd ) const = 0;
64   
65   virtual Standard_Boolean Accept(const Standard_Integer& theObj) = 0;
66
67  protected:
68   gp_Pnt                      myXYZ;
69   const Handle(Bnd_HArray1OfSphere)& mySphereArray;
70   Bnd_Sphere&                                            mySol;
71
72 };
73
74 class Bnd_SphereUBTreeSelectorMin : public Bnd_SphereUBTreeSelector
75 {
76 public:
77   Bnd_SphereUBTreeSelectorMin (const Handle(Bnd_HArray1OfSphere)& theSphereArray,
78                 Bnd_Sphere& theSol)
79                 : Bnd_SphereUBTreeSelector(theSphereArray, theSol),
80                   myMinDist(RealLast())
81   {}
82   
83   void SetMinDist( const Standard_Real theMinDist )
84   { myMinDist = theMinDist; }
85
86   Standard_Real MinDist() const
87   { return myMinDist; }
88
89   Standard_Boolean Reject( const Bnd_Sphere &theBnd ) const
90   { 
91     Bnd_SphereUBTreeSelectorMin* me =
92       const_cast<Bnd_SphereUBTreeSelectorMin*>(this);
93     // myMinDist is decreased each time a nearer object is found
94     return theBnd.IsOut( myXYZ.XYZ(), me->myMinDist );
95   }
96
97   Standard_Boolean Accept(const Standard_Integer&);
98
99 private:
100         Standard_Real   myMinDist;
101 };
102
103 Standard_Boolean Bnd_SphereUBTreeSelectorMin::Accept(const Standard_Integer& theInd)
104 {
105   const Bnd_Sphere& aSph = mySphereArray->Value(theInd);
106   Standard_Real aCurDist;
107
108     if ( (aCurDist = aSph.SquareDistance(myXYZ.XYZ())) < mySol.SquareDistance(myXYZ.XYZ()) )
109     {
110       mySol = aSph;
111       if ( aCurDist < myMinDist ) 
112         myMinDist = aCurDist;
113
114       return Standard_True;
115     }
116
117   return Standard_False;
118 }
119
120 class Bnd_SphereUBTreeSelectorMax : public Bnd_SphereUBTreeSelector
121 {
122 public:
123   Bnd_SphereUBTreeSelectorMax (const Handle(Bnd_HArray1OfSphere)& theSphereArray,
124                 Bnd_Sphere& theSol)
125                 : Bnd_SphereUBTreeSelector(theSphereArray, theSol),
126                   myMaxDist(0)
127   {}
128
129   void SetMaxDist( const Standard_Real theMaxDist )
130   { myMaxDist = theMaxDist; }
131
132   Standard_Real MaxDist() const
133   { return myMaxDist; }
134
135   Standard_Boolean Reject( const Bnd_Sphere &theBnd ) const
136   { 
137     Bnd_SphereUBTreeSelectorMax* me =
138       const_cast<Bnd_SphereUBTreeSelectorMax*>(this);
139     // myMaxDist is decreased each time a nearer object is found
140     return theBnd.IsOut( myXYZ.XYZ(), me->myMaxDist );
141   }
142
143   Standard_Boolean Accept(const Standard_Integer&);
144
145 private:
146         Standard_Real   myMaxDist;
147 };
148
149 Standard_Boolean Bnd_SphereUBTreeSelectorMax::Accept(const Standard_Integer& theInd)
150 {
151   const Bnd_Sphere& aSph = mySphereArray->Value(theInd);
152   Standard_Real aCurDist;
153
154     if ( (aCurDist = aSph.SquareDistance(myXYZ.XYZ())) > mySol.SquareDistance(myXYZ.XYZ()) )
155     {
156       mySol = aSph;
157       if ( aCurDist > myMaxDist ) 
158         myMaxDist = aCurDist;
159
160       return Standard_True;
161     }
162
163   return Standard_False;
164 }
165
166
167
168 //=============================================================================
169
170 /*-----------------------------------------------------------------------------
171 Function:
172    Find all extremum distances between point P and surface
173   S using sampling (NbU,NbV).
174
175 Method:
176    The algorithm bases on the hypothesis that sampling is precise enough, 
177   if there exist N extreme distances between the point and the surface,
178   so there also exist N extrema between the point and the grid.
179   So, the algorithm consists in starting from extrema of the grid to find the 
180   extrema of the surface.
181   The extrema are calculated by the algorithm math_FunctionSetRoot with the
182   following arguments:
183   - F: Extrema_FuncExtPS created from P and S,
184   - UV: math_Vector the components which of are parameters of the extremum on the 
185     grid,
186   - Tol: Min(TolU,TolV), (Prov.:math_FunctionSetRoot does not autorize a vector)
187   - UVinf: math_Vector the components which of are lower limits of u and v,
188   - UVsup: math_Vector the components which of are upper limits of u and v.
189
190 Processing:
191   a- Creation of the table of distances (TbDist(0,NbU+1,0,NbV+1)):
192      The table is expanded at will; lines 0 and NbU+1 and
193      columns 0 and NbV+1 are initialized at RealFirst() or RealLast()
194      to simplify the tests carried out at stage b
195      (there is no need to test if the point is on border of the grid).
196   b- Calculation of extrema:
197      First the minimums and then the maximums are found. These 2 procedured 
198      pass in a similar way:
199   b.a- Initialization:
200       - 'borders' of table  TbDist (RealLast() in case of minimums
201         and  RealLast() in case of maximums),
202       - table TbSel(0,NbU+1,0,NbV+1) of selection of points for 
203         calculation of local extremum (0). When a point will selected,
204         it will not be selectable, as well as the ajacent points 
205         (8 at least). The corresponding addresses will be set to 1.
206   b.b- Calculation of minimums (or maximums):
207        All distances from table TbDist are parsed in a loop:
208       - search minimum (or maximum) in the grid,
209       - calculate extremum on the surface,
210       - update table TbSel.
211 -----------------------------------------------------------------------------*/
212
213 static Standard_Boolean IsoIsDeg  (const Adaptor3d_Surface& S,
214                                    const Standard_Real      Param,
215                                    const GeomAbs_IsoType    IT,
216                                    const Standard_Real      TolMin,
217                                    const Standard_Real      TolMax) 
218 {
219     Standard_Real U1=0.,U2=0.,V1=0.,V2=0.,T;
220     Standard_Boolean Along = Standard_True;
221     U1 = S.FirstUParameter();
222     U2 = S.LastUParameter();
223     V1 = S.FirstVParameter();
224     V2 = S.LastVParameter();
225     gp_Vec D1U,D1V;
226     gp_Pnt P;
227     Standard_Real Step,D1NormMax;
228     if (IT == GeomAbs_IsoV) 
229     {
230       Step = (U2 - U1)/10;
231       D1NormMax=0.;
232       for (T=U1;T<=U2;T=T+Step) 
233       {
234         S.D1(T,Param,P,D1U,D1V);
235         D1NormMax=Max(D1NormMax,D1U.Magnitude());
236       }
237
238       if (D1NormMax >TolMax || D1NormMax < TolMin ) 
239            Along = Standard_False;
240     }
241     else 
242     {
243       Step = (V2 - V1)/10;
244       D1NormMax=0.;
245       for (T=V1;T<=V2;T=T+Step) 
246       {
247         S.D1(Param,T,P,D1U,D1V);
248         D1NormMax=Max(D1NormMax,D1V.Magnitude());
249       }
250
251       if (D1NormMax >TolMax || D1NormMax < TolMin ) 
252            Along = Standard_False;
253
254
255     }
256     return Along;
257 }
258 //----------------------------------------------------------
259 Extrema_GenExtPS::Extrema_GenExtPS() 
260 {
261   myDone = Standard_False;
262   myInit = Standard_False;
263   myFlag = Extrema_ExtFlag_MINMAX;
264   myAlgo = Extrema_ExtAlgo_Grad;
265 }
266
267
268 Extrema_GenExtPS::Extrema_GenExtPS (const gp_Pnt&          P,
269                               const Adaptor3d_Surface& S,
270                               const Standard_Integer NbU, 
271                               const Standard_Integer NbV,
272                               const Standard_Real    TolU, 
273                               const Standard_Real    TolV,
274                               const Extrema_ExtFlag F,
275                               const Extrema_ExtAlgo A) 
276   : myF (P,S), myFlag(F), myAlgo(A)
277 {
278   Initialize(S, NbU, NbV, TolU, TolV);
279   Perform(P);
280 }
281
282 Extrema_GenExtPS::Extrema_GenExtPS (const gp_Pnt&          P,
283                               const Adaptor3d_Surface& S,
284                               const Standard_Integer NbU, 
285                               const Standard_Integer NbV,
286                               const Standard_Real    Umin,
287                               const Standard_Real    Usup,
288                               const Standard_Real    Vmin,
289                               const Standard_Real    Vsup,
290                               const Standard_Real    TolU, 
291                               const Standard_Real    TolV,
292                               const Extrema_ExtFlag F,
293                               const Extrema_ExtAlgo A) 
294   : myF (P,S), myFlag(F), myAlgo(A)
295 {
296   Initialize(S, NbU, NbV, Umin, Usup, Vmin, Vsup, TolU, TolV);
297   Perform(P);
298 }
299
300
301 void Extrema_GenExtPS::Initialize(const Adaptor3d_Surface& S,
302                                   const Standard_Integer NbU, 
303                                   const Standard_Integer NbV,
304                                   const Standard_Real    TolU, 
305                                   const Standard_Real    TolV)
306 {
307   myumin = S.FirstUParameter();
308   myusup = S.LastUParameter();
309   myvmin = S.FirstVParameter();
310   myvsup = S.LastVParameter();
311   Initialize(S,NbU,NbV,myumin,myusup,myvmin,myvsup,TolU,TolV);
312 }
313
314
315 void Extrema_GenExtPS::Initialize(const Adaptor3d_Surface& S,
316                                   const Standard_Integer NbU, 
317                                   const Standard_Integer NbV,
318                                   const Standard_Real    Umin,
319                                   const Standard_Real    Usup,
320                                   const Standard_Real    Vmin,
321                                   const Standard_Real    Vsup,
322                                   const Standard_Real    TolU, 
323                                   const Standard_Real    TolV)
324 {
325   myInit = Standard_True;
326   myS = (Adaptor3d_SurfacePtr)&S;
327   myusample = NbU;
328   myvsample = NbV;
329   mytolu = TolU;
330   mytolv = TolV;
331   myumin = Umin;
332   myusup = Usup;
333   myvmin = Vmin;
334   myvsup = Vsup;
335
336   if ((myusample < 2) ||
337       (myvsample < 2)) { Standard_OutOfRange::Raise(); }
338
339   myF.Initialize(S);
340
341   mySphereUBTree.Nullify();
342
343   if(myAlgo == Extrema_ExtAlgo_Grad)
344   {
345           //If flag was changed and extrema not reinitialized Extrema would fail
346     mypoints = new TColgp_HArray2OfPnt(0,myusample+1,0,myvsample+1);
347   Standard_Real PasU = myusup - myumin;
348   Standard_Real PasV = myvsup - myvmin;
349   Standard_Real U0 = PasU / myusample / 100.;
350   Standard_Real V0 = PasV / myvsample / 100.;
351   gp_Pnt P1;
352   PasU = (PasU - U0) / (myusample - 1);
353   PasV = (PasV - V0) / (myvsample - 1);
354   U0 = U0/2. + myumin;
355   V0 = V0/2. + myvmin;
356
357 // Calculation of distances
358
359   Standard_Integer NoU, NoV;
360   Standard_Real U, V;
361   for ( NoU = 1, U = U0; NoU <= myusample; NoU++, U += PasU) {
362     for ( NoV = 1, V = V0; NoV <= myvsample; NoV++, V += PasV) {
363       P1 = myS->Value(U, V);
364       mypoints->SetValue(NoU,NoV,P1);
365     }
366   }
367   }
368
369   //mypoints = new TColgp_HArray2OfPnt(0,myusample+1,0,myvsample+1);
370
371 /*
372 a- Constitution of the table of distances (TbDist(0,myusample+1,0,myvsample+1)):
373    ---------------------------------------------------------------
374 */
375
376 // Parameterisation of the sample
377
378
379 }
380
381 void Extrema_GenExtPS::BuildTree()
382 {
383   // if tree already exists, assume it is already correctly filled
384   if ( ! mySphereUBTree.IsNull() )
385     return;
386
387   Standard_Real PasU = myusup - myumin;
388   Standard_Real PasV = myvsup - myvmin;
389   Standard_Real U0 = PasU / myusample / 100.;
390   Standard_Real V0 = PasV / myvsample / 100.;
391   gp_Pnt P1;
392   PasU = (PasU - U0) / (myusample - 1);
393   PasV = (PasV - V0) / (myvsample - 1);
394   U0 = U0/2. + myumin;
395   V0 = V0/2. + myvmin;
396
397   // Calculation of distances
398   mySphereUBTree = new Extrema_UBTreeOfSphere;
399   Extrema_UBTreeFillerOfSphere aFiller(*mySphereUBTree);
400   Standard_Integer i = 0;
401   Standard_Real U, V;
402   mySphereArray = new Bnd_HArray1OfSphere(0, myusample * myvsample);
403   Standard_Integer NoU, NoV;
404   for ( NoU = 1, U = U0; NoU <= myusample; NoU++, U += PasU) {
405     for ( NoV = 1, V = V0; NoV <= myvsample; NoV++, V += PasV) {
406       P1 = myS->Value(U, V);
407       Bnd_Sphere aSph(P1.XYZ(), 0/*mytolu < mytolv ? mytolu : mytolv*/, NoU, NoV);
408       aFiller.Add(i, aSph);
409       mySphereArray->SetValue( i, aSph );
410       i++;
411     }
412   }
413   aFiller.Fill();
414 }
415
416 void Extrema_GenExtPS::FindSolution(const gp_Pnt& P, const math_Vector& UV, const Standard_Real PasU, const Standard_Real PasV, const Extrema_ExtFlag f)
417 {
418   math_Vector Tol(1,2);
419   Tol(1) = mytolu;
420   Tol(2) = mytolv;
421
422   math_Vector UVinf(1,2), UVsup(1,2);
423   UVinf(1) = myumin;
424   UVinf(2) = myvmin;
425   UVsup(1) = myusup;
426   UVsup(2) = myvsup;
427
428   math_Vector errors(1,2);
429   math_Vector root(1, 2);
430   Standard_Real eps = 1.e-9;
431   Standard_Integer nbsubsample = 11;
432
433   Standard_Integer aNbMaxIter = 100;
434
435   gp_Pnt PStart = myS->Value(UV(1), UV(2));
436   Standard_Real DistStart = P.SquareDistance(PStart);
437   Standard_Real DistSol = DistStart;
438   
439   math_FunctionSetRoot S (myF,UV,Tol,UVinf,UVsup, aNbMaxIter);
440   Standard_Boolean ToResolveOnSubgrid = Standard_False;
441   if (f == Extrema_ExtFlag_MIN)
442   {
443     if(S.IsDone())
444     {
445       root = S.Root();
446       myF.Value(root, errors);
447       gp_Pnt PSol = myS->Value(root(1), root(2));
448       DistSol = P.SquareDistance(PSol);
449       if(Abs(errors(1)) > eps || Abs(errors(2)) > eps || DistStart < DistSol)
450         //try to improve solution on subgrid of sample points
451         ToResolveOnSubgrid = Standard_True;
452     }
453     else
454       ToResolveOnSubgrid = Standard_True;
455     
456     if (ToResolveOnSubgrid)
457     {
458       Standard_Real u1 = Max(UV(1) - PasU, myumin), u2 = Min(UV(1) + PasU, myusup);
459       Standard_Real v1 = Max(UV(2) - PasV, myvmin), v2 = Min(UV(2) + PasV, myvsup);
460       
461       if(u2 - u1 < 2.*PasU) {
462         if(Abs(u1 - myumin) < 1.e-9) {
463           u2 = u1 + 2.*PasU;
464           u2 = Min(u2, myusup);
465         }
466         if(Abs(u2 - myusup) < 1.e-9) {
467           u1 = u2 - 2.*PasU;
468           u1 = Max(u1, myumin);
469         }
470       }
471       
472       if(v2 - v1 < 2.*PasV) {
473         if(Abs(v1 - myvmin) < 1.e-9) {
474           v2 = v1 + 2.*PasV;
475           v2 = Min(v2, myvsup);
476         }
477         if(Abs(v2 - myvsup) < 1.e-9) {
478           v1 = v2 - 2.*PasV;
479           v1 = Max(v1, myvmin);
480         }
481       }
482       
483       Standard_Real du = (u2 - u1)/(nbsubsample-1);
484       Standard_Real dv = (v2 - v1)/(nbsubsample-1);
485       Standard_Real u, v;
486       Standard_Real dist;
487       
488       Standard_Boolean NewSolution = Standard_False;
489       Standard_Integer Nu, Nv;
490       for (Nu = 1, u = u1; Nu < nbsubsample; Nu++, u += du) {
491         for (Nv = 1, v = v1; Nv < nbsubsample; Nv++, v += dv) {
492           gp_Pnt Puv = myS->Value(u, v);
493           dist = P.SquareDistance(Puv);
494           
495           if(dist < DistSol) {
496             UV(1) = u;
497             UV(2) = v;
498             NewSolution = Standard_True;
499             DistSol = dist;
500           }
501         }
502       }
503       
504       if(NewSolution) {
505         //try to precise
506         math_FunctionSetRoot S (myF,UV,Tol,UVinf,UVsup, aNbMaxIter);
507       }
508     } //end of if (ToResolveOnSubgrid)
509   } //end of if (f == Extrema_ExtFlag_MIN)
510   
511   myDone = Standard_True;
512 }
513
514 void Extrema_GenExtPS::SetFlag(const Extrema_ExtFlag F)
515 {
516   myFlag = F;
517 }
518
519 void Extrema_GenExtPS::SetAlgo(const Extrema_ExtAlgo A)
520 {
521   myAlgo = A;
522 }
523
524 void Extrema_GenExtPS::Perform(const gp_Pnt& P) 
525 {  
526   //BuildTree();
527   myDone = Standard_False;
528   myF.SetPoint(P);
529
530   Standard_Real PasU = myusup - myumin;
531   Standard_Real PasV = myvsup - myvmin;
532   Standard_Real U, U0 = PasU / myusample / 100.;
533   Standard_Real V, V0 = PasV / myvsample / 100.;
534   PasU = (PasU - U0) / (myusample - 1);
535   PasV = (PasV - V0) / (myvsample - 1);
536   U0 = U0/2.+myumin;
537   V0 = V0/2.+myvmin;
538
539   //math_Vector Tol(1, 2);
540   math_Vector UV(1,2);
541
542   if(myAlgo == Extrema_ExtAlgo_Grad)
543   {
544     Standard_Integer NoU,NoV;
545
546     TColStd_Array2OfReal TheDist(0, myusample+1, 0, myvsample+1);
547     for ( NoU = 1, U = U0; NoU <= myusample; NoU++, U += PasU) {
548       for ( NoV = 1, V = V0; NoV <= myvsample; NoV++, V += PasV) {
549         TheDist(NoU, NoV) = P.SquareDistance(mypoints->Value(NoU, NoV));
550       }
551     }
552
553     TColStd_Array2OfInteger TbSel(0,myusample+1,0,myvsample+1);
554     TbSel.Init(0);
555
556     Standard_Real Dist;
557
558     if(myFlag == Extrema_ExtFlag_MIN || myFlag == Extrema_ExtFlag_MINMAX) 
559     {
560       for (NoV = 0; NoV <= myvsample+1; NoV++) {
561         TheDist(0,NoV) = RealLast();
562         TheDist(myusample+1,NoV) = RealLast();
563       }
564       for (NoU = 1; NoU <= myusample; NoU++) {
565         TheDist(NoU,0) = RealLast();
566         TheDist(NoU,myvsample+1) = RealLast();
567       }
568       for (NoU = 1; NoU <= myusample; NoU++) {
569         for (NoV = 1; NoV <= myvsample; NoV++) {
570           if (TbSel(NoU,NoV) == 0) {
571             Dist = TheDist(NoU,NoV);
572             if ((TheDist(NoU-1,NoV-1) >= Dist) &&
573               (TheDist(NoU-1,NoV  ) >= Dist) &&
574               (TheDist(NoU-1,NoV+1) >= Dist) &&
575               (TheDist(NoU  ,NoV-1) >= Dist) &&
576               (TheDist(NoU  ,NoV+1) >= Dist) &&
577               (TheDist(NoU+1,NoV-1) >= Dist) &&
578               (TheDist(NoU+1,NoV  ) >= Dist) &&
579               (TheDist(NoU+1,NoV+1) >= Dist)) {
580                 //Create array of UV vectors to calculate min
581                 UV(1) = U0 + (NoU - 1) * PasU;
582                 UV(2) = V0 + (NoV - 1) * PasV;
583                 FindSolution(P, UV, PasU, PasV, Extrema_ExtFlag_MIN);
584             }
585           }
586         }
587       }
588     }
589     
590     if(myFlag == Extrema_ExtFlag_MAX || myFlag == Extrema_ExtFlag_MINMAX)
591     {
592       for (NoV = 0; NoV <= myvsample+1; NoV++) {
593         TheDist(0,NoV) = RealFirst();
594         TheDist(myusample+1,NoV) = RealFirst();
595       }
596       for (NoU = 1; NoU <= myusample; NoU++) {
597         TheDist(NoU,0) = RealFirst();
598         TheDist(NoU,myvsample+1) = RealFirst();
599       }
600       for (NoU = 1; NoU <= myusample; NoU++) {
601         for (NoV = 1; NoV <= myvsample; NoV++) {
602           if (TbSel(NoU,NoV) == 0) {
603             Dist = TheDist(NoU,NoV);
604             if ((TheDist(NoU-1,NoV-1) <= Dist) &&
605               (TheDist(NoU-1,NoV  ) <= Dist) &&
606               (TheDist(NoU-1,NoV+1) <= Dist) &&
607               (TheDist(NoU  ,NoV-1) <= Dist) &&
608               (TheDist(NoU  ,NoV+1) <= Dist) &&
609               (TheDist(NoU+1,NoV-1) <= Dist) &&
610               (TheDist(NoU+1,NoV  ) <= Dist) &&
611               (TheDist(NoU+1,NoV+1) <= Dist)) {
612                 //Create array of UV vectors to calculate max
613                 UV(1) = U0 + (NoU - 1) * PasU;
614                 UV(2) = V0 + (NoV - 1) * PasV;
615                 FindSolution(P, UV, PasU, PasV, Extrema_ExtFlag_MAX);
616             }
617           }
618         }
619       }
620     }
621   }
622   else
623   {
624     BuildTree();
625     if(myFlag == Extrema_ExtFlag_MIN || myFlag == Extrema_ExtFlag_MINMAX)
626     {
627       Bnd_Sphere aSol = mySphereArray->Value(0);
628       Bnd_SphereUBTreeSelectorMin aSelector(mySphereArray, aSol);
629       //aSelector.SetMaxDist( RealLast() );
630       aSelector.DefineCheckPoint( P );
631       Standard_Integer aNbSel = mySphereUBTree->Select( aSelector );
632       //TODO: check if no solution in binary tree
633       Bnd_Sphere& aSph = aSelector.Sphere();
634
635       UV(1) = U0 + (aSph.U() - 1) * PasU;
636       UV(2) = V0 + (aSph.V() - 1) * PasV;
637
638       FindSolution(P, UV, PasU, PasV, Extrema_ExtFlag_MIN);
639     }
640     if(myFlag == Extrema_ExtFlag_MAX || myFlag == Extrema_ExtFlag_MINMAX)
641     {
642       Bnd_Sphere aSol = mySphereArray->Value(0);
643       Bnd_SphereUBTreeSelectorMax aSelector(mySphereArray, aSol);
644       //aSelector.SetMaxDist( RealLast() );
645       aSelector.DefineCheckPoint( P );
646       Standard_Integer aNbSel = mySphereUBTree->Select( aSelector );
647       //TODO: check if no solution in binary tree
648       Bnd_Sphere& aSph = aSelector.Sphere();
649
650       UV(1) = U0 + (aSph.U() - 1) * PasU;
651       UV(2) = V0 + (aSph.V() - 1) * PasV;
652
653       FindSolution(P, UV, PasU, PasV, Extrema_ExtFlag_MAX);
654     }
655   }
656 }
657 //=============================================================================
658
659 Standard_Boolean Extrema_GenExtPS::IsDone () const { return myDone; }
660 //=============================================================================
661
662 Standard_Integer Extrema_GenExtPS::NbExt () const
663 {
664   if (!IsDone()) { StdFail_NotDone::Raise(); }
665   return myF.NbExt();
666 }
667 //=============================================================================
668
669 Standard_Real Extrema_GenExtPS::SquareDistance (const Standard_Integer N) const
670 {
671   if (!IsDone()) { StdFail_NotDone::Raise(); }
672   return myF.SquareDistance(N);
673 }
674 //=============================================================================
675
676 Extrema_POnSurf Extrema_GenExtPS::Point (const Standard_Integer N) const
677 {
678   if (!IsDone()) { StdFail_NotDone::Raise(); }
679   return myF.Point(N);
680 }
681 //=============================================================================