src/Extrema/Extrema_GenExtCC.gxx

   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 #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,
  56                               const Standard_Real /*TolU*/,
  57                               const Standard_Real /*TolV*/) : myF (C1,C2), myDone (Standard_False)
  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
 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();
 175
 176   myF.SubIntervalInitialize(UVinf,UVsup);
 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;
 198   const Handle(TColStd_HArray1OfReal)& aParamArray1 = aCache1->Parameters();
 199   const Handle(TColStd_HArray1OfReal)& aParamArray2 = aCache2->Parameters();
 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:
 214
 215           UV(1) = aParamArray1->Value(NoU);
 216           UV(2) = aParamArray2->Value(NoV);
 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:
 271
 272           UV(1) = aParamArray1->Value(NoU);
 273           UV(2) = aParamArray2->Value(NoV);
 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 }