Generic Quadtree Class. More...

#include <decQuadtree.h>

Inheritance diagram for decQuadtree:

Public Types
enum	eQuadrants { eqXnegYneg, eqXnegYpos, eqXposYneg, eqXposYpos, eqNotFound, eqLeftTop = eqXnegYpos, eqRightTop = eqXposYpos, eqLeftBottom = eqXnegYneg, eqRightBottom = eqXposYneg }
	Specified the constants used for the quadrants. More...
Public Member Functions
Constructors and Destructors
	decQuadtree (const decVector2 &center, const decVector2 &halfSize)
	Creates a new generic quadtree object.
virtual	~decQuadtree ()
	Cleans up the generic quadtree object.
Management
decQuadtree *	GetParent () const
	Retrieves the parent of the quadtree or NULL if a root quadtree.
void	SetParent (decQuadtree *parent)
	Sets the parent of the quadtree or NULL if a root quadtree.
const decVector2 &	GetCenter () const
	Retrieves the center of the quadtree.
const decVector2 &	GetHalfSize () const
	Retrieves the half size of the quadtree.
decQuadtree *	GetNodeAt (int quadrant) const
	Retrieves one of the 8 child nodes.
void	SetNodeAt (int quadrant, decQuadtree *quadtree)
	Sets one of the eight child nodes.
decQuadtree *	GetNodeAtBox (const decVector2 &boxCenter, const decVector2 &boxHalfSize)
	Looks for the child node in which the given box lies.
decQuadtree *	GetNodeAtPoint (const decVector2 &point)
	Looks for the child node in which the given point lies.
decQuadtree *	FindNodeAtBox (const decVector2 &boxCenter, const decVector2 &boxHalfSize) const
	Looks for the child node in which the box lies.
int	FindQuadrantAtBox (const decVector2 &boxCenter, const decVector2 &boxHalfSize) const
	Looks for the quadrant in which the element lies.
bool	ContainsBox (const decVector2 &boxCenter, const decVector2 &boxHalfSize) const
	Determines if the box is located completely in this node.
decQuadtree *	FindNodeAtPoint (const decVector2 &point) const
	Looks for the child node in which the point lies.
int	FindQuadrantAtPoint (const decVector2 &point) const
	Looks for the quadrant in which the point lies.
bool	ContainsPoint (const decVector2 &point) const
	Determines if the point is located in this node.
decQuadtree *	SearchTreeForBox (const decVector2 &boxCenter, const decVector2 &boxHalfSize) const
	Searches for the Node containing a given box.
decQuadtree *	SearchTreeForPoint (const decVector2 &point) const
	Searches for the Node where the given point lies in.
void	VisitNodes (decQuadtreeVisitor *visitor)
	Visits all nodes.
void	VisitNodesColliding (decQuadtreeVisitor visitor, decCollisionVolume volume)
	Visits all nodes which collide with the given collision volume.
void	ClearTree (bool clearNodes)
	Clears the quadtree.
virtual decQuadtree *	CreateQuadtree (int quadrant) const =0
	Creates new quadtree for the specified quadrant.
virtual void	ClearNodeContent ()=0
	Clears the content of this node.

Detailed Description

Generic Quadtree Class.

Provides the generic implementation of an quadtree algorithm. For real usage subclass this class and implement the required functions. Every Quadtree object is the root of an quadtree. The top most quadtree object with no parent is the real quadtree root and all children virtual quadtree roots. The subclass overwrites the node creation function to create nodes of its own class. Furthermore the subclass has to implement the management of the node content. This quadtree class only provides the skeleton required for an quadtree algorithm and does not implement any node content logic.

Author:: Plüss Roland

Version:: 1.0

Date:: 2008

Member Enumeration Documentation

enum decQuadtree::eQuadrants

Specified the constants used for the quadrants.

There exists two equal versions suitable for different types of implementations. The first set of quadrant definitions is classified using the axis coordinates. They are also aligned in a way that the definition value represents a bit mask. The first bit is the x axis and the second the y axis. A set bit indicates positive direction and a 0 negative direction. This set is useful for implementations working with bit masks to identify quadrants. The second set of quadrant definitions uses verbal descriptions of the quadrants and is useful for implementations based around the logic location of an quadrant. Both sets include also a definition for a null quadrant. This is used by functions searching for quadrants to indicate that no matching quadrant could be found.

Enumerator:

eqXnegYneg	Node X- Y-, bitwise 00.
eqXnegYpos	Node X- Y+, bitwise 01.
eqXposYneg	Node X+ Y-, bitwise 10.
eqXposYpos	Node X+ Y+, bitwise 11.
eqNotFound	Special constant for searching meaning no match.
eqLeftTop	Node Left-Top.
eqRightTop	Node Right-Top.
eqLeftBottom	Node Left-Bottom.
eqRightBottom	Node Right-Bottom.

Constructor & Destructor Documentation

decQuadtree::decQuadtree	(	const decVector2 &	center,
		const decVector2 &	halfSize
	)

Creates a new generic quadtree object.

virtual decQuadtree::~decQuadtree ( ) [virtual]

Cleans up the generic quadtree object.

Member Function Documentation

virtual void decQuadtree::ClearNodeContent ( ) [pure virtual]

Clears the content of this node.

Implemented in decDefaultQuadtree.

void decQuadtree::ClearTree ( bool clearNodes )

Clears the quadtree.

If clearNodes is set to true all elements are cleared and nodes are reset to NULL. Otherwise only all elements are removed but the nodes stay intact.

bool decQuadtree::ContainsBox	(	const decVector2 &	boxCenter,
		const decVector2 &	boxHalfSize
	)		const

Determines if the box is located completely in this node.

bool decQuadtree::ContainsPoint ( const decVector2 & point ) const

Determines if the point is located in this node.

virtual decQuadtree* decQuadtree::CreateQuadtree ( int quadrant ) const [pure virtual]

Creates new quadtree for the specified quadrant.

Implement this function to create a new quadtree of your own type. Do not set the parent of quadtree. The caller is responsible for this action if applicable.

Implemented in decDefaultQuadtree.

decQuadtree* decQuadtree::FindNodeAtBox	(	const decVector2 &	boxCenter,
		const decVector2 &	boxHalfSize
	)		const

Looks for the child node in which the box lies.

If found the node is returned. If no node could be found NULL or the node does not exist yet NULL is returned.

decQuadtree* decQuadtree::FindNodeAtPoint ( const decVector2 & point ) const

Looks for the child node in which the point lies.

If found the node is returned. If no node could be found NULL or the node does not exist yet NULL is returned.

int decQuadtree::FindQuadrantAtBox	(	const decVector2 &	boxCenter,
		const decVector2 &	boxHalfSize
	)		const

Looks for the quadrant in which the element lies.

Returns eqNotFound if no quadrant fully contains the element.

int decQuadtree::FindQuadrantAtPoint ( const decVector2 & point ) const

Looks for the quadrant in which the point lies.

const decVector2& decQuadtree::GetCenter ( ) const [inline]

Retrieves the center of the quadtree.

const decVector2& decQuadtree::GetHalfSize ( ) const [inline]

Retrieves the half size of the quadtree.

decQuadtree* decQuadtree::GetNodeAt ( int quadrant ) const

Retrieves one of the 8 child nodes.

This is NULL if there exists no such node yet. You can use either an index from 0 to 3 inclusive or use one of the the eQuadrants constants.

decQuadtree* decQuadtree::GetNodeAtBox	(	const decVector2 &	boxCenter,
		const decVector2 &	boxHalfSize
	)

Looks for the child node in which the given box lies.

If the child node does not yet exist it is created. If found the node is returned. If no node could be found NULL is returned.

decQuadtree* decQuadtree::GetNodeAtPoint ( const decVector2 & point )

Looks for the child node in which the given point lies.

If the child node does not yet exist it is created. If found the node is returned. If no node could be found NULL is returned.

decQuadtree* decQuadtree::GetParent ( ) const [inline]

Retrieves the parent of the quadtree or NULL if a root quadtree.

decQuadtree* decQuadtree::SearchTreeForBox	(	const decVector2 &	boxCenter,
		const decVector2 &	boxHalfSize
	)		const

Searches for the Node containing a given box.

decQuadtree* decQuadtree::SearchTreeForPoint ( const decVector2 & point ) const

Searches for the Node where the given point lies in.

void decQuadtree::SetNodeAt	(	int	quadrant,
		decQuadtree *	quadtree
	)

Sets one of the eight child nodes.

You can use either an index from 0 to 3 inclusive or use one of the the eQuadrant constants. Node can be NULL to remove the child node.

void decQuadtree::SetParent ( decQuadtree * parent )

Sets the parent of the quadtree or NULL if a root quadtree.

void decQuadtree::VisitNodes ( decQuadtreeVisitor * visitor )

Visits all nodes.

void decQuadtree::VisitNodesColliding	(	decQuadtreeVisitor *	visitor,
		decCollisionVolume *	volume
	)

Visits all nodes which collide with the given collision volume.

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

decQuadtree.h

decQuadtree Class Reference

Public Types

Public Member Functions

Detailed Description

Member Enumeration Documentation

Constructor & Destructor Documentation

Member Function Documentation