FIFE  be64c707dea6b3250bd4355bf5c825d25920087d
quadtree.h
Go to the documentation of this file.
1 /***************************************************************************
2  * Copyright (C) 2005-2019 by the FIFE team *
3  * http://www.fifengine.net *
4  * This file is part of FIFE. *
5  * *
6  * FIFE is free software; you can redistribute it and/or *
7  * modify it under the terms of the GNU Lesser General Public *
8  * License as published by the Free Software Foundation; either *
9  * version 2.1 of the License, or (at your option) any later version. *
10  * *
11  * This library is distributed in the hope that it will be useful, *
12  * but WITHOUT ANY WARRANTY; without even the implied warranty of *
13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU *
14  * Lesser General Public License for more details. *
15  * *
16  * You should have received a copy of the GNU Lesser General Public *
17  * License along with this library; if not, write to the *
18  * Free Software Foundation, Inc., *
19  * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA *
20  ***************************************************************************/
21 
22 #ifndef FIFE_UTIL_QUADTREE_H
23 #define FIFE_UTIL_QUADTREE_H
24 
25 // Standard C++ library includes
26 #include <cassert>
27 
28 // 3rd party library includes
29 
30 // FIFE includes
31 // These includes are split up in two parts, separated by one empty line
32 // First block: files included from the FIFE root src directory
33 // Second block: files included from the same folder
34 #include "rect.h"
35 
36 namespace FIFE {
37 
40 template<typename DataType, int32_t MinimumSize = 128>
41 class QuadNode {
42  protected:
45  int32_t m_x,m_y,m_size;
46  DataType m_data;
47 
48  public:
55  QuadNode(QuadNode* parent, int32_t x, int32_t y, int32_t size)
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;
58  }
59 
61  delete m_nodes[0];
62  delete m_nodes[1];
63  delete m_nodes[2];
64  delete m_nodes[3];
65  }
66 
78  QuadNode* find_container(int32_t x, int32_t y, int32_t w, int32_t h);
79  QuadNode* find_container(const Rect& rect) {
80  return find_container(rect.x,rect.y,rect.w,rect.h);
81  }
82 
92  template<typename Visitor>
93  void apply_visitor(Visitor& visitor, int32_t d = 0) {
94  if( !visitor.visit(this, d) )
95  return;
96  if( m_nodes[0] ) m_nodes[0]->apply_visitor(visitor, d + 1);
97  if( m_nodes[1] ) m_nodes[1]->apply_visitor(visitor, d + 1);
98  if( m_nodes[2] ) m_nodes[2]->apply_visitor(visitor, d + 1);
99  if( m_nodes[3] ) m_nodes[3]->apply_visitor(visitor, d + 1);
100  }
101 
104  int32_t x() const { return m_x; };
105 
108  int32_t y() const { return m_y; };
109 
112  int32_t size() const { return m_size; };
113 
116  DataType& data() { return m_data; };
117 
126  bool contains(int32_t x, int32_t y, int32_t w, int32_t h) const;
127 
129  void splice();
130 
133  QuadNode* parent() { return m_parent; };
134 
140  QuadNode* create_parent(int32_t x, int32_t y, int32_t w, int32_t h);
141  protected:
142  int32_t subnode(int32_t x, int32_t y, int32_t w, int32_t h) const;
143 };
144 
149 template<typename DataType, int32_t MinimumSize = 128>
150 class QuadTree {
151  public:
153 
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);
162  }
163 
165  assert( m_root->parent() == 0 );
166  delete m_root;
167  }
168 
182  Node* find_container(int32_t x, int32_t y, int32_t w, int32_t h);
183  Node* find_container(const Rect& rect) {
184  return find_container(rect.x,rect.y,rect.w,rect.h);
185  }
186 
189  template<typename Visitor>
190  Visitor& apply_visitor(Visitor& visitor) {
191  m_root->apply_visitor(visitor,0);
192  return visitor;
193  }
194 
195  void clear() {
196  int32_t x = m_root->x();
197  int32_t y = m_root->y();
198  int32_t s = m_root->size();
199  delete m_root;
200  m_cursor = m_root = new Node(0L,x,y,s);
201  }
202 
203  protected:
204  Node *m_root;
205  Node *m_cursor;
206 };
207 
208 
209 template<typename DataType, int32_t MinimumSize>
210 inline
211 bool QuadNode<DataType,MinimumSize>::contains(int32_t x, int32_t y, int32_t w, int32_t h) const {
212  if (x < m_x)
213  return false;
214  if (y < m_y)
215  return false;
216  if (x + w >= m_x + m_size)
217  return false;
218  if (y + h >= m_y + m_size)
219  return false;
220  return true;
221 }
222 
223 template<typename DataType, int32_t MinimumSize>
224 inline
225 int32_t QuadNode<DataType,MinimumSize>::subnode(int32_t x, int32_t y, int32_t w, int32_t h) const {
226  /*
227  Very small performance impact - roughly 5% for
228  the already very fast find_container function.
229  */
230  //assert(contains(x,y,w,h));
231 
232  if (x >= m_x + m_size/2) {
233  if (y >= m_y + m_size/2) {
234  return 3;
235  }
236  if (y + h < m_y + m_size/2) {
237  return 1;
238  }
239  return -1;
240  }
241  if (x + w < m_x + m_size/2) {
242  if (y >= m_y + m_size/2) {
243  return 2;
244  }
245  if (y + h < m_y + m_size/2) {
246  return 0;
247  }
248  }
249  return -1;
250 }
251 
252 template<typename DataType,int32_t MinimumSize>
254 QuadNode<DataType,MinimumSize>::find_container(int32_t x, int32_t y, int32_t w, int32_t h) {
255  if( !contains(x,y,w,h) ) {
256  if (m_parent) {
257  return m_parent->find_container(x,y,w,h);
258  }
259  return 0L;
260  }
261 
262  if (m_size <= MinimumSize) {
263  return this;
264  }
265 
266  int32_t r = subnode(x,y,w,h);
267  switch(r) {
268  case -1:
269  return this;
270  case 0:
271  if( m_nodes[0] == 0) {
273  }
274  return m_nodes[0]->find_container(x,y,w,h);
275  case 1:
276  if( m_nodes[1] == 0) {
278  }
279  return m_nodes[1]->find_container(x,y,w,h);
280  case 2:
281  if( m_nodes[2] == 0) {
283  }
284  return m_nodes[2]->find_container(x,y,w,h);
285  case 3:
286  if( m_nodes[3] == 0) {
288  }
289  return m_nodes[3]->find_container(x,y,w,h);
290  default:
291  assert("BUG in QuadTree !" == 0);
292  return 0L;
293  }
294 }
295 
296 template<typename DataType,int32_t MinimumSize>
298 QuadNode<DataType,MinimumSize>::create_parent(int32_t x, int32_t y, int32_t w, int32_t h) {
299  /*
300  If used only by the tree, these two are superfluous.
301  */
302  if( contains(x,y,w,h) )
303  return this;
304  if( m_parent )
305  return m_parent;
306 
307  if (x >= m_x) {
308  if (y >= m_y) { // we are node 0
309  m_parent = new QuadNode(0L,m_x,m_y,m_size*2);
310  m_parent->m_nodes[0] = this;
311  return m_parent;
312  }
313  if (y + w < m_y + m_size) { // we are node 2
314  m_parent = new QuadNode(0L,m_x,m_y - m_size,m_size*2);
315  m_parent->m_nodes[2] = this;
316  return m_parent;
317  }
318  }
319  if (x + h < m_x + m_size) {
320  if (y >= m_y) { // we are node 1
321  m_parent = new QuadNode(0L,m_x-m_size,m_y,m_size*2);
322  m_parent->m_nodes[1] = this;
323  return m_parent;
324  }
325  if (y + w < m_y + m_size) { // we are node 3
326  m_parent = new QuadNode(0L,m_x-m_size,m_y - m_size,m_size*2);
327  m_parent->m_nodes[3] = this;
328  return m_parent;
329  }
330  }
331 
332  // It does not matter....
333  m_parent = new QuadNode(0L,m_x,m_y,m_size*2);
334  m_parent->m_nodes[0] = this;
335  return m_parent;
336 }
337 
338 template<typename DataType,int32_t MinimumSize>
340  if (m_size <= MinimumSize)
341  return;
342 
343  if( m_nodes[0] == 0) {
345  }
346  if( m_nodes[1] == 0) {
348  }
349  if( m_nodes[2] == 0) {
351  }
352  if( m_nodes[3] == 0) {
354  }
355 }
356 
357 template<typename DataType,int32_t MinimumSize>
359 QuadTree<DataType,MinimumSize>::find_container(int32_t x, int32_t y, int32_t w, int32_t h) {
360  m_cursor = m_cursor->find_container(x,y,w,h);
361  while( m_cursor == 0L ) {
362  m_root = m_root->create_parent(x,y,w,h);
363  m_cursor = m_root->find_container(x,y,w,h);
364  }
365  return m_cursor;
366 }
367 
368 
369 }
370 
371 #endif // QUADTREE_H
DataType m_data
Definition: quadtree.h:46
int32_t m_y
Definition: quadtree.h:45
QuadNode * parent()
Return the parent node.
Definition: quadtree.h:133
Node * find_container(int32_t x, int32_t y, int32_t w, int32_t h)
Find a container node for a given rectangle.
Definition: quadtree.h:359
T h
Height of the rectangle.
Definition: rect.h:93
T x
The X Coordinate.
Definition: rect.h:84
Node * m_cursor
Definition: quadtree.h:205
DataType & data()
Return a reference to the data of the node.
Definition: quadtree.h:116
void splice()
Expand the subnodes - only needed for debugging/profiling worst cases.
Definition: quadtree.h:339
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...
Definition: quadtree.h:93
QuadTree(int32_t x=0, int32_t y=0, int32_t starting_size=MinimumSize)
Create a new QuadTree.
Definition: quadtree.h:159
Node * find_container(const Rect &rect)
Definition: quadtree.h:183
Dynamic QuadTree A space partitioning tree automatically expanding to adjust to any object size put i...
Definition: quadtree.h:150
void clear()
Definition: quadtree.h:195
int32_t subnode(int32_t x, int32_t y, int32_t w, int32_t h) const
Definition: quadtree.h:225
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...
Definition: quadtree.h:298
int32_t size() const
Return the size (width and height) of the node.
Definition: quadtree.h:112
QuadNode * m_nodes[4]
Definition: quadtree.h:44
QuadNode * find_container(const Rect &rect)
Definition: quadtree.h:79
QuadNode< DataType, MinimumSize > Node
Definition: quadtree.h:152
T y
The Y Coordinate.
Definition: rect.h:87
QuadNode(QuadNode *parent, int32_t x, int32_t y, int32_t size)
Create a new QuadNode.
Definition: quadtree.h:55
int32_t m_size
Definition: quadtree.h:45
QuadTree Node.
Definition: quadtree.h:41
Node * m_root
Definition: quadtree.h:204
QuadNode * m_parent
Definition: quadtree.h:43
int32_t y() const
Return the Y position of the node.
Definition: quadtree.h:108
QuadNode * find_container(int32_t x, int32_t y, int32_t w, int32_t h)
Find a container node for a given rectangle.
Definition: quadtree.h:254
Visitor & apply_visitor(Visitor &visitor)
Apply a visitor recursively to the QuadTree.
Definition: quadtree.h:190
T w
Width of the rectangle.
Definition: rect.h:90
bool contains(int32_t x, int32_t y, int32_t w, int32_t h) const
Check whether a rectangle is contained in the node.
Definition: quadtree.h:211
int32_t x() const
Return the X position of the node.
Definition: quadtree.h:104
int32_t m_x
Definition: quadtree.h:45