Quad Tree Implementation in C++11

Question

The following source code is working Quad Tree Implementation in C++11. How can I simplify the source code but also allow the user to bring his own Point Class Implementation?

#pragma once

#include <algorithm>
#include <array>
#include <cstddef>
#include <functional>
#include <vector>

namespace forest {
template <typename T, std::size_t Capacity>
class QuadTree {
 public:
  using Point = std::array<T, 2>;
  using Points = std::vector<Point>;
  using PointsIt = typename std::vector<Point>::iterator;
  using Callback = std::function<void(const Point &)>;

 public:
  class Range {
    template <typename U, std::size_t K>
    friend class QuadTree;

   private:
    Point mOrigin;
    Point mTransform;

   public:
    Range() = default;

    Range(const Point &origin, const Point &transform)
        : mOrigin(origin), mTransform(transform) {}

    ~Range() = default;

   public:
    void setOrigin(const Point &origin) { mOrigin = origin; }
    void setTransform(const Point &transform) { mTransform = transform; }

   public:
    Point getOrigin() const { return mOrigin; }
    Point getTransform() const { return mTransform; }

   public:
    bool Contains(const Point &point) const {
      return point[0] >= mOrigin[0] - mTransform[0] &&
             point[0] <= mOrigin[0] + mTransform[0] &&
             point[1] >= mOrigin[1] - mTransform[1] &&
             point[1] <= mOrigin[1] + mTransform[1];
    }
    bool Intersects(const Range &other) const {
      return mOrigin[0] - mTransform[0] <=
                 other.mOrigin[0] + other.mTransform[0] &&
             mOrigin[0] + mTransform[0] >=
                 other.mOrigin[0] - other.mTransform[0] &&
             mOrigin[1] - mTransform[1] <=
                 other.mOrigin[1] + other.mTransform[1] &&
             mOrigin[1] + mTransform[1] >=
                 other.mOrigin[1] - other.mTransform[1];
    }
  };

 private:
  Points mBucket;

 private:
  Range mBoundary;

 private:
  bool mDivided{false};

 private:
  QuadTree *NW{nullptr};
  QuadTree *NE{nullptr};
  QuadTree *SW{nullptr};
  QuadTree *SE{nullptr};

 private:
  void Divide() {
    NW = new QuadTree<T, Capacity>(
        {{mBoundary.mOrigin[0] - mBoundary.mTransform[0] / 2,
          mBoundary.mOrigin[1] + mBoundary.mTransform[1] / 2},
         {mBoundary.mTransform[0] / 2, mBoundary.mTransform[1] / 2}});
    NE = new QuadTree<T, Capacity>(
        {{mBoundary.mOrigin[0] + mBoundary.mTransform[0] / 2,
          mBoundary.mOrigin[1] + mBoundary.mTransform[1] / 2},
         {mBoundary.mTransform[0] / 2, mBoundary.mTransform[1] / 2}});
    SW = new QuadTree<T, Capacity>(
        {{mBoundary.mOrigin[0] - mBoundary.mTransform[0] / 2,
          mBoundary.mOrigin[1] - mBoundary.mTransform[1] / 2},
         {mBoundary.mTransform[0] / 2, mBoundary.mTransform[1] / 2}});
    SE = new QuadTree<T, Capacity>(
        {{mBoundary.mOrigin[0] + mBoundary.mTransform[0] / 2,
          mBoundary.mOrigin[1] - mBoundary.mTransform[1] / 2},
         {mBoundary.mTransform[0] / 2, mBoundary.mTransform[1] / 2}});
    mDivided = true;
  }
  void Merge() {
    delete NW;
    delete NE;
    delete SW;
    delete SE;
    NW = nullptr;
    NE = nullptr;
    SW = nullptr;
    SE = nullptr;
    mDivided = false;
  }

 public:
  QuadTree() = delete;
  QuadTree(const Range &BOUNDARY) : mBoundary(BOUNDARY) {}
  ~QuadTree() { Clear(); }

 public:
  bool Insert(const Point &point) {
    if (!mBoundary.Contains(point)) return false;
    if (!mDivided) {
      if (std::find(mBucket.begin(), mBucket.end(), point) != mBucket.end())
        return false;
      mBucket.push_back(point);
      if (mBucket.size() > Capacity) {
        Divide();
        PointsIt it = mBucket.begin();
        while (it != mBucket.end()) {
          if (NW->mBoundary.Contains(*it))
            NW->Insert(*it);
          else if (NE->mBoundary.Contains(*it))
            NE->Insert(*it);
          else if (SW->mBoundary.Contains(*it))
            SW->Insert(*it);
          else if (SE->mBoundary.Contains(*it))
            SE->Insert(*it);
          it = mBucket.erase(it);
        }
      }
      return true;
    }
    return NW->Insert(point) || NE->Insert(point) || SW->Insert(point) ||
           SE->Insert(point);
  }
  bool Remove(const Point &point) {
    if (!mBoundary.Contains(point)) return false;
    if (!mDivided) {
      PointsIt begin = mBucket.begin();
      PointsIt end = mBucket.end();
      mBucket.erase(std::remove(begin, end, point), end);
      return true;
    }
    if (NW->Remove(point) || NE->Remove(point) || SW->Remove(point) ||
        SE->Remove(point)) {
      if (!NW->mDivided && !NE->mDivided && !SW->mDivided && !SE->mDivided) {
        if (NW->mBucket.empty() && NE->mBucket.empty() && SW->mBucket.empty() &&
            SE->mBucket.empty()) {
          Merge();
        }
      }
      return true;
    }
    return false;
  }
  bool Search(const Point &point) {
    if (!mBoundary.Contains(point)) return false;
    if (mDivided) {
      return NW->Search(point) || NE->Search(point) || SW->Search(point) ||
             SE->Search(point);
    }
    return std::find(mBucket.begin(), mBucket.end(), point) != mBucket.end();
  }
  void Query(const Range &range, const Callback callback) {
    if (!range.Intersects(mBoundary)) return;
    if (mDivided) {
      NW->Query(range, callback);
      NE->Query(range, callback);
      SW->Query(range, callback);
      SE->Query(range, callback);
    } else {
      for (auto child : mBucket) {
        if (range.Contains(child)) {
          callback(child);
        }
      }
    }
  }

 public:
  void Clear() {
    if (mDivided) {
      NW->Clear();
      NE->Clear();
      SW->Clear();
      SE->Clear();
    }
    mBucket.clear();
    Merge();
  }
};
}  // namespace forest

Answer 1

General

You labeled this as C++11; I'll try and stick to that feature set.

Everything after public: or private: gains that access qualifier, so you only have to use it once.

You use using: that is a good practice, using PointsIt = typename std::vector<Point>::iterator; but in most cases where you would need to use an iterator, auto has the same effect and is less work if you change your containers. The other reason why you'll most likely never write access an iterator type directly is that a ranged based for loop should be used instead.

QuadTree(const Range &BOUNDARY) : mBoundary(BOUNDARY) {}`

Capitalization is usually preserved for constants or compile time definitions; boundary would do nicely. The members NW, NE, etc. are not marked as members by your own convention should be mNW, etc. at least.

Your Range which you use with the variable name mBoundary, that is basically the extent or bounding box of the area of the node. There is nothing wrong with using the same name as the class name for a member variable, and it looks like you weren't quite happy with Range as you named the member variable differently. Boundary seems to be a better term than range anyway, 'Extent', 'BoundingBox' would also work.

There doesn't seem to be any specific reason to make the range a class inside of the QuadTree; it's just as comfortable on the outside as on the inside.

I personally prefer the public parts above the private section, but that is really a taste issue.

Range

The you declared the default constructor, but that lets you construct an invalid range. There is no need to make the quadtree a friend; if you just want to save the writing effort, Range could as well be a struct with member access. The defaulted constructor will leave the members in your range uninitialized, that is not a good thing. You could initialize things with {0} but depending on your application that might not be the correct thing to do.

Have you noticed that all the operations you do on your Range structure need to calculate the actual bounds? You would be better off storing the left, right, top and bottom bounds and checking against those.

QuadTree

To help with some of the suggestions in the following paragraph, I'd probably split the node type and the tree type.

In most operations you check for each quadrant if the point is in the quadrant, at the worst case (SE) that is 4 Contains calls, but you are trying to insert the point into a quad, besides being totally out of bounds of the tree, the test for the quadrant can be down with 2 checks. The point is either north or south of the horizontal midline, and east or west of the vertical midline. You can ascertain once at the root node if the point is within bounds and then you just need to check which quadrant you want to add the point to. Determining the quadrant for insertion before doing the insertion will reduce the complexity of your code as you will move from the pattern that you have

NW->DoOperation(point) || NE->DoOperation(point) || SW->DoOperation(point) || SE->DoOperation(point)

to

auto node = GetQuadrant(point);
node->DoOperation(point);

Even with 4 nodes replacing your member NW, NE, etc with an array of nodes will reduce complexity somewhat and increase readability.

Depending on the actual use, it might be better to amortize merges, i.e. not immediately merge empty nodes as the tree grows. In a dynamic system with a somewhat constant number of points, you would eventually reach an equilibrium and stop have to allocate new nodes of your tree. As the grid that you are partitioning is regular, a new split would be along the same lines as the old split. If you want, you could give the user a function to collapse the tree back to its minimal form.

Floating point comparisons

I don't know how you use this, but unless the values passed into this function for the point are exactly the same as the ones that you added this will fail. In graphical applications and games, floating point values would be compared by looking at an interval; if the values are within the interval they would be considered the same. So unless you pass exactly the same floating point value to functions like Search() or Remove() they will fail.

Insert()

Your insert function already checks if the node is in the bounds, so there is no need to check again; the array with the points can be cleared at the end of the iteration, as all points are moved to their respective quadrants. Using a range-based for loop will also be more idiomatic. I'd also change some of the checks to positive to reduce complexity. As you are iterating over all points you can clear the bucket in one step once you are done.

Remove()

There is no need to introduce the temporary begin and end:

  m_bucket.erase(m_bucket.begin(), m_bucket.end(), point), m_bucket.end());

works as well

But the return value true only indicates that the point was within the boundary, not that it was actually deleted.

Search()

What is the use for this? Within the domain of a program the user of your API usually knows that whether they added a point to the tree or not. Being able to look it up might not really be helpful.

Query()

Executing a callback for each found point might not yield the best performance. Depending on use, I'd probably prefer an interface that just returns the points that are part of the query. What this is doing here is more ProcessPointsInRange(). If you allow the user to pass in the results array then you can even amortize allocations over time.