gsKdNode< d, Z > Struct Template Reference

Detailed Description

template<short_t d, class Z = index_t>
struct gismo::gsKdNode< d, Z >

Struct representing a kd-tree node.

The nodes are of two types:

• Split nodes
• Leaf nodes

Template parameters

Parameters

d	is the dimension
Z	is the box-coordinate index type

Collaboration diagram for gsKdNode< d, Z >:

Public Member Functions
gsKdNode *	adaptiveAlignedSplit (kdBox const &insBox, int index_level)
gsKdNode *	adaptiveSplit (kdBox const &insBox)
void	anyMidSplit (int index_level)
	gsKdNode ()
	Constructor (empty node)
	gsKdNode (point const &upp)
	Constructor (root node)
	gsKdNode (point const &low, point const &upp)
	Constructor (root node)
	gsKdNode (kdBox const &bb)
	Constructor (leaf node)
	gsKdNode (const gsKdNode &o, gsKdNode *parentNode=NULL)
void	merge ()
	Merges terminal node (i.e., two children are joined)
void	nextMidSplit ()
	Splits the node in the middle (ie. two children are added)
void	split ()
	Splits the node (i.e., two children are added)
void	split (int splitAxis, Z splitPos)
	Splits the node (i.e., two children are added)
	~gsKdNode ()
	Recursively deletes the whole subtree under this node.

Public Attributes
int	axis
kdBox *	box
gsKdNode *	left
	Pointer to the left child of this split node (if it is one)
int	level
gsKdNode *	parent
	Pointer to the parent node.
Z	pos
	Split coordinate (meaningfull only for split nodes)
gsKdNode *	right
	Pointer to the right child of this split node (if it is one)

Constructor & Destructor Documentation

gsKdNode ( const gsKdNode< d, Z > &  o, gsKdNode< d, Z > *  parentNode = NULL  )

inline

Recursively copies the whole subtree under o, and sets it's parent to parentNode

Member Function Documentation

gsKdNode* adaptiveAlignedSplit ( kdBox const &  insBox, int  index_level  )

inline

Splits the node adaptively (i.e., two children are added) according to insBox. If non-degenerate split is impossible, then this is a no-op. Splitting is done on a coordinate of the current level (aligned) returns the child that intersects insBox or NULL (if no split)

gsKdNode* adaptiveSplit ( kdBox const &  insBox )

inline

Splits the node adaptively (i.e., two children are added) according to insBox. If non-degenerate split is impossible, then this is a no-op

void anyMidSplit ( int  index_level )

inline

Splits the node in the middle (ie. two children are added) If non-degenerate split is impossible, then this is a no-op

Member Data Documentation

int axis

axis in which the children of this node split the domain special value -1 denotes a leaf node

kdBox* box

The box held in this leaf node (if leaf) box->first is the lower left corner of the box box->second is the upper right corner of the box

int level

level in which the box in the node is completely contained special value -1 denotes unknown level (in case of a split node)