src/MAT2d/MAT2d_MiniPath.cxx

   1 // Created on: 1993-10-07
   2 // Created by: Yves FRICAUD
   3 // Copyright (c) 1993-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 <MAT2d_MiniPath.ixx>
  23 #include <MAT2d_Connexion.hxx>
  24 #include <MAT2d_Array2OfConnexion.hxx>
  25 #include <Extrema_POnCurv2d.hxx>
  26 #include <Extrema_ExtCC2d.hxx>
  27 #include <Extrema_ExtPC2d.hxx>
  28 #include <Geom2dAdaptor_Curve.hxx>
  29 #include <Geom2d_Point.hxx>
  30 #include <Geom2d_CartesianPoint.hxx>
  31 #include <TColStd_SequenceOfInteger.hxx>
  32 #include <TColGeom2d_SequenceOfGeometry.hxx>
  33 #include <Standard_NotImplemented.hxx>
  34
  35 //============================================================================
  36 //function : MAT2d_MiniPath()
  37 //purpose  :
  38 //============================================================================
  39 MAT2d_MiniPath::MAT2d_MiniPath()
  40 {
  41 }
  42
  43 //============================================================================
  44 //function : Perform
  45 //purpose  : Calcul du chemin reliant les differents elements de <aFigure>.
  46 //           le chemin part de la ligne <IndStart>.
  47 //           <Sense> = True les lignes sont orientes dans le sens trigo.
  48 //============================================================================
  49 void MAT2d_MiniPath::Perform
  50   (const MAT2d_SequenceOfSequenceOfGeometry& Figure,
  51    const Standard_Integer                    IndStart,
  52    const Standard_Boolean                    Sense)
  53 {
  54
  55   Standard_Integer         i,j;
  56   Standard_Integer         NbLines   = Figure.Length();
  57   MAT2d_Array2OfConnexion  Connexion (1,NbLines,1,NbLines);
  58
  59   indStart     = IndStart;
  60   theDirection = 1.;
  61   if (Sense) theDirection = -1.;
  62
  63   //----------------------------------------------------------------------
  64   // Calcul des connexions qui realisent le minimum de distance entre les
  65   // differents elements de la figure.
  66   //----------------------------------------------------------------------
  67   for (i = 1; i < NbLines; i++) {
  68     for (j =i+1; j <= NbLines; j++){
  69       Connexion(i,j) = MinimumL1L2(Figure,i,j);
  70       Connexion(j,i) = Connexion(i,j)->Reverse();
  71     }
  72   }
  73
  74   TColStd_SequenceOfInteger Set1;
  75   TColStd_SequenceOfInteger Set2;
  76   Standard_Real             DistS1S2;
  77   Standard_Integer          IndiceLine1,IndiceLine2;
  78   Standard_Integer          ISuiv =0,MinOnSet1 =0,MinOnSet2 =0;
  79   //---------------------------------------------------------------------------
  80   // - 0 Set1 est initialise avec la ligne de depart.
  81   //     Set2 contient toutes les autres.
  82   //---------------------------------------------------------------------------
  83
  84   Set1.Append(IndStart);
  85
  86   for (i=1 ; i<=NbLines ; i++){
  87     if (i != IndStart){
  88       Set2.Append(i);
  89     }
  90   }
  91
  92   //---------------------------------------------------------------------------
  93   // - 1 Recherche de la connexion C la plus courte entre Set1 et Set2.
  94   // - 2 La ligne de Set2 realisant le minimum de distance est inseree dans
  95   //     Set1 et supprime dans Set2.
  96   // - 3 Insertion de la connexion dans l ensemble des connexions.
  97   // - 4 Si Set2 est non vide retour en 1.
  98   //---------------------------------------------------------------------------
  99
 100   while (!Set2.IsEmpty()){
 101     DistS1S2 = RealLast();
 102     for (i = 1; i <= Set1.Length(); i++) {
 103       IndiceLine1 = Set1.Value(i);
 104       for (j = 1 ; j<= Set2.Length() ;j++) {
 105         IndiceLine2 = Set2.Value(j);
 106         if(Connexion(IndiceLine1,IndiceLine2)->Distance() < DistS1S2) {
 107           ISuiv     = j;
 108           DistS1S2  = Connexion(IndiceLine1,IndiceLine2)->Distance();
 109           MinOnSet1 = IndiceLine1;
 110           MinOnSet2 = IndiceLine2;
 111         }
 112       }
 113     }
 114     Set1.Append(Set2.Value(ISuiv));
 115     Set2.Remove(ISuiv);
 116     Append(Connexion(MinOnSet1,MinOnSet2));
 117   }
 118
 119   //----------------------------------------------------------------
 120   // Construction du chemin en parcourant l ensemble des connexions.
 121   //----------------------------------------------------------------
 122   RunOnConnexions() ;
 123 }
 124
 125
 126 //============================================================================
 127 //function : Append
 128 //purpose  : Insertion d une nouvelle connexion dans le chemin.
 129 //
 130 //           Les connexions et les lignes constituent un arbre dont
 131 //           - les noeuds sont les lignes.
 132 //           - les connexions sont les branches.
 133 //
 134 //============================================================================
 135 void MAT2d_MiniPath::Append(const Handle(MAT2d_Connexion)& C)
 136 {
 137   Handle(MAT2d_Connexion) CC;
 138
 139   if (!theConnexions.IsBound(C->IndexFirstLine())) {
 140     MAT2d_SequenceOfConnexion Seq;
 141     theConnexions.Bind(C->IndexFirstLine(),Seq);
 142     theConnexions(C->IndexFirstLine()).Append(C);
 143     theFather.Bind(C->IndexSecondLine(),C);
 144     return;
 145   }
 146
 147   MAT2d_SequenceOfConnexion& Seq  = theConnexions(C->IndexFirstLine());
 148   Standard_Integer IndexAfter     = 0;
 149   Standard_Integer NbConnexions   = Seq.Length();
 150
 151   for (Standard_Integer i = 1; i <= NbConnexions; i++) {
 152     CC = Seq.Value(i);
 153     if (CC->IsAfter(C,theDirection)){
 154       IndexAfter = i;
 155       break;
 156     }
 157   }
 158   //----------------------------------------------------------------------
 159   // Insertion de <C> avant <IAfter>.
 160   // Si <IAfter> = 0 => Pas de connexions apres <C> => <C> est la
 161   // derniere.
 162   //----------------------------------------------------------------------
 163   if (IndexAfter == 0) {
 164     Seq.Append(C);
 165   }
 166   else {
 167     Seq.InsertBefore(IndexAfter,C);
 168   }
 169   theFather.Bind(C->IndexSecondLine(),C);
 170   return;
 171 }
 172
 173 //============================================================================
 174 //function : Path
 175 //purpose  : Retour de la sequence de connexions definissant le chemin.
 176 //============================================================================
 177 const MAT2d_SequenceOfConnexion& MAT2d_MiniPath::Path() const
 178 {
 179   return thePath;
 180 }
 181
 182 //============================================================================
 183 //function : IsConnexionsFrom
 184 //purpose :
 185 //============================================================================
 186 Standard_Boolean MAT2d_MiniPath::IsConnexionsFrom
 187   (const Standard_Integer i) const
 188 {
 189   return (theConnexions.IsBound(i));
 190 }
 191
 192 //============================================================================
 193 //function : Connexions
 194 //purpose  : Retour de la sequence de connexions issue de la ligne <i>.
 195 //============================================================================
 196 MAT2d_SequenceOfConnexion& MAT2d_MiniPath::ConnexionsFrom
 197   (const Standard_Integer i)
 198 {
 199   return theConnexions.ChangeFind(i);
 200 }
 201
 202 //============================================================================
 203 //function : IsRoot
 204 //purpose  :
 205 //============================================================================
 206 Standard_Boolean MAT2d_MiniPath::IsRoot(const Standard_Integer ILine) const
 207 {
 208   return (ILine == indStart);
 209 }
 210
 211 //============================================================================
 212 //function : Father
 213 //purpose  : Retour de la premiere connexion qui arrive sur la ligne i
 214 //============================================================================
 215 Handle(MAT2d_Connexion) MAT2d_MiniPath::Father(const Standard_Integer ILine)
 216 {
 217   return theFather.ChangeFind(ILine);
 218 }
 219
 220
 221 //============================================================================
 222 //function : RunOnConnexions
 223 //purpose  : Construction de <thePath> en parcourant <theConnexions>.
 224 //============================================================================
 225 void MAT2d_MiniPath::RunOnConnexions()
 226 {
 227   Standard_Integer                  i;
 228   Handle(MAT2d_Connexion)           C;
 229   const MAT2d_SequenceOfConnexion&  SC = theConnexions(indStart);
 230
 231   thePath.Clear();
 232
 233   for ( i = 1; i <= SC.Length(); i++) {
 234     C = SC.Value(i);
 235     thePath.Append(C);
 236     ExploSons(thePath,C);
 237     thePath.Append(C->Reverse());
 238   }
 239 }
 240
 241 //============================================================================
 242 //function : ExploSons
 243 //purpose  :
 244 //============================================================================
 245 void MAT2d_MiniPath::ExploSons(      MAT2d_SequenceOfConnexion& CResult,
 246                                const Handle(MAT2d_Connexion)&   CRef   )
 247 {
 248   Standard_Integer                 i;
 249   Standard_Integer                 Index = CRef->IndexSecondLine();
 250
 251   if (!theConnexions.IsBound(Index)) return;
 252
 253   const MAT2d_SequenceOfConnexion& SC    = theConnexions(Index);
 254   Handle(MAT2d_Connexion)          CRR   = CRef->Reverse();
 255   Handle(MAT2d_Connexion)          C;
 256
 257   for ( i = 1; i <= SC.Length(); i++) {
 258     C = SC.Value(i);
 259     if (C->IsAfter(CRR,theDirection)) {
 260       CResult.Append(C);
 261       ExploSons(CResult,C);
 262       CResult.Append(C->Reverse());
 263     }
 264   }
 265
 266   for ( i = 1; i <= SC.Length(); i++) {
 267     C = SC.Value(i);
 268     if (!C->IsAfter(CRR,theDirection)) {
 269       CResult.Append(C);
 270       ExploSons(CResult,C);
 271       CResult.Append(C->Reverse());
 272     }
 273     else {
 274       break;
 275     }
 276   }
 277 }
 278
 279
 280 //============================================================================
 281 //function : MinimumL1L2
 282 //purpose  : Calcul de la connexion realisant le minimum de distance entre les
 283 //           lignes d indice <IL1> et <IL2> dans <Figure>.
 284 //============================================================================
 285 Handle(MAT2d_Connexion) MAT2d_MiniPath::MinimumL1L2
 286   (const MAT2d_SequenceOfSequenceOfGeometry& Figure,
 287    const Standard_Integer                    IL1,
 288    const Standard_Integer                    IL2) const
 289 {
 290   Extrema_POnCurv2d              PointOnCurv1,PointOnCurv2;
 291   Standard_Integer               IC1,IC2,IMinC1 =0,IMinC2 =0,i;
 292   Standard_Real                  DistL1L2_2,DistP1P2_2;
 293   Standard_Real                  ParameterOnC1 =0.,ParameterOnC2 =0.;
 294   TColGeom2d_SequenceOfGeometry  L1,L2;
 295   gp_Pnt2d                       Point1,Point2,P1,P2;
 296   Handle(Geom2d_Curve)           Item1;
 297   Handle(Geom2d_Curve)           Item2;
 298
 299   L1 = Figure.Value(IL1);
 300   L2 = Figure.Value(IL2);
 301
 302   DistL1L2_2 = RealLast();
 303
 304   //---------------------------------------------------------------------------
 305   // Calcul des extremas de distances entre les composants de L1 et de L2.
 306   //---------------------------------------------------------------------------
 307
 308   for (IC1 = 1; IC1 <= L1.Length(); IC1++) {
 309
 310     Handle(Standard_Type)   Type1 = L1.Value(IC1)->DynamicType();
 311     if (Type1 != STANDARD_TYPE(Geom2d_CartesianPoint)) {
 312       Item1 = Handle(Geom2d_Curve)::DownCast(L1.Value(IC1));
 313     }
 314     else {
 315         P1 = Handle(Geom2d_Point)::DownCast(L1.Value(IC1))->Pnt2d();
 316     }
 317
 318     for (IC2 = 1; IC2 <= L2.Length(); IC2++) {
 319
 320       Handle(Standard_Type)   Type2 = L2.Value(IC2)->DynamicType();
 321       if (Type2 != STANDARD_TYPE(Geom2d_CartesianPoint)) {
 322         Item2 = Handle(Geom2d_Curve)::DownCast(L2.Value(IC2));
 323       }
 324       else {
 325         P2 = Handle(Geom2d_Point)::DownCast(L2.Value(IC2))->Pnt2d();
 326       }
 327
 328       if (Type1 == STANDARD_TYPE(Geom2d_CartesianPoint) &&
 329           Type2 == STANDARD_TYPE(Geom2d_CartesianPoint)   ) {
 330         DistP1P2_2 = P1.SquareDistance(P2);
 331         if (DistP1P2_2 <= DistL1L2_2) {
 332           DistL1L2_2      = DistP1P2_2;
 333           IMinC1        = IC1;
 334           IMinC2        = IC2;
 335           Point1        = P1;
 336           Point2        = P2;
 337           ParameterOnC1 = 0.;
 338           ParameterOnC2 = 0.;
 339         }
 340       }
 341       else if (Type1 == STANDARD_TYPE(Geom2d_CartesianPoint)) {
 342         Geom2dAdaptor_Curve C2(Item2);
 343         Extrema_ExtPC2d Extremas(P1,C2);
 344         if (Extremas.IsDone()){
 345           for (i = 1; i <= Extremas.NbExt(); i++) {
 346             if (Extremas.SquareDistance(i) < DistL1L2_2) {
 347               DistL1L2_2    = Extremas.SquareDistance(i);
 348               IMinC1        = IC1;
 349               IMinC2        = IC2;
 350               PointOnCurv2  = Extremas.Point(i);
 351               ParameterOnC1 = 0.;
 352               ParameterOnC2 = PointOnCurv2.Parameter();
 353               Point1        = P1;
 354               Point2        = PointOnCurv2.Value();
 355             }
 356           }
 357         }
 358       }
 359       else if (Type2 == STANDARD_TYPE(Geom2d_CartesianPoint)) {
 360         Geom2dAdaptor_Curve C1(Item1);
 361         Extrema_ExtPC2d Extremas(P2,C1);
 362         if (Extremas.IsDone()){
 363           for (i=1;i<=Extremas.NbExt();i++) {
 364             if (Extremas.SquareDistance(i) < DistL1L2_2) {
 365               DistL1L2_2    = Extremas.SquareDistance(i);
 366               IMinC1        = IC1;
 367               IMinC2        = IC2;
 368               PointOnCurv1  = Extremas.Point(i);
 369               ParameterOnC2 = 0.;
 370               ParameterOnC1 = PointOnCurv1.Parameter();
 371               Point1        = PointOnCurv1.Value();
 372               Point2        = P2;
 373             }
 374           }
 375         }
 376       }
 377       else {
 378         Geom2dAdaptor_Curve C1(Item1);
 379         Geom2dAdaptor_Curve C2(Item2);
 380         Extrema_ExtCC2d Extremas(C1,C2);
 381         if (!Extremas.IsParallel() && Extremas.IsDone()){
 382           for ( i=1; i <= Extremas.NbExt(); i++) {
 383             if (Extremas.SquareDistance(i) < DistL1L2_2) {
 384               DistL1L2_2    = Extremas.SquareDistance(i);
 385               IMinC1        = IC1;
 386               IMinC2        = IC2;
 387               Extremas.Points(i,PointOnCurv1,PointOnCurv2);
 388               ParameterOnC1 = PointOnCurv1.Parameter();
 389               ParameterOnC2 = PointOnCurv2.Parameter();
 390               Point1        = PointOnCurv1.Value();
 391               Point2        = PointOnCurv2.Value();
 392             }
 393           }
 394         }
 395       }
 396     }
 397   }
 398   Handle(MAT2d_Connexion) ConnexionL1L2;
 399   ConnexionL1L2 = new MAT2d_Connexion(IL1,IL2,IMinC1,IMinC2,sqrt (DistL1L2_2),
 400                                       ParameterOnC1,ParameterOnC2,
 401                                       Point1,Point2);
 402   return ConnexionL1L2;
 403 }
 404
 405
 406
 407
 408
 409
 410
 411
 412
 413
 414
 415
 416
 417
 418
 419
 420
 421
 422
 423
 424
 425
 426