-1
\$\begingroup\$

I'm currently implementing my own QuadTree in C++. It runs well with 100 items, but once you start adding more it slows down. remove, getAll, and insert have all been profiled as taking a while. Any advice is appreciated!

class QuadTree {
private:
    const static int MAX_OBJECTS = 20;
    AABB bounds;

    std::vector<QuadTree> children;
    std::set<Locatable*> entities;
    std::set<Locatable*> allEntities;

    // Internal methods
    void split() {
        children.clear();

        double width = (bounds.getWidth() / 2);
        double height = (bounds.getHeight() / 2);
        double x = bounds.getX();
        double y = bounds.getY();

        children.push_back(QuadTree(AABB(x + width, y, width, height)));
        children.push_back(QuadTree(AABB(x, y, width, height)));
        children.push_back(QuadTree(AABB(x, y + height, width, height)));
        children.push_back(QuadTree(AABB(x + width, y + height, width, height)));
    }

    int getIndex(AABB& aabb) {
        double vertMid = bounds.getVertMid();
        double horzMid = bounds.getHorzMid();

        // Fits in top
        bool topQuadrant = aabb.getY() + aabb.getHeight() < horzMid;
        // Fits in botom
        bool bottomQuadrant = aabb.getY() > horzMid;

        // Fits in left
        if (aabb.getX() + aabb.getWidth() < vertMid) {
            if (topQuadrant) {
                return 1;
            } else if (bottomQuadrant) {
                return 2;
            }
        }
        // Fits in right
        else if (aabb.getX() > vertMid) {
            if (topQuadrant) {
                return 0;
            } else if (bottomQuadrant) {
                return 3;
            }
        }

        return -1;
    }

    void merge(std::set<Locatable*>& one, std::set<Locatable*> two) {
        one.insert(two.begin(), two.end());
    }
    // End Internal methods
public:
    QuadTree(AABB bounds) : bounds(bounds) {
        children.reserve(4);
    }

    // Base
    void clear() {
        entities.clear();
        allEntities.clear();

        for (auto it = children.begin(); it != children.end(); it++) {
            it->clear();
        }

        children.clear();
    }

void insert(Locatable* object) {
    AABB aabb = object->getAABB();

    allEntities.insert(object);

    if (entities.size() > MAX_OBJECTS) {
        if (children.empty()) {
            split();

            auto it = entities.begin();
            while (it != entities.end()) {
                int index = getIndex((*it)->getAABB());
                if (index != -1) {
                    children.at(index).insert(*it);
                    it = entities.erase(it);
                }
                else {
                    it++;
                }
            }
        }

        int index = getIndex(aabb);
        if (index != -1) {
            children.at(index).insert(object);
        }
        else {
            entities.insert(object);
        }
    }
    else {
        entities.insert(object);
    }
}

    void remove(Locatable* object, AABB aabb) {
        auto it = allEntities.find(object);
        if (it == allEntities.end()) {
            return;
        }
        allEntities.erase(it);

        it = entities.find(object);
        if (it == entities.end()) {
            if (!children.empty()) {
                int index = getIndex(aabb);

                if (index != -1) {
                    children.at(index).remove(object, aabb);
                }
            }
        }
        else {
            entities.erase(it);
        }
    }

    QuadTree* getLowestRoot(AABB aabb) {
        int index = getIndex(aabb);
        if (index == -1 || children.empty()) {
            return this;
        }
        return children.at(index).getLowestRoot(aabb);
    }

    std::set<Locatable*> getAll() {
        std::set<Locatable*> result;
        if (children.empty()) {
            return entities;
        }

        result = entities;
        for (auto it = children.begin(); it != children.end(); it++) {
            merge(result, it->getAll());
        }

        return result;
    }
    // End Base
};
\$\endgroup\$
3
  • \$\begingroup\$ I was about to say/add that in my answer. Is your insert performance improved now? Do you have any performance problem remaining? \$\endgroup\$
    – ChrisW
    Mar 24, 2014 at 3:56
  • \$\begingroup\$ A big problem was that I was attempting 70 updates for second. I have dropped that number to 30. \$\endgroup\$
    – Tips48
    Mar 24, 2014 at 3:56
  • \$\begingroup\$ Yeah, getAll and remove are still a little on the slow side \$\endgroup\$
    – Tips48
    Mar 24, 2014 at 3:57

2 Answers 2

3
\$\begingroup\$

General Notes

  • Pass references rather than values if you don't need a copy of the object. Use const references if you don't want the function to change the object.
  • Declare member functions to be const if they don't change the state of the object.
  • Range-based loops are easier to read than explicitly using iterators.
  • Separate header and implementation files makes it easier to see an overview of a class without having to wade through the gory details.
  • Compare the performance of unordered_set to set.
  • In the code posted below I changed the coding style. Your coding style isn't wrong. I'm just very anal and was too lazy to change it back.

AABB

  • Defining an AABB by its corners is more intuitive than one corner and a size. The latter isn't wrong, but you might want to consider this alternative.
  • I moved getIndex() to the AABB class because it is more logical.
  • I made getIndex() simpler.

.

class AABB
{
public:
  AABB(double minX,double minY,double maxX,double maxY);
  double getMinX() const;
  double getMinY() const;
  double getMaxX() const;
  double getMaxY() const;
  double getMidX() const;
  double getMidY() const;
  int getQuad(const AABB& aabb) const;
private:
  int getQuad(double x,double y) const;
private:
  double minX;
  double minY;
  double maxX;
  double maxY;
  double midX;
  double midY;
};

AABB::AABB(double minX_,double minY_,double maxX_,double maxY_)
  :minX(minX_),
  minY(minY_),
  maxX(maxX_),
  maxY(maxY_),
  midX((minX_+maxX_)/2.0),
  midY((minY_+maxY_)/2.0)
{}

double AABB::getMinX() const
{
  return minX;
}

double AABB::getMinY() const
{
  return minY;
}

double AABB::getMaxX() const
{
  return maxX;
}

double AABB::getMaxY() const
{
  return maxY;
}

double AABB::getMidX() const
{
  return midX;
}

double AABB::getMidY() const
{
  return midY;
}

int AABB::getQuad(const AABB& aabb) const
{
  int tl = getQuad(aabb.getMinX(),aabb.getMinY());
  int br = getQuad(aabb.getMaxX(),aabb.getMaxY());
  if(tl==br)
    return tl;
  return -1;
}

int AABB::getQuad(double x,double y) const
{
  if(y<getMidY())
  {
    if(x<getMidX())
      return 1;
    else
      return 0;
  }
  else
  {
    if(x<getMidX())
      return 2;
    else
      return 3;
  }
}

Locatable

const AABB& getAABB() const;

clear()

  • You don't need to call clear() on all of the children. The children will be destroyed when you clear() the vector.

insert() / split()

  • Your improved insert() is much better than your original version.
  • Don't make a copy of the AABB just pass it by reference.
  • In insert(), the code that reinserts the entities is only run after split(). Move that code into split() so we can make insert() a little simpler.

remove()

  • Does the AABB passed to this function differ from object->getAABB()?
  • You can optimistically call erase() and read the return value rather than using iterators.

getAll()

  • You are doing a huge amount of work by maintaining allEntities. It has everything you need.
  • Don't make a copy unless necessary.

getLowestRoot()

  • This function is great, but do you do anything with the object returned other than call getAll()? If not, replace it with getAllIn().

Eliminate entities or allEntities

These variables are redundant and maintaining them both is too much overhead. The one you should eliminate depends on how often you call insert()/remove() compared to getAll(). Both versions are below. I did very little testing for correctness so you probably want to ensure that these have the same output as your current version.

class QuadTree
{
private:
  static const int MAX_OBJECTS = 20;
public:
  QuadTree(const AABB& bounds);
  void clear();
  void insert(Locatable* object);
  void remove(Locatable* object);
  void remove(Locatable* object,const AABB& aabb);
  QuadTree* getLowestRoot(const AABB& aabb);
  const std::unordered_set<Locatable*>& getAll() const;
  const std::unordered_set<Locatable*>& getAllIn(const AABB& aabb) const;
private:
  void split();
private:
  AABB bounds;
  std::vector<QuadTree> children;
  std::unordered_set<Locatable*> allEntities;
};

QuadTree::QuadTree(const AABB& bounds)
  :bounds(bounds)
{
  children.reserve(4);
}

void QuadTree::clear()
{
  allEntities.clear();
  children.clear();
}

void QuadTree::insert(Locatable* object)
{
  allEntities.emplace(object);
  if(children.empty())
  {
    if(allEntities.size() > MAX_OBJECTS)
      split();
  }
  else
  {
    int index = bounds.getQuad(object->getAABB());
    if(index!=-1)
      children.at(index).insert(object);
  }
}

void QuadTree::remove(Locatable* object)
{
  if(allEntities.erase(object)!=0 && !children.empty())
  {
    int index = bounds.getQuad(object->getAABB());
    if (index != -1)
      children.at(index).remove(object);
  }
}

void QuadTree::remove(Locatable* object,const AABB& aabb)
{
  if(allEntities.erase(object)!=0 && !children.empty())
  {
    int index = bounds.getQuad(aabb);
    if (index != -1)
      children.at(index).remove(object),aabb;
  }
}

QuadTree* QuadTree::getLowestRoot(const AABB& aabb)
{
  if(children.empty())
    return this;
  int index = bounds.getQuad(aabb);
  if(index == -1)
    return this;
  return children.at(index).getLowestRoot(aabb);
}

const std::unordered_set<Locatable*>& QuadTree::getAll() const
{
  return allEntities;
}

const std::unordered_set<Locatable*>& QuadTree::getAllIn(const AABB& aabb) const
{
  if(children.empty())
    return allEntities;
  int index = bounds.getQuad(aabb);
  if(index == -1)
    return allEntities;
  return children.at(index).getAllIn(aabb);
}

void QuadTree::split()
{
  children.emplace_back(AABB(bounds.getMidX(),bounds.getMinY(),bounds.getMaxX(),bounds.getMidY()));
  children.emplace_back(AABB(bounds.getMinX(),bounds.getMinY(),bounds.getMidX(),bounds.getMidY()));
  children.emplace_back(AABB(bounds.getMinX(),bounds.getMidY(),bounds.getMidX(),bounds.getMaxY()));
  children.emplace_back(AABB(bounds.getMidX(),bounds.getMidY(),bounds.getMaxX(),bounds.getMaxY()));

  for(Locatable* l : allEntities)
  {
    int index = bounds.getQuad(l->getAABB());
    if(index!=-1)
      children.at(index).insert(l);
  }
}

.

class QuadTree
{
private:
  static const int MAX_OBJECTS = 20;
public:
  QuadTree(const AABB& bounds);
  void clear();
  void insert(Locatable* object);
  void remove(Locatable* object);
  void remove(Locatable* object,const AABB& aabb);
  QuadTree* getLowestRoot(const AABB& aabb);
  void getAll(std::unordered_set<Locatable*>& all) const;
  void getAllIn(std::unordered_set<Locatable*>& all,const AABB& aabb) const;
private:
  void split();
private:
  AABB bounds;
  std::vector<QuadTree> children;
  std::unordered_set<Locatable*> entities;
};

QuadTree::QuadTree(const AABB& bounds)
  :bounds(bounds)
{
  children.reserve(4);
}

void QuadTree::clear()
{
  entities.clear();
  children.clear();
}

void QuadTree::insert(Locatable* object)
{
  if(children.empty())
  {
    entities.emplace(object);
    if(entities.size() > MAX_OBJECTS)
      split();
  }
  else
  {
    int index = bounds.getQuad(object->getAABB());
    if(index==-1)
      entities.emplace(object);
    else
      children.at(index).insert(object);
  }
}

void QuadTree::remove(Locatable* object)
{
  if(entities.erase(object)==0 && !children.empty())
  {
    int index = bounds.getQuad(object->getAABB());
    if(index!=-1)
      children.at(index).remove(object);
  }
}

void QuadTree::remove(Locatable* object,const AABB& aabb)
{
  if(entities.erase(object)==0 && !children.empty())
  {
    int index = bounds.getQuad(aabb);
    if(index!=-1)
      children.at(index).remove(object,aabb);
  }
}

QuadTree* QuadTree::getLowestRoot(const AABB& aabb)
{
  if(children.empty())
    return this;
  int index = bounds.getQuad(aabb);
  if(index == -1)
    return this;
  return children.at(index).getLowestRoot(aabb);
}

void QuadTree::getAll(std::unordered_set<Locatable*>& all) const
{
  for(Locatable* l : entities)
    all.emplace(l);
  if(!children.empty())
  {
    children.at(0).getAll(all);
    children.at(1).getAll(all);
    children.at(2).getAll(all);
    children.at(3).getAll(all);
  }
}

void QuadTree::getAllIn(std::unordered_set<Locatable*>& all,const AABB& aabb) const
{
  if(children.empty())
  {
    getAll(all);
    return;
  }
  int index = bounds.getQuad(aabb);
  if(index == -1)
  {
    getAll(all);
    return;
  }
  return children.at(index).getAllIn(all,aabb);
}

void QuadTree::split()
{
  children.emplace_back(AABB(bounds.getMidX(),bounds.getMinY(),bounds.getMaxX(),bounds.getMidY()));
  children.emplace_back(AABB(bounds.getMinX(),bounds.getMinY(),bounds.getMidX(),bounds.getMidY()));
  children.emplace_back(AABB(bounds.getMinX(),bounds.getMidY(),bounds.getMidX(),bounds.getMaxY()));
  children.emplace_back(AABB(bounds.getMidX(),bounds.getMidY(),bounds.getMaxX(),bounds.getMaxY()));

  auto cit = entities.cbegin();
  while(cit!=entities.cend())
  {
    int index = bounds.getQuad((*cit)->getAABB());
    if(index!=-1)
    {
      children.at(index).insert(*cit);
      cit = entities.erase(cit);
    }
    else
      ++cit;
  }
}

Other Optimizations

  • Consider other data structures such as a k-d tree. You can make the tree more balanced by moving the pivot points.
  • Tune MAX_OBJECTS.
  • Restructure your code so that insert(), remove(), and getAll() are called less often.
  • After splitting, if an entity cannot be inserted into any children, put it in a different data structure.
\$\endgroup\$
2
\$\begingroup\$

getAll returns a set, which is an ordered set. The ordering will be done by comparing Location*. I doubt you care about the order of Location* and it would be faster to use std::unordered_set instead.

Similarly, remove and insert might be faster if entities and allEntities were of type std::unordered_set instead of std::set.

Use the reserve method, or the size_t argument passed to the constructor, to specify a size of unordered_set that's big enough for the expected number of objects in it.


I don't understand why allEntities exists. The only way it's used is in remove, where it implements an early return if the object isn't in the Quadtree.

If that's what it's for then you don't need it in every level: you only need it on the top-level Quadtree. Therefore you should have two types of Quadtree:

  • A more complicated, top-level one which includes allEntities
  • A simpler one used for children which doesn't include allEntities

Beware that remove uses allEntities to test for existence in the tree, but the getLowestRoot method does not.

And the getLowest Root should (to optimize performance) verify whether is has children before it calls getIndex.


The remove method, as coded, should throw an exception if getIndex returns -1 (because that would be unexpected/theoretically impossible/a bug).


split should call children.reserve(4) not children.clear() because it's only called once.


Yeah, getAll and remove are still a little on the slow side.

getAll just needs to return the contents of allEntities, instead of recursing into children.

remove should be faster if you use unordered_set instead of set (see for example Why on earth would anyone use set instead of unordered_set?).

remove would also be (slightly) faster if AABB were passed by reference instead of by value.

I suspect that Locatable::getAABB should return a const reference, and that you shouldn't have statements like ...

AABB aabb = object->getAABB();

... but should instead prefer ...

const AABB& aabb = object->getAABB();

The code is a bit careless with its use of comparisons; in the following code ...

    bool topQuadrant = aabb.getY() + aabb.getHeight() < horzMid;
    // Fits in botom
    bool bottomQuadrant = aabb.getY() > horzMid;

... I would have expected <= in the 1st comparison or >=in the second.


The insert method was buggy (very buggy and slightly buggy) until I commented and you fixed it twice. It now has a new problem:

  • Immediately after you split, you no longer have 20 objects in entities
  • Therefore the next several elements will be stored in entities instead of being assigned to a quadrant

IMO you may want code like this:

// In the top-level type of Quadtree, which has allEntities member
// assuming this type has Quadtree as a private superclass
void insert(Locatable* object) {
    // only if this is the top-level type of Quadtree
    allEntities.insert(object);
    Quadtree::insert(object);
}

// In the type of Quadtree used for children and as a superclass of above
void insert(Locatable* object) {

    if (children.empty()) {
        if (entities.size() <= MAX_OBJECTS)) {
            // don't split
            entities.insert(object);
            return;
        }
        // else split existing elements
        // before inserting object into children
        split();

        auto it = entities.begin();
        while (it != entities.end()) {
            int index = getIndex((*it)->getAABB());
            if (index != -1) {
                children.at(index).insert(*it);
                // https://stackoverflow.com/q/15662412/49942
                it = entities.erase(it);
            }
            else {
                it++;
            }
        }
    }
    // else insert into children
    int index = getIndex(aabb->getAABB());
    if (index != -1) {
        children.at(index).insert(object);
    }
    else {
        entities.insert(object);
    }
}
\$\endgroup\$
1
  • \$\begingroup\$ I understand, thank you. I've adapted my code to be similar to your suggestion. \$\endgroup\$
    – Tips48
    Mar 25, 2014 at 22:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.