22 #ifndef FIFE_UTIL_QUADTREE_H 23 #define FIFE_UTIL_QUADTREE_H 40 template<
typename DataType,
int32_t MinimumSize = 128>
56 : m_parent(parent),m_x(x),m_y(y),m_size(size),m_data() {
57 m_nodes[0] = m_nodes[1] = m_nodes[2] = m_nodes[3] = 0L;
92 template<
typename Visitor>
94 if( !visitor.visit(
this, d) )
104 int32_t
x()
const {
return m_x; };
108 int32_t
y()
const {
return m_y; };
126 bool contains(int32_t x, int32_t y, int32_t w, int32_t h)
const;
142 int32_t
subnode(int32_t x, int32_t y, int32_t w, int32_t h)
const;
149 template<
typename DataType,
int32_t MinimumSize = 128>
159 QuadTree(int32_t
x = 0, int32_t
y = 0, int32_t starting_size = MinimumSize) {
160 assert(starting_size>1);
161 m_cursor = m_root =
new Node(0L,
x,
y,starting_size);
165 assert( m_root->parent() == 0 );
189 template<
typename Visitor>
191 m_root->apply_visitor(visitor,0);
196 int32_t x = m_root->x();
197 int32_t y = m_root->y();
198 int32_t s = m_root->size();
200 m_cursor = m_root =
new Node(0L,x,y,s);
209 template<
typename DataType,
int32_t MinimumSize>
223 template<
typename DataType,
int32_t MinimumSize>
252 template<
typename DataType,
int32_t MinimumSize>
262 if (
m_size <= MinimumSize) {
291 assert(
"BUG in QuadTree !" == 0);
296 template<
typename DataType,
int32_t MinimumSize>
338 template<
typename DataType,
int32_t MinimumSize>
340 if (
m_size <= MinimumSize)
357 template<
typename DataType,
int32_t MinimumSize>
361 while( m_cursor == 0L ) {
QuadNode * parent()
Return the parent node.
Node * find_container(int32_t x, int32_t y, int32_t w, int32_t h)
Find a container node for a given rectangle.
T h
Height of the rectangle.
DataType & data()
Return a reference to the data of the node.
void splice()
Expand the subnodes - only needed for debugging/profiling worst cases.
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 tak...
QuadTree(int32_t x=0, int32_t y=0, int32_t starting_size=MinimumSize)
Create a new QuadTree.
Node * find_container(const Rect &rect)
Dynamic QuadTree A space partitioning tree automatically expanding to adjust to any object size put i...
int32_t subnode(int32_t x, int32_t y, int32_t w, int32_t h) const
QuadNode * 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 th...
int32_t size() const
Return the size (width and height) of the node.
QuadNode * find_container(const Rect &rect)
QuadNode< DataType, MinimumSize > Node
QuadNode(QuadNode *parent, int32_t x, int32_t y, int32_t size)
Create a new QuadNode.
int32_t y() const
Return the Y position of the node.
QuadNode * find_container(int32_t x, int32_t y, int32_t w, int32_t h)
Find a container node for a given rectangle.
Visitor & apply_visitor(Visitor &visitor)
Apply a visitor recursively to the QuadTree.
T w
Width of the rectangle.
bool contains(int32_t x, int32_t y, int32_t w, int32_t h) const
Check whether a rectangle is contained in the node.
int32_t x() const
Return the X position of the node.