AXOM
Axom provides a robust, flexible software infrastructure for the development of multi-physics applications and computational tools.
axom::spin::ImplicitGrid< NDIMS, TheIndexType > Class Template Reference

An implicit grid is an occupancy-based spatial index over an indexed set of objects in space. More...

#include </home/docs/checkouts/readthedocs.org/user_builds/axom/checkouts/docs-essman-container_strict/src/axom/spin/ImplicitGrid.hpp>

Public Types

using IndexType = TheIndexType
 
using GridCell = primal::Point< IndexType, NDIMS >
 
using SpacePoint = primal::Point< double, NDIMS >
 
using SpaceVec = primal::Vector< double, NDIMS >
 
using SpatialBoundingBox = primal::BoundingBox< double, NDIMS >
 
using LatticeType = RectangularLattice< NDIMS, double, IndexType >
 
using SizePolicy = slam::policies::RuntimeSize< IndexType >
 
using ElementSet = slam::OrderedSet< IndexType, IndexType, SizePolicy >
 
using BinSet = slam::OrderedSet< IndexType, IndexType, SizePolicy >
 
using BitsetType = slam::BitSet
 
using BinBitMap = slam::Map< slam::Set< IndexType, IndexType >, BitsetType >
 

Public Member Functions

 ImplicitGrid ()
 Default constructor for an ImplicitGrid. More...
 
 ImplicitGrid (const SpatialBoundingBox &boundingBox, const GridCell *gridRes, int numElts)
 Constructor for an implicit grid from a bounding box, a grid resolution a number of elements. More...
 
 ImplicitGrid (const double *bbMin, const double *bbMax, const int *gridRes, int numElts)
 Constructor for an implicit grid from arrays of primitive types. More...
 
bool isInitialized () const
 
void initialize (const SpatialBoundingBox &boundingBox, const GridCell *gridRes, int numElts)
 Initializes an implicit grid or resolution gridRes over an axis aligned domain covered by boundingBox. The implicit grid indexes a set with numElts elements. More...
 
const GridCellgridResolution () const
 
int numIndexElements () const
 
void insert (SpatialBoundingBox bbox, IndexType idx)
 Inserts an element with index idx and bounding box bbox into the implicit grid. More...
 
BitsetType getCandidates (const SpacePoint &pt) const
 
BitsetType getCandidates (const SpatialBoundingBox &box) const
 
template<typename QueryGeom >
std::vector< IndexTypegetCandidatesAsArray (const QueryGeom &query) const
 
bool contains (const GridCell &gridCell, IndexType idx) const
 

Detailed Description

template<int NDIMS, typename TheIndexType = int>
class axom::spin::ImplicitGrid< NDIMS, TheIndexType >

An implicit grid is an occupancy-based spatial index over an indexed set of objects in space.

An ImplicitGrid divides a given rectilinear slab of space (defined by an axis aligned bounding box) into uniformly sized cells of a specified resolution. The GridCells of the ImplicitGrid index a subset of the items from an indexed set whose cardinality is specified during the ImplicitGrid's initialization. Users can insert items from the indexed set into an ImplicitGrid by providing the item's bounding box and index.

In contrast to a spin::UniformGrid, which encodes an array of indices for each cell in the underlying multidimensional grid, the ImplicitGrid encodes a single array of bins per dimension, each of which has a bitset over the index space. Thus, the storage overhead of an ImplicitGrid is fixed at initialization time to \( numElts * sum_i { res[i] } \) bits. Queries are implemented in terms of unions and intersections of bitsets.

One might prefer an ImplicitGrid over a UniformGrid when one expects a relatively dense index relative to the grid resolution (i.e. that there will be many items indexed per bucket). The ImplicitGrid is designed for quick indexing and searching over a static (and relatively small index space) in a relatively coarse grid.

Member Typedef Documentation

◆ IndexType

template<int NDIMS, typename TheIndexType = int>
using axom::spin::ImplicitGrid< NDIMS, TheIndexType >::IndexType = TheIndexType

◆ GridCell

template<int NDIMS, typename TheIndexType = int>
using axom::spin::ImplicitGrid< NDIMS, TheIndexType >::GridCell = primal::Point<IndexType, NDIMS>

◆ SpacePoint

template<int NDIMS, typename TheIndexType = int>
using axom::spin::ImplicitGrid< NDIMS, TheIndexType >::SpacePoint = primal::Point<double, NDIMS>

◆ SpaceVec

template<int NDIMS, typename TheIndexType = int>
using axom::spin::ImplicitGrid< NDIMS, TheIndexType >::SpaceVec = primal::Vector<double, NDIMS>

◆ SpatialBoundingBox

template<int NDIMS, typename TheIndexType = int>
using axom::spin::ImplicitGrid< NDIMS, TheIndexType >::SpatialBoundingBox = primal::BoundingBox<double, NDIMS>

◆ LatticeType

template<int NDIMS, typename TheIndexType = int>
using axom::spin::ImplicitGrid< NDIMS, TheIndexType >::LatticeType = RectangularLattice<NDIMS, double, IndexType>

◆ SizePolicy

template<int NDIMS, typename TheIndexType = int>
using axom::spin::ImplicitGrid< NDIMS, TheIndexType >::SizePolicy = slam::policies::RuntimeSize<IndexType>

◆ ElementSet

template<int NDIMS, typename TheIndexType = int>
using axom::spin::ImplicitGrid< NDIMS, TheIndexType >::ElementSet = slam::OrderedSet<IndexType, IndexType, SizePolicy>

◆ BinSet

template<int NDIMS, typename TheIndexType = int>
using axom::spin::ImplicitGrid< NDIMS, TheIndexType >::BinSet = slam::OrderedSet<IndexType, IndexType, SizePolicy>

◆ BitsetType

template<int NDIMS, typename TheIndexType = int>
using axom::spin::ImplicitGrid< NDIMS, TheIndexType >::BitsetType = slam::BitSet

◆ BinBitMap

template<int NDIMS, typename TheIndexType = int>
using axom::spin::ImplicitGrid< NDIMS, TheIndexType >::BinBitMap = slam::Map<slam::Set<IndexType, IndexType>, BitsetType>

Constructor & Destructor Documentation

◆ ImplicitGrid() [1/3]

template<int NDIMS, typename TheIndexType = int>
axom::spin::ImplicitGrid< NDIMS, TheIndexType >::ImplicitGrid ( )
inline

Default constructor for an ImplicitGrid.

Note
Users must call initialize() to initialize the ImplicitGrid after constructing with the default constructor

◆ ImplicitGrid() [2/3]

template<int NDIMS, typename TheIndexType = int>
axom::spin::ImplicitGrid< NDIMS, TheIndexType >::ImplicitGrid ( const SpatialBoundingBox boundingBox,
const GridCell gridRes,
int  numElts 
)
inline

Constructor for an implicit grid from a bounding box, a grid resolution a number of elements.

Parameters
[in]boundingBoxBounding box of domain to index
[in]gridResPointer to resolution for lattice covering bounding box
[in]numEltsThe number of elements to be indexed
Precondition
gridRes is either NULL or has NDIMS coordinates
See also
initialize() for details on setting grid resolution when gridRes is NULL

References axom::spin::ImplicitGrid< NDIMS, TheIndexType >::initialize().

◆ ImplicitGrid() [3/3]

template<int NDIMS, typename TheIndexType = int>
axom::spin::ImplicitGrid< NDIMS, TheIndexType >::ImplicitGrid ( const double *  bbMin,
const double *  bbMax,
const int *  gridRes,
int  numElts 
)
inline

Constructor for an implicit grid from arrays of primitive types.

Parameters
[in]bbMinLower bounds of mesh bounding box
[in]bbMaxUpper bounds of mesh bounding box
[in]gridResResolution for lattice covering mesh bounding box
[in]numEltsThe number of elements in the index space
Precondition
bbMin and bbMax are not NULL and have NDIMS coordinates
gridRes is either NULL or has NDIMS coordinates
See also
initialize() for details on setting grid resolution when gridRes is NULL

References axom::spin::ImplicitGrid< NDIMS, TheIndexType >::initialize(), and SLIC_ASSERT.

Member Function Documentation

◆ isInitialized()

template<int NDIMS, typename TheIndexType = int>
bool axom::spin::ImplicitGrid< NDIMS, TheIndexType >::isInitialized ( ) const
inline

Predicate to check if the ImplicitGrid has been initialized

◆ initialize()

template<int NDIMS, typename TheIndexType = int>
void axom::spin::ImplicitGrid< NDIMS, TheIndexType >::initialize ( const SpatialBoundingBox boundingBox,
const GridCell gridRes,
int  numElts 
)
inline

Initializes an implicit grid or resolution gridRes over an axis aligned domain covered by boundingBox. The implicit grid indexes a set with numElts elements.

Parameters
[in]boundingBoxBounding box of domain to index
[in]gridResResolution for lattice covering bounding box
[in]numEltsThe number of elements to be indexed
Precondition
The ImplicitGrid has not already been initialized
Note
When gridRes is NULL, we use a heuristic to set the grid resolution to the N^th root of numElts. We also ensure that the resolution along any dimension is at least one.

References axom::primal::Point< T, NDIMS >::array(), axom::utilities::max(), axom::primal::Vector< T, NDIMS >::norm(), axom::primal::BoundingBox< T, NDIMS >::range(), axom::spin::rectangular_lattice_from_bounding_box(), and SLIC_ASSERT.

Referenced by axom::spin::ImplicitGrid< NDIMS, TheIndexType >::ImplicitGrid().

◆ gridResolution()

template<int NDIMS, typename TheIndexType = int>
const GridCell& axom::spin::ImplicitGrid< NDIMS, TheIndexType >::gridResolution ( ) const
inline

Accessor for ImplicitGrid's resolution

◆ numIndexElements()

template<int NDIMS, typename TheIndexType = int>
int axom::spin::ImplicitGrid< NDIMS, TheIndexType >::numIndexElements ( ) const
inline

◆ insert()

template<int NDIMS, typename TheIndexType = int>
void axom::spin::ImplicitGrid< NDIMS, TheIndexType >::insert ( SpatialBoundingBox  bbox,
IndexType  idx 
)
inline

Inserts an element with index idx and bounding box bbox into the implicit grid.

Parameters
[in]bboxThe bounding box of the element
[in]idxThe index of the element
Note
bbox is intentionally passed by value since insert() modifies its bounds

References axom::utilities::clampLower(), axom::utilities::clampUpper(), axom::primal::BoundingBox< T, NDIMS >::expand(), axom::primal::BoundingBox< T, NDIMS >::getMax(), axom::primal::BoundingBox< T, NDIMS >::getMin(), axom::spin::RectangularLattice< NDIMS, SpaceCoordType, CellCoordType >::gridCell(), axom::slam::Map< SetType, DataType, StridePolicy >::set(), and SLIC_ASSERT.

◆ getCandidates() [1/2]

template<int NDIMS, typename TheIndexType = int>
BitsetType axom::spin::ImplicitGrid< NDIMS, TheIndexType >::getCandidates ( const SpacePoint pt) const
inline

Finds the candidate elements in the vicinity of query point pt

Parameters
[in]ptThe query point
Returns
A bitset bSet whose bits correspond to the elements of the IndexSet. The bits of bSet are set if their corresponding element bounding boxes overlap the grid cell containing pt.

References axom::utilities::clampUpper(), axom::primal::BoundingBox< T, NDIMS >::contains(), and axom::spin::RectangularLattice< NDIMS, SpaceCoordType, CellCoordType >::gridCell().

Referenced by axom::spin::ImplicitGrid< NDIMS, TheIndexType >::getCandidatesAsArray().

◆ getCandidates() [2/2]

template<int NDIMS, typename TheIndexType = int>
BitsetType axom::spin::ImplicitGrid< NDIMS, TheIndexType >::getCandidates ( const SpatialBoundingBox box) const
inline

Finds the candidate elements in the vicinity of query box box

Parameters
[in]boxThe query box
Returns
A bitset bSet whose bits correspond to the elements of the IndexSet. The bits of bSet are set if their corresponding element bounding boxes overlap the grid cell containing box

References axom::primal::BoundingBox< T, NDIMS >::getMax(), axom::primal::BoundingBox< T, NDIMS >::getMin(), axom::spin::RectangularLattice< NDIMS, SpaceCoordType, CellCoordType >::gridCell(), and axom::primal::BoundingBox< T, NDIMS >::intersectsWith().

◆ getCandidatesAsArray()

template<int NDIMS, typename TheIndexType = int>
template<typename QueryGeom >
std::vector<IndexType> axom::spin::ImplicitGrid< NDIMS, TheIndexType >::getCandidatesAsArray ( const QueryGeom &  query) const
inline

Returns an explicit list of candidates in the vicinity of a query object

Template Parameters
QueryGeomThe type of the query object (e.g. point or box)
Parameters
[in]queryThe query object
Returns
A list of indexes from the IndexSet whose corresponding bounding boxes overlap the grid cell containing query
Precondition
This function is implemented in terms of ImplicitGrid::getCandidates(const QueryGeom& ). An overload for the actual QueryGeom type (e.g. SpacePoint or SpatialBoundingBox) must exist.
Note
This function returns the same information as getCandidates(), but in a different format. While the latter returns a bitset of the candidates, this function returns an explicit list of indices.
See also
getCandidates()

References axom::slam::BitSet::count(), axom::slam::BitSet::find_first(), axom::slam::BitSet::find_next(), axom::spin::ImplicitGrid< NDIMS, TheIndexType >::getCandidates(), and axom::slam::BitSet::npos.

◆ contains()

template<int NDIMS, typename TheIndexType = int>
bool axom::spin::ImplicitGrid< NDIMS, TheIndexType >::contains ( const GridCell gridCell,
IndexType  idx 
) const
inline

Tests whether grid cell gridPt indexes the element with index idx

Parameters
[in]gridCellThe cell within the ImplicitGrid that we are testing
[in]idxAn element index from the IndexSet to test
Precondition
idx should be in the IndexSet. I.e. 0 <= idx < numIndexElements()
Returns
True if the bounding box of element idx overlaps with GridCell gridCell.

References axom::utilities::clampLower(), axom::utilities::clampUpper(), axom::slam::OrderedSet< PosType, ElemType, SizePolicy, OffsetPolicy, StridePolicy, IndirectionPolicy, SubsettingPolicy >::isValidIndex(), axom::slam::OrderedSet< PosType, ElemType, SizePolicy, OffsetPolicy, StridePolicy, IndirectionPolicy, SubsettingPolicy >::size(), and SLIC_ASSERT.


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