quadtree.h

00001 /***************************************************************************
00002  *   Copyright (C) 2005-2008 by the FIFE team                              *
00003  *   http://www.fifengine.de                                               *
00004  *   This file is part of FIFE.                                            *
00005  *                                                                         *
00006  *   FIFE is free software; you can redistribute it and/or                 *
00007  *   modify it under the terms of the GNU Lesser General Public            *
00008  *   License as published by the Free Software Foundation; either          *
00009  *   version 2.1 of the License, or (at your option) any later version.    *
00010  *                                                                         *
00011  *   This library is distributed in the hope that it will be useful,       *
00012  *   but WITHOUT ANY WARRANTY; without even the implied warranty of        *
00013  *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU     *
00014  *   Lesser General Public License for more details.                       *
00015  *                                                                         *
00016  *   You should have received a copy of the GNU Lesser General Public      *
00017  *   License along with this library; if not, write to the                 *
00018  *   Free Software Foundation, Inc.,                                       *
00019  *   51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA          *
00020  ***************************************************************************/
00021 
00022 #ifndef FIFE_UTIL_QUADTREE_H
00023 #define FIFE_UTIL_QUADTREE_H
00024 
00025 // Standard C++ library includes
00026 #include <cassert>
00027 
00028 // 3rd party library includes
00029 
00030 // FIFE includes
00031 // These includes are split up in two parts, separated by one empty line
00032 // First block: files included from the FIFE root src directory
00033 // Second block: files included from the same folder
00034 #include "rect.h"
00035 
00036 namespace FIFE {
00037 
00040 template<typename DataType, int MinimumSize = 128>
00041 class QuadNode {
00042     protected:
00043         QuadNode *m_parent;
00044         QuadNode *m_nodes[4];
00045         int m_x,m_y,m_size;
00046         DataType m_data;
00047 
00048     public:
00055         QuadNode(QuadNode* parent, int x, int y, int size) 
00056             : m_parent(parent),m_x(x),m_y(y),m_size(size),m_data() {
00057             m_nodes[0] = m_nodes[1] = m_nodes[2] = m_nodes[3] = 0L;
00058         }
00059 
00060         ~QuadNode() {
00061             delete m_nodes[0];
00062             delete m_nodes[1];
00063             delete m_nodes[2];
00064             delete m_nodes[3];
00065         }
00066 
00078         QuadNode* find_container(int x, int y, int w, int h);
00079         QuadNode* find_container(const Rect& rect) {
00080             return find_container(rect.x,rect.y,rect.w,rect.h);
00081         }
00082 
00092         template<typename Visitor>
00093         void apply_visitor(Visitor& visitor, int d = 0) {
00094             if( !visitor.visit(this, d) )
00095                 return;
00096             if( m_nodes[0] ) m_nodes[0]->apply_visitor(visitor, d + 1);
00097             if( m_nodes[1] ) m_nodes[1]->apply_visitor(visitor, d + 1);
00098             if( m_nodes[2] ) m_nodes[2]->apply_visitor(visitor, d + 1);
00099             if( m_nodes[3] ) m_nodes[3]->apply_visitor(visitor, d + 1);
00100         }
00101 
00104         int x() const { return m_x; };
00105 
00108         int y() const { return m_y; };
00109 
00112         int size() const { return m_size; };
00113 
00116         DataType& data() { return m_data; };
00117         
00126         bool contains(int x, int y, int w, int h) const;
00127 
00129         void splice();
00130 
00133         QuadNode* parent() { return m_parent; };
00134 
00140         QuadNode* create_parent(int x, int y, int w, int h);
00141     protected:
00142         int  subnode(int x, int y, int w, int h) const;
00143 };
00144 
00149 template<typename DataType, int MinimumSize = 128>
00150 class QuadTree {
00151     public:
00152         typedef QuadNode<DataType,MinimumSize> Node;
00153 
00159         QuadTree(int x = 0, int y = 0, int starting_size = MinimumSize) {
00160             assert(starting_size>1);
00161             m_cursor = m_root = new Node(0L,x,y,starting_size);
00162         }
00163 
00164         ~QuadTree() {
00165             assert( m_root->parent() == 0 );
00166             delete m_root;
00167         }
00168 
00182         Node* find_container(int x, int y, int w, int h);
00183         Node* find_container(const Rect& rect) {
00184             return find_container(rect.x,rect.y,rect.w,rect.h);
00185         }
00186 
00189         template<typename Visitor>
00190         Visitor& apply_visitor(Visitor& visitor) {
00191             m_root->apply_visitor(visitor,0);
00192             return visitor;
00193         }
00194 
00195         void clear() {
00196             int x = m_root->x();
00197             int y = m_root->y();
00198             int s = m_root->size();
00199             delete m_root;
00200             m_cursor = m_root = new Node(0L,x,y,s);
00201         }
00202 
00203     protected:
00204         Node *m_root;
00205         Node *m_cursor;
00206 };
00207 
00208 
00209 template<typename DataType, int MinimumSize>
00210 inline
00211 bool QuadNode<DataType,MinimumSize>::contains(int x, int y, int w, int h) const {
00212     if (x < m_x)
00213         return false;
00214     if (y < m_y)
00215         return false;
00216     if (x + w >= m_x + m_size)
00217         return false;
00218     if (y + h >= m_y + m_size)
00219         return false;
00220     return true;
00221 }
00222 
00223 template<typename DataType, int MinimumSize>
00224 inline
00225 int QuadNode<DataType,MinimumSize>::subnode(int x, int y, int w, int h) const {
00226     /*
00227         Very small performance impact - roughly 5% for
00228         the already very fast find_container function.
00229     */
00230     //assert(contains(x,y,w,h));
00231 
00232     if (x >= m_x + m_size/2) {
00233         if (y >= m_y + m_size/2) {
00234             return 3;
00235         }
00236         if (y + h < m_y + m_size/2) {
00237             return 1;
00238         }
00239         return -1;
00240     }
00241     if (x + w < m_x + m_size/2) {
00242         if (y >= m_y + m_size/2) {
00243             return 2;
00244         }
00245         if (y + h < m_y + m_size/2) {
00246             return 0;
00247         }
00248     }
00249     return -1;
00250 }
00251 
00252 template<typename DataType,int MinimumSize>
00253 QuadNode<DataType,MinimumSize>*
00254 QuadNode<DataType,MinimumSize>::find_container(int x, int y, int w, int h) {
00255     if( !contains(x,y,w,h) ) {
00256         if (m_parent) {
00257             return m_parent->find_container(x,y,w,h);
00258         }
00259         return 0L;
00260     }
00261 
00262     if (m_size <= MinimumSize) {
00263         return this;
00264     }
00265 
00266     int r = subnode(x,y,w,h);
00267     switch(r) {
00268     case -1:
00269         return this;
00270     case 0:
00271         if( m_nodes[0] == 0) {
00272             m_nodes[0] = new QuadNode<DataType,MinimumSize>(this,m_x,m_y,m_size/2);
00273         }
00274         return m_nodes[0]->find_container(x,y,w,h);
00275     case 1:
00276         if( m_nodes[1] == 0) {
00277             m_nodes[1] = new QuadNode<DataType,MinimumSize>(this,m_x + m_size/2,m_y,m_size/2);
00278         }
00279         return m_nodes[1]->find_container(x,y,w,h);
00280     case 2:
00281         if( m_nodes[2] == 0) {
00282             m_nodes[2] = new QuadNode<DataType,MinimumSize>(this,m_x,m_y + m_size/2,m_size/2);
00283         }
00284         return m_nodes[2]->find_container(x,y,w,h);
00285     case 3:
00286         if( m_nodes[3] == 0) {
00287             m_nodes[3] = new QuadNode<DataType,MinimumSize>(this,m_x + m_size/2,m_y + m_size/2,m_size/2);
00288         }
00289         return m_nodes[3]->find_container(x,y,w,h);
00290     default:
00291         assert("BUG in QuadTree !" == 0);
00292         return 0L;
00293     }
00294 }
00295 
00296 template<typename DataType,int MinimumSize>
00297 QuadNode<DataType,MinimumSize>* 
00298 QuadNode<DataType,MinimumSize>::create_parent(int x, int y, int w, int h) {
00299     /*
00300         If used only by the tree, these two are superfluous.
00301     */
00302     if( contains(x,y,w,h) )
00303         return this;
00304     if( m_parent )
00305         return m_parent;
00306 
00307     if (x >= m_x) {
00308         if (y >= m_y) { // we are node 0
00309             m_parent = new QuadNode(0L,m_x,m_y,m_size*2);
00310             m_parent->m_nodes[0] = this;
00311             return m_parent;
00312         }
00313         if (y + w < m_y + m_size) { // we are node 2
00314             m_parent = new QuadNode(0L,m_x,m_y - m_size,m_size*2);
00315             m_parent->m_nodes[2] = this;
00316             return m_parent;
00317         }
00318     }
00319     if (x + h < m_x + m_size) {
00320         if (y >= m_y) { // we are node 1
00321             m_parent = new QuadNode(0L,m_x-m_size,m_y,m_size*2);
00322             m_parent->m_nodes[1] = this;
00323             return m_parent;
00324         }
00325         if (y + w < m_y + m_size) { // we are node 3
00326             m_parent = new QuadNode(0L,m_x-m_size,m_y - m_size,m_size*2);
00327             m_parent->m_nodes[3] = this;
00328             return m_parent;
00329         }
00330     }
00331 
00332     // It does not matter....
00333     m_parent = new QuadNode(0L,m_x,m_y,m_size*2);
00334     m_parent->m_nodes[0] = this;
00335     return m_parent;
00336 }
00337 
00338 template<typename DataType,int MinimumSize>
00339 void QuadNode<DataType,MinimumSize>::splice() {
00340     if (m_size <= MinimumSize)
00341         return;
00342 
00343     if( m_nodes[0] == 0) {
00344         m_nodes[0] = new QuadNode<DataType,MinimumSize>(this,m_x,m_y,m_size/2);
00345     }
00346     if( m_nodes[1] == 0) {
00347         m_nodes[1] = new QuadNode<DataType,MinimumSize>(this,m_x + m_size/2,m_y,m_size/2);
00348     }
00349     if( m_nodes[2] == 0) {
00350         m_nodes[2] = new QuadNode<DataType,MinimumSize>(this,m_x,m_y + m_size/2,m_size/2);
00351     }
00352     if( m_nodes[3] == 0) {
00353         m_nodes[3] = new QuadNode<DataType,MinimumSize>(this,m_x + m_size/2,m_y + m_size/2,m_size/2);
00354     }
00355 }
00356 
00357 template<typename DataType,int MinimumSize>
00358 QuadNode<DataType,MinimumSize>*
00359 QuadTree<DataType,MinimumSize>::find_container(int x, int y, int w, int h) {
00360     m_cursor = m_cursor->find_container(x,y,w,h);
00361     while( m_cursor == 0L ) {
00362         m_root = m_root->create_parent(x,y,w,h);
00363         m_cursor = m_root->find_container(x,y,w,h);
00364     }
00365     return m_cursor;
00366 }
00367 
00368 
00369 }
00370 
00371 #endif // QUADTREE_H