A grid discretization using hexagonal cells. More...

#include <hexagonal.hh>

Inheritance diagram for Utopia::HexagonalGrid< Space >:

Collaboration diagram for Utopia::HexagonalGrid< Space >:

Public Types
using	Base = Grid< Space >
	Base class type. More...

using	SpaceVec = typename Space::SpaceVec
	The type of vectors that have a relation to physical space. More...

using	MultiIndex = MultiIndexType< dim >
	The type of multi-index like arrays, e.g. the grid shape. More...

using	Config = DataIO::Config
	The configuration type. More...

Public Types inherited from Utopia::Grid< Space >
using	Self = Grid< Space >
	Type of this class, i.e. the base grid class. More...

using	SpaceVec = typename Space::SpaceVec
	The type of vectors that have a relation to physical space. More...

using	MultiIndex = MultiIndexType< dim >
	The type of multi-index like arrays, e.g. the grid shape. More...

using	Config = DataIO::Config
	The configuration type. More...

Public Member Functions
	HexagonalGrid (std::shared_ptr< Space > space, const Config &cfg)
	Construct a hexagonal grid discretization. More...

IndexType	num_cells () const override
	Number of hexagonal cells required to fill the physical space. More...

SpaceVec	effective_resolution () const override
	The effective cell resolution into each physical space dimension. More...

MultiIndex	shape () const override
	Get shape of the hexagonal grid. More...

GridStructure	structure () const override
	Structure of the grid. More...

MultiIndex	midx_of (const IndexType id) const override
	Returns the multi-index of the cell with the given ID. More...

SpaceVec	barycenter_of (const IndexType id) const override
	Returns the barycenter of the cell with the given ID. More...

SpaceVec	extent_of (const IndexType) const override
	Returns the extent of the cell with the given ID. More...

std::vector< SpaceVec >	vertices_of (const IndexType id) const override
	Returns the vertices of the cell with the given ID. More...

IndexType	cell_at (const SpaceVec &pos) const override
	Return the ID of the cell covering the given point in physical space. More...

std::set< IndexType >	boundary_cells (std::string select="all") const override
	Retrieve a set of cell indices that are at a specified boundary. More...

Public Member Functions inherited from Utopia::Grid< Space >
	Grid (std::shared_ptr< Space > space, const Config &cfg)
	Construct a grid discretization. More...

virtual	~Grid ()=default
	Virtual destructor to allow polymorphic destruction. More...

IndexContainer	neighbors_of (const IndexType id) const
	Returns the indices of the neighbors of the cell with the given ID. More...

void	select_neighborhood (NBMode nb_mode, const Config &nb_params={})

const NBMode &	nb_mode () const
	Const reference to the currently selected neighborhood mode. More...

const Config &	nb_params () const
	The neighborhood parameters of the currently selected neighborhood. More...

auto	nb_size () const
	Maximum size of the currently selected neighborhood. More...

auto	resolution () const
	Get scalar resolution value of this grid. More...

std::string	structure_name () const
	Structure of the grid as std::string. More...

const std::shared_ptr< Space > &	space () const
	Const reference to the space this grid maps to. More...

bool	is_periodic () const
	Whether the space this grid maps to is periodic. More...

Static Public Attributes
static constexpr DimType	dim = Space::dim
	The dimensionality of the space to be discretized (for easier access) More...

Static Public Attributes inherited from Utopia::Grid< Space >
static constexpr DimType	dim = Space::dim
	The dimensionality of the space to be discretized (for easier access) More...

Protected Member Functions
NBFuncID< Base >	get_nb_func (NBMode nb_mode, const Config &nb_params) override
	Retrieve the neighborhood function depending on the mode. More...

DistType	expected_num_neighbors (const NBMode &nb_mode, const Config &) const override
	Computes the expected number of neighbors for a neighborhood mode. More...

NBFuncID< Base >	get_nb_func_hexagonal (const Config &nb_params)
	Returns a standalone hexagonal neighborhood function. More...

template<DimType axis, bool periodic>
void	add_neighbors_in_ (const IndexType root_id, IndexContainer &neighbor_ids) const
	Add both direct neighbors to a container of indices. More...

template<bool check_shape = false>
DistType	get_nb_param_distance (const Config &params) const
	Extract the `distance` neighborhood parameter from the given config. More...

Protected Attributes
NBFuncID< Base >	_nb_hexagonal_periodic
	The Von-Neumann neighborhood for periodic grids. More...

NBFuncID< Base >	_nb_hexagonal_nonperiodic
	The Von-Neumann neighborhood for non-periodic grids. More...

Protected Attributes inherited from Utopia::Grid< Space >
const std::shared_ptr< Space >	_space
	The space that is to be discretized. More...

const DistType	_resolution
	How many cells to place per length unit of space. More...

NBMode	_nb_mode
	Neighborhood mode. More...

Config	_nb_params
	Neighborhood parameters. More...

NBFuncID< Self >	_nb_func
	Neighborhood function (working on cell IDs) More...

NBFuncID< Self >	_nb_empty
	A neighborhood function for empty neighborhood. More...

Private Member Functions
MultiIndex	determine_shape () const
	Get shape of the hexagonal grid. More...

Private Attributes
const MultiIndex	_shape
	The (multi-index) shape of the grid, resulting from resolution. More...

const SpaceVec	_cell_extent
	The extent of each cell of this discretization (same for all) More...

Detailed Description

template<class Space>
class Utopia::HexagonalGrid< Space >

A grid discretization using hexagonal cells.

This is a grid discretization using hexagonal cells

The hexagonal tiling is constructed in pointy-topped orientation (one vertex of the hexagon pointing up) with an even row offset (every even row is displaced half a cell width to the right).

The hexagonal cellular arrangement covers a periodic space perfectly. In this setup the right-most cell in offset rows is half cut, covering the remaining space at the left boundary. Similarly, the tip of the cells in the upper-most row covers the free space at the lower boundary. In non-periodic space these cells are cut and at the opposite boundary space remains under-represented.

Top: pointy tops are cut off
Right: offset row cells are cut in half
Bottom: no cutoff, but unrepresented area the same shape as the top-side cutoff. Points within these triangles are mapped to nearest cell
Left: no cutoff, but unrepresented area the same shape as the right-side cutoff. Points within these half-cells are mapped to the nearest cell.

Note: Indices are constructed in "Fortran"-style, i.e. with the first index changing fastest (also called "column major"). For example, when iterating over the cell IDs and having a 2D space, the iteration goes first along the x-axis and then along the y-axis: 0, 1, …, N_x, N_x + 1, …, 2*N_x, 2*N_x + 1, …, N_x * N_y - 1

For more information on hexagonal grids, see this tutorial.

This class has been implemented following the above tutorial written by Amit Patel and published on www.redblobgames.com (last accessed version from May 2020).

Member Typedef Documentation

◆ Base

template<class Space >

using Utopia::HexagonalGrid< Space >::Base = Grid<Space>

Base class type.

◆ Config

template<class Space >

using Utopia::HexagonalGrid< Space >::Config = DataIO::Config

The configuration type.

◆ MultiIndex

template<class Space >

using Utopia::HexagonalGrid< Space >::MultiIndex = MultiIndexType<dim>

The type of multi-index like arrays, e.g. the grid shape.

◆ SpaceVec

template<class Space >

using Utopia::HexagonalGrid< Space >::SpaceVec = typename Space::SpaceVec

The type of vectors that have a relation to physical space.

Constructor & Destructor Documentation

◆ HexagonalGrid()

template<class Space >

Utopia::HexagonalGrid< Space >::HexagonalGrid	(	std::shared_ptr< Space >	space,
		const Config &	cfg
	)

inline

Construct a hexagonal grid discretization.

Parameters

space	The space to construct the discretization for
cfg	Further configuration parameters

Member Function Documentation

◆ add_neighbors_in_()

template<class Space >

template<DimType axis, bool periodic>

void Utopia::HexagonalGrid< Space >::add_neighbors_in_	(	const IndexType	root_id,
		IndexContainer &	neighbor_ids
	)		const

inlineprotected

Add both direct neighbors to a container of indices.

This function takes an index container and populates it with the indices of neighboring cells in different dimensions, specified by template parameter 0 < axis < number of dimensions - 1.

The algorithm first calculates whether the given root cell index has a front or back boundary in the chosen dimension. If so, the neighboring cell is only added if the grid is periodic.

Parameters

root_id	Which cell to find the agents of
neighbor_ids	The container to populate with the indices

Template Parameters

axis	The axis along which to add the neighbors (0-based!)
periodic	Whether the grid is periodic

Returns: void

◆ barycenter_of()

template<class Space >

SpaceVec Utopia::HexagonalGrid< Space >::barycenter_of ( const IndexType id ) const

inlineoverridevirtual

Returns the barycenter of the cell with the given ID.

Note: This method does not perform bounds checking of the given ID!

Implements Utopia::Grid< Space >.

◆ boundary_cells()

template<class Space >

std::set<IndexType> Utopia::HexagonalGrid< Space >::boundary_cells ( std::string select = "all" ) const

inlineoverridevirtual

Retrieve a set of cell indices that are at a specified boundary.

Note: For a periodic space, an empty container is returned; no error or warning is emitted.

Parameters

select Which boundary to return the cell IDs of. If 'all', all boundary cells are returned. Other available values depend on the dimensionality of the grid: 2D: left, right, bottom, top

Implements Utopia::Grid< Space >.

◆ cell_at()

template<class Space >

IndexType Utopia::HexagonalGrid< Space >::cell_at ( const SpaceVec & pos ) const

inlineoverridevirtual

Return the ID of the cell covering the given point in physical space.

Cells are interpreted as covering half-open intervals in space, i.e., including their low-value edges and excluding their high-value edges. The special case of points on high-value edges for non-periodic space behaves such that these points are associated with the cells at the boundary.

For non-periodic space only: The offset geometry of the hexagonal lattice does not permit to cover a rectangular non-periodic space perfectly. At the boundary, a position in uncovered space is mapped to the closest cell. Details: The hexagonal cellular arrangement is covering the periodic equivalent perfectly. In this setup the right-most cell in offset rows is half cut, covering the space at the left boundary. Similarly, the tip of the cells in the upper-most row covers the free space at the lower boundary. In non-periodic space these cells are cut and at the opposite boundary space remains under-represented. Positions in this space are mapped to the closest cell.

Top: pointy tops are cut off
Right: offset row cells are cut in half
Bottom: no cutoff, but unrepresented area the same shape as the top-side cutoff. Points within these triangles are mapped to nearest cell
Left: no cutoff, but unrepresented area the same shape as the right-side cutoff. Points within these half-cells are mapped to the nearest cell.

Note: This function always returns IDs of cells that are inside physical space. For non-periodic space, a check is performed whether the given point is inside the physical space associated with this grid. For periodic space, the given position is mapped back into the physical space.

Implements Utopia::Grid< Space >.

◆ determine_shape()

template<class Space >

MultiIndex Utopia::HexagonalGrid< Space >::determine_shape ( ) const

inlineprivate

Get shape of the hexagonal grid.

Integer rounding takes place here. A physical space of extents of 2.1 length units in each dimension (resp. the shape of the hexagon) and a resolution of two cells per unit length will result in 4 cells in each dimension, each cell's size scaled up slightly and the effective resolution thus slightly smaller than the specified resolution.

Note: In non-periodic space the the number of rows needs to be a pair value in pointy-top orientation.; Note the offset rows are cut and the right end of the domain (if not periodic). Therefore the width of the cells is such, that N * width = Length, that is non-offset rows span the entire width.

◆ effective_resolution()

template<class Space >

SpaceVec Utopia::HexagonalGrid< Space >::effective_resolution ( ) const

inlineoverridevirtual

The effective cell resolution into each physical space dimension.

Implements Utopia::Grid< Space >.

◆ expected_num_neighbors()

template<class Space >

DistType Utopia::HexagonalGrid< Space >::expected_num_neighbors	(	const NBMode &	nb_mode,
		const Config &
	)		const

inlineoverrideprotectedvirtual

Computes the expected number of neighbors for a neighborhood mode.

Implements Utopia::Grid< Space >.

◆ extent_of()

template<class Space >

SpaceVec Utopia::HexagonalGrid< Space >::extent_of ( const IndexType ) const

inlineoverridevirtual

Returns the extent of the cell with the given ID.

The cell's extent corresponds to the tip-to-tip distance of the cell

Note: This method does not perform bounds checking of the given ID!

Implements Utopia::Grid< Space >.

◆ get_nb_func()

template<class Space >

NBFuncID<Base> Utopia::HexagonalGrid< Space >::get_nb_func	(	NBMode	nb_mode,
		const Config &	nb_params
	)

inlineoverrideprotectedvirtual

Retrieve the neighborhood function depending on the mode.

Implements Utopia::Grid< Space >.

◆ get_nb_func_hexagonal()

template<class Space >

NBFuncID<Base> Utopia::HexagonalGrid< Space >::get_nb_func_hexagonal ( const Config & nb_params )

inlineprotected

Returns a standalone hexagonal neighborhood function.

It extracts the distance parameter from the configuration and depending on the distance parameter and the periodicity of the space decides between four different neighborhood calculation functions. The returned callable does rely on the SquareGrid object, but it includes all parameters from the configuration that can be computed once and then captured; this avoids recomputation.

Parameters

nb_params The configuration for the hexagonal neighborhood method. Expected keys: distance (optional, defaults to 1), which refers to the Manhattan distance of included neighbors.

◆ get_nb_param_distance()

template<class Space >

template<bool check_shape = false>

DistType Utopia::HexagonalGrid< Space >::get_nb_param_distance ( const Config & params ) const

inlineprotected

Extract the distance neighborhood parameter from the given config.

Note: This will never return a KeyError; if the key is not given, this method will return 1.

Template Parameters

check_shape Whether to check the shape of the grid is large enough for this distance. For all SquareGrid neighborhoods in periodic space, the grid needs to be at least 2 * distance + 1 cells wide in each dimension.

Parameters

params The neighborhood parameters to extract the distance parameter from.

◆ midx_of()

template<class Space >

MultiIndex Utopia::HexagonalGrid< Space >::midx_of ( const IndexType id ) const

inlineoverridevirtual

Returns the multi-index of the cell with the given ID.

Note: This method does not perform bounds checking of the given ID!

Implements Utopia::Grid< Space >.

◆ num_cells()

template<class Space >

IndexType Utopia::HexagonalGrid< Space >::num_cells ( ) const

inlineoverridevirtual

Number of hexagonal cells required to fill the physical space.

This is calculated simply from the _shape member.

Implements Utopia::Grid< Space >.

◆ shape()

template<class Space >

MultiIndex Utopia::HexagonalGrid< Space >::shape ( ) const

inlineoverridevirtual

Get shape of the hexagonal grid.

Implements Utopia::Grid< Space >.

◆ structure()

template<class Space >

GridStructure Utopia::HexagonalGrid< Space >::structure ( ) const

inlineoverridevirtual

Structure of the grid.

Implements Utopia::Grid< Space >.

◆ vertices_of()

template<class Space >

std::vector<SpaceVec> Utopia::HexagonalGrid< Space >::vertices_of ( const IndexType id ) const

inlineoverridevirtual

Returns the vertices of the cell with the given ID.

The vertices (pointy-topped arrangement) are given in counter-clockwise order, starting with the position of the bottom left-hand vertex (8 o'clock) of the cell.

Note: This method does not perform bounds checking of the given ID!

Implements Utopia::Grid< Space >.

Member Data Documentation

◆ _cell_extent

template<class Space >

const SpaceVec Utopia::HexagonalGrid< Space >::_cell_extent

private

The extent of each cell of this discretization (same for all)

The cell's extent corresponds to the tip-to-tip distance

◆ _nb_hexagonal_nonperiodic

template<class Space >

NBFuncID<Base> Utopia::HexagonalGrid< Space >::_nb_hexagonal_nonperiodic

protected

Initial value:

= 
        [this](const IndexType root_id)
    {
        
        IndexContainer neighbor_ids{};
 
        neighbor_ids.reserve(2 * dim);
 
        add_neighbors_in_<0, false>(root_id, neighbor_ids);
        add_neighbors_in_<1, false>(root_id, neighbor_ids);
        add_neighbors_in_<2, false>(root_id, neighbor_ids);
 
        return neighbor_ids;
    }

The Von-Neumann neighborhood for non-periodic grids.

◆ _nb_hexagonal_periodic

template<class Space >

NBFuncID<Base> Utopia::HexagonalGrid< Space >::_nb_hexagonal_periodic

protected

Initial value:

= 
        [this](const IndexType root_id)
    {
        
        IndexContainer neighbor_ids{};
 
        neighbor_ids.reserve(3 * dim);
 
        add_neighbors_in_<0, true>(root_id, neighbor_ids);
        add_neighbors_in_<1, true>(root_id, neighbor_ids);
        add_neighbors_in_<2, true>(root_id, neighbor_ids);
 
        return neighbor_ids;
    }

The Von-Neumann neighborhood for periodic grids.

◆ _shape

template<class Space >

const MultiIndex Utopia::HexagonalGrid< Space >::_shape

private

The (multi-index) shape of the grid, resulting from resolution.

◆ dim

template<class Space >

constexpr DimType Utopia::HexagonalGrid< Space >::dim = Space::dim

staticconstexpr

The dimensionality of the space to be discretized (for easier access)

The documentation for this class was generated from the following file:

include/utopia/core/grids/hexagonal.hh

Public Types

Public Member Functions

Static Public Attributes

Protected Member Functions

Protected Attributes

Private Member Functions

Private Attributes

Detailed Description

template<class Space> class Utopia::HexagonalGrid< Space >

Member Typedef Documentation

◆ Base

◆ Config

◆ MultiIndex

◆ SpaceVec

Constructor & Destructor Documentation

◆ HexagonalGrid()

Member Function Documentation

◆ add_neighbors_in_()

◆ barycenter_of()

◆ boundary_cells()

◆ cell_at()

◆ determine_shape()

◆ effective_resolution()

◆ expected_num_neighbors()

◆ extent_of()

◆ get_nb_func()

◆ get_nb_func_hexagonal()

◆ get_nb_param_distance()

◆ midx_of()

◆ num_cells()

◆ shape()

◆ structure()

◆ vertices_of()

Member Data Documentation

◆ _cell_extent

◆ _nb_hexagonal_nonperiodic

◆ _nb_hexagonal_periodic

◆ _shape

◆ dim

template<class Space>
class Utopia::HexagonalGrid< Space >