1 // Created on: 2007-05-26
2 // Created by: Andrey BETENEV
3 // Copyright (c) 2007-2014 OPEN CASCADE SAS
5 // This file is part of Open CASCADE Technology software library.
7 // This library is free software; you can redistribute it and/or modify it under
8 // the terms of the GNU Lesser General Public License version 2.1 as published
9 // by the Free Software Foundation, with special exception defined in the file
10 // OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT
11 // distribution for complete text of the license and disclaimer of any warranty.
13 // Alternatively, this file may be used under the terms of Open CASCADE
14 // commercial license or contractual agreement.
16 #ifndef NCollection_CellFilter_HeaderFile
17 #define NCollection_CellFilter_HeaderFile
19 #include <Standard_Real.hxx>
20 #include <NCollection_LocalArray.hxx>
21 #include <NCollection_Array1.hxx>
22 #include <NCollection_List.hxx>
23 #include <NCollection_Map.hxx>
24 #include <NCollection_DataMap.hxx>
25 #include <NCollection_IncAllocator.hxx>
26 #include <NCollection_TypeDef.hxx>
28 //! Auxiliary enumeration serving as responce from method Inspect
29 enum NCollection_CellFilter_Action
31 CellFilter_Keep = 0, //!< Target is needed and should be kept
32 CellFilter_Purge = 1 //!< Target is not needed and can be removed from the current cell
36 * A data structure for sorting geometric objects (called targets) in
37 * n-dimensional space into cells, with associated algorithm for fast checking
38 * of coincidence (overlapping, intersection, etc.) with other objects
39 * (called here bullets).
43 * The algorithm is based on hash map, thus it has linear time of initialization
44 * (O(N) where N is number of cells covered by added targets) and constant-time
45 * search for one bullet (more precisely, O(M) where M is number of cells covered
48 * The idea behind the algorithm is to separate each co-ordinate of the space
49 * into equal-size cells. Note that this works well when cell size is
50 * approximately equal to the characteristic size of the involved objects
51 * (targets and bullets; including tolerance eventually used for coincidence
56 * The target objects to be searched are added to the tool by methods Add();
57 * each target is classified as belonging to some cell(s). The data on cells
58 * (list of targets found in each one) are stored in the hash map with key being
59 * cumulative index of the cell by all co-ordinates.
60 * Thus the time needed to find targets in some cell is O(1) * O(number of
61 * targets in the cell).
63 * As soon as all the targets are added, the algorithm is ready to check for
65 * To find the targets coincident with any given bullet, it checks all the
66 * candidate targets in the cell(s) covered by the bullet object
67 * (methods Inspect()).
69 * The methods Add() and Inspect() have two flavours each: one accepts
70 * single point identifying one cell, another accept two points specifying
71 * the range of cells. It should be noted that normally at least one of these
72 * methods is called as for range of cells: either due to objects having non-
73 * zero size, or in order to account for the tolerance when objects are points.
75 * The set of targets can be modified during the process: new targets can be
76 * added by Add(), existing targets can be removed by Remove().
80 * The algorithm is implemented as template class, thus it is capable to
81 * work with objects of any type. The only argument of the template should be
82 * the specific class providing all necessary features required by the
85 * - typedef "Target" defining type of target objects.
86 * This type must have copy constructor
88 * - typedef "Point" defining type of geometrical points used
90 * - enum Dimension whose value must be dimension of the point
92 * - method Coord() returning value of the i-th coordinate of the point:
94 * static Standard_Real Coord (int i, const Point& thePnt);
96 * Note that index i is from 0 to Dimension-1.
98 * - method IsEqual() used by Remove() to identify objects to be removed:
100 * Standard_Boolean IsEqual (const Target& theT1, const Target& theT2);
102 * - method Inspect() performing necessary actions on the candidate target
103 * object (usially comparison with the currently checked bullet object):
105 * NCollection_CellFilter_Action Inspect (const Target& theObject);
107 * The returned value can be used to command CellFilter
108 * to remove the inspected item from the current cell; this allows
109 * to exclude the items that has been processed and are not needed any
110 * more in further search (for better performance).
112 * Note that method Inspect() can be const and/or virtual.
115 template <class Inspector> class NCollection_CellFilter
118 typedef TYPENAME Inspector::Target Target;
119 typedef TYPENAME Inspector::Point Point;
123 //! Constructor; initialized by dimension count and cell size.
125 //! Note: the cell size must be ensured to be greater than
126 //! maximal co-ordinate of the involved points divided by INT_MAX,
127 //! in order to avoid integer overflow of cell index.
129 //! By default cell size is 0, which is invalid; thus if default
130 //! constructor is used, the tool must be initialized later with
131 //! appropriate cell size by call to Reset()
132 NCollection_CellFilter (const Standard_Integer theDim,
133 const Standard_Real theCellSize = 0,
134 const Handle(NCollection_IncAllocator)& theAlloc = 0)
135 : myCellSize(0, theDim - 1)
138 Reset (theCellSize, theAlloc);
141 //! Clear the data structures, set new cell size and allocator
142 void Reset (Standard_Real theCellSize,
143 const Handle(NCollection_IncAllocator)& theAlloc=0)
145 for (int i=0; i < myDim; i++)
146 myCellSize(i) = theCellSize;
147 resetAllocator ( theAlloc );
150 //! Clear the data structures and set new cell sizes and allocator
151 void Reset (NCollection_Array1<Standard_Real> theCellSize,
152 const Handle(NCollection_IncAllocator)& theAlloc=0)
154 myCellSize = theCellSize;
155 resetAllocator ( theAlloc );
158 //! Adds a target object for further search at a point (into only one cell)
159 void Add (const Target& theTarget, const Point &thePnt)
161 Cell aCell (thePnt, myCellSize);
162 add (aCell, theTarget);
165 //! Adds a target object for further search in the range of cells
166 //! defined by two points (the first point must have all co-ordinates equal or
167 //! less than the same co-ordinate of the second point)
168 void Add (const Target& theTarget,
169 const Point &thePntMin, const Point &thePntMax)
171 // get cells range by minimal and maximal co-ordinates
172 Cell aCellMin (thePntMin, myCellSize);
173 Cell aCellMax (thePntMax, myCellSize);
174 Cell aCell = aCellMin;
175 // add object recursively into all cells in range
176 iterateAdd (myDim-1, aCell, aCellMin, aCellMax, theTarget);
179 //! Find a target object at a point and remove it from the structures.
180 //! For usage of this method "operator ==" should be defined for Target.
181 void Remove (const Target& theTarget, const Point &thePnt)
183 Cell aCell (thePnt, myCellSize);
184 remove (aCell, theTarget);
187 //! Find a target object in the range of cells defined by two points and
188 //! remove it from the structures
189 //! (the first point must have all co-ordinates equal or
190 //! less than the same co-ordinate of the second point).
191 //! For usage of this method "operator ==" should be defined for Target.
192 void Remove (const Target& theTarget,
193 const Point &thePntMin, const Point &thePntMax)
195 // get cells range by minimal and maximal co-ordinates
196 Cell aCellMin (thePntMin, myCellSize);
197 Cell aCellMax (thePntMax, myCellSize);
198 Cell aCell = aCellMin;
199 // remove object recursively from all cells in range
200 iterateRemove (myDim-1, aCell, aCellMin, aCellMax, theTarget);
203 //! Inspect all targets in the cell corresponding to the given point
204 void Inspect (const Point& thePnt, Inspector &theInspector)
206 Cell aCell (thePnt, myCellSize);
207 inspect (aCell, theInspector);
210 //! Inspect all targets in the cells range limited by two given points
211 //! (the first point must have all co-ordinates equal or
212 //! less than the same co-ordinate of the second point)
213 void Inspect (const Point& thePntMin, const Point& thePntMax,
214 Inspector &theInspector)
216 // get cells range by minimal and maximal co-ordinates
217 Cell aCellMin (thePntMin, myCellSize);
218 Cell aCellMax (thePntMax, myCellSize);
219 Cell aCell = aCellMin;
220 // inspect object recursively into all cells in range
221 iterateInspect (myDim-1, aCell,
222 aCellMin, aCellMax, theInspector);
225 #if defined(__SUNPRO_CC) && (__SUNPRO_CC <= 0x530)
226 public: // work-around against obsolete SUN WorkShop 5.3 compiler
232 * Auxiliary class for storing points belonging to the cell as the list
238 // Empty constructor is forbidden.
239 Standard_NoSuchObject::Raise("NCollection_CellFilter::ListNode()");
247 * Auxilary structure representing a cell in the space.
248 * Cells are stored in the map, each cell contains list of objects
249 * that belong to that cell.
255 //! Constructor; computes cell indices
256 Cell (const Point& thePnt,
257 const NCollection_Array1<Standard_Real>& theCellSize)
258 : index(theCellSize.Size()),
261 for (int i = 0; i < theCellSize.Size(); i++)
263 Standard_Real val = (Standard_Real)(Inspector::Coord(i, thePnt) / theCellSize(theCellSize.Lower() + i));
264 //If the value of index is greater than
265 //INT_MAX it is decreased correspondingly for the value of INT_MAX. If the value
266 //of index is less than INT_MIN it is increased correspondingly for the absolute
268 index[i] = long((val > INT_MAX - 1) ? fmod(val, (Standard_Real) INT_MAX)
269 : (val < INT_MIN + 1) ? fmod(val, (Standard_Real) INT_MIN)
274 //! Copy constructor: ensure that list is not deleted twice
275 Cell (const Cell& theOther)
276 : index(theOther.index.Size())
281 //! Assignment operator: ensure that list is not deleted twice
282 void operator = (const Cell& theOther)
284 Standard_Integer myDim = Standard_Integer(theOther.index.Size());
285 for(Standard_Integer anIdx = 0; anIdx < myDim; anIdx++)
286 index[anIdx] = theOther.index[anIdx];
288 Objects = theOther.Objects;
289 ((Cell&)theOther).Objects = 0;
292 //! Destructor; calls destructors for targets contained in the list
295 for ( ListNode* aNode = Objects; aNode; aNode = aNode->Next )
296 aNode->Object.~Target();
297 // note that list nodes need not to be freed, since IncAllocator is used
301 //! Compare cell with other one
302 Standard_Boolean IsEqual (const Cell& theOther) const
304 Standard_Integer myDim = Standard_Integer(theOther.index.Size());
305 for (int i=0; i < myDim; i++)
306 if ( index[i] != theOther.index[i] ) return Standard_False;
307 return Standard_True;
310 //! Compute hash code
311 Standard_Integer HashCode (const Standard_Integer theUpper) const
313 // number of bits per each dimension in the hash code
314 Standard_Integer myDim = Standard_Integer(index.Size());
315 const Standard_Size aShiftBits = (BITS(long)-1) / myDim;
317 for (int i=0; i < myDim; i++)
318 aCode = ( aCode << aShiftBits ) ^ index[i];
319 return (unsigned)aCode % theUpper;
323 NCollection_LocalArray<long, 10> index;
327 // definition of global functions is needed for map
328 friend Standard_Integer HashCode (const Cell &aCell, const Standard_Integer theUpper)
329 { return aCell.HashCode(theUpper); }
330 friend Standard_Boolean IsEqual (const Cell &aCell1, const Cell &aCell2)
331 { return aCell1.IsEqual(aCell2); }
335 //! Reset allocator to the new one
336 void resetAllocator (const Handle(NCollection_IncAllocator)& theAlloc)
338 if ( theAlloc.IsNull() )
339 myAllocator = new NCollection_IncAllocator;
341 myAllocator = theAlloc;
342 myCells.Clear ( myAllocator );
345 //! Add a new target object into the specified cell
346 void add (const Cell& theCell, const Target& theTarget)
348 // add a new cell or get reference to existing one
349 Cell& aMapCell = (Cell&)myCells.Added (theCell);
351 // create a new list node and add it to the beginning of the list
352 ListNode* aNode = (ListNode*)myAllocator->Allocate(sizeof(ListNode));
353 new (&aNode->Object) Target (theTarget);
354 aNode->Next = aMapCell.Objects;
355 aMapCell.Objects = aNode;
358 //! Internal addition function, performing iteration for adjacent cells
359 //! by one dimension; called recursively to cover all dimensions
360 void iterateAdd (int idim, Cell &theCell,
361 const Cell& theCellMin, const Cell& theCellMax,
362 const Target& theTarget)
364 int start = theCellMin.index[idim];
365 int end = theCellMax.index[idim];
366 for (int i=start; i <= end; i++) {
367 theCell.index[idim] = i;
368 if ( idim ) // recurse
369 iterateAdd (idim-1, theCell, theCellMin, theCellMax, theTarget);
370 else // add to this cell
371 add (theCell, theTarget);
375 //! Remove the target object from the specified cell
376 void remove (const Cell& theCell, const Target& theTarget)
378 // check if any objects are recorded in that cell
379 if ( ! myCells.Contains (theCell) )
382 // iterate by objects in the cell and check each
383 Cell& aMapCell = (Cell&)myCells.Added (theCell);
384 ListNode* aNode = aMapCell.Objects;
385 ListNode* aPrev = NULL;
388 ListNode* aNext = aNode->Next;
389 if (Inspector::IsEqual (aNode->Object, theTarget))
391 aNode->Object.~Target();
392 (aPrev ? aPrev->Next : aMapCell.Objects) = aNext;
393 // note that aNode itself need not to be freed, since IncAllocator is used
401 //! Internal removal function, performing iteration for adjacent cells
402 //! by one dimension; called recursively to cover all dimensions
403 void iterateRemove (int idim, Cell &theCell,
404 const Cell& theCellMin, const Cell& theCellMax,
405 const Target& theTarget)
407 int start = theCellMin.index[idim];
408 int end = theCellMax.index[idim];
409 for (int i=start; i <= end; i++) {
410 theCell.index[idim] = i;
411 if ( idim ) // recurse
412 iterateRemove (idim-1, theCell, theCellMin, theCellMax, theTarget);
413 else // remove from this cell
414 remove (theCell, theTarget);
418 //! Inspect the target objects in the specified cell.
419 void inspect (const Cell& theCell, Inspector& theInspector)
421 // check if any objects are recorded in that cell
422 if ( ! myCells.Contains (theCell) )
425 // iterate by objects in the cell and check each
426 Cell& aMapCell = (Cell&)myCells.Added (theCell);
427 ListNode* aNode = aMapCell.Objects;
428 ListNode* aPrev = NULL;
430 ListNode* aNext = aNode->Next;
431 NCollection_CellFilter_Action anAction =
432 theInspector.Inspect (aNode->Object);
433 // delete items requested to be purged
434 if ( anAction == CellFilter_Purge ) {
435 aNode->Object.~Target();
436 (aPrev ? aPrev->Next : aMapCell.Objects) = aNext;
437 // note that aNode itself need not to be freed, since IncAllocator is used
445 //! Inspect the target objects in the specified range of the cells
446 void iterateInspect (int idim, Cell &theCell,
447 const Cell& theCellMin, const Cell& theCellMax,
448 Inspector& theInspector)
450 int start = theCellMin.index[idim];
451 int end = theCellMax.index[idim];
452 for (int i=start; i <= end; i++) {
453 theCell.index[idim] = i;
454 if ( idim ) // recurse
455 iterateInspect (idim-1, theCell, theCellMin, theCellMax, theInspector);
456 else // inspect this cell
457 inspect (theCell, theInspector);
462 Standard_Integer myDim;
463 Handle(NCollection_BaseAllocator) myAllocator;
464 NCollection_Map<Cell> myCells;
465 NCollection_Array1<Standard_Real> myCellSize;
469 * Base class defining part of the Inspector interface
470 * for CellFilter algorithm, working with gp_XYZ points in 3d space
474 struct NCollection_CellFilter_InspectorXYZ
477 enum { Dimension = 3 };
480 typedef gp_XYZ Point;
482 //! Access to co-ordinate
483 static Standard_Real Coord (int i, const Point &thePnt) { return thePnt.Coord(i+1); }
485 //! Auxiliary method to shift point by each coordinate on given value;
486 //! useful for preparing a points range for Inspect with tolerance
487 Point Shift (const Point& thePnt, Standard_Real theTol) const
488 { return Point (thePnt.X() + theTol, thePnt.Y() + theTol, thePnt.Z() + theTol); }
492 * Base class defining part of the Inspector interface
493 * for CellFilter algorithm, working with gp_XY points in 2d space
497 struct NCollection_CellFilter_InspectorXY
500 enum { Dimension = 2 };
505 //! Access to co-ordinate
506 static Standard_Real Coord (int i, const Point &thePnt) { return thePnt.Coord(i+1); }
508 //! Auxiliary method to shift point by each coordinate on given value;
509 //! useful for preparing a points range for Inspect with tolerance
510 Point Shift (const Point& thePnt, Standard_Real theTol) const
511 { return Point (thePnt.X() + theTol, thePnt.Y() + theTol); }