Open CASCADE Technology  6.9.0
Data Structures | Public Types | Public Member Functions | Protected Member Functions | Protected Attributes | Friends

NCollection_CellFilter< Inspector > Class Template Reference

#include <NCollection_CellFilter.hxx>

Data Structures

struct  Cell
 
struct  ListNode
 

Public Types

typedef TYPENAME Inspector::Target Target
 
typedef TYPENAME Inspector::Point Point
 

Public Member Functions

 NCollection_CellFilter (Standard_Real theCellSize=0, const Handle< NCollection_IncAllocator > &theAlloc=0)
 Constructor; initialized by cell size. More...
 
 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. More...
 
void Reset (Standard_Real theCellSize, const Handle< NCollection_IncAllocator > &theAlloc=0)
 Clear the data structures, set new cell size and allocator. More...
 
void Reset (Standard_Real theCellSize[], const Handle< NCollection_IncAllocator > &theAlloc=0)
 Clear the data structures and set new cell sizes and allocator. More...
 
void Add (const Target &theTarget, const Point &thePnt)
 Adds a target object for further search at a point (into only one cell) More...
 
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) More...
 
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. More...
 
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. More...
 
void Inspect (const Point &thePnt, Inspector &theInspector)
 Inspect all targets in the cell corresponding to the given point. More...
 
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) More...
 

Protected Member Functions

void resetAllocator (const Handle< NCollection_IncAllocator > &theAlloc)
 Reset allocator to the new one. More...
 
void add (const Cell &theCell, const Target &theTarget)
 Add a new target object into the specified cell. More...
 
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. More...
 
void remove (const Cell &theCell, const Target &theTarget)
 Remove the target object from the specified cell. More...
 
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. More...
 
void inspect (const Cell &theCell, Inspector &theInspector)
 Inspect the target objects in the specified cell. More...
 
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. More...
 

Protected Attributes

Handle< NCollection_BaseAllocatormyAllocator
 
NCollection_Map< CellmyCells
 
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)
 

Detailed Description

template<class Inspector>
class NCollection_CellFilter< Inspector >

A data structure for sorting geometric objects (called targets) in n-dimensional space into cells, with associated algorithm for fast checking of coincidence (overlapping, intersection, etc.) with other objects (called here bullets).

Description

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).

Usage

The target objects to be searched are added to the tool by methods Add(); each target is classified as belonging to some cell(s). The data on cells (list of targets found in each one) are stored in the hash map with key being cumulative index of the cell by all co-ordinates. Thus the time needed to find targets in some cell is O(1) * O(number of targets in the cell).

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 methods Add() and Inspect() have two flavours each: one accepts single point identifying one cell, another accept two points specifying the range of cells. It should be noted that normally at least one of these methods is called as for range of cells: either due to objects having non- zero size, or in order to account for the tolerance when objects are points.

The set of targets can be modified during the process: new targets can be added by Add(), existing targets can be removed by Remove().

Implementation

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:

Member Typedef Documentation

template<class Inspector>
typedef TYPENAME Inspector::Point NCollection_CellFilter< Inspector >::Point
template<class Inspector>
typedef TYPENAME Inspector::Target NCollection_CellFilter< Inspector >::Target

Constructor & Destructor Documentation

template<class Inspector>
NCollection_CellFilter< Inspector >::NCollection_CellFilter ( Standard_Real  theCellSize = 0,
const Handle< NCollection_IncAllocator > &  theAlloc = 0 
)
inline

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()

template<class Inspector>
NCollection_CellFilter< Inspector >::NCollection_CellFilter ( Standard_Real  theCellSize[],
const Handle< NCollection_IncAllocator > &  theAlloc = 0 
)
inline

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.

Member Function Documentation

template<class Inspector>
void NCollection_CellFilter< Inspector >::Add ( const Target theTarget,
const Point thePnt 
)
inline

Adds a target object for further search at a point (into only one cell)

template<class Inspector>
void NCollection_CellFilter< Inspector >::Add ( const Target theTarget,
const Point thePntMin,
const Point thePntMax 
)
inline

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)

template<class Inspector>
void NCollection_CellFilter< Inspector >::add ( const Cell theCell,
const Target theTarget 
)
inlineprotected

Add a new target object into the specified cell.

template<class Inspector>
void NCollection_CellFilter< Inspector >::Inspect ( const Point thePnt,
Inspector &  theInspector 
)
inline

Inspect all targets in the cell corresponding to the given point.

template<class Inspector>
void NCollection_CellFilter< Inspector >::Inspect ( const Point thePntMin,
const Point thePntMax,
Inspector &  theInspector 
)
inline

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)

template<class Inspector>
void NCollection_CellFilter< Inspector >::inspect ( const Cell theCell,
Inspector &  theInspector 
)
inlineprotected

Inspect the target objects in the specified cell.

template<class Inspector>
void NCollection_CellFilter< Inspector >::iterateAdd ( int  idim,
Cell theCell,
const Cell theCellMin,
const Cell theCellMax,
const Target theTarget 
)
inlineprotected

Internal addition function, performing iteration for adjacent cells by one dimension; called recursively to cover all dimensions.

template<class Inspector>
void NCollection_CellFilter< Inspector >::iterateInspect ( int  idim,
Cell theCell,
const Cell theCellMin,
const Cell theCellMax,
Inspector &  theInspector 
)
inlineprotected

Inspect the target objects in the specified range of the cells.

template<class Inspector>
void NCollection_CellFilter< Inspector >::iterateRemove ( int  idim,
Cell theCell,
const Cell theCellMin,
const Cell theCellMax,
const Target theTarget 
)
inlineprotected

Internal removal function, performing iteration for adjacent cells by one dimension; called recursively to cover all dimensions.

template<class Inspector>
void NCollection_CellFilter< Inspector >::Remove ( const Target theTarget,
const Point thePnt 
)
inline

Find a target object at a point and remove it from the structures. For usage of this method "operator ==" should be defined for Target.

template<class Inspector>
void NCollection_CellFilter< Inspector >::Remove ( const Target theTarget,
const Point thePntMin,
const Point thePntMax 
)
inline

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.

template<class Inspector>
void NCollection_CellFilter< Inspector >::remove ( const Cell theCell,
const Target theTarget 
)
inlineprotected

Remove the target object from the specified cell.

template<class Inspector>
void NCollection_CellFilter< Inspector >::Reset ( Standard_Real  theCellSize,
const Handle< NCollection_IncAllocator > &  theAlloc = 0 
)
inline

Clear the data structures, set new cell size and allocator.

template<class Inspector>
void NCollection_CellFilter< Inspector >::Reset ( Standard_Real  theCellSize[],
const Handle< NCollection_IncAllocator > &  theAlloc = 0 
)
inline

Clear the data structures and set new cell sizes and allocator.

template<class Inspector>
void NCollection_CellFilter< Inspector >::resetAllocator ( const Handle< NCollection_IncAllocator > &  theAlloc)
inlineprotected

Reset allocator to the new one.

Friends And Related Function Documentation

template<class Inspector>
Standard_Integer HashCode ( const Cell aCell,
const Standard_Integer  theUpper 
)
friend
template<class Inspector>
Standard_Boolean IsEqual ( const Cell aCell1,
const Cell aCell2 
)
friend

Field Documentation

template<class Inspector>
Handle< NCollection_BaseAllocator > NCollection_CellFilter< Inspector >::myAllocator
protected
template<class Inspector>
NCollection_Map<Cell> NCollection_CellFilter< Inspector >::myCells
protected
template<class Inspector>
Standard_Real NCollection_CellFilter< Inspector >::myCellSize[Inspector::Dimension]
protected

The documentation for this class was generated from the following file: