RectangularLattice¶

The RectangularLattice is a helper class that maps all of N-D space into a regular, rectangular grid of cells identified by integer coordinates. The grid is defined by an origin point and a vector indicating spacing in each dimension.

The figure shows an example RectangularLattice in 2D, with its origin (circled) at (-0.6, -0.2) and spacing (1.2, 0.8). Given a query point, the RectangularLattice will return the coordinates of the cell that contains the point. It will also return the bounding box of a cell, or the coordinates of a cell’s lower-left corner.

The following example shows the use of the RectangularLattice. First, include the header and (if desired) declare type aliases. Using const int in2d = 2 makes a 2D lattice.

#include "axom/spin/RectangularLattice.hpp"
// We'll be using a 2D lattice with space coordinates of type double
// and cell coordinates of type int.
using RectLatticeType = axom::spin::RectangularLattice<in2D, double, int>;
// Get the types of coordinates and bounding box from the RectangularLattice
using RLGridCell = RectLatticeType::GridCell;
using RLSpacePt = RectLatticeType::SpacePoint;
using RLSpaceVec = RectLatticeType::SpaceVector;
using RLBBox = RectLatticeType::SpatialBoundingBox;

Use the RectangularLattice to find grid cells.

  // Origin and spacing
  double origin[] = {-0.6, -0.2};
  double spacing[] = {1.2, 0.8};

  // Instantiate a RectangularLattice.
  // Other constructors allow the use of Point and Vector objects.
  RectLatticeType lat(origin, spacing);

  // Query point (2.0, 1.2) should be in grid cell (2, 1)
  RLSpacePt pA = RLSpacePt::make_point(2.0, 1.2);
  RLGridCell cA = lat.gridCell(pA);
  std::cout << "Point " << pA << " is in grid cell " << cA
            << " (should be (2, 1))" << std::endl;

  // Query point (2.3, 0.8) should also be in grid cell (2, 1)
  RLSpacePt pB = RLSpacePt::make_point(2.3, 0.8);
  RLGridCell cB = lat.gridCell(pB);
  std::cout << "Point " << pB << " is in grid cell " << cB
            << " (should be (2, 1))" << std::endl;

  // What is the lowest corner and bounding box of the shared cell?
  RLSpacePt cellcorner = lat.spacePoint(cB);
  RLBBox cellbbox = lat.cellBounds(cB);
  std::cout << "The lower corner of the grid cell is " << cellcorner
            << " and its bounding box is " << cellbbox << std::endl;

Mortonizer¶

The Mortonizer (along with its associated class MortonBase) implements the Morton index, an operation that associates each point in N-D space with a point on a space-filling curve [1]. The PointHash class adapts the Mortonizer to provide a hashing functionality for use with std::unordered_map or similar container classes.

The math of the Morton index works with integers. Thus the Mortonizer and its dependent class PointHash will not work with floating point coordinates. The following code example shows how the cells of a RectangularLattice, which have integer coordinates, can be used with a hash table.

The Mortonizer works by interleaving bits from each coordinate of the input point and finite computer hardware limits its resolution. If the MortonIndexType is 64-bits, then in 2D it can uniquely index the least significant 32 bits of the x- and y-coordinates. In 3D, it can uniquely index the least significant 21 bits of the x-, y-, and z-coordinates.

To use the PointHash, include the header and (as desired) declare type aliases.

#include "axom/spin/MortonIndex.hpp"
#include <unordered_map>
// The PointHash will allow us to use integral N-D coordinates as a hash key.
// This example will use RectangularLattice grid cell coordinates as keys to
// a std::unordered_map.
using PointHashType = axom::spin::PointHash<RLGridCell::CoordType>;
// Here's a class defined elsewhere that will do some work on a point.
class DataContainer;
using MapType = std::unordered_map<RLGridCell, DataContainer, PointHashType>;

The RectangularLattice grid cell associated with a query point can be stored, using a PointHash, in a std::unordered_map.

  // Make a RectangularLattice to bin query points.
  double origin[] = {-0.6, -0.2};
  double spacing[] = {1.2, 0.8};
  RectLatticeType lat(origin, spacing);

  // Make the map from grid point to DataContainer
  MapType map;

  // For several query points, create a DataContainer if necessary and register
  // the point.
  std::vector<RLSpacePt> pts = generatePoints();
  for(RLSpacePt p : pts)
  {
    RLGridCell g = lat.gridCell(p);
    DataContainer dat;
    if(map.count(g) > 0)
    {
      dat = map[g];
    }
    dat.registerPoint(p);
    map[g] = dat;
  }

  // Report on what was registered.
  for(auto iter : map)
  {
    RLGridCell g = iter.first;
    DataContainer dat = iter.second;
    std::cout << "Grid cell " << g << " holds " << dat.count << " points."
              << std::endl;
  }

Footnotes