# 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

[1] | The Morton index is also known, among other things, as the Z-order curve: see its Wikipedia page. |