gf::SpaceTree Class Reference

Binary space random partionning tree. More...

#include <gf/SpaceTree.h>

Public Types
using	Callback = std::function< bool(const SpaceTree &)>
	A callback function for traversing the tree. More...

Public Member Functions
	SpaceTree (const RectI &area)
	Constructor. More...
const RectI &	getArea () const
	Get the area of the node. More...
int	getLevel () const
	Get the level of the node in the tree. More...
void	removeChildren ()
	Remove the children of the node. More...
bool	splitOnce (Random &random, Vector2i minSize, float maxRatio=1.5f)
	Split the node once. More...
void	splitRecursive (Random &random, int levelMax, Vector2i minSize, Vector2i maxSize, float maxRatio=1.5f)
	Split a node recursively. More...
bool	isLeaf () const
	Check if a node is a leaf. More...
const SpaceTree *	getLeftChild () const
	Get the left child. More...
SpaceTree *	getLeftChild ()
	Get the left child. More...
const SpaceTree *	getRightChild () const
	Get the right child. More...
SpaceTree *	getRightChild ()
	Get the right child. More...
const SpaceTree *	getFather () const
	Get the father of the node. More...
SpaceTree *	getFather ()
	Get the father of the node. More...
bool	contains (Vector2i position) const
	Check if the area of the node contains a position. More...
const SpaceTree *	find (Vector2i position) const
	Find the deepest node containing a position. More...
bool	traversePreOrder (Callback callback) const
	Traverse the nodes in pre-order. More...
bool	traverseInOrder (Callback callback) const
	Traverse the nodes in in-order. More...
bool	traversePostOrder (Callback callback) const
	Traverse the nodes in post-order. More...
bool	traverseLevelOrder (Callback callback) const
	Traverse the nodes in level-order. More...
bool	traverseInvertedLevelOrder (Callback callback) const
	Traverse the nodes in inverted level-order. More...

Detailed Description

Binary space random partionning tree.

This class implements a random binary space partitioning tree. More precisely, this class is a node in the tree.

Member Typedef Documentation

Callback

using gf::SpaceTree::Callback = std::function<bool(const SpaceTree&)>

A callback function for traversing the tree.

The function returns a boolean indicating if the traversal can continue.

Constructor & Destructor Documentation

SpaceTree()

gf::SpaceTree::SpaceTree

(

const RectI &

area

)

Constructor.

Parameters

area	The area to split for this node

Member Function Documentation

contains()

bool gf::SpaceTree::contains

(

Vector2i

position

)

const

Check if the area of the node contains a position.

Parameters

position

The position to check

find()

const SpaceTree* gf::SpaceTree::find

(

Vector2i

position

)

const

Find the deepest node containing a position.

Parameters

position

The position to find

Returns

A node or nullptr if the position is outside the tree

getArea()

const RectI& gf::SpaceTree::getArea ( ) const

inline

Get the area of the node.

Returns

The area of the node

getFather() [1/2]

const SpaceTree* gf::SpaceTree::getFather ( ) const

inline

Get the father of the node.

The root of the tree has no father.

Returns

The father of the node

getFather() [2/2]

SpaceTree* gf::SpaceTree::getFather ( )

inline

Get the father of the node.

The root of the tree has no father.

Returns

The father of the node

getLeftChild() [1/2]

const SpaceTree* gf::SpaceTree::getLeftChild ( ) const

inline

Get the left child.

Returns

The left child if it exists or nullptr

getLeftChild() [2/2]

SpaceTree* gf::SpaceTree::getLeftChild ( )

inline

Get the left child.

Returns

The left child if it exists or nullptr

getLevel()

int gf::SpaceTree::getLevel ( ) const

inline

Get the level of the node in the tree.

The root of the tree is at level 0, its children at level 1, etc.

Returns

The level of the node

getRightChild() [1/2]

const SpaceTree* gf::SpaceTree::getRightChild ( ) const

inline

Get the right child.

Returns

The right child if it exists or nullptr

getRightChild() [2/2]

SpaceTree* gf::SpaceTree::getRightChild ( )

inline

Get the right child.

Returns

The right child if it exists or nullptr

isLeaf()

bool gf::SpaceTree::isLeaf ( ) const

inline

Check if a node is a leaf.

A leaf has no children.

Returns

True if the node is a leaf

removeChildren()

void gf::SpaceTree::removeChildren

(

)

Remove the children of the node.

splitOnce()

bool gf::SpaceTree::splitOnce	(	Random &	random,
		Vector2i	minSize,
		float	maxRatio = 1.5f
	)

Split the node once.

This function may create two children if the conditions are met.

Parameters

random	A random generator
minSize	The minimum size under which a node cannot be split
maxRatio	The maximum ratio between the width and height

Returns

True if the node has actually been split

splitRecursive()

void gf::SpaceTree::splitRecursive	(	Random &	random,
		int	levelMax,
		Vector2i	minSize,
		Vector2i	maxSize,
		float	maxRatio = 1.5f
	)

Split a node recursively.

Parameters

random	A random generator
levelMax	The maximum level of a node
minSize	The minimum size under which a node cannot be split
maxSize	The maximum size over which a node must be split
maxRatio	The maximum ratio between the width and height

traverseInOrder()

bool gf::SpaceTree::traverseInOrder

(

Callback

callback

)

const

Traverse the nodes in in-order.

Parameters

callback

A function to call on each node

See also

Tree traversal - Wikipedia

traverseInvertedLevelOrder()

bool gf::SpaceTree::traverseInvertedLevelOrder

(

Callback

callback

)

const

Traverse the nodes in inverted level-order.

Parameters

callback

A function to call on each node

See also

Tree traversal - Wikipedia

traverseLevelOrder()

bool gf::SpaceTree::traverseLevelOrder

(

Callback

callback

)

const

Traverse the nodes in level-order.

Level-order is also known as breadth first search

Parameters

callback

A function to call on each node

See also

Tree traversal - Wikipedia

traversePostOrder()

bool gf::SpaceTree::traversePostOrder

(

Callback

callback

)

const

Traverse the nodes in post-order.

Parameters

callback

A function to call on each node

See also

Tree traversal - Wikipedia

traversePreOrder()

bool gf::SpaceTree::traversePreOrder

(

Callback

callback

)

const

Traverse the nodes in pre-order.

Parameters

callback

A function to call on each node

See also

Tree traversal - Wikipedia