Quadtree implementation

Question

I've implemented a quadtree in C++. Ignore any apparent similarity to the pseudocode on Wikipedia, it's all in your head, I swear.

How can I improve it? Algorithm speed/space improvements, any extra functions that I'm likely to want... as well as general practice.

#ifndef _QUADTREE_H_
#define _QUADTREE_H_

#include <vector>
#include <iostream>

struct Point
{
    float x, y;
    Point(float x = 0, float y = 0):x(x), y(y){};
};

struct AABB
{
    Point centre;
    Point halfSize;

    AABB(Point centre = Point(), Point halfSize = Point()): centre(centre), halfSize(halfSize){};

    bool contains(Point a)
    {
        if(a.x < centre.x + halfSize.x && a.x > centre.x - halfSize.x)
        {
            if(a.y < centre.y + halfSize.y && a.y > centre.y - halfSize.y)
            {
                return true;
            }
        }
        return false;
    }

    bool intersects(AABB other)
    {
        //this right > that left                                          this left <s that right
        if(centre.x + halfSize.x > other.centre.x - other.halfSize.x || centre.x - halfSize.x < other.centre.x + other.halfSize.x)
        {
        // This bottom > that top
            if(centre.y + halfSize.y > other.centre.y - other.halfSize.y || centre.y - halfSize.y < other.centre.y + other.halfSize.y)
            {
                return true;
            }
        }
        return false;
    }
};

template <typename T>
struct Data
{
    Point pos;
    T* load;

    Data(Point pos = Point(), T* data = NULL): pos(pos), load(data){};
};


template <class T>
class Quadtree
{
    private:
        //4 children
        Quadtree* nw;
        Quadtree* ne;
        Quadtree* sw;
        Quadtree* se;

        AABB boundary;

        std::vector< Data<T> > objects;

        int CAPACITY;       
    public:
        Quadtree<T>();
        Quadtree<T>(AABB boundary);

        ~Quadtree();

        bool insert(Data<T> d);
        void subdivide();
        std::vector< Data<T> > queryRange(AABB range);
};

template <class T>
Quadtree<T>::Quadtree()
{
    CAPACITY = 4;
    nw = NULL;
    ne = NULL;
    sw = NULL;
    se = NULL;
    boundary = AABB();
    objects = std::vector< Data<T> >();
}

template <class T>
Quadtree<T>::Quadtree(AABB boundary)
{
    objects = std::vector< Data<T> >();
    CAPACITY = 4;
    nw = NULL;
    ne = NULL;
    sw = NULL;
    se = NULL;
    this->boundary = boundary;
}

template <class T>
Quadtree<T>::~Quadtree()
{
    delete nw;
    delete sw;
    delete ne;
    delete se;
}

template <class T>
void Quadtree<T>::subdivide()
{
    Point qSize = Point(boundary.halfSize.x, boundary.halfSize.y);
    Point qCentre = Point(boundary.centre.x - qSize.x, boundary.centre.y - qSize.y);
    nw = new Quadtree(AABB(qCentre, qSize));

    qCentre = Point(boundary.centre.x + qSize.x, boundary.centre.y - qSize.y);
    ne = new Quadtree(AABB(qCentre, qSize));

    qCentre = Point(boundary.centre.x - qSize.x, boundary.centre.y + qSize.y);
    sw = new Quadtree(AABB(qCentre, qSize));

    qCentre = Point(boundary.centre.x + qSize.x, boundary.centre.y + qSize.y);
    se = new Quadtree(AABB(qCentre, qSize));
}

template <class T>
bool Quadtree<T>::insert(Data<T> d)
{
    if(!boundary.contains(d.pos))
    {
        return false;
    }

    if(objects.size() < CAPACITY)
    {
        objects.push_back(d);
        return true;
    }

    if(nw == NULL)
    {
        subdivide();
    }

    if(nw->insert(d))
    {
        return true;
    }
    if(ne->insert(d))
    {
        return true;
    }
    if(sw->insert(d))
    {
        return true;
    }
    if(se->insert(d))
    {
        return true;
    }

    return false;   
}

template <class T>
std::vector< Data<T> > Quadtree<T>::queryRange(AABB range)
{
    std::vector< Data<T> > pInRange = std::vector< Data<T> >();

    if(!boundary.intersects(range))
    {
        return pInRange;
    }

    for(int i = 0; i < objects.size(); i++)
    {
        if(range.contains(objects.at(i).pos))
        {
            pInRange.push_back(objects.at(i));
        }
    }

    if(nw == NULL)
    {
        return pInRange;
   }

    std::vector< Data<T> > temp = nw->queryRange(range);
    pInRange.insert(pInRange.end(), temp.begin(), temp.end());

    temp = ne->queryRange(range);
    pInRange.insert(pInRange.end(), temp.begin(), temp.end());

    temp = sw->queryRange(range);
    pInRange.insert(pInRange.end(), temp.begin(), temp.end());

    temp = se->queryRange(range);
    pInRange.insert(pInRange.end(), temp.begin(), temp.end());

    return pInRange;
}
#endif

I'm not particularly happy about defining CAPACITY like I do, putting const int CAPACITY = 4; in the header would be much nicer than having it twice, but initialising in class declarations is C++14, right?

Answer 1

Ok, so here we go for a few tips:

• Several methods such as AABB::contains and AABB::intersects do not modify the AABB instance they are called with. Therefore, you should const-qualify these methods to make sure that they can also be called in a const context.

  bool intersects(AABB other) const { /* ... */ }
                              ^^^^^
  

• As pointed by @glampert in the comments, an AABB instance wheights four floats, so it's becoming quite heavy compared to a built-in type. Therefore, when you pass it to a function, you might want to pass it by const reference instead of passing it by value if you only plan to read from it without modifying it:

  bool intersects(const AABB& other) const { /* ... */ }
                  ^^^^^     ^
  

• _QUADTREE_H_ begins with an underscore followed by a capital letter. Therefore, it is an identifier reserved to the implementation. To fix this, the simplest thing to do is to drop the leading underscore and use QUADTREE_H_ instead.

• Wherever possible (hint: always), use nullptr instead of NULL to avoid subtle and tricky overload problems.

• From C++11 onward, you can write Point pos = {} instead of Point pos = Point() to default-initialize the Point. It is terser and incurs less changes if you ever want to change the class name.

• You can also drop the class name when you declare and initialize at once thanks to C++11 uniform initialization:

  Point qSize = { boundary.halfSize.x, boundary.halfSize.y };
  

  Note that in this case, what you actually want to write is probably this:

  Point qSize = boundary.halfSize;
  

  As a size note, if you need to do more Point/Vector arithmetics, you better implement the full classes and overload the operators to gain in readability and avoid having to write everything coordinate-by-coordinate everytime you need to perform a simple operation.

• If CAPACITY is never meant to change, you could make it a static constexpr member variable. Also, I wouldn't use ALLCAPS_CASE for its name, which is a case that we generally use to denote the use of macros.

  static constexpr int capacity = 4;
  

• Try to use the constructor initialization list when you can so that the compiler does not have to assign values to variable after the object is constructed:

  template <class T>
  Quadtree<T>::Quadtree():
      nw{nullptr},
      ne{nullptr},
      sw{nullptr},
      se{nullptr}
  {}
  

  You don't have to explicitly default-initialize the other parameters since they will be default-initialized anyway if you don't write anything.

• You have an old C-style for loop with indices-based iteration here:

  for(int i = 0; i < objects.size(); i++)
  {
      if(range.contains(objects.at(i).pos))
      {
          pInRange.push_back(objects.at(i));
      }
  }
  

  I am sure that you will like the C++11 range-based for loop:

  for(auto&& object: objects)
  {
      if(range.contains(object.pos))
      {
          pInRange.push_back(object);
      }
  }
  

  Hey, it's terser and you don't have to fear off-by-one iteration errors anymore :)

• Also, you wondered whether in-class initializer were C++14. Good news, they are avaible in C++11. They were only slightly upgraded to cover more obscure cases in C++14, so you can totally write your Point class like this:

  struct Point
  {
      float x = 0.0f;
      float y = 0.0f;
  };
  

  The constructor will then use the in-class initializers to initialize the structure. Note that I changed 0 to 0.0f which is the correct literal for float. While correct literals are generally not that relevant, getting them right becomes more and more important in a type-deducing C++ world.

Answer 2

I think the centres you are calculating for the boundaries of the sub-trees do not match the member names: for example, the centre position for nw should be in fact the one of sw.

This could be an issue if you will add optimisations for choosing the correct child node based on the object and sub-node positions according to the center of the parent tree (and I think you should do it, e.g. if you are going to use this quadtree to store geometrical objects in computer graphics).

---

Also, but I'm not totally sure about it, I thought some logic behind the quadTree is to store data only on leaf nodes; now you are storing part of the data in every node, and expanding the tree as needed: this would cause searching operations to be executed in every node, which complicates a bit the logic for each of them, and this could be a sub-optimal solution.

Answer 3

Sorry I am late to this party, but your code is actually useful to me, so I am using it as a start for my own; here are my comments on style.

1. No need for ; after functions. Only declarations end in semicolons.

2. When passing AABB objects, which are on the large side, consider passing parameters by const & instead of copying. It is faster to copy objects less than 3 words. This is 4 floats, it is kind of borderline but I will check. Certainly if you use double, then pass by reference. 2b. AABB is a weird name. Boundary would be better.

3. Do not pull code out of the class when it is so short. The constructor and destructor are 4 lines each, the code becomes more readable and shorter when kept in the class definition, and this is the kind of code where you want those inlined anyway.

4. Do not pass Data by value!!! This is huge, you have no idea how big T could be. Always by reference when you don't know.

5. The biggest so far that I found is that in insert, you are testing nw,ne,sw,se. You should be comparing your value and deciding which one to do without trying them all!

6. You might consider having only a single bounding box at the top and computing the bounds of each sub quadtree dynamically. It might be just as fast and would take substantially less space.