degate  0.1.2
Public Member Functions | Private Member Functions | Private Attributes | Static Private Attributes | Friends
degate::QuadTree< T > Class Template Reference

Quad tree to store objects and to accesss them with a two dimensional access path. More...

#include <QuadTree.h>

Inheritance diagram for degate::QuadTree< T >:
Inheritance graph
[legend]

List of all members.

Public Member Functions

const std::string get_name () const
 QuadTree (BoundingBox const &box, int max_entries=50)
 Create a new quadtree.
 ~QuadTree ()
 Destruct a quadtree.
void get_all_elements (std::vector< T > &vec) const
bool is_leave () const
 Check if the quadtree or a quadtree node is a leaf node.
ret_t insert (T object)
 Insert an object into the quadtree.
ret_t remove (T object)
 Remove an object from the quadtree.
void notify_shape_change (T object)
 Notify that the bounding box of an object changed.
unsigned int total_size () const
 Get the number of objects that are stored in a quadtree node and in all child nodes.
unsigned int depth () const
 Get the number of layers, that quadtree has.
bool is_empty () const
unsigned int get_width () const
 Get the dimension of the quadtree.
unsigned int get_height () const
 Get the dimension of the quadtree.
region_iterator< T > region_iter_begin (int min_x, int max_x, int min_y, int max_y)
 Get an interator to iterate over quadtree nodes down to the leafes.
region_iterator< T > region_iter_begin (BoundingBox const &bbox)
 Get a region iterator to iterate over quatree objects.
region_iterator< T > region_iter_begin ()
 Get a region iterator to iterate over the complete quatree.
region_iterator< T > region_iter_end ()
 Get an end marker for the region iteration.
BoundingBox const & get_bounding_box () const
 Get the bounding box for a quad tree layer.
void print (std::ostream &os=std::cout, int tabs=0, bool recursive=false)
 Print the quadtree.

Private Member Functions

 QuadTree (BoundingBox const &box, QuadTree *parent, std::string node_name, int max_entries=50)
QuadTree< T > * traverse_downto_bounding_box (BoundingBox const &box)
ret_t split ()
ret_t reinsert_objects ()
bool is_splitable () const

Private Attributes

unsigned int max_entries
BoundingBox box
std::vector< QuadTree< T > > subtree_nodes
std::list< T > children
QuadTreeparent
std::string node_name

Static Private Attributes

static const int NW = 0
static const int NE = 1
static const int SW = 2
static const int SE = 3
static const unsigned int bbox_min_size = 10

Friends

class region_iterator< T >

Detailed Description

template<typename T>
class degate::QuadTree< T >

Quad tree to store objects and to accesss them with a two dimensional access path.

Definition at line 69 of file QuadTree.h.


Constructor & Destructor Documentation

template<typename T >
degate::QuadTree< T >::QuadTree ( BoundingBox const &  box,
QuadTree< T > *  parent,
std::string  node_name,
int  max_entries = 50 
) [private]

Definition at line 244 of file QuadTree.h.

References degate::QuadTree< T >::node_name.

                                                                                                         {
    this->box = box;
    this->max_entries = max_entries;
    this->parent = parent;

    node_name = parent->node_name + std::string("/") + _node_name;
  }
template<typename T >
degate::QuadTree< T >::QuadTree ( BoundingBox const &  box,
int  max_entries = 50 
)

Create a new quadtree.

Parameters:
boxThe bounding box defines the dimension of the quadtree.
max_entriesDefines how many objects should be stored in a quadtree node, before the node is splitted. This value is not a hard limit. The quadtree can ignore this parameter, if it has no choice.

Definition at line 236 of file QuadTree.h.

                                                                {
    this->box = box;
    this->max_entries = max_entries;
    parent = NULL;
    node_name = "/";
  }
template<typename T >
degate::QuadTree< T >::~QuadTree ( )

Destruct a quadtree.

Definition at line 253 of file QuadTree.h.

                         {
  }

Member Function Documentation

template<typename T >
unsigned int degate::QuadTree< T >::depth ( ) const

Get the number of layers, that quadtree has.

Definition at line 437 of file QuadTree.h.

                                        {

    unsigned int max_d = 0;
    if(!is_leave()) {
      for(typename std::vector< QuadTree<T> >::const_iterator it = subtree_nodes.begin();
          it != subtree_nodes.end();
          ++it) {

        unsigned int d = (*it).depth();
        max_d = std::max(max_d, d);
      }
    }
    return 1 + max_d;
  }
template<typename T>
void degate::QuadTree< T >::get_all_elements ( std::vector< T > &  vec) const

Definition at line 257 of file QuadTree.h.

Referenced by degate::Layer::cloneDeepInto().

                                                            {
    std::copy(children.begin(), children.end(), back_inserter(vec));
    std::for_each(subtree_nodes.begin(), subtree_nodes.end(), [&vec](const QuadTree<T> &q) {
      q.get_all_elements(vec);
    });
  }

Here is the caller graph for this function:

template<typename T >
BoundingBox const & degate::QuadTree< T >::get_bounding_box ( ) const

Get the bounding box for a quad tree layer.

Definition at line 489 of file QuadTree.h.

Referenced by degate::Layer::cloneShallow(), and degate::Layer::get_bounding_box().

                                                         {
    return box;
  }

Here is the caller graph for this function:

template<typename T >
unsigned int degate::QuadTree< T >::get_height ( ) const

Get the dimension of the quadtree.

Definition at line 270 of file QuadTree.h.

Referenced by degate::Layer::get_height().

                                             {
    return box.get_height();
  }

Here is the caller graph for this function:

template<typename T>
const std::string degate::QuadTree< T >::get_name ( ) const [inline]

Definition at line 104 of file QuadTree.h.

{ return node_name; }
template<typename T >
unsigned int degate::QuadTree< T >::get_width ( ) const

Get the dimension of the quadtree.

Definition at line 265 of file QuadTree.h.

Referenced by degate::Layer::get_width().

                                            {
    return box.get_width();
  }

Here is the caller graph for this function:

template<typename T>
ret_t degate::QuadTree< T >::insert ( object)

Insert an object into the quadtree.

Definition at line 341 of file QuadTree.h.

References degate::QuadTree< T >::children, degate::QuadTree< T >::insert(), degate::QuadTree< T >::is_splitable(), degate::QuadTree< T >::reinsert_objects(), degate::RET_ERR, RET_IS_NOT_OK, degate::RET_OK, and degate::QuadTree< T >::split().

Referenced by degate::Layer::add_object(), and degate::QuadTree< T >::insert().

                                    {

    ret_t ret;
    const BoundingBox & bbox =
      get_bbox_trait_selector<is_pointer<T>::value>::get_bounding_box_for_object(object);

    QuadTree<T> * found = traverse_downto_bounding_box(bbox);
    assert(found != NULL);

    if(found != NULL) {

      if((found->children.size() >= max_entries) && found->is_splitable()) {

        if(RET_IS_NOT_OK(ret = found->split())) return ret;
        if(RET_IS_NOT_OK(ret = found->reinsert_objects())) return ret;
        if(RET_IS_NOT_OK(ret = found->insert(object))) return ret;
        return RET_OK;
      }
      else {
        found->children.push_back(object);
        return RET_OK;
      }
    }
    return RET_ERR;
  }

Here is the call graph for this function:

Here is the caller graph for this function:

template<typename T>
bool degate::QuadTree< T >::is_empty ( ) const [inline]

Definition at line 166 of file QuadTree.h.

Referenced by degate::Layer::is_empty().

{ return total_size() == 0; }

Here is the caller graph for this function:

template<typename T >
bool degate::QuadTree< T >::is_leave ( ) const

Check if the quadtree or a quadtree node is a leaf node.

Definition at line 398 of file QuadTree.h.

Referenced by degate::QuadTree< T >::remove().

                                   {
    return subtree_nodes.size() == 4 ? false : true;
  }

Here is the caller graph for this function:

template<typename T >
bool degate::QuadTree< T >::is_splitable ( ) const [private]

Definition at line 276 of file QuadTree.h.

Referenced by degate::QuadTree< T >::insert().

Here is the caller graph for this function:

template<typename T>
void degate::QuadTree< T >::notify_shape_change ( object)

Notify that the bounding box of an object changed.

It might be neccessary to adjust the objects position in the quadtree.

Definition at line 368 of file QuadTree.h.

Referenced by degate::Layer::notify_shape_change().

                                                {
    remove(object);
    insert(object);
  }

Here is the caller graph for this function:

template<typename T >
void degate::QuadTree< T >::print ( std::ostream &  os = std::cout,
int  tabs = 0,
bool  recursive = false 
)

Print the quadtree.

Definition at line 494 of file QuadTree.h.

References degate::gen_tabs(), degate::BoundingBox::get_max_x(), degate::BoundingBox::get_max_y(), degate::BoundingBox::get_min_x(), and degate::BoundingBox::get_min_y().

Referenced by degate::Layer::print().

                                                                   {

    os
      << gen_tabs(tabs) << "Node name                      : " << get_name() << std::endl
      << gen_tabs(tabs) << "Bounding box                   : x = "
      << box.get_min_x() << " .. " << box.get_max_x()
      << " / y = "
      << box.get_min_y() << " .. " << box.get_max_y()
      << std::endl

      << gen_tabs(tabs) << "Num elements in this node      : " << children.size() << std::endl
      << gen_tabs(tabs) << "Preferred max num of elements : " << max_entries << std::endl
      << std::endl
      ;

    if(parent == NULL /* || children.size() < 5 */ ) {

      for(typename std::list<T>::iterator c_iter = children.begin();
          c_iter != children.end(); ++c_iter) {

        const BoundingBox & e_bb =
          get_bbox_trait_selector<is_pointer<T>::value>::get_bounding_box_for_object(*c_iter);

        os
          << gen_tabs(tabs) << "    + Element bounding box           : x = "
          << e_bb.get_min_x() << " .. " << e_bb.get_max_x()
          << " / y = "
          << e_bb.get_min_y() << " .. " << e_bb.get_max_y()
          << std::endl;
      }

      os << std::endl;
    }

    if(recursive) {
      for(typename std::vector<QuadTree<T> >::iterator stn_iter = subtree_nodes.begin();
          stn_iter != subtree_nodes.end(); ++stn_iter) {
        (*stn_iter).print(os, tabs+1);
      }
    }


  }

Here is the call graph for this function:

Here is the caller graph for this function:

template<typename T >
region_iterator< T > degate::QuadTree< T >::region_iter_begin ( int  min_x,
int  max_x,
int  min_y,
int  max_y 
)

Get an interator to iterate over quadtree nodes down to the leafes.

Get an end marker for the iteration

See also:
down_iter_begin() Get a region iterator to iterate over quatree objects.

Definition at line 466 of file QuadTree.h.

Referenced by degate::Layer::exists_type_in_region(), degate::Layer::get_distance_to_gate_boundary(), degate::Layer::get_object_at_position(), degate::Layer::objects_begin(), and degate::Layer::region_begin().

                                                                                              {

    BoundingBox bbox(min_x, max_x, min_y, max_y);
    return region_iter_begin(bbox);
  }

Here is the caller graph for this function:

template<typename T >
region_iterator< T > degate::QuadTree< T >::region_iter_begin ( BoundingBox const &  bbox)

Get a region iterator to iterate over quatree objects.

Definition at line 473 of file QuadTree.h.

                                                                            {
    return region_iterator<T>(this, bbox);
  }
template<typename T >
region_iterator< T > degate::QuadTree< T >::region_iter_begin ( )

Get a region iterator to iterate over the complete quatree.

Definition at line 478 of file QuadTree.h.

                                                    {
    return region_iterator<T>(this, box);
  }
template<typename T >
region_iterator< T > degate::QuadTree< T >::region_iter_end ( )

Get an end marker for the region iteration.

Definition at line 483 of file QuadTree.h.

Referenced by degate::Layer::exists_type_in_region(), degate::Layer::get_distance_to_gate_boundary(), degate::Layer::get_object_at_position(), degate::Layer::objects_end(), and degate::Layer::region_end().

                                                  {
    return region_iterator<T>();
  }

Here is the caller graph for this function:

template<typename T >
ret_t degate::QuadTree< T >::reinsert_objects ( ) [private]

Definition at line 325 of file QuadTree.h.

References degate::RET_OK.

Referenced by degate::QuadTree< T >::insert().

                                      {

    typename std::list<T> children_copy = children;

    children.clear();

    for(typename std::list<T>::iterator it = children_copy.begin();
        it != children_copy.end();
        ++it) {
      insert(*it);
    }

    return RET_OK;
  }

Here is the caller graph for this function:

template<typename T>
ret_t degate::QuadTree< T >::remove ( object)

Remove an object from the quadtree.

Definition at line 374 of file QuadTree.h.

References degate::QuadTree< T >::children, degate::QuadTree< T >::is_leave(), degate::RET_ERR, degate::RET_OK, and degate::QuadTree< T >::subtree_nodes.

Referenced by degate::Layer::remove_object().

                                    {
    const BoundingBox & bbox =
      get_bbox_trait_selector<is_pointer<T>::value>::get_bounding_box_for_object(object);

    QuadTree<T> * found = traverse_downto_bounding_box(bbox);
    assert(found != NULL);
    if(found != NULL) {
      found->children.remove(object);

      if(!found->is_leave() &&
         found->subtree_nodes[NW].children.size() == 0 &&
         found->subtree_nodes[NE].children.size() == 0 &&
         found->subtree_nodes[SW].children.size() == 0 &&
         found->subtree_nodes[SE].children.size() == 0) {
        found->subtree_nodes.clear();
      }

      return RET_OK;
    }
    return RET_ERR;
  }

Here is the call graph for this function:

Here is the caller graph for this function:

template<typename T >
ret_t degate::QuadTree< T >::split ( ) [private]

Definition at line 283 of file QuadTree.h.

References debug(), degate::RET_ERR, degate::RET_OK, and TM.

Referenced by degate::QuadTree< T >::insert().

                           {
    if(is_splitable()) {

      BoundingBox nw(box.get_min_x(), box.get_center_x(),
                     box.get_min_y(), box.get_center_y());


      BoundingBox sw(box.get_min_x(), box.get_center_x(),
                     box.get_center_y() + 1, box.get_max_y());


      BoundingBox ne(box.get_center_x() + 1, box.get_max_x(),
                     box.get_min_y(), box.get_center_y());


      BoundingBox se(box.get_center_x() + 1, box.get_max_x(),
                     box.get_center_y() + 1,  box.get_max_y());


      QuadTree<T> node_nw(nw, this, "NW", max_entries);
      QuadTree<T> node_ne(ne, this, "NE", max_entries);
      QuadTree<T> node_sw(sw, this, "SW", max_entries);
      QuadTree<T> node_se(se, this, "SE", max_entries);


      subtree_nodes.push_back(node_nw);
      subtree_nodes.push_back(node_ne);
      subtree_nodes.push_back(node_sw);
      subtree_nodes.push_back(node_se);

      return RET_OK;
    }

    debug(TM, "Failed to split a quadtree node of width %d and height %d that is %sa leave",
          box.get_width(),
          box.get_height(),
          is_leave() ? "" : "not ");
    assert(1 == 0);
    return RET_ERR;
  }

Here is the call graph for this function:

Here is the caller graph for this function:

template<typename T >
unsigned int degate::QuadTree< T >::total_size ( ) const

Get the number of objects that are stored in a quadtree node and in all child nodes.

Definition at line 423 of file QuadTree.h.

Referenced by degate::QuadTree< quadtree_element_type >::is_empty().

                                             {
    unsigned int this_node = children.size();
    unsigned int sub_nodes = 0;
    if(!is_leave()) {
      for(typename std::vector< QuadTree<T> >::const_iterator it = subtree_nodes.begin();
          it != subtree_nodes.end();
          ++it) {
        sub_nodes += (*it).total_size();
      }
    }
    return this_node + sub_nodes;
  }

Here is the caller graph for this function:

template<typename T >
QuadTree< T > * degate::QuadTree< T >::traverse_downto_bounding_box ( BoundingBox const &  box) [private]

Definition at line 403 of file QuadTree.h.

References degate::BoundingBox::get_bounding_box(), and degate::BoundingBox::in_bounding_box().

                                                                                 {

    if(is_leave()) return this;

    for(typename std::vector< QuadTree<T> >::iterator it = subtree_nodes.begin();
        it != subtree_nodes.end();
        ++it) {

      const BoundingBox & sub_bbox = (*it).box.get_bounding_box();

      //if(sub_bbox.in_bounding_box(box)) { // sub_bbox within box?
        if(box.in_bounding_box(sub_bbox)) { // box within sub_bbox?
        return (*it).traverse_downto_bounding_box(box);
      }
    }
    //    assert(1 == 0);
    return this;
  }

Here is the call graph for this function:


Friends And Related Function Documentation

template<typename T>
friend class region_iterator< T > [friend]

Definition at line 71 of file QuadTree.h.


Member Data Documentation

template<typename T>
const unsigned int degate::QuadTree< T >::bbox_min_size = 10 [static, private]

Definition at line 81 of file QuadTree.h.

template<typename T>
BoundingBox degate::QuadTree< T >::box [private]

Definition at line 85 of file QuadTree.h.

template<typename T>
std::list<T> degate::QuadTree< T >::children [private]

Definition at line 87 of file QuadTree.h.

Referenced by degate::QuadTree< T >::insert(), and degate::QuadTree< T >::remove().

template<typename T>
unsigned int degate::QuadTree< T >::max_entries [private]

Definition at line 83 of file QuadTree.h.

template<typename T>
const int degate::QuadTree< T >::NE = 1 [static, private]

Definition at line 77 of file QuadTree.h.

template<typename T>
std::string degate::QuadTree< T >::node_name [private]
template<typename T>
const int degate::QuadTree< T >::NW = 0 [static, private]

Definition at line 76 of file QuadTree.h.

template<typename T>
QuadTree* degate::QuadTree< T >::parent [private]

Definition at line 89 of file QuadTree.h.

template<typename T>
const int degate::QuadTree< T >::SE = 3 [static, private]

Definition at line 79 of file QuadTree.h.

template<typename T>
std::vector<QuadTree<T> > degate::QuadTree< T >::subtree_nodes [private]
template<typename T>
const int degate::QuadTree< T >::SW = 2 [static, private]

Definition at line 78 of file QuadTree.h.


The documentation for this class was generated from the following file: