#include <TreeNode.hpp>

Inheritance diagram for TreeNode:

[legend]

Public Types
enum	Wall { BACK , FRONT , LEFT , RIGHT , BOTTOM , TOP }

Public Member Functions
	TreeNode (const Box &extent)

	TreeNode (TreeNode *parent, int id, const Box &extent)

virtual	~TreeNode ()

void	addNeighbor (Wall wall, TreeNode *node)

virtual void	addNeighbors ()=0

virtual TreeNode *	child (Vec r)=0

const vector< TreeNode * > &	children () const

virtual void	createChildren (int id)=0

void	deleteNeighbor (Wall wall, TreeNode *node)

int	id () const

bool	isChildless () const

TreeNode *	leafChild (Vec r)

int	level () const

const TreeNode *	neighbor (Wall wall, Vec r) const

const vector< TreeNode * > &	neighbors (Wall wall) const

TreeNode *	parent ()

void	sortNeighbors ()

void	subdivide (vector< TreeNode * > &nodev)

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

Static Public Member Functions
static void	makeNeighbors (Wall wall1, TreeNode node1, TreeNode node2)

Protected Member Functions
void	addChild (TreeNode *child)

TreeNode *	childAt (int l)

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 Attributes
vector< TreeNode * >	_children

int	_id

int	_level

std::array< vector< TreeNode * >, 6 >	_neighbors

TreeNode *	_parent

Detailed Description

TreeNode is an abstract class that represents nodes in a TreeSpatialGrid. It holds a node identifier, the spatial extent of the node (a cuboid lined up with the coordinate axes), and links to the parent, children and neighbors of the node.

Member Enumeration Documentation

◆ Wall

enum TreeNode::Wall

This enum contains a constant for each of the six walls in a node. The x-coordinate increases from BACK to FRONT, the y-coordinate increases from LEFT to RIGHT, and the z-coordinate increases from BOTTOM to TOP.

Constructor & Destructor Documentation

◆ TreeNode() [1/2]

TreeNode::TreeNode	(	TreeNode *	parent,
		int	id,
		const Box &	extent
	)

This constructor creates a new tree node with the specified parent node, identifier, and spatial extent. The constructor sets the level of the new node to be one higher than the level of the parent. If the pointer to the parent is null, the level of the new node is zero.

◆ TreeNode() [2/2]

TreeNode::TreeNode ( const Box & extent )

This constructor creates a new root node with the specified spatial extent. The constructor sets both the node identifier and the level of the new root node to zero.

◆ ~TreeNode()

virtual TreeNode::~TreeNode ( )

virtual

Trivial virtual destructor.

Member Function Documentation

◆ addChild()

void TreeNode::addChild ( TreeNode * child )

protected

This function adds the specified child to the end of the child list.

◆ addNeighbor()

void TreeNode::addNeighbor	(	Wall	wall,
		TreeNode *	node
	)

This function adds a node to the list of neighbors corresponding to a given wall.

◆ addNeighbors()

virtual void TreeNode::addNeighbors ( )

pure virtual

This function adds the relevant neighbors to a node with children (the function does nothing if the node doesn't have any children). It considers internal neighbors among the children as well as the neighbors of the parent node (i.e. this node). These external neighbors are distributed among the children depending on the geometry; note that a particular external neighbor may be neighbor to multiple children.

Implemented in BinTreeNode, and OctTreeNode.

◆ child()

virtual TreeNode * TreeNode::child ( Vec r )

pure virtual

This function returns a pointer to the node's child that contains the specified point, assuming that the point is inside the node. Invoking this function on a childless node results in undefined behavior.

Implemented in BinTreeNode, and OctTreeNode.

◆ childAt()

TreeNode * TreeNode::childAt ( int l )

protected

This function returns a pointer to the node's child with index $l$ . The appropriate range for the index depends on the subclass (e.g. 0-1 for binary tree, 0-7 for octtree). Invoking this function on a childless node of with a child index out of the appropriate range results in undefined behavior.

◆ children()

const vector< TreeNode * > & TreeNode::children ( ) const

This function returns a list of pointers to the node's children. The list is either empty or of the size appropriate for the subclass (e.g. 2 for binary tree, 8 for octtree).

◆ createChildren()

virtual void TreeNode::createChildren ( int id )

pure virtual

This function creates new nodes partitioning the node, and adds these new nodes as its own child nodes. Subdivision happens according to a fixed scheme determined by each subclass. The children are assigned consecutive integer identifiers, starting with the identifier specified as an argument to this function. A node does NOT take ownership of its children, so the caller is responsible for deleting the child nodes when they are no longer needed. Invoking this function on a node that already has children results in undefined behavior.

Implemented in BinTreeNode, and OctTreeNode.

◆ deleteNeighbor()

void TreeNode::deleteNeighbor	(	Wall	wall,
		TreeNode *	node
	)

This function deletes a node from the list of neighbors corresponding to a given wall.

◆ id()

int TreeNode::id ( ) const

This function returns the ID number of the node.

◆ isChildless()

bool TreeNode::isChildless ( ) const

This function returns true if the node has no children, or false if it has children.

◆ leafChild()

TreeNode * TreeNode::leafChild ( Vec r )

This function returns a pointer to the deepest node in the descendent hierarchy of this node that contains the specified position, or the null pointer if the position is outside the node. It uses the child(r) function resursively to locate the appropriate node.

◆ level()

int TreeNode::level ( ) const

This function returns the level of the node.

◆ makeNeighbors()

static void TreeNode::makeNeighbors	(	Wall	wall1,
		TreeNode *	node1,
		TreeNode *	node2
	)

static

This static function makes the two specified nodes neighbors by adding node2 as a neighbor to node1 at wall1, and adding node1 as a neighbor to node2 at the complementing wall (back/front, left/right, bottom/top).

◆ neighbor()

const TreeNode * TreeNode::neighbor	(	Wall	wall,
		Vec	r
	)		const

This function returns a pointer to the node just beyond a given wall that contains the specified position, or null if such a node can't be found by searching the neighbors of that wall. The function expects that the neighbors of the node have been added.

◆ neighbors()

const vector< TreeNode * > & TreeNode::neighbors ( Wall wall ) const

This function returns a list of pointers to the node's neighbors at the given wall. The list may be empty, for example because neighbors are still being added.

◆ parent()

TreeNode * TreeNode::parent ( )

This function returns a pointer to the parent of the node.

◆ sortNeighbors()

void TreeNode::sortNeighbors ( )

This function sorts the neighbor lists for each wall of this node so that neighbors with a larger overlap area are listed first. The function should be called only after neighbors have been added for all nodes in the tree.

◆ subdivide()

void TreeNode::subdivide ( vector< TreeNode * > & nodev )

This function subdivides the node by creating the appropriate number of child subnodes (through the createChildren() function) and appending pointers to these children to the specified node list. The node identifiers of the child nodes are set so that the node identifier matches the index of the node in the node list. Finally, the neighbor lists are updated (through the addNeighbors() function).

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

TreeNode.hpp

Public Types

Public Member Functions

Static Public Member Functions

Protected Member Functions

Private Attributes

Detailed Description

Member Enumeration Documentation

◆ Wall

Constructor & Destructor Documentation

◆ TreeNode() [1/2]

◆ TreeNode() [2/2]

◆ ~TreeNode()

Member Function Documentation

◆ addChild()

◆ addNeighbor()

◆ addNeighbors()

◆ child()

◆ childAt()

◆ children()

◆ createChildren()

◆ deleteNeighbor()

◆ id()

◆ isChildless()

◆ leafChild()

◆ level()

◆ makeNeighbors()

◆ neighbor()

◆ neighbors()

◆ parent()

◆ sortNeighbors()

◆ subdivide()