# ImplicitGrid¶

Where the `UniformGrid`

divides a rectangular region of interest into bins,
the `ImplicitGrid`

divides each axis of the region of interest into bins.
Each `UniformGrid`

bin holds indexes of items that intersect that bin; each
`ImplicitGrid`

bin is a bitset that indicates the items intersecting that bin.

The following figure shows a 2D `ImplicitGrid`

indexing a collection of
polygons. A query point determines the bin to search for intersecting
polygons. The application retrieves that bin’s bitset from each axis and
computes bitwise AND operator. The code takes that result and tests for query
point intersection (possibly an expensive operation) with each of the polygons
indicated by bits set “on.”

The `ImplicitGrid`

is designed for quick indexing and searching over a static
index space in a relatively coarse grid, making it suitable for repeated
construction as well as lookup. The following example shows the use of the
`ImplicitGrid`

. It is similar to the figure but tests a point against 2D
triangles instead of polygons.

```
#include "axom/spin/ImplicitGrid.hpp"
// the ImplicitGrid will be in 2D
using IGridT = axom::spin::ImplicitGrid<in2D>;
// useful derived types
using IGridCell = typename IGridT::GridCell;
using ISpacePt = typename IGridT::SpacePoint;
using IBBox = typename IGridT::SpatialBoundingBox;
using IBitsetType = typename IGridT::BitsetType;
using IBitsetIndexType = typename IBitsetType::Index;
// some functions we'll use
bool expensiveTest(ISpacePt& query, Triangle2DType& tri);
void makeTriangles(std::vector<Triangle2DType>& tris);
```

After including the header and setting up types, set up the index.

```
// here are the triangles.
std::vector<Triangle2DType> tris;
makeTriangles(tris);
// Set up the ImplicitGrid: ten bins on an axis
IGridCell res(10);
// establish the domain of the ImplicitGrid.
IBBox bbox(ISpacePt::zero(), ISpacePt::ones());
// room for one hundred elements in the index
const int numElts = static_cast<int>(tris.size());
IGridT grid(bbox, &res, numElts);
// load the bounding box of each triangle, along with its index,
// into the ImplicitGrid.
for(int i = 0; i < numElts; ++i)
{
grid.insert(findBbox(tris[i]), i);
}
```

Inexpensive queries to the index reduce the number of calls to a (possibly) expensive test routine.

```
// Here is our query point
ISpacePt qpt = ISpacePt::make_point(0.63, 0.42);
// Which triangles might it intersect?
IBitsetType candidates = grid.getCandidates(qpt);
int totalTrue = 0;
// Iterate over the bitset and test the candidates expensively.
IBitsetIndexType index = candidates.find_first();
while(index != IBitsetType::npos)
{
if(expensiveTest(qpt, tris[index]))
{
totalTrue += 1;
}
index = candidates.find_next(index);
}
```