00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022 #ifndef FIFE_UTIL_QUADTREE_H
00023 #define FIFE_UTIL_QUADTREE_H
00024
00025
00026 #include <cassert>
00027
00028
00029
00030
00031
00032
00033
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
00228
00229
00230
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
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) {
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) {
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) {
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) {
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
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