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);
  }