UGDK  0.4.1
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros
intervalkdtree.h
Go to the documentation of this file.
1 #ifndef UGDK_UTIL_INTERVALKDTREE_H_
2 #define UGDK_UTIL_INTERVALKDTREE_H_
3 
4 #include <cassert>
5 #include <cstddef>
6 #include <map>
7 #include <list>
8 #include <vector>
9 #include <climits>
10 #ifdef DEBUG
11 #include <iostream>
12 #endif
13 
14 namespace ugdk {
15 
16 namespace ikdtree {
17 
18 template <int DIMENSIONS>
19 class Box;
20 
21 template <class T, int DIMENSIONS>
22 class Node;
23 
24 template <class T, int DIMENSIONS>
25 class Item;
26 
27 typedef double Coordinate;
28 
29 template <class T, int DIMENSIONS>
30 class IntervalKDTree {
31  public:
32  IntervalKDTree (const Box<DIMENSIONS>& tree_bounding_box,
33  unsigned int max_elements_per_leaf);
34  ~IntervalKDTree ();
35  void Clear ();
36  void Insert (Box<DIMENSIONS> bounding_box, T element);
37  void Remove (T element);
38  void Update (const Box<DIMENSIONS>& new_bounding_box, T element);
39  std::vector<T>* getIntersectingItems (const Box<DIMENSIONS>& boundary) const;
40  unsigned int max_elements_per_leaf ();
41 #ifdef DEBUG
42  unsigned int max_height_;
43  void PrintTree ();
44 #endif
45  private:
46  unsigned int max_elements_per_leaf_;
47  Box<DIMENSIONS> tree_bounding_box_;
48  std::map<T,Item<T, DIMENSIONS>* > container_items_;
49  Node<T, DIMENSIONS> * root_;
50  void UpdateItem (Item<T, DIMENSIONS> * item);
51 };
52 
53 template <int DIMENSIONS>
54 class Box {
55  public:
56  Box (const Coordinate *min_coordinates, const Coordinate *max_coordinates);
57  Box (const Box& box);
58  void setBox (const Box& box);
59  ~Box ();
60  bool IsBelow (int depth, Coordinate boundary) const;
61  bool IsAbove (int depth, Coordinate boundary) const;
62  bool Contains (const Box& box) const;
63  bool Intersects (const Box *box) const;
64  protected:
65  Coordinate min_coordinates_[DIMENSIONS];
66  Coordinate max_coordinates_[DIMENSIONS];
67 };
68 
69 //************* Implementation **************
70 
71 //**** Classes needed for implementation ****
72 
73 template <class T, int DIMENSIONS>
74 class Item : public Box<DIMENSIONS> {
75  public :
76  Item (Box<DIMENSIONS> bounding_box, T element);
77  ~Item ();
78  T element ();
79  void set_container_node (Node<T, DIMENSIONS> *container_node);
80  Node<T, DIMENSIONS> *container_node ();
81 #ifdef DEBUG
82  void Print ();
83 #endif
84  private:
85  typedef Box<DIMENSIONS> super;
86  T element_;
87  Node<T, DIMENSIONS> *container_node_;
88 };
89 
90 template <class T, int DIMENSIONS>
91 class Node : public Box<DIMENSIONS> {
92  public:
93  Node (IntervalKDTree<T, DIMENSIONS> * const tree, Node *parent, int depth,
94  Coordinate *min_coordinates, Coordinate *max_coordinates);
95  Node (IntervalKDTree<T, DIMENSIONS> * const tree, Node *parent, int depth,
96  const Box<DIMENSIONS>& coordinates);
97  ~Node ();
98  void InsertItem (Item<T, DIMENSIONS> *item);
99  void RemoveItem (Item<T, DIMENSIONS> *item);
100  void getIntersectingItems (const Box<DIMENSIONS>& boundary,
101  std::vector<T> *items) const;
102  void Clear ();
103  int depth_;
104  Coordinate division_boundary_;
105  bool has_children_;
106 #ifdef DEBUG
107  void PrintTreeRootedAtThisNode ();
108 #endif
109  private:
110  typedef Box<DIMENSIONS> super;
111  IntervalKDTree<T, DIMENSIONS> *tree_;
112  Node * parent_;
113  Node * low_child_, * high_child_;
114  // TODO: Test if some kind of tree is faster than a list
115  // Maybe an interval tree along one of the other axis (not
116  // on the axis that this node divides)
117  // Maybe even another KD-Interval-Tree. (but taking care to not
118  // have infinite recursive trees)
119  std::list<Item<T, DIMENSIONS> *> items_;
120 
121  void Divide ();
122  void Merge ();
123 };
124 
125 // IntervalKDTree implementation
126 
127 template <class T, int DIMENSIONS>
128 IntervalKDTree<T, DIMENSIONS>::IntervalKDTree (
129  const Box<DIMENSIONS>& tree_bounding_box,
130  unsigned int max_elements_per_leaf) :
131  max_elements_per_leaf_(max_elements_per_leaf),
132  tree_bounding_box_(tree_bounding_box),
133  container_items_() {
134  root_ = new Node<T, DIMENSIONS>(this, NULL, 0, tree_bounding_box);
135 #ifdef DEBUG
136  max_height_ = 0;
137 #endif
138 }
139 
140 template <class T, int DIMENSIONS>
141 IntervalKDTree<T, DIMENSIONS>::~IntervalKDTree () {
142  root_->Clear ();
143  delete root_;
144 }
145 
146 template <class T, int DIMENSIONS>
147 void IntervalKDTree<T, DIMENSIONS>::Clear () {
148  container_items_.clear ();
149  root_->Clear ();
150  delete root_;
151  root_ = new Node<T,DIMENSIONS> (this, NULL, 0, tree_bounding_box_);
152 }
153 
154 template <class T, int DIMENSIONS>
155 void IntervalKDTree<T, DIMENSIONS>::Insert (Box<DIMENSIONS> bounding_box, T element) {
156  // Shouldn't insert an element twice!
157  assert (!container_items_.count (element));
158  Item<T, DIMENSIONS> * item = new Item<T, DIMENSIONS> (bounding_box, element);
159  root_->InsertItem (item);
160  container_items_[element] = item;
161 }
162 
163 template <class T, int DIMENSIONS>
164 void IntervalKDTree<T, DIMENSIONS>::Remove (T element) {
165  assert (container_items_.count (element));
166  if (container_items_.count (element)) {
167  Item<T, DIMENSIONS> *item = container_items_[element];
168  Node<T, DIMENSIONS> *node = item->container_node();
169  node->RemoveItem (item);
170  container_items_.erase (element);
171  delete item;
172  }
173 }
174 
175 template <class T, int DIMENSIONS>
176 void IntervalKDTree<T, DIMENSIONS>::Update (const Box<DIMENSIONS>& new_bounding_box,
177  T element) {
178  // Shouldn't update an unexisting element!
179  assert (container_items_.count(element));
180  Item<T, DIMENSIONS> * item = container_items_[element];
181  item->setBox (new_bounding_box);
182  UpdateItem (item);
183 }
184 
185 template <class T, int DIMENSIONS>
186 void IntervalKDTree<T, DIMENSIONS>::UpdateItem (Item<T, DIMENSIONS> * item) {
187  Node<T, DIMENSIONS> *container_node = item->container_node ();
188 
189  if ((container_node->has_children_ &&
190  (item->IsBelow (container_node->depth_,
191  container_node->division_boundary_)
192  || item->IsAbove (container_node->depth_,
193  container_node->division_boundary_))
194  ) || !container_node->Contains (*item)) {
195  // We need to place it in a different node
196  // Remove and add item
197  container_node->RemoveItem (item);
198  root_->InsertItem (item);
199  }
200 }
201 
202 template <class T, int DIMENSIONS>
203 std::vector<T>* IntervalKDTree<T, DIMENSIONS>::getIntersectingItems (
204  const Box<DIMENSIONS>& boundary) const {
205  std::vector<T>* items = new std::vector<T>;
206  root_->getIntersectingItems (boundary, items);
207  return items;
208 }
209 
210 template <class T, int DIMENSIONS>
211 unsigned int IntervalKDTree<T, DIMENSIONS>::max_elements_per_leaf () {
212  return max_elements_per_leaf_;
213 }
214 
215 #ifdef DEBUG
216 template <class T, int DIMENSIONS>
217 void IntervalKDTree<T, DIMENSIONS>::PrintTree () {
218  root_->PrintTreeRootedAtThisNode ();
219 }
220 #endif
221 
222 // Box implementation
223 
224 template <int DIMENSIONS>
225 Box<DIMENSIONS>::Box (const Coordinate *min_coordinates, const Coordinate *max_coordinates) {
226  if (min_coordinates != NULL && max_coordinates != NULL) {
227  for (int k = 0; k < DIMENSIONS; ++k) {
228  min_coordinates_[k] = min_coordinates[k];
229  max_coordinates_[k] = max_coordinates[k];
230  }
231  }
232 }
233 
234 template <int DIMENSIONS>
235 Box<DIMENSIONS>::Box (const Box& box) {
236  for (int k = 0; k < DIMENSIONS; ++k) {
237  min_coordinates_[k] = box.min_coordinates_[k];
238  max_coordinates_[k] = box.max_coordinates_[k];
239  }
240 }
241 
242 template <int DIMENSIONS>
243 Box<DIMENSIONS>::~Box () {}
244 
245 template <int DIMENSIONS>
246 void Box<DIMENSIONS>::setBox (const Box& box) {
247  for (int k = 0; k < DIMENSIONS; ++k) {
248  min_coordinates_[k] = box.min_coordinates_[k];
249  max_coordinates_[k] = box.max_coordinates_[k];
250  }
251 }
252 
253 template <int DIMENSIONS>
254 bool Box<DIMENSIONS>::IsBelow (int depth, Coordinate boundary) const {
255  return max_coordinates_[depth % DIMENSIONS] <= boundary;
256 }
257 
258 template <int DIMENSIONS>
259 bool Box<DIMENSIONS>::IsAbove (int depth, Coordinate boundary) const {
260  return boundary < min_coordinates_[depth % DIMENSIONS];
261 }
262 
263 template <int DIMENSIONS>
264 bool Box<DIMENSIONS>::Contains (const Box& box) const {
265  for (int k = 0; k < DIMENSIONS; ++k) {
266  // first comparison is a strict inequality
267  // because of the way IsBelow and IsAbove are
268  // defined.
269  if (!( min_coordinates_[k] < box.min_coordinates_[k]
270  && box.max_coordinates_[k] <= max_coordinates_[k]))
271  return false;
272  }
273  return true;
274 }
275 
276 template <int DIMENSIONS>
277 bool Box<DIMENSIONS>::Intersects (const Box *box) const {
278  for (int k = 0; k < DIMENSIONS; ++k) {
279  if (!( min_coordinates_[k] <= box->max_coordinates_[k]
280  && box->min_coordinates_[k] <= max_coordinates_[k]))
281  // found separating axis
282  return false;
283  }
284  return true;
285 }
286 
287 // Item Implementation
288 
289 template <class T, int DIMENSIONS>
290 Item<T, DIMENSIONS>::Item (Box<DIMENSIONS> bounding_box, T element) :
291  super (bounding_box), element_(element) {}
292 
293 template <class T, int DIMENSIONS>
294 Item<T, DIMENSIONS>::~Item () {}
295 
296 template <class T, int DIMENSIONS>
297 Node<T, DIMENSIONS>* Item<T, DIMENSIONS>::container_node () {
298  return container_node_;
299 }
300 
301 template <class T, int DIMENSIONS>
302 void Item<T, DIMENSIONS>::set_container_node (Node<T, DIMENSIONS> *container_node) {
303  container_node_ = container_node;
304 }
305 
306 template <class T, int DIMENSIONS>
307 T Item<T, DIMENSIONS>::element () {
308  return element_;
309 }
310 
311 #ifdef DEBUG
312 template <class T, int DIMENSIONS>
313 void Item<T, DIMENSIONS>::Print () {
314  std::cout << element_;
315 }
316 #endif
317 
318 // Node Implementation
319 
320 template <class T, int DIMENSIONS>
321 Node<T, DIMENSIONS>::Node (IntervalKDTree<T, DIMENSIONS> * const tree,
322  Node *parent, int depth,
323  Coordinate *min_coordinates, Coordinate *max_coordinates) :
324  super (min_coordinates, max_coordinates), depth_(depth), has_children_(false),
325  tree_(tree), parent_(parent), low_child_(NULL), high_child_(NULL) {}
326 
327 template <class T, int DIMENSIONS>
328 Node<T, DIMENSIONS>::Node (IntervalKDTree<T, DIMENSIONS> * const tree,
329  Node *parent, int depth, const Box<DIMENSIONS>& coordinates) :
330  super (coordinates), depth_(depth), has_children_(false),
331  tree_(tree), parent_(parent), low_child_(NULL), high_child_(NULL) {}
332 
333 template <class T, int DIMENSIONS>
334 Node<T, DIMENSIONS>::~Node () {
335  if (low_child_)
336  delete low_child_;
337  if (high_child_)
338  delete high_child_;
339 }
340 
341 template <class T, int DIMENSIONS>
342 void Node<T, DIMENSIONS>::InsertItem (Item<T, DIMENSIONS> *item) {
343 #ifdef DEBUG
344  if (static_cast<unsigned int>(depth_) > tree_->max_height_) {
345  tree_->max_height_ = depth_;
346  }
347 #endif
348  if (has_children_) {
349  if (item->IsBelow (depth_, division_boundary_)) {
350  assert (low_child_);
351  low_child_->InsertItem (item);
352  return;
353  } else if (item->IsAbove (depth_, division_boundary_)) {
354  assert (high_child_);
355  high_child_->InsertItem (item);
356  return;
357  }
358  }
359  items_.push_back (item);
360  item->set_container_node (this);
361  if (!has_children_ && items_.size() > tree_->max_elements_per_leaf()) {
362  Divide ();
363  }
364 }
365 
366 template <class T, int DIMENSIONS>
367 void Node<T, DIMENSIONS>::RemoveItem (Item<T, DIMENSIONS> *item) {
368  items_.remove (item);
369  if (parent_)
370  parent_->Merge ();
371 }
372 
373 template <class T, int DIMENSIONS>
374 void Node<T, DIMENSIONS>::getIntersectingItems (const Box<DIMENSIONS>& boundary,
375  std::vector<T> *intersecting_items) const {
376  for (typename std::list<Item<T, DIMENSIONS> *>::const_iterator it = items_.begin();
377  it != items_.end(); ++it) {
378  if (boundary.Intersects (*it)) {
379  intersecting_items->push_back ((*it)->element ());
380  }
381  }
382  if (has_children_) {
383  if (boundary.IsBelow (depth_, division_boundary_)) {
384  low_child_->getIntersectingItems (boundary, intersecting_items);
385  } else if (boundary.IsAbove (depth_, division_boundary_)) {
386  high_child_->getIntersectingItems (boundary, intersecting_items);
387  } else {
388  low_child_->getIntersectingItems (boundary, intersecting_items);
389  high_child_->getIntersectingItems (boundary, intersecting_items);
390  }
391  }
392 }
393 
394 template <class T, int DIMENSIONS>
395 void Node<T, DIMENSIONS>::Divide () {
396  assert (!has_children_);
397  has_children_ = true;
398 
399  int dimension = depth_ % DIMENSIONS;
400  // TODO: Test other strategies for dividing space
401  division_boundary_ = ( this->min_coordinates_[dimension]
402  + this->max_coordinates_[dimension]) / 2;
403 
404  Coordinate new_min_coordinates[DIMENSIONS],
405  new_max_coordinates[DIMENSIONS];
406  for (int k = 0; k < DIMENSIONS; ++k) {
407  if (k == dimension) {
408  new_min_coordinates[k] = new_max_coordinates[k]
409  = division_boundary_;
410  } else {
411  new_min_coordinates[k] = this->min_coordinates_[k];
412  new_max_coordinates[k] = this->max_coordinates_[k];
413  }
414  }
415  low_child_ = new Node (tree_, this, depth_ + 1,
416  this->min_coordinates_, new_max_coordinates);
417  high_child_ = new Node (tree_, this, depth_ + 1,
418  new_min_coordinates, this->max_coordinates_);
419 
420  std::list<Item<T, DIMENSIONS> *> old_items_list = items_;
421  items_.clear();
422  for (typename std::list<Item<T, DIMENSIONS> *>::iterator it
423  = old_items_list.begin(); it != old_items_list.end(); ++it) {
424  InsertItem (*it);
425  }
426 }
427 
428 template <class T, int DIMENSIONS>
429 void Node<T, DIMENSIONS>::Merge () {
430  assert (has_children_);
431  if ( !low_child_->has_children_
432  && !high_child_->has_children_
433  && (items_.size ()
434  + low_child_->items_.size ()
435  + high_child_->items_.size ()
436  < tree_->max_elements_per_leaf () )) {
437  for (typename std::list<Item<T, DIMENSIONS> *>::iterator it
438  = low_child_->items_.begin(); it != low_child_->items_.end();
439  ++it) {
440  items_.push_back (*it);
441  (*it)->set_container_node (this);
442  }
443  for (typename std::list<Item<T, DIMENSIONS> *>::iterator it
444  = high_child_->items_.begin(); it != high_child_->items_.end();
445  ++it) {
446  items_.push_back (*it);
447  (*it)->set_container_node (this);
448  }
449  delete low_child_;
450  low_child_ = NULL;
451  delete high_child_;
452  high_child_ = NULL;
453  has_children_ = false;
454  if (parent_)
455  parent_->Merge();
456  }
457 }
458 
459 template <class T, int DIMENSIONS>
460 void Node<T, DIMENSIONS>::Clear () {
461  if (has_children_) {
462  low_child_->Clear ();
463  high_child_->Clear ();
464  delete low_child_;
465  low_child_ = NULL;
466  delete high_child_;
467  high_child_ = NULL;
468  }
469  for (typename std::list<Item<T, DIMENSIONS> *>::iterator it
470  = items_.begin(); it != items_.end(); ++it) {
471  delete *it;
472  }
473 }
474 
475 #ifdef DEBUG
476 template <class T, int DIMENSIONS>
477 void Node<T, DIMENSIONS>::PrintTreeRootedAtThisNode () {
478  if (has_children_) {
479  high_child_->PrintTreeRootedAtThisNode ();
480  }
481  for (int i = 0; i < depth_; ++i) {
482  std::cout << "\t";
483  }
484  int i = 0;
485  for (typename std::list<Item<T, DIMENSIONS> *>::iterator it
486  = items_.begin(); it != items_.end(); ++it, ++i) {
487  std::cout << "[" << i << "] = ";
488  (*it)->Print ();
489  std::cout << "; ";
490  }
491  std::cout << std::endl;
492  if (has_children_) {
493  low_child_->PrintTreeRootedAtThisNode ();
494  }
495 }
496 #endif
497 
498 } // namespace ikdtree
499 
500 } // namespace ugdk
501 
502 #endif