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
6 // This file is part of Open CASCADE Technology software library.
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.
14 // Alternatively, this file may be used under the terms of Open CASCADE
15 // commercial license or contractual agreement.
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>
27 //=======================================================================
28 //function : Bnd_BoundSortBox2d
30 //=======================================================================
31 Bnd_BoundSortBox2d::Bnd_BoundSortBox2d()
32 : discrX(0), discrY(0)
36 //=======================================================================
37 //function : Initialize
39 //=======================================================================
41 void Bnd_BoundSortBox2d::Initialize(const Bnd_Box2d& CompleteBox,
42 const Handle(Bnd_HArray1OfBox2d)& SetOfBox)
45 myBndComponents=SetOfBox;
46 discrX=SetOfBox->Length();
49 Standard_Real xmin, ymin, xmax, ymax;
50 Standard_Real middleX=0.;
51 Standard_Real middleY=0.;
53 const Bnd_Array1OfBox2d & taBox=myBndComponents->Array1();
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);
63 middleX=middleX/taBox.Length();
64 middleY=middleY/taBox.Length();
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;
71 if (middleX < Epsilon(100.)) {
75 else if (middleX > deltaX) {
76 discrX=(Standard_Integer)((Xmax-Xmin)/middleX);
81 if (middleY < Epsilon(100.)) {
85 else if (middleY > deltaY) {
86 discrY=(Standard_Integer)((Ymax-Ymin)/middleY + 0.1);
94 //=======================================================================
95 //function : Initialize
97 //=======================================================================
99 void Bnd_BoundSortBox2d::Initialize(const Handle(Bnd_HArray1OfBox2d)& SetOfBox)
101 myBndComponents=SetOfBox;
102 discrX=SetOfBox->Length();
105 Standard_Real xmin, ymin, xmax, ymax;
106 Standard_Real middleX=0.;
107 Standard_Real middleY=0.;
109 const Bnd_Array1OfBox2d & taBox=myBndComponents->Array1();
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);
120 middleX=middleX/taBox.Length();
121 middleY=middleY/taBox.Length();
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;
128 if (middleX < Epsilon(100.)) {
132 else if (middleX > deltaX) {
133 discrX=(Standard_Integer)((Xmax-Xmin)/middleX);
138 if (middleY < Epsilon(100.)) {
142 else if (middleY > deltaY) {
143 discrY=(Standard_Integer)((Ymax-Ymin)/middleY + 0.1);
152 //=======================================================================
153 //function : SortBoxes
155 //=======================================================================
157 void Bnd_BoundSortBox2d::SortBoxes()
159 Standard_NullValue_Raise_if (discrX+discrY <=0, "BoundSortBox2d nul!");
161 Standard_Integer labox, lacase, firstcase, lastcase;
162 Standard_Real xmin, ymin, xmax, ymax;
163 const Bnd_Array1OfBox2d & taBox=myBndComponents->Array1();
165 axisX=new TColStd_HArray1OfListOfInteger(1, discrX);
166 TColStd_Array1OfListOfInteger & tabListX=axisX->ChangeArray1();
168 axisY=new TColStd_HArray1OfListOfInteger(1, discrY);
169 TColStd_Array1OfListOfInteger & tabListY=axisY->ChangeArray1();
171 for (labox=taBox.Lower(); labox<=taBox.Upper(); labox++) {
172 if (!taBox(labox).IsVoid()) {
173 taBox(labox).Get(xmin, ymin, xmax, ymax);
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);
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);
194 //=======================================================================
195 //function : Initialize
197 //=======================================================================
199 void Bnd_BoundSortBox2d::Initialize(const Bnd_Box2d& CompleteBox,
200 const Standard_Integer nbComponents)
202 Standard_NullValue_Raise_if (nbComponents <=0, "BoundSortBox nul!");
205 myBndComponents=new Bnd_HArray1OfBox2d(1, nbComponents);
208 myBndComponents->Init( emptyBox );
213 Standard_Real Xmax, Ymax;
214 CompleteBox.Get(Xmin, Ymin, Xmax, Ymax);
216 deltaX=(Xmax-Xmin)/(Standard_Real)discrX;
217 deltaY=(Ymax-Ymin)/(Standard_Real)discrY;
219 if (deltaX < Epsilon(100.)) {
223 else axisX=new TColStd_HArray1OfListOfInteger(1, discrX);
225 if (deltaY < Epsilon(100.)) {
229 else axisY=new TColStd_HArray1OfListOfInteger(1, discrY);
232 //=======================================================================
235 //=======================================================================
237 void Bnd_BoundSortBox2d::Add(const Bnd_Box2d& theBox,
238 const Standard_Integer boxIndex)
240 Standard_MultiplyDefined_Raise_if
241 (!(myBndComponents->Value(boxIndex).IsVoid()),
242 " This box is already defined !");
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);
250 if (taBox.Lower()<=boxIndex && boxIndex<=taBox.Upper())
251 taBox(boxIndex).Update(xmin, ymin, xmax, ymax);
253 TColStd_Array1OfListOfInteger & tabListX=axisX->ChangeArray1();
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);
263 TColStd_Array1OfListOfInteger & tabListY=axisY->ChangeArray1();
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);
276 //=======================================================================
279 //=======================================================================
282 const TColStd_ListOfInteger& Bnd_BoundSortBox2d::Compare
283 (const Bnd_Box2d& theBox)
285 Standard_NullValue_Raise_if (discrX+discrY <=0,
286 "Compare sur 1 BoundSortBox2d nul!");
289 if (theBox.IsVoid()) return lastResult;
290 if (theBox.IsOut(myBox)) return lastResult;
292 Standard_Integer lacase, firstcase, lastcase;
293 Standard_Real xmin, ymin, xmax, ymax;
294 theBox.Get(xmin, ymin, xmax, ymax);
296 const Bnd_Array1OfBox2d & taBox=myBndComponents->Array1();
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()) {
309 Crible.Bind(theList.Value(), 2);
312 if (cardY==0) return lastResult;
315 if (ymin > Ymin+deltaY || ymax < Ymin)
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;
341 if (xmin > Xmin+deltaX || xmax < Xmin) return lastResult;
345 for(Standard_Integer i=taBox.Lower();i<=taBox.Upper();i++)
347 lastResult.Append(i);
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());
360 lastResult.Append(itDM.Key());
370 //=======================================================================
373 //=======================================================================
375 void Bnd_BoundSortBox2d::Dump() const
377 Standard_Integer lacase;
379 cout << "axis X : " << discrX << " intervalles de " << deltaX << endl;
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() << " ";
392 cout << "axis Y : " << discrY << " intervalles de " << deltaY << endl;
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() << " ";