TreeSpatialGrid Class Reference

#include <TreeSpatialGrid.hpp>

Inheritance diagram for TreeSpatialGrid:

Public Member Functions
	~TreeSpatialGrid ()
int	cellIndex (Position bfr) const override
Position	centralPositionInCell (int m) const override
std::unique_ptr< PathSegmentGenerator >	createPathSegmentGenerator () const override
double	diagonal (int m) const override
int	numCells () const override
Position	randomPositionInCell (int m) const override
double	volume (int m) const override
void	writeTopology (TextOutFile *outfile) const
Public Member Functions inherited from BoxSpatialGrid
Box	boundingBox () const override
int	dimension () const override
double	maxX () const
double	maxY () const
double	maxZ () const
double	minX () const
double	minY () const
double	minZ () const
Public Member Functions inherited from SpatialGrid
virtual Box	boundingBox () const =0
virtual int	cellIndex (Position bfr) const =0
virtual Position	centralPositionInCell (int m) const =0
virtual std::unique_ptr< PathSegmentGenerator >	createPathSegmentGenerator () const =0
virtual double	diagonal (int m) const =0
virtual int	dimension () const =0
virtual int	numCells () const =0
virtual Position	randomPositionInCell (int m) const =0
virtual double	volume (int m) const =0
virtual void	writeGridPlotFiles (const SimulationItem *probe) const
Public Member Functions inherited from SimulationItem
template<class T >
T *	find (bool setup=true) const
template<class T >
T *	interface (int levels=-999999, bool setup=true) const
virtual string	itemName () const
void	setup ()
string	typeAndName () const
Public Member Functions inherited from Item
	Item (const Item &)=delete
virtual	~Item ()
void	addChild (Item *child)
const vector< Item * > &	children () const
virtual void	clearItemListProperty (const PropertyDef *property)
void	destroyChild (Item *child)
virtual bool	getBoolProperty (const PropertyDef *property) const
virtual vector< double >	getDoubleListProperty (const PropertyDef *property) const
virtual double	getDoubleProperty (const PropertyDef *property) const
virtual string	getEnumProperty (const PropertyDef *property) const
virtual int	getIntProperty (const PropertyDef *property) const
virtual vector< Item * >	getItemListProperty (const PropertyDef *property) const
virtual Item *	getItemProperty (const PropertyDef *property) const
virtual string	getStringProperty (const PropertyDef *property) const
int	getUtilityProperty (string name) const
virtual void	insertIntoItemListProperty (const PropertyDef *property, int index, Item *item)
Item &	operator= (const Item &)=delete
Item *	parent () const
virtual void	removeFromItemListProperty (const PropertyDef *property, int index)
virtual void	setBoolProperty (const PropertyDef *property, bool value)
virtual void	setDoubleListProperty (const PropertyDef *property, vector< double > value)
virtual void	setDoubleProperty (const PropertyDef *property, double value)
virtual void	setEnumProperty (const PropertyDef *property, string value)
virtual void	setIntProperty (const PropertyDef *property, int value)
virtual void	setItemProperty (const PropertyDef *property, Item *item)
virtual void	setStringProperty (const PropertyDef *property, string value)
void	setUtilityProperty (string name, int value)
virtual string	type () const
Public Member Functions inherited from Box
	Box ()
	Box (double xmin, double ymin, double zmin, double xmax, double ymax, double zmax)
	Box (Vec rmin, Vec rmax)
void	cellIndices (int &i, int &j, int &k, Vec r, int nx, int ny, int nz) const
Vec	center () const
bool	contains (const Box &box) const
bool	contains (double x, double y, double z) const
bool	contains (Vec r) const
double	diagonal () const
void	extend (const Box &box)
const Box &	extent () const
void	extent (double &xmin, double &ymin, double &zmin, double &xmax, double &ymax, double &zmax) const
Vec	fracPos (double xfrac, double yfrac, double zfrac) const
Vec	fracPos (int xd, int yd, int zd, int xn, int yn, int zn) const
bool	intersects (const Box &box) const
bool	intersects (Vec r, const Vec k, double &smin, double &smax) const
bool	intersects (Vec rc, double r) const
Vec	rmax () const
Vec	rmin () const
double	volume () const
Vec	widths () const
double	xmax () const
double	xmin () const
double	xwidth () const
double	ymax () const
double	ymin () const
double	ywidth () const
double	zmax () const
double	zmin () const
double	zwidth () const

Protected Member Functions
	TreeSpatialGrid ()
virtual vector< TreeNode * >	constructTree ()=0
void	setupSelfAfter () override
void	write_xy (SpatialGridPlotFile *outfile) const override
void	write_xyz (SpatialGridPlotFile *outfile) const override
void	write_xz (SpatialGridPlotFile *outfile) const override
void	write_yz (SpatialGridPlotFile *outfile) const override
Protected Member Functions inherited from BoxSpatialGrid
	BoxSpatialGrid ()
void	setupSelfBefore () override
Protected Member Functions inherited from SpatialGrid
	SpatialGrid ()
Random *	random () const
void	setupSelfBefore () override
virtual void	write_xy (SpatialGridPlotFile *outfile) const
virtual void	write_xyz (SpatialGridPlotFile *outfile) const
virtual void	write_xz (SpatialGridPlotFile *outfile) const
virtual void	write_yz (SpatialGridPlotFile *outfile) const
Protected Member Functions inherited from SimulationItem
	SimulationItem ()
virtual bool	offersInterface (const std::type_info &interfaceTypeInfo) const
virtual void	setupSelfAfter ()
virtual void	setupSelfBefore ()
Protected Member Functions inherited from Item
	Item ()
Protected Member Functions inherited from Box
void	setExtent (const Box &extent)
void	setExtent (double xmin, double ymin, double zmin, double xmax, double ymax, double zmax)

Private Types
using	BaseType = BoxSpatialGrid
using	ItemType = TreeSpatialGrid

Private Member Functions
int	cellIndexForNode (const TreeNode *node) const
TreeNode *	nodeForCellIndex (int m) const
TreeNode *	root () const

Private Attributes
vector< int >	_cellindexv
double	_eps
vector< int >	_idv
vector< TreeNode * >	_nodev

Friends
class	ItemRegistry
class	MySegmentGenerator

Detailed Description

TreeSpatialGrid is an abstract subclass of the BoxSpatialGrid class, and represents three-dimensional spatial grids with cuboidal cells organized in a hierarchical tree. The tree's root node encloses the complete spatial domain, and nodes on subsequent levels recursively divide space into ever finer nodes. The depth of the tree can vary from place to place. The leaf nodes (those that are not further subdivided) are the actual spatial cells.

The actual tree construction, including the choice of node type (a subclass of TreeNode) is delegated to each concrete subclass. This base class implements all other aspects required for using the grid, such as calculating paths traversing the grid. Depending on the type of TreeNode, the tree can become an octtree (8 children per node) or a binary tree (2 children per node). Other node types could be implemented, as long as they are cuboids lined up with the coordinate axes.

Constructor & Destructor Documentation

TreeSpatialGrid()

TreeSpatialGrid::TreeSpatialGrid ( )

inlineprotected

Default constructor for abstract Item subclass TreeSpatialGrid : "a hierarchical tree spatial grid" .

~TreeSpatialGrid()

TreeSpatialGrid::~TreeSpatialGrid

(

)

The destructor deletes all tree nodes created during setup.

Member Function Documentation

cellIndex()

int TreeSpatialGrid::cellIndex ( Position  bfr ) const

overridevirtual

This function returns the index of the cell that contains the position $\mathbf{r}$. For a tree grid, the search algorithm starts at the root node and selects the child node that contains the position. This procedure is repeated until the node is childless, i.e. until it is a leaf node that corresponds to an actual spatial cell.

Implements SpatialGrid.

cellIndexForNode()

int TreeSpatialGrid::cellIndexForNode ( const TreeNode *  node ) const

private

This function returns the cell index $m$ of a node in the tree. It just obtains the node ID from the node and determines the corresponding cell index from the precalculated cell index vector.

centralPositionInCell()

Position TreeSpatialGrid::centralPositionInCell ( int  m ) const

overridevirtual

This function returns the central location of the cell with index $m$. For a tree grid, it determines the node ID corresponding to the cell index $m$, and then calculates the central position in that node through

$$\begin{array}{rl}x& =x_{\text{min}}+\frac{1}{2}\mathrm{\Delta }x\\ y& =y_{\text{min}}+\frac{1}{2}\mathrm{\Delta }y\\ z& =z_{\text{min}}+\frac{1}{2}\mathrm{\Delta }z\end{array}$$

Implements SpatialGrid.

constructTree()

virtual vector< TreeNode * > TreeSpatialGrid::constructTree ( )

protectedpure virtual

This function must be implemented in a subclass. It constructs the hierarchical tree and all (interconnected) nodes forming the tree. All nodes are instances of the same TreeNode subclass, selected by this function. The function returns a list of pointers to all created nodes (leaf and nonleaf). Ownership of the nodes resides in this returned list (not in the node hierarchy itself) and is thus handed to the caller.

Each (leaf and nonleaf) node is given an identifier (ID) corresponding to its index in the list. The first node in the list is the root node of tree, i.e. the node encompasssing the complete spatial domain. Thus, by definition, the root node has an ID of zero.

This function also causes the nodes to construct neighbor lists, interconnecting the nodes according to their spatial relationship. The neighbor lists are sorted so that the neighbors with the largest overlapping border area are listed first, increasing (on average) the probability of locating the correct neighbor early in the list.

Implemented in FileTreeSpatialGrid, and PolicyTreeSpatialGrid.

createPathSegmentGenerator()

std::unique_ptr< PathSegmentGenerator > TreeSpatialGrid::createPathSegmentGenerator ( ) const

overridevirtual

This function creates and hands over ownership of a path segment generator (an instance of a PathSegmentGenerator subclass) appropriate for a tree grid, implemented as a private PathSegmentGenerator subclass. The algorithm used to construct the path is described below.

The function uses a rather straighforward algorithm. It determines the cell that contains the starting position, and calculates the first wall of the cell that will be crossed. The pathlength $\mathrm{\Delta }s$ is determined and the current position is moved to a new position along this path, a tiny fraction further than $\mathrm{\Delta }s$,

$$\begin{array}{rl}{x}_{\text{new}}& =x_{\text{current}}+(\mathrm{\Delta }s+ϵ)k_x\\ y_{\text{new}}& =y_{\text{current}}+(\mathrm{\Delta }s+ϵ)k_y\\ z_{\text{new}}& =z_{\text{current}}+(\mathrm{\Delta }s+ϵ)k_z\end{array}$$

where

$$ϵ={10}^{-12}\sqrt{x_{\text{max}}^2+y_{\text{max}}^2+z_{\text{max}}^2}$$

By adding this small extra bit, we ensure that the new position is now within the next cell, and we can repeat this exercise. This loop is terminated when the next position is outside the grid.

To determine the cell index of the "next cell" in this algorithm, the function uses the neighbor lists constructed for each tree node during setup.

Implements SpatialGrid.

diagonal()

double TreeSpatialGrid::diagonal ( int  m ) const

overridevirtual

This function returns the actuale diagonal of the cell with index $m$. For a tree grid, it determines the node ID corresponding to the cell index $m$, and then simply calculates the diagonal of the corresponding cuboidal node using $d=\sqrt{(\mathrm{\Delta }x{)}^2+(\mathrm{\Delta }y{)}^2+(\mathrm{\Delta }z{)}^2}$.

Implements SpatialGrid.

nodeForCellIndex()

TreeNode * TreeSpatialGrid::nodeForCellIndex ( int  m ) const

private

This function returns a pointer to the node corresponding to cell index $m$. It just reads the node ID of the $m$'th leaf cell from the precalculated ID vector and returns the corresponding pointer of the tree vector.

numCells()

int TreeSpatialGrid::numCells ( ) const

overridevirtual

This function returns the number of cells in the grid.

Implements SpatialGrid.

randomPositionInCell()

Position TreeSpatialGrid::randomPositionInCell ( int  m ) const

overridevirtual

This function returns a random location from the cell with index $m$. For a tree grid, it determines the node ID corresponding to the cell index $m$, and then calculates a random position in that cell through

$$\begin{array}{rl}x& =x_{\text{min}}+{\mathcal{X}}_1\mathrm{\Delta }x\\ y& =y_{\text{min}}+{\mathcal{X}}_2\mathrm{\Delta }y\\ z& =z_{\text{min}}+{\mathcal{X}}_3\mathrm{\Delta }z\end{array}$$

with ${\mathcal{X}}_1$, ${\mathcal{X}}_2$ and ${\mathcal{X}}_3$ three uniform deviates.

Implements SpatialGrid.

root()

TreeNode * TreeSpatialGrid::root ( ) const

private

This function returns a pointer to the root node of the tree.

setupSelfAfter()

void TreeSpatialGrid::setupSelfAfter ( )

overrideprotectedvirtual

This function invokes the constructTree() function, to be implemented by a subclass, causing the tree to be constructed. The subclass returns a list of all created nodes back to the base class, and gives each node an identifier (ID) corresponding to its index in this list. Ownership of the nodes resides in the list passed back to the base class (not in the subclass, and not in the node hierarchy itself).

After the subclass passes back the tree nodes, this function creates an extra vector that contains the node IDs of all leaf nodes, i.e. all nodes corresponding to the actual spatial cells. Conversely, the function also creates a vector with the cell indices of all the nodes, i.e. the rank $m$ of the node in the ID vector if the node is a leaf, and the number -1 if the node is not a leaf (and hence not a spatial cell). Finally, the function logs some details on the number of cells in the tree.

Reimplemented from SimulationItem.

volume()

double TreeSpatialGrid::volume ( int  m ) const

overridevirtual

This function returns the volume of the cell with index $m$. For a tree grid, it determines the node ID corresponding to the cell index $m$, and then simply calculates the volume of the corresponding cuboidal node using $V=\mathrm{\Delta }x\mathrm{\Delta }y\mathrm{\Delta }z$.

Implements SpatialGrid.

write_xy()

void TreeSpatialGrid::write_xy ( SpatialGridPlotFile *  outfile ) const

overrideprotectedvirtual

This function writes the intersection of the grid with the xy plane to the specified SpatialGridPlotFile object.

Reimplemented from SpatialGrid.

write_xyz()

void TreeSpatialGrid::write_xyz ( SpatialGridPlotFile *  outfile ) const

overrideprotectedvirtual

This function writes 3D information for the cells up to a certain level in the grid structure to the specified SpatialGridPlotFile object. The output is limited to some predefined number of cells to keep the line density in the output plot within reason.

Reimplemented from SpatialGrid.

write_xz()

void TreeSpatialGrid::write_xz ( SpatialGridPlotFile *  outfile ) const

overrideprotectedvirtual

This function writes the intersection of the grid with the xz plane to the specified SpatialGridPlotFile object.

Reimplemented from SpatialGrid.

write_yz()

void TreeSpatialGrid::write_yz ( SpatialGridPlotFile *  outfile ) const

overrideprotectedvirtual

This function writes the intersection of the grid with the yz plane to the specified SpatialGridPlotFile object.

Reimplemented from SpatialGrid.

writeTopology()

void TreeSpatialGrid::writeTopology

(

TextOutFile *

outfile

)

const

This function writes the topology of the tree to the specified text file in a simple, proprietary format. After a brief descriptive header, it writes lines that each contain just a single integer number. The first line specifies the number of children for each nonleaf node (2 for a binary tree, 8 for an octtree, or 0 if the root node has not been subdivided). The second line contains 1 if the root node is subdivided, or 0 if not. The following lines similarly contain 1 or 0 indicating subdivision for any children of the preceding node, recursively, in a depth-first traversal of the tree.

---

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

• TreeSpatialGrid.hpp