FIFE
2008.0
|
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