FIFE  6e1afdbeda11afe9ac53e6023a4be96ef88f1dc6
FIFE::QuadNode< DataType, MinimumSize > Class Template Reference

QuadTree Node. More...

#include <quadtree.h>

+ Collaboration diagram for FIFE::QuadNode< DataType, MinimumSize >:

Public Member Functions

 QuadNode (QuadNode *parent, int32_t x, int32_t y, int32_t size)
 Create a new QuadNode. More...
 
 ~QuadNode ()
 
QuadNodefind_container (int32_t x, int32_t y, int32_t w, int32_t h)
 Find a container node for a given rectangle. More...
 
QuadNodefind_container (const Rect &rect)
 
template<typename Visitor >
void apply_visitor (Visitor &visitor, int32_t d=0)
 Apply a visitor recursively to the QuadTree A visitor is an object which has a visit method which takes as parameters a pointer to a QuadNode and an integer. More...
 
int32_t x () const
 Return the X position of the node. More...
 
int32_t y () const
 Return the Y position of the node. More...
 
int32_t size () const
 Return the size (width and height) of the node. More...
 
DataType & data ()
 Return a reference to the data of the node. More...
 
bool contains (int32_t x, int32_t y, int32_t w, int32_t h) const
 Check whether a rectangle is contained in the node. More...
 
void splice ()
 Expand the subnodes - only needed for debugging/profiling worst cases. More...
 
QuadNodeparent ()
 Return the parent node. More...
 
QuadNodecreate_parent (int32_t x, int32_t y, int32_t w, int32_t h)
 Create a new parent node for a rectangle This will create a new parent node end expand the tree so that the given rectangle will eventually be contained after enough calls of this function. More...
 

Protected Member Functions

int32_t subnode (int32_t x, int32_t y, int32_t w, int32_t h) const
 

Protected Attributes

QuadNodem_parent
 
QuadNodem_nodes [4]
 
int32_t m_x
 
int32_t m_y
 
int32_t m_size
 
DataType m_data
 

Detailed Description

template<typename DataType, int32_t MinimumSize = 128>
class FIFE::QuadNode< DataType, MinimumSize >

QuadTree Node.

Definition at line 41 of file quadtree.h.

Constructor & Destructor Documentation

template<typename DataType, int32_t MinimumSize = 128>
FIFE::QuadNode< DataType, MinimumSize >::QuadNode ( QuadNode< DataType, MinimumSize > *  parent,
int32_t  x,
int32_t  y,
int32_t  size 
)
inline

Create a new QuadNode.

Parameters
parentThe parent QuadNode this node is contained in or null.
xThe X position of this QuadNode.
yThe Y position of this QuadNode.
sizeThe width and height of this QuadNode.

Definition at line 55 of file quadtree.h.

Referenced by FIFE::QuadNode< DataType, MinimumSize >::create_parent().

+ Here is the caller graph for this function:

template<typename DataType, int32_t MinimumSize = 128>
FIFE::QuadNode< DataType, MinimumSize >::~QuadNode ( )
inline

Member Function Documentation

template<typename DataType, int32_t MinimumSize = 128>
template<typename Visitor >
void FIFE::QuadNode< DataType, MinimumSize >::apply_visitor ( Visitor &  visitor,
int32_t  d = 0 
)
inline

Apply a visitor recursively to the QuadTree A visitor is an object which has a visit method which takes as parameters a pointer to a QuadNode and an integer.

The integer is the depth of the given node. If the method returns true it is applied recursivly to all existing subnodes with a depth increased by one. The application happens in Z order (top left, top right, bottom left and finally bottom right).

Definition at line 93 of file quadtree.h.

References FIFE::QuadNode< DataType, MinimumSize >::apply_visitor().

Referenced by FIFE::QuadNode< DataType, MinimumSize >::apply_visitor(), and FIFE::LayerCache::collect().

+ Here is the caller graph for this function:

template<typename DataType , int32_t MinimumSize>
bool FIFE::QuadNode< DataType, MinimumSize >::contains ( int32_t  x,
int32_t  y,
int32_t  w,
int32_t  h 
) const
inline

Check whether a rectangle is contained in the node.

A rectangle is contained in a node, iff:

x >= x() and x + w < x() + size() and y >= y() and y + h < y() + size()

That is the top and left borders are inclusive, but the right and bottom borders are exclusive.

Definition at line 211 of file quadtree.h.

References FIFE::QuadNode< DataType, MinimumSize >::m_size, FIFE::QuadNode< DataType, MinimumSize >::m_x, and FIFE::QuadNode< DataType, MinimumSize >::m_y.

Referenced by FIFE::QuadNode< DataType, MinimumSize >::create_parent(), FIFE::QuadNode< DataType, MinimumSize >::data(), and FIFE::QuadNode< DataType, MinimumSize >::find_container().

+ Here is the caller graph for this function:

template<typename DataType , int32_t MinimumSize>
QuadNode< DataType, MinimumSize > * FIFE::QuadNode< DataType, MinimumSize >::create_parent ( int32_t  x,
int32_t  y,
int32_t  w,
int32_t  h 
)

Create a new parent node for a rectangle This will create a new parent node end expand the tree so that the given rectangle will eventually be contained after enough calls of this function.

Definition at line 298 of file quadtree.h.

References FIFE::QuadNode< DataType, MinimumSize >::contains(), FIFE::QuadNode< DataType, MinimumSize >::m_nodes, FIFE::QuadNode< DataType, MinimumSize >::m_parent, FIFE::QuadNode< DataType, MinimumSize >::m_size, FIFE::QuadNode< DataType, MinimumSize >::m_x, FIFE::QuadNode< DataType, MinimumSize >::m_y, and FIFE::QuadNode< DataType, MinimumSize >::QuadNode().

Referenced by FIFE::QuadTree< DataType, MinimumSize >::find_container(), and FIFE::QuadNode< DataType, MinimumSize >::parent().

+ Here is the caller graph for this function:

template<typename DataType, int32_t MinimumSize = 128>
DataType& FIFE::QuadNode< DataType, MinimumSize >::data ( )
inline
template<typename DataType , int32_t MinimumSize>
QuadNode< DataType, MinimumSize > * FIFE::QuadNode< DataType, MinimumSize >::find_container ( int32_t  x,
int32_t  y,
int32_t  w,
int32_t  h 
)

Find a container node for a given rectangle.

This guarantees to return a Node with the following properties: 1.) The node contains the rectangle (as defined by the contains function). 2.) All subnodes can not contain the rectangle or it has the MinimumSize. 3.) In case these properties can only be fulfilled by extending the tree upwards, that is by creating a new root node - this function will return null.

This function will extend the tree automatically so that this guarantee can be fulfilled.

Definition at line 254 of file quadtree.h.

References FIFE::QuadNode< DataType, MinimumSize >::contains(), FIFE::QuadNode< DataType, MinimumSize >::find_container(), FIFE::QuadNode< DataType, MinimumSize >::m_nodes, FIFE::QuadNode< DataType, MinimumSize >::m_parent, FIFE::QuadNode< DataType, MinimumSize >::m_size, FIFE::QuadNode< DataType, MinimumSize >::m_x, FIFE::QuadNode< DataType, MinimumSize >::m_y, and FIFE::QuadNode< DataType, MinimumSize >::subnode().

Referenced by FIFE::LayerCache::collect(), FIFE::QuadNode< DataType, MinimumSize >::find_container(), FIFE::QuadTree< DataType, MinimumSize >::find_container(), FIFE::QuadTree< InstanceList, MIN_TREE_SIZE >::find_container(), FIFE::LayerCache::updatePosition(), FIFE::QuadNode< DataType, MinimumSize >::~QuadNode(), and FIFE::QuadTree< InstanceList, MIN_TREE_SIZE >::~QuadTree().

+ Here is the caller graph for this function:

template<typename DataType, int32_t MinimumSize = 128>
QuadNode* FIFE::QuadNode< DataType, MinimumSize >::find_container ( const Rect rect)
inline
template<typename DataType, int32_t MinimumSize = 128>
QuadNode* FIFE::QuadNode< DataType, MinimumSize >::parent ( )
inline

Return the parent node.

Definition at line 133 of file quadtree.h.

References FIFE::QuadNode< DataType, MinimumSize >::create_parent(), FIFE::QuadNode< DataType, MinimumSize >::m_parent, and FIFE::QuadNode< DataType, MinimumSize >::subnode().

Referenced by FIFE::LayerCache::collect().

+ Here is the caller graph for this function:

template<typename DataType, int32_t MinimumSize = 128>
int32_t FIFE::QuadNode< DataType, MinimumSize >::size ( void  ) const
inline

Return the size (width and height) of the node.

Definition at line 112 of file quadtree.h.

References FIFE::QuadNode< DataType, MinimumSize >::m_size.

Referenced by FIFE::RenderVisitor::visit(), and FIFE::CacheTreeCollector::visit().

+ Here is the caller graph for this function:

template<typename DataType , int32_t MinimumSize>
void FIFE::QuadNode< DataType, MinimumSize >::splice ( )

Expand the subnodes - only needed for debugging/profiling worst cases.

Definition at line 339 of file quadtree.h.

References FIFE::QuadNode< DataType, MinimumSize >::m_nodes, FIFE::QuadNode< DataType, MinimumSize >::m_size, FIFE::QuadNode< DataType, MinimumSize >::m_x, and FIFE::QuadNode< DataType, MinimumSize >::m_y.

Referenced by FIFE::QuadNode< DataType, MinimumSize >::data().

+ Here is the caller graph for this function:

template<typename DataType , int32_t MinimumSize>
int32_t FIFE::QuadNode< DataType, MinimumSize >::subnode ( int32_t  x,
int32_t  y,
int32_t  w,
int32_t  h 
) const
inlineprotected
template<typename DataType, int32_t MinimumSize = 128>
int32_t FIFE::QuadNode< DataType, MinimumSize >::x ( ) const
inline
template<typename DataType, int32_t MinimumSize = 128>
int32_t FIFE::QuadNode< DataType, MinimumSize >::y ( ) const
inline

Member Data Documentation

template<typename DataType, int32_t MinimumSize = 128>
DataType FIFE::QuadNode< DataType, MinimumSize >::m_data
protected

Definition at line 46 of file quadtree.h.

Referenced by FIFE::QuadNode< DataType, MinimumSize >::data().

template<typename DataType, int32_t MinimumSize = 128>
QuadNode* FIFE::QuadNode< DataType, MinimumSize >::m_nodes[4]
protected
template<typename DataType, int32_t MinimumSize = 128>
QuadNode* FIFE::QuadNode< DataType, MinimumSize >::m_parent
protected

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