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>
26 //=======================================================================
27 //function : Bnd_BoundSortBox2d
29 //=======================================================================
30 Bnd_BoundSortBox2d::Bnd_BoundSortBox2d()
31 : discrX(0), discrY(0)
35 //=======================================================================
36 //function : Initialize
38 //=======================================================================
40 void Bnd_BoundSortBox2d::Initialize(const Bnd_Box2d& CompleteBox,
41 const Handle(Bnd_HArray1OfBox2d)& SetOfBox)
44 myBndComponents=SetOfBox;
45 discrX=SetOfBox->Length();
48 Standard_Real xmin, ymin, xmax, ymax;
49 Standard_Real middleX=0.;
50 Standard_Real middleY=0.;
52 const Bnd_Array1OfBox2d & taBox=myBndComponents->Array1();
54 Standard_Integer labox;
55 for (labox=taBox.Lower(); labox<=taBox.Upper(); labox++) {
56 if (!taBox(labox).IsVoid()) {
57 taBox.Value(labox).Get(xmin, ymin, xmax, ymax);
62 middleX=middleX/taBox.Length();
63 middleY=middleY/taBox.Length();
65 Standard_Real Xmax, Ymax;
66 CompleteBox.Get(Xmin, Ymin, Xmax, Ymax);
67 deltaX=(Xmax-Xmin)/(Standard_Real)discrX;
68 deltaY=(Ymax-Ymin)/(Standard_Real)discrY;
70 if (middleX < Epsilon(100.)) {
74 else if (middleX > deltaX) {
75 discrX=(Standard_Integer)((Xmax-Xmin)/middleX);
80 if (middleY < Epsilon(100.)) {
84 else if (middleY > deltaY) {
85 discrY=(Standard_Integer)((Ymax-Ymin)/middleY + 0.1);
93 //=======================================================================
94 //function : Initialize
96 //=======================================================================
98 void Bnd_BoundSortBox2d::Initialize(const Handle(Bnd_HArray1OfBox2d)& SetOfBox)
100 myBndComponents=SetOfBox;
101 discrX=SetOfBox->Length();
104 Standard_Real xmin, ymin, xmax, ymax;
105 Standard_Real middleX=0.;
106 Standard_Real middleY=0.;
108 const Bnd_Array1OfBox2d & taBox=myBndComponents->Array1();
110 Standard_Integer labox;
111 for (labox=taBox.Lower(); labox<=taBox.Upper(); labox++) {
112 if (!taBox(labox).IsVoid()) {
113 myBox.Add(taBox(labox));
114 taBox.Value(labox).Get(xmin, ymin, xmax, ymax);
119 middleX=middleX/taBox.Length();
120 middleY=middleY/taBox.Length();
122 Standard_Real Xmax, Ymax;
123 myBox.Get(Xmin, Ymin, Xmax, Ymax);
124 deltaX=(Xmax-Xmin)/(Standard_Real)discrX;
125 deltaY=(Ymax-Ymin)/(Standard_Real)discrY;
127 if (middleX < Epsilon(100.)) {
131 else if (middleX > deltaX) {
132 discrX=(Standard_Integer)((Xmax-Xmin)/middleX);
137 if (middleY < Epsilon(100.)) {
141 else if (middleY > deltaY) {
142 discrY=(Standard_Integer)((Ymax-Ymin)/middleY + 0.1);
151 //=======================================================================
152 //function : SortBoxes
154 //=======================================================================
156 void Bnd_BoundSortBox2d::SortBoxes()
158 Standard_NullValue_Raise_if (discrX+discrY <=0, "BoundSortBox2d nul!");
160 Standard_Integer labox, lacase, firstcase, lastcase;
161 Standard_Real xmin, ymin, xmax, ymax;
162 const Bnd_Array1OfBox2d & taBox=myBndComponents->Array1();
164 axisX=new TColStd_HArray1OfListOfInteger(1, discrX);
165 TColStd_Array1OfListOfInteger & tabListX=axisX->ChangeArray1();
167 axisY=new TColStd_HArray1OfListOfInteger(1, discrY);
168 TColStd_Array1OfListOfInteger & tabListY=axisY->ChangeArray1();
170 for (labox=taBox.Lower(); labox<=taBox.Upper(); labox++) {
171 if (!taBox(labox).IsVoid()) {
172 taBox(labox).Get(xmin, ymin, xmax, ymax);
175 firstcase=(Standard_Integer ) Max(1.0, (xmin-Xmin)/deltaX);
176 lastcase=(Standard_Integer ) Min((Standard_Real)discrX, ((xmax-Xmin)/deltaX)+1);
177 for (lacase=firstcase; lacase<=lastcase; lacase++) {
178 tabListX(lacase).Append(labox);
183 firstcase=(Standard_Integer ) Max(1.0, (ymin-Ymin)/deltaY);
184 lastcase=(Standard_Integer ) Min((Standard_Real)discrY, ((ymax-Ymin)/deltaY)+1);
185 for (lacase=firstcase; lacase<=lastcase; lacase++) {
186 tabListY(lacase).Append(labox);
193 //=======================================================================
194 //function : Initialize
196 //=======================================================================
198 void Bnd_BoundSortBox2d::Initialize(const Bnd_Box2d& CompleteBox,
199 const Standard_Integer nbComponents)
201 Standard_NullValue_Raise_if (nbComponents <=0, "BoundSortBox nul!");
204 myBndComponents=new Bnd_HArray1OfBox2d(1, nbComponents);
207 myBndComponents->Init( emptyBox );
212 Standard_Real Xmax, Ymax;
213 CompleteBox.Get(Xmin, Ymin, Xmax, Ymax);
215 deltaX=(Xmax-Xmin)/(Standard_Real)discrX;
216 deltaY=(Ymax-Ymin)/(Standard_Real)discrY;
218 if (deltaX < Epsilon(100.)) {
222 else axisX=new TColStd_HArray1OfListOfInteger(1, discrX);
224 if (deltaY < Epsilon(100.)) {
228 else axisY=new TColStd_HArray1OfListOfInteger(1, discrY);
231 //=======================================================================
234 //=======================================================================
236 void Bnd_BoundSortBox2d::Add(const Bnd_Box2d& theBox,
237 const Standard_Integer boxIndex)
239 Standard_MultiplyDefined_Raise_if
240 (!(myBndComponents->Value(boxIndex).IsVoid()),
241 " This box is already defined !");
243 if (!theBox.IsVoid()) {
244 Bnd_Array1OfBox2d & taBox=myBndComponents->ChangeArray1();
245 Standard_Integer theGap, firstGap , lastGap;
246 Standard_Real xmin, ymin, xmax, ymax;
247 theBox.Get(xmin, ymin, xmax, ymax);
249 if (taBox.Lower()<=boxIndex && boxIndex<=taBox.Upper())
250 taBox(boxIndex).Update(xmin, ymin, xmax, ymax);
252 TColStd_Array1OfListOfInteger & tabListX=axisX->ChangeArray1();
255 firstGap=(Standard_Integer ) Max(1.0, ((xmin-Xmin)/deltaX)+1);
256 lastGap=(Standard_Integer ) Min((Standard_Real)discrX, ((xmax-Xmin)/deltaX)+1);
257 for (theGap=firstGap; theGap<=lastGap; theGap++) {
258 tabListX(theGap).Append(boxIndex);
262 TColStd_Array1OfListOfInteger & tabListY=axisY->ChangeArray1();
265 firstGap=(Standard_Integer ) Max(1.0, ((ymin-Ymin)/deltaY)+1);
266 lastGap=(Standard_Integer ) Min((Standard_Real)discrY, ((ymax-Ymin)/deltaY)+1);
267 for (theGap=firstGap; theGap<=lastGap; theGap++) {
268 tabListY(theGap).Append(boxIndex);
275 //=======================================================================
278 //=======================================================================
281 const TColStd_ListOfInteger& Bnd_BoundSortBox2d::Compare
282 (const Bnd_Box2d& theBox)
284 Standard_NullValue_Raise_if (discrX+discrY <=0,
285 "Compare sur 1 BoundSortBox2d nul!");
288 if (theBox.IsVoid()) return lastResult;
289 if (theBox.IsOut(myBox)) return lastResult;
291 Standard_Integer lacase, firstcase, lastcase;
292 Standard_Real xmin, ymin, xmax, ymax;
293 theBox.Get(xmin, ymin, xmax, ymax);
295 const Bnd_Array1OfBox2d & taBox=myBndComponents->Array1();
299 Standard_Integer cardY=0;
300 if (discrY>1 && (!theBox.IsOpenYmin() || !theBox.IsOpenYmax())) {
301 const TColStd_Array1OfListOfInteger & tabList=axisY->Array1();
302 firstcase=(Standard_Integer ) Max(1.0, (ymin-Ymin)/deltaY);
303 lastcase=(Standard_Integer ) Min((Standard_Real)discrY, ((ymax-Ymin)/deltaY)+1);
304 for (lacase=firstcase; lacase<=lastcase; lacase++) {
305 TColStd_ListIteratorOfListOfInteger theList(tabList(lacase));
306 for (; theList.More(); theList.Next()) {
308 Crible.Bind(theList.Value(), 2);
311 if (cardY==0) return lastResult;
314 if (ymin > Ymin+deltaY || ymax < Ymin)
319 if (discrX>1 && (!theBox.IsOpenXmin() || !theBox.IsOpenXmax())) {
320 const TColStd_Array1OfListOfInteger & tabList=axisX->Array1();
321 firstcase=(Standard_Integer ) Max(1.0, (xmin-Xmin)/deltaX);
322 lastcase=(Standard_Integer ) Min((Standard_Real)discrX, ((xmax-Xmin)/deltaX)+1);
323 for (lacase=firstcase; lacase<=lastcase; lacase++) {
324 TColStd_ListIteratorOfListOfInteger theList(tabList(lacase));
325 for (; theList.More(); theList.Next()) {
326 if (Crible.IsBound(theList.Value())) {
327 if (Crible(theList.Value())==theFound) {
328 if (!taBox.Value(theList.Value()).IsOut(theBox)){
329 lastResult.Append(theList.Value());
330 Crible(theList.Value())=0;
340 if (xmin > Xmin+deltaX || xmax < Xmin) return lastResult;
344 for(Standard_Integer i=taBox.Lower();i<=taBox.Upper();i++)
346 lastResult.Append(i);
351 TColStd_DataMapIteratorOfDataMapOfIntegerInteger itDM(Crible);
352 for (; itDM.More(); itDM.Next()) {
353 if (itDM.Value()==theFound) {
354 if (taBox.Lower()<=itDM.Key() && itDM.Key()<=taBox.Upper()) {
355 if (!taBox(itDM.Key()).IsOut(theBox))
356 lastResult.Append(itDM.Key());
359 lastResult.Append(itDM.Key());
369 //=======================================================================
372 //=======================================================================
374 void Bnd_BoundSortBox2d::Dump() const
376 Standard_Integer lacase;
378 std::cout << "axis X : " << discrX << " intervalles de " << deltaX << std::endl;
380 const TColStd_Array1OfListOfInteger & tabList=axisX->Array1();
381 for (lacase=1; lacase<=discrX; lacase++) {
382 std::cout << " X " << lacase << " : " ;
383 TColStd_ListIteratorOfListOfInteger theList(tabList(lacase));
384 for (; theList.More(); theList.Next()) {
385 std::cout << theList.Value() << " ";
391 std::cout << "axis Y : " << discrY << " intervalles de " << deltaY << std::endl;
393 const TColStd_Array1OfListOfInteger & tabList=axisY->Array1();
394 for (lacase=1; lacase<=discrY; lacase++) {
395 std::cout << " Y " << lacase << " : " ;
396 TColStd_ListIteratorOfListOfInteger theList(tabList(lacase));
397 for (; theList.More(); theList.Next()) {
398 std::cout << theList.Value() << " ";