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/v0.3.3/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<>, 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 GridCell &	gridResolution () 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< IndexType >	getCandidatesAsArray (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<>, 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]	boundingBox	Bounding box of domain to index
[in]	gridRes	Pointer to resolution for lattice covering bounding box
[in]	numElts	The 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]	bbMin	Lower bounds of mesh bounding box
[in]	bbMax	Upper bounds of mesh bounding box
[in]	gridRes	Resolution for lattice covering mesh bounding box
[in]	numElts	The 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]	boundingBox	Bounding box of domain to index
[in]	gridRes	Resolution for lattice covering bounding box
[in]	numElts	The 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

Returns the number of elements in the ImplicitGrid's index set

References axom::slam::OrderedSet< PosType, ElemType, SizePolicy, OffsetPolicy, StridePolicy, IndirectionPolicy, SubsettingPolicy >::size().

◆ 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]	bbox	The bounding box of the element
[in]	idx	The 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] pt The 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] box The 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

QueryGeom The type of the query object (e.g. point or box)

Parameters

[in] query The 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]	gridCell	The cell within the ImplicitGrid that we are testing
[in]	idx	An 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:

/home/docs/checkouts/readthedocs.org/user_builds/axom/checkouts/v0.3.3/src/axom/spin/ImplicitGrid.hpp

Public Types

Public Member Functions

Detailed Description

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

Member Typedef Documentation

◆ IndexType

◆ GridCell

◆ SpacePoint

◆ SpaceVec

◆ SpatialBoundingBox

◆ LatticeType

◆ SizePolicy

◆ ElementSet

◆ BinSet

◆ BitsetType

◆ BinBitMap

Constructor & Destructor Documentation

◆ ImplicitGrid() [1/3]

◆ ImplicitGrid() [2/3]

◆ ImplicitGrid() [3/3]

Member Function Documentation

◆ isInitialized()

◆ initialize()

◆ gridResolution()

◆ numIndexElements()

◆ insert()

◆ getCandidates() [1/2]

◆ getCandidates() [2/2]

◆ getCandidatesAsArray()

◆ contains()

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