#include <quadtree.h>
Public Member Functions | |
QuadNode (QuadNode *parent, int x, int y, int size) | |
QuadNode * | find_container (int x, int y, int w, int h) |
template<typename Visitor > | |
void | apply_visitor (Visitor &visitor, int d=0) |
int | x () const |
int | y () const |
int | size () const |
DataType & | data () |
bool | contains (int x, int y, int w, int h) const |
void | splice () |
Expand the subnodes - only needed for debugging/profiling worst cases. | |
QuadNode * | parent () |
QuadNode * | create_parent (int x, int y, int w, int h) |
QuadTree Node
Definition at line 40 of file quadtree.h.
FIFE::QuadNode< DataType, MinimumSize >::QuadNode | ( | QuadNode< DataType, MinimumSize > * | parent, | |
int | x, | |||
int | y, | |||
int | size | |||
) | [inline] |
Create a new QuadNode
parent | The parent QuadNode this node is contained in or null. | |
x | The X position of this QuadNode. | |
y | The Y position of this QuadNode. | |
size | The width and height of this QuadNode. |
Definition at line 49 of file quadtree.h.
Referenced by FIFE::QuadNode< DataType, MinimumSize >::create_parent().
void FIFE::QuadNode< DataType, MinimumSize >::apply_visitor | ( | Visitor & | visitor, | |
int | 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 87 of file quadtree.h.
Referenced by FIFE::QuadTree< InstanceList, kTreeDepth >::apply_visitor().
bool FIFE::QuadNode< DataType, MinimumSize >::contains | ( | int | x, | |
int | y, | |||
int | w, | |||
int | h | |||
) | const [inline] |
Check whether a rectangle is contained in the node. A rectangle is contained in a node, iff:
That is the top and left borders are inclusive, but the right and bottom borders are exclusive.
Definition at line 210 of file quadtree.h.
Referenced by FIFE::QuadNode< DataType, MinimumSize >::create_parent(), and FIFE::QuadNode< DataType, MinimumSize >::find_container().
QuadNode< DataType, MinimumSize > * FIFE::QuadNode< DataType, MinimumSize >::create_parent | ( | int | x, | |
int | y, | |||
int | w, | |||
int | h | |||
) | [inline] |
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 297 of file quadtree.h.
References FIFE::QuadNode< DataType, MinimumSize >::contains(), and FIFE::QuadNode< DataType, MinimumSize >::QuadNode().
Referenced by FIFE::QuadTree< DataType, MinimumSize >::find_container().
DataType& FIFE::QuadNode< DataType, MinimumSize >::data | ( | ) | [inline] |
Return a reference to the data of the node.
Definition at line 110 of file quadtree.h.
QuadNode< DataType, MinimumSize > * FIFE::QuadNode< DataType, MinimumSize >::find_container | ( | int | x, | |
int | y, | |||
int | w, | |||
int | h | |||
) | [inline] |
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 253 of file quadtree.h.
References FIFE::QuadNode< DataType, MinimumSize >::contains(), and FIFE::QuadNode< DataType, MinimumSize >::find_container().
Referenced by FIFE::QuadTree< DataType, MinimumSize >::find_container(), and FIFE::QuadNode< DataType, MinimumSize >::find_container().
QuadNode* FIFE::QuadNode< DataType, MinimumSize >::parent | ( | ) | [inline] |
Return the parent node
Definition at line 127 of file quadtree.h.
int FIFE::QuadNode< DataType, MinimumSize >::size | ( | void | ) | const [inline] |
Return the size (width and height) of the node.
Definition at line 106 of file quadtree.h.
int FIFE::QuadNode< DataType, MinimumSize >::x | ( | ) | const [inline] |
Return the X position of the node.
Definition at line 98 of file quadtree.h.
int FIFE::QuadNode< DataType, MinimumSize >::y | ( | ) | const [inline] |
Return the Y position of the node.
Definition at line 102 of file quadtree.h.