src/Bnd/Bnd_BoundSortBox2d.cxx

   1 // Created on: 1993-03-08
   2 // Created by: Didier PIFFAULT
   3 // Copyright (c) 1993-1999 Matra Datavision
   4 // Copyright (c) 1999-2014 OPEN CASCADE SAS
   5 //
   6 // This file is part of Open CASCADE Technology software library.
   7 //
   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
  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.
  13 //
  14 // Alternatively, this file may be used under the terms of Open CASCADE
  15 // commercial license or contractual agreement.
  16
  17
  18 #include <Bnd_Array1OfBox.hxx>
  19 #include <Bnd_BoundSortBox2d.hxx>
  20 #include <Bnd_Box2d.hxx>
  21 #include <Standard_MultiplyDefined.hxx>
  22 #include <Standard_NullValue.hxx>
  23 #include <TColStd_Array1OfListOfInteger.hxx>
  24 #include <TColStd_DataMapIteratorOfDataMapOfIntegerInteger.hxx>
  25 #include <TColStd_ListIteratorOfListOfInteger.hxx>
  26
  27 //=======================================================================
  28 //function : Bnd_BoundSortBox2d
  29 //purpose  :
  30 //=======================================================================
  31 Bnd_BoundSortBox2d::Bnd_BoundSortBox2d()
  32      : discrX(0), discrY(0)
  33 {}
  34
  35
  36 //=======================================================================
  37 //function : Initialize
  38 //purpose  :
  39 //=======================================================================
  40
  41 void Bnd_BoundSortBox2d::Initialize(const Bnd_Box2d& CompleteBox,
  42                                     const Handle(Bnd_HArray1OfBox2d)& SetOfBox)
  43 {
  44   myBox=CompleteBox;
  45   myBndComponents=SetOfBox;
  46   discrX=SetOfBox->Length();
  47   discrY=discrX;
  48
  49   Standard_Real xmin, ymin, xmax, ymax;
  50   Standard_Real middleX=0.;
  51   Standard_Real middleY=0.;
  52
  53   const Bnd_Array1OfBox2d & taBox=myBndComponents->Array1();
  54
  55   Standard_Integer labox;
  56   for (labox=taBox.Lower(); labox<=taBox.Upper(); labox++) {
  57     if (!taBox(labox).IsVoid()) {
  58       taBox.Value(labox).Get(xmin, ymin, xmax, ymax);
  59       middleX+=xmax-xmin;
  60       middleY+=ymax-ymin;
  61     }
  62   }
  63   middleX=middleX/taBox.Length();
  64   middleY=middleY/taBox.Length();
  65
  66   Standard_Real Xmax, Ymax;
  67   CompleteBox.Get(Xmin, Ymin, Xmax, Ymax);
  68   deltaX=(Xmax-Xmin)/(Standard_Real)discrX;
  69   deltaY=(Ymax-Ymin)/(Standard_Real)discrY;
  70
  71   if (middleX < Epsilon(100.)) {
  72     discrX=1;
  73     deltaX=Xmax-Xmin;
  74   }
  75   else if (middleX > deltaX) {
  76     discrX=(Standard_Integer)((Xmax-Xmin)/middleX);
  77     deltaX=middleX;
  78     discrX++;
  79   }
  80
  81   if (middleY < Epsilon(100.)) {
  82     discrY=1;
  83     deltaY=Ymax-Ymin;
  84   }
  85   else if (middleY > deltaY) {
  86     discrY=(Standard_Integer)((Ymax-Ymin)/middleY + 0.1);
  87     deltaY=middleY;
  88     discrY++;
  89   }
  90
  91   SortBoxes();
  92 }
  93
  94 //=======================================================================
  95 //function : Initialize
  96 //purpose  :
  97 //=======================================================================
  98
  99 void  Bnd_BoundSortBox2d::Initialize(const Handle(Bnd_HArray1OfBox2d)& SetOfBox)
 100 {
 101   myBndComponents=SetOfBox;
 102   discrX=SetOfBox->Length();
 103   discrY=discrX;
 104
 105   Standard_Real xmin, ymin, xmax, ymax;
 106   Standard_Real middleX=0.;
 107   Standard_Real middleY=0.;
 108
 109   const Bnd_Array1OfBox2d & taBox=myBndComponents->Array1();
 110
 111   Standard_Integer labox;
 112   for (labox=taBox.Lower(); labox<=taBox.Upper(); labox++) {
 113     if (!taBox(labox).IsVoid()) {
 114       myBox.Add(taBox(labox));
 115       taBox.Value(labox).Get(xmin, ymin, xmax, ymax);
 116       middleX+=xmax-xmin;
 117       middleY+=ymax-ymin;
 118     }
 119   }
 120   middleX=middleX/taBox.Length();
 121   middleY=middleY/taBox.Length();
 122
 123   Standard_Real Xmax, Ymax;
 124   myBox.Get(Xmin, Ymin, Xmax, Ymax);
 125   deltaX=(Xmax-Xmin)/(Standard_Real)discrX;
 126   deltaY=(Ymax-Ymin)/(Standard_Real)discrY;
 127
 128   if (middleX < Epsilon(100.)) {
 129     discrX=1;
 130     deltaX=Xmax-Xmin;
 131   }
 132   else if (middleX > deltaX) {
 133     discrX=(Standard_Integer)((Xmax-Xmin)/middleX);
 134     deltaX=middleX;
 135     discrX++;
 136   }
 137
 138   if (middleY < Epsilon(100.)) {
 139     discrY=1;
 140     deltaY=Ymax-Ymin;
 141   }
 142   else if (middleY > deltaY) {
 143     discrY=(Standard_Integer)((Ymax-Ymin)/middleY + 0.1);
 144     deltaY=middleY;
 145     discrY++;
 146   }
 147
 148   SortBoxes();
 149 }
 150
 151
 152 //=======================================================================
 153 //function : SortBoxes
 154 //purpose  :
 155 //=======================================================================
 156
 157 void  Bnd_BoundSortBox2d::SortBoxes()
 158 {
 159   Standard_NullValue_Raise_if (discrX+discrY <=0, "BoundSortBox2d nul!");
 160
 161   Standard_Integer labox, lacase, firstcase, lastcase;
 162   Standard_Real xmin, ymin, xmax, ymax;
 163   const  Bnd_Array1OfBox2d & taBox=myBndComponents->Array1();
 164
 165   axisX=new TColStd_HArray1OfListOfInteger(1, discrX);
 166   TColStd_Array1OfListOfInteger & tabListX=axisX->ChangeArray1();
 167
 168   axisY=new TColStd_HArray1OfListOfInteger(1, discrY);
 169   TColStd_Array1OfListOfInteger & tabListY=axisY->ChangeArray1();
 170
 171   for (labox=taBox.Lower(); labox<=taBox.Upper(); labox++) {
 172     if (!taBox(labox).IsVoid()) {
 173       taBox(labox).Get(xmin, ymin, xmax, ymax);
 174
 175       if (discrX>1) {
 176         firstcase=(Standard_Integer ) Max(1.0, (xmin-Xmin)/deltaX);
 177         lastcase=(Standard_Integer ) Min((Standard_Real)discrX, ((xmax-Xmin)/deltaX)+1);
 178         for (lacase=firstcase; lacase<=lastcase; lacase++) {
 179           tabListX(lacase).Append(labox);
 180         }
 181       }
 182
 183       if (discrY >1) {
 184         firstcase=(Standard_Integer ) Max(1.0, (ymin-Ymin)/deltaY);
 185         lastcase=(Standard_Integer ) Min((Standard_Real)discrY, ((ymax-Ymin)/deltaY)+1);
 186         for (lacase=firstcase; lacase<=lastcase; lacase++) {
 187           tabListY(lacase).Append(labox);
 188         }
 189       }
 190     }
 191   }
 192 }
 193
 194 //=======================================================================
 195 //function : Initialize
 196 //purpose  :
 197 //=======================================================================
 198
 199 void  Bnd_BoundSortBox2d::Initialize(const Bnd_Box2d& CompleteBox,
 200                                      const Standard_Integer nbComponents)
 201 {
 202   Standard_NullValue_Raise_if (nbComponents <=0, "BoundSortBox nul!");
 203
 204   myBox=CompleteBox;
 205   myBndComponents=new Bnd_HArray1OfBox2d(1, nbComponents);
 206
 207   Bnd_Box2d emptyBox;
 208   myBndComponents->Init( emptyBox );
 209
 210   discrX=nbComponents;
 211   discrY=nbComponents;
 212
 213   Standard_Real Xmax, Ymax;
 214   CompleteBox.Get(Xmin, Ymin, Xmax, Ymax);
 215
 216   deltaX=(Xmax-Xmin)/(Standard_Real)discrX;
 217   deltaY=(Ymax-Ymin)/(Standard_Real)discrY;
 218
 219   if (deltaX < Epsilon(100.)) {
 220     discrX=1;
 221     deltaX=Xmax-Xmin;
 222   }
 223   else axisX=new TColStd_HArray1OfListOfInteger(1, discrX);
 224
 225   if (deltaY < Epsilon(100.)) {
 226     discrY=1;
 227     deltaY=Ymax-Ymin;
 228   }
 229   else axisY=new TColStd_HArray1OfListOfInteger(1, discrY);
 230 }
 231
 232 //=======================================================================
 233 //function : Add
 234 //purpose  :
 235 //=======================================================================
 236
 237 void  Bnd_BoundSortBox2d::Add(const Bnd_Box2d& theBox,
 238                               const Standard_Integer boxIndex)
 239 {
 240   Standard_MultiplyDefined_Raise_if
 241     (!(myBndComponents->Value(boxIndex).IsVoid()),
 242      " This box is already defined !");
 243
 244   if (!theBox.IsVoid()) {
 245     Bnd_Array1OfBox2d & taBox=myBndComponents->ChangeArray1();
 246     Standard_Integer theGap, firstGap , lastGap;
 247     Standard_Real xmin, ymin, xmax, ymax;
 248     theBox.Get(xmin, ymin, xmax, ymax);
 249
 250     if (taBox.Lower()<=boxIndex  && boxIndex<=taBox.Upper())
 251       taBox(boxIndex).Update(xmin, ymin, xmax, ymax);
 252
 253     TColStd_Array1OfListOfInteger & tabListX=axisX->ChangeArray1();
 254
 255     if (discrX>1) {
 256       firstGap=(Standard_Integer ) Max(1.0, ((xmin-Xmin)/deltaX)+1);
 257       lastGap=(Standard_Integer ) Min((Standard_Real)discrX, ((xmax-Xmin)/deltaX)+1);
 258       for (theGap=firstGap; theGap<=lastGap; theGap++) {
 259         tabListX(theGap).Append(boxIndex);
 260       }
 261     }
 262
 263     TColStd_Array1OfListOfInteger & tabListY=axisY->ChangeArray1();
 264
 265     if (discrY >1) {
 266       firstGap=(Standard_Integer ) Max(1.0, ((ymin-Ymin)/deltaY)+1);
 267       lastGap=(Standard_Integer ) Min((Standard_Real)discrY, ((ymax-Ymin)/deltaY)+1);
 268       for (theGap=firstGap; theGap<=lastGap; theGap++) {
 269         tabListY(theGap).Append(boxIndex);
 270       }
 271     }
 272   }
 273 }
 274
 275
 276 //=======================================================================
 277 //function : Compare
 278 //purpose  :
 279 //=======================================================================
 280
 281
 282 const TColStd_ListOfInteger& Bnd_BoundSortBox2d::Compare
 283   (const Bnd_Box2d& theBox)
 284 {
 285   Standard_NullValue_Raise_if (discrX+discrY <=0,
 286                                "Compare sur 1 BoundSortBox2d nul!");
 287
 288   lastResult.Clear();
 289   if (theBox.IsVoid()) return lastResult;
 290   if (theBox.IsOut(myBox)) return lastResult;
 291
 292   Standard_Integer lacase, firstcase, lastcase;
 293   Standard_Real xmin, ymin, xmax, ymax;
 294   theBox.Get(xmin, ymin, xmax, ymax);
 295
 296   const Bnd_Array1OfBox2d & taBox=myBndComponents->Array1();
 297   Crible.Clear();
 298   theFound=2;
 299
 300   Standard_Integer cardY=0;
 301   if (discrY>1 && (!theBox.IsOpenYmin() || !theBox.IsOpenYmax())) {
 302     const TColStd_Array1OfListOfInteger & tabList=axisY->Array1();
 303     firstcase=(Standard_Integer ) Max(1.0, (ymin-Ymin)/deltaY);
 304     lastcase=(Standard_Integer ) Min((Standard_Real)discrY, ((ymax-Ymin)/deltaY)+1);
 305     for (lacase=firstcase; lacase<=lastcase; lacase++) {
 306       TColStd_ListIteratorOfListOfInteger theList(tabList(lacase));
 307       for (; theList.More(); theList.Next()) {
 308         cardY++;
 309         Crible.Bind(theList.Value(), 2);
 310       }
 311     }
 312     if (cardY==0) return lastResult;
 313   }
 314   else {
 315     if (ymin > Ymin+deltaY || ymax < Ymin)
 316       return lastResult;
 317     theFound-=2;
 318   }
 319
 320   if (discrX>1 && (!theBox.IsOpenXmin() || !theBox.IsOpenXmax())) {
 321     const TColStd_Array1OfListOfInteger & tabList=axisX->Array1();
 322     firstcase=(Standard_Integer ) Max(1.0, (xmin-Xmin)/deltaX);
 323     lastcase=(Standard_Integer ) Min((Standard_Real)discrX, ((xmax-Xmin)/deltaX)+1);
 324     for (lacase=firstcase; lacase<=lastcase; lacase++) {
 325       TColStd_ListIteratorOfListOfInteger theList(tabList(lacase));
 326       for (; theList.More(); theList.Next()) {
 327         if (Crible.IsBound(theList.Value())) {
 328           if (Crible(theList.Value())==theFound) {
 329             if (!taBox.Value(theList.Value()).IsOut(theBox)){
 330               lastResult.Append(theList.Value());
 331               Crible(theList.Value())=0;
 332             }
 333           }
 334         }
 335       }
 336     }
 337     return lastResult;
 338   }
 339
 340   else {
 341     if (xmin > Xmin+deltaX || xmax < Xmin) return lastResult;
 342     else if (discrY==1)
 343       {
 344         lacase=1;
 345         for(Standard_Integer i=taBox.Lower();i<=taBox.Upper();i++)
 346           {
 347             lastResult.Append(i);
 348           }
 349       }
 350     else{
 351
 352       TColStd_DataMapIteratorOfDataMapOfIntegerInteger itDM(Crible);
 353       for (; itDM.More(); itDM.Next()) {
 354         if (itDM.Value()==theFound) {
 355           if (taBox.Lower()<=itDM.Key() && itDM.Key()<=taBox.Upper()) {
 356             if (!taBox(itDM.Key()).IsOut(theBox))
 357               lastResult.Append(itDM.Key());
 358           }
 359           else {
 360             lastResult.Append(itDM.Key());
 361           }
 362         }
 363       }
 364     }
 365   }
 366   return lastResult;
 367 }
 368
 369
 370 //=======================================================================
 371 //function : Dump
 372 //purpose  :
 373 //=======================================================================
 374
 375 void Bnd_BoundSortBox2d::Dump() const
 376 {
 377   Standard_Integer lacase;
 378
 379   cout <<   "axis X : " << discrX << " intervalles de " << deltaX << endl;
 380   if (discrX>1) {
 381     const TColStd_Array1OfListOfInteger & tabList=axisX->Array1();
 382     for (lacase=1; lacase<=discrX; lacase++) {
 383       cout << "     X " << lacase << " : " ;
 384       TColStd_ListIteratorOfListOfInteger theList(tabList(lacase));
 385       for (; theList.More(); theList.Next()) {
 386         cout << theList.Value() << " ";
 387       }
 388       cout << "\n";
 389     }
 390   }
 391
 392   cout <<   "axis Y : " << discrY << " intervalles de " << deltaY << endl;
 393   if (discrY>1) {
 394     const TColStd_Array1OfListOfInteger & tabList=axisY->Array1();
 395     for (lacase=1; lacase<=discrY; lacase++) {
 396       cout << "     Y " << lacase << " : " ;
 397       TColStd_ListIteratorOfListOfInteger theList(tabList(lacase));
 398       for (; theList.More(); theList.Next()) {
 399         cout << theList.Value() << " ";
 400       }
 401       cout << "\n";
 402     }
 403   }
 404 }