Classes | Public Member Functions | Protected Types | Protected Attributes | Private Member Functions | List of all members
SurgSim::DataStructures::Grid< T, N > Class Template Reference

n-dimensional grid structure with uniform non-cubic cells This data structure is useful to search for neighbors in a given range (the size of each cell) More...

#include <SurgSim/DataStructures/Grid.h>

Classes

struct  CellContent
 Data structure for a cell's content (the list of elements and the list of all the neighbors) More...
 
class  NDIdHash
 Enable the NDId to be used as a key in an unordered map. More...
 

Public Member Functions

 Grid (const Eigen::Matrix< double, N, 1 > &cellSize, const Eigen::AlignedBox< double, N > &bounds)
 Constructor. More...
 
virtual ~Grid ()
 Destructor. More...
 
void reset ()
 Reset the grid content and the neighbors' mapping. More...
 
template<class Derived >
void addElement (const T element, const Eigen::MatrixBase< Derived > &position)
 Add an element in the grid. More...
 
const std::vector< T > & getNeighbors (const T &element)
 Retrieve an elements' neighbors. More...
 
template<class Derived >
const std::vector< T > & getNeighbors (const Eigen::MatrixBase< Derived > &position)
 Retrieve the neighbors of a location. More...
 

Protected Types

typedef Eigen::Matrix< int, N, 1 > NDId
 The type of the n-dimensional cell Id. More...
 

Protected Attributes

std::unordered_map< NDId, CellContent, NDIdHashm_activeCells
 Active cells (referenced by their ids (spatial hashing)) with their content. More...
 
std::unordered_map< T, NDIdm_cellIds
 Mapping from element to cell id containing the element. More...
 
Eigen::Matrix< double, N, 1 > m_size
 Size of each cell (same on all dimension) More...
 
Eigen::AlignedBox< double, N > m_aabb
 Grid min and max. More...
 
bool m_neighborsDirtyFlag
 Does the neighbors needs to be recomputed ? More...
 

Private Member Functions

void update ()
 Update the neighbors lists. More...
 
void getNeighborsCellIds (NDId cellId, std::array< NDId, powerOf3< N >::value > *cellsIds)
 Retrieve the neighboring cells id (including this cell) More...
 
bool isNdGreaterOrEqual (const NDId &a, const NDId &b)
 

Detailed Description

template<typename T, size_t N>
class SurgSim::DataStructures::Grid< T, N >

n-dimensional grid structure with uniform non-cubic cells This data structure is useful to search for neighbors in a given range (the size of each cell)

Template Parameters
TElement type to be stored
NThe dimension of the grid (i.e. 2 => 2D, 3 => 3D)

Member Typedef Documentation

◆ NDId

template<typename T , size_t N>
typedef Eigen::Matrix<int, N, 1> SurgSim::DataStructures::Grid< T, N >::NDId
protected

The type of the n-dimensional cell Id.

Constructor & Destructor Documentation

◆ Grid()

template<typename T , size_t N>
SurgSim::DataStructures::Grid< T, N >::Grid ( const Eigen::Matrix< double, N, 1 > &  cellSize,
const Eigen::AlignedBox< double, N > &  bounds 
)

Constructor.

Parameters
cellSizeThe size of each cell in dimension N (i.e. cells are not necessarily cubic).
boundsThe dimension-N boundaries of the space covered by the grid.

◆ ~Grid()

template<typename T , size_t N>
SurgSim::DataStructures::Grid< T, N >::~Grid ( )
virtual

Destructor.

Member Function Documentation

◆ addElement()

template<typename T , size_t N>
template<class Derived >
void SurgSim::DataStructures::Grid< T, N >::addElement ( const T  element,
const Eigen::MatrixBase< Derived > &  position 
)

Add an element in the grid.

Parameters
elementto be added at this position
positionof the element in the n-D space
Note
If the position is outside of the grid, the element is simply not added to the grid

Flag that the neighbors list will need to be recomputed on the next access

◆ getNeighbors() [1/2]

template<typename T , size_t N>
const std::vector< T > & SurgSim::DataStructures::Grid< T, N >::getNeighbors ( const T &  element)

Retrieve an elements' neighbors.

Parameters
elementThe element for which the neighbors are requested
Returns
The element's neighbors list (including the element itself)

◆ getNeighbors() [2/2]

template<typename T , size_t N>
template<class Derived >
const std::vector< T > & SurgSim::DataStructures::Grid< T, N >::getNeighbors ( const Eigen::MatrixBase< Derived > &  position)

Retrieve the neighbors of a location.

Parameters
positionThe position for which the neighbors are requested
Returns
The neighbors for this position, i.e. all the elements in the positions cell and all surrounding cells

◆ getNeighborsCellIds()

template<typename T , size_t N>
void SurgSim::DataStructures::Grid< T, N >::getNeighborsCellIds ( NDId  cellId,
std::array< NDId, powerOf3< N >::value > *  cellsIds 
)
private

Retrieve the neighboring cells id (including this cell)

Parameters
cellIdfor which the neighbors cells are requested
cellsIds[out] Neighbors cells ids

◆ isNdGreaterOrEqual()

template<typename T , size_t N>
bool SurgSim::DataStructures::Grid< T, N >::isNdGreaterOrEqual ( const NDId a,
const NDId b 
)
private
Parameters
aThe first cell ID.
bThe second cell ID.
Returns
true if a is > b.

◆ reset()

template<typename T , size_t N>
void SurgSim::DataStructures::Grid< T, N >::reset ( )

Reset the grid content and the neighbors' mapping.

◆ update()

template<typename T , size_t N>
void SurgSim::DataStructures::Grid< T, N >::update ( )
private

Update the neighbors lists.

Member Data Documentation

◆ m_aabb

template<typename T , size_t N>
Eigen::AlignedBox<double, N> SurgSim::DataStructures::Grid< T, N >::m_aabb
protected

Grid min and max.

◆ m_activeCells

template<typename T , size_t N>
std::unordered_map<NDId, CellContent, NDIdHash> SurgSim::DataStructures::Grid< T, N >::m_activeCells
protected

Active cells (referenced by their ids (spatial hashing)) with their content.

◆ m_cellIds

template<typename T , size_t N>
std::unordered_map<T, NDId> SurgSim::DataStructures::Grid< T, N >::m_cellIds
protected

Mapping from element to cell id containing the element.

◆ m_neighborsDirtyFlag

template<typename T , size_t N>
bool SurgSim::DataStructures::Grid< T, N >::m_neighborsDirtyFlag
protected

Does the neighbors needs to be recomputed ?

◆ m_size

template<typename T , size_t N>
Eigen::Matrix<double, N, 1> SurgSim::DataStructures::Grid< T, N >::m_size
protected

Size of each cell (same on all dimension)


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