|
Public Types |
typedef Inspector::Target | Target |
typedef Inspector::Point | Point |
Public Member Functions |
| NCollection_CellFilter (Standard_Real theCellSize=0, const Handle(NCollection_IncAllocator)&theAlloc=0) |
| Constructor; initialized by cell size. Note: the cell size must be ensured to be greater than maximal co-ordinate of the involved points divided by INT_MAX, in order to avoid integer overflow of cell index. By default cell size is 0, which is invalid; thus if default constructor is used, the tool must be initialized later with appropriate cell size by call to Reset().
|
| NCollection_CellFilter (Standard_Real theCellSize[], const Handle(NCollection_IncAllocator)&theAlloc=0) |
| Constructor; initialized by cell sizes along each dimension. Note: the cell size in each dimension must be ensured to be greater than maximal co-ordinate of the involved points by this dimension divided by INT_MAX, in order to avoid integer overflow of cell index.
|
void | Reset (Standard_Real theCellSize, const Handle(NCollection_IncAllocator)&theAlloc=0) |
| Clear the data structures, set new cell size and allocator.
|
void | Reset (Standard_Real theCellSize[], const Handle(NCollection_IncAllocator)&theAlloc=0) |
| Clear the data structures and set new cell sizes and allocator.
|
void | Add (const Target &theTarget, const Point &thePnt) |
| Adds a target object for further search at a point (into only one cell).
|
void | Add (const Target &theTarget, const Point &thePntMin, const Point &thePntMax) |
| Adds a target object for further search in the range of cells defined by two points (the first point must have all co-ordinates equal or less than the same co-ordinate of the second point).
|
void | Remove (const Target &theTarget, const Point &thePnt) |
| Find a target object at a point and remove it from the structures. For usage of this method "operator ==" should be defined for Target.
|
void | Remove (const Target &theTarget, const Point &thePntMin, const Point &thePntMax) |
| Find a target object in the range of cells defined by two points and remove it from the structures (the first point must have all co-ordinates equal or less than the same co-ordinate of the second point). For usage of this method "operator ==" should be defined for Target.
|
void | Inspect (const Point &thePnt, Inspector &theInspector) |
| Inspect all targets in the cell corresponding to the given point.
|
void | Inspect (const Point &thePntMin, const Point &thePntMax, Inspector &theInspector) |
| Inspect all targets in the cells range limited by two given points (the first point must have all co-ordinates equal or less than the same co-ordinate of the second point).
|
Protected Member Functions |
void | resetAllocator (const Handle(NCollection_IncAllocator)&theAlloc) |
| Reset allocator to the new one.
|
void | add (const Cell &theCell, const Target &theTarget) |
| Add a new target object into the specified cell.
|
void | iterateAdd (int idim, Cell &theCell, const Cell &theCellMin, const Cell &theCellMax, const Target &theTarget) |
| Internal addition function, performing iteration for adjacent cells by one dimension; called recursively to cover all dimensions.
|
void | remove (const Cell &theCell, const Target &theTarget) |
| Remove the target object from the specified cell.
|
void | iterateRemove (int idim, Cell &theCell, const Cell &theCellMin, const Cell &theCellMax, const Target &theTarget) |
| Internal removal function, performing iteration for adjacent cells by one dimension; called recursively to cover all dimensions.
|
void | inspect (const Cell &theCell, Inspector &theInspector) |
| Inspect the target objects in the specified cell.
|
void | iterateInspect (int idim, Cell &theCell, const Cell &theCellMin, const Cell &theCellMax, Inspector &theInspector) |
| Inspect the target objects in the specified range of the cells.
|
| Handle (NCollection_BaseAllocator) myAllocator |
Protected Attributes |
NCollection_Map< Cell > | myCells |
Standard_Real | myCellSize [Inspector::Dimension] |
Friends |
Standard_Integer | HashCode (const Cell &aCell, const Standard_Integer theUpper) |
Standard_Boolean | IsEqual (const Cell &aCell1, const Cell &aCell2) |
Data Structures |
struct | Cell |
struct | ListNode |
The algorithm is based on hash map, thus it has linear time of initialization (O(N) where N is number of cells covered by added targets) and constant-time search for one bullet (more precisely, O(M) where M is number of cells covered by the bullet).
The idea behind the algorithm is to separate each co-ordinate of the space into equal-size cells. Note that this works well when cell size is approximately equal to the characteristic size of the involved objects (targets and bullets; including tolerance eventually used for coincidence check).
As soon as all the targets are added, the algorithm is ready to check for coincidence. To find the targets coincident with any given bullet, it checks all the candidate targets in the cell(s) covered by the bullet object (methods Inspect()).
The set of targets can be modified during the process: new targets can be added by Add(), existing targets can be removed by Remove().
The algorithm is implemented as template class, thus it is capable to work with objects of any type. The only argument of the template should be the specific class providing all necessary features required by the algorithm:
Note that index i is from 0 to Dimension-1.
The returned value can be used to command CellFilter to remove the inspected item from the current cell; this allows to exclude the items that has been processed and are not needed any more in further search (for better performance).