22 #ifndef FIFE_UTIL_QUADTREE_H
23 #define FIFE_UTIL_QUADTREE_H
40 template<
typename DataType,
int32_t MinimumSize = 128>
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);
189 template<
typename Visitor>
209 template<
typename DataType,
int32_t MinimumSize>
216 if (x + w >= m_x + m_size)
218 if (y + h >= m_y + m_size)
223 template<
typename DataType,
int32_t MinimumSize>
232 if (x >= m_x + m_size/2) {
233 if (y >= m_y + m_size/2) {
236 if (y + h < m_y + m_size/2) {
241 if (x + w < m_x + m_size/2) {
242 if (y >= m_y + m_size/2) {
245 if (y + h < m_y + m_size/2) {
252 template<
typename DataType,
int32_t MinimumSize>
255 if( !contains(x,y,w,h) ) {
262 if (m_size <= MinimumSize) {
266 int32_t r = subnode(x,y,w,h);
271 if( m_nodes[0] == 0) {
276 if( m_nodes[1] == 0) {
281 if( m_nodes[2] == 0) {
286 if( m_nodes[3] == 0) {
291 assert(
"BUG in QuadTree !" == 0);
296 template<
typename DataType,
int32_t MinimumSize>
302 if( contains(x,y,w,h) )
309 m_parent =
new QuadNode(0L,m_x,m_y,m_size*2);
310 m_parent->m_nodes[0] =
this;
313 if (y + w < m_y + m_size) {
314 m_parent =
new QuadNode(0L,m_x,m_y - m_size,m_size*2);
315 m_parent->m_nodes[2] =
this;
319 if (x + h < m_x + m_size) {
321 m_parent =
new QuadNode(0L,m_x-m_size,m_y,m_size*2);
322 m_parent->m_nodes[1] =
this;
325 if (y + w < m_y + m_size) {
326 m_parent =
new QuadNode(0L,m_x-m_size,m_y - m_size,m_size*2);
327 m_parent->m_nodes[3] =
this;
333 m_parent =
new QuadNode(0L,m_x,m_y,m_size*2);
334 m_parent->m_nodes[0] =
this;
338 template<
typename DataType,
int32_t MinimumSize>
340 if (m_size <= MinimumSize)
343 if( m_nodes[0] == 0) {
346 if( m_nodes[1] == 0) {
349 if( m_nodes[2] == 0) {
352 if( m_nodes[3] == 0) {
357 template<
typename DataType,
int32_t MinimumSize>
361 while( m_cursor == 0L ) {
int32_t subnode(int32_t x, int32_t y, int32_t w, int32_t h) const
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.
bool contains(int32_t x, int32_t y, int32_t w, int32_t h) const
Check whether a rectangle is contained in the node.
Node * find_container(const Rect &rect)
Dynamic QuadTree A space partitioning tree automatically expanding to adjust to any object size put i...
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...
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.
int32_t size() const
Return the size (width and height) 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.
int32_t x() const
Return the X position of the node.
T w
Width of the rectangle.