22 #ifndef FIFE_UTIL_QUADTREE_H
23 #define FIFE_UTIL_QUADTREE_H
40 template<
typename DataType,
int32_t MinimumSize = 128>
45 int32_t m_x,m_y,m_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;
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; };
112 int32_t
size()
const {
return m_size; };
116 DataType&
data() {
return m_data; };
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);
161 m_cursor = m_root =
new Node(0L,x,y,starting_size);
165 assert( m_root->
parent() == 0 );
189 template<
typename Visitor>
196 int32_t x = m_root->
x();
197 int32_t y = m_root->
y();
198 int32_t s = m_root->
size();
200 m_cursor = m_root =
new Node(0L,x,y,s);
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>
253 QuadNode<DataType,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 ) {
Node * find_container(int32_t x, int32_t y, int32_t w, int32_t h)
void splice()
Expand the subnodes - only needed for debugging/profiling worst cases.
void apply_visitor(Visitor &visitor, int32_t d=0)
QuadTree(int32_t x=0, int32_t y=0, int32_t starting_size=MinimumSize)
bool contains(int32_t x, int32_t y, int32_t w, int32_t h) const
QuadNode * create_parent(int32_t x, int32_t y, int32_t w, int32_t h)
QuadNode(QuadNode *parent, int32_t x, int32_t y, int32_t size)
QuadNode * find_container(int32_t x, int32_t y, int32_t w, int32_t h)
Visitor & apply_visitor(Visitor &visitor)
credit to phoku for his NodeDisplay example which the visitor code is adapted from ( he coded the qua...