title: Quadtree moving of stored points
body: <p>I use a quad tree as a datastructure to store points. As I need to find in a fast way all points in certain area.</p>
  
  <p>However I need to move the points. In my C++ program. As the movement happens to all points but for every point in an different direction I currently destroy my quadtree and rebuild it, which causes lots of allocation and deletion. </p>
  
  <p>My question is therefore is there a better datastructure for this kind of problem?</p>
  
  <p>I have the following requirements:
  I have n-Points.</p>
  
  <p>I need to get in an fast way all points in a given certain area. With my quadtree this is about O(log(n)). However this operation is called m times where m > n therefore it is about O(m*log(n)).</p>
  
  <p>I need to move all points. At the moment this runs in about O(n*logn). This method is only called once for all m.</p>
  
  <p>However I find this solution at the moment unsatisfactory. As I always destroy my quadtree and rebuild it which causes an overhead due to the allocation.</p>
  
  <p><strong>UPDATE:</strong>
  The points are not uniformely distributed. There are positions where they are dense and some position where there are few points.</p>
  
  <p>Here is some simplified code. Here the code of the pointer which are stored:</p>
  
  <pre><code>class Point
  {
      public:
      Point(double x, double y):x(x),y(y){};
  
      void movePoint(double ux, double uy);
  
      double x;
      double y;
  };
  </code></pre>
  
  <p>here is the interface of the quad tree</p>
  
  <pre><code>class QuadTree
  {
  public:
      QuadTree(double north, double west, double south, double east,
               int maxItems);
  
      //inserts a point into the tree runs in log(n)
      bool put(Point* pt);
      // returns all point in the rectange defined by the four variables runs in log(n)
      std::vector&lt;Point*&gt; get(double north, double west, double south, double east);
      // deletes everything in the quad tree
      void clear();
  
  private:
  
      QuadTreeNode* top_=nullptr;
  
  };
  </code></pre>
  
  <p>and here the interface of the QuadTreeNode with the get and put method implementation to show how a Point is stored.</p>
  
  <pre><code>class QuadTreeNode
  {
  public:
  
      QuadTreeNode(double north, double west, double south, double east,
                   int maximumItems);
  
      ~QuadTreeNode();
  
      //split the node if to much items are stored.
      void split();
      //returns the children of the node
      QuadTreeNode* getChild(double x, double y);
  
      bool put(Point* leaf){
        if (children_ == nullptr) {
          items_.push_back(leaf);
  
          if (items_.size() &gt; maxItems_)
              split();
          return true;
        } else {
          QuadTreeNode* node = getChild(leaf-&gt;getX(), leaf-&gt;getY());
          if (node != nullptr) {
              return node-&gt;put(leaf);
          }
         }
        return false;
      }
  
      std::vector&lt;Point*&gt; QuadTreeNode::get(QuadRectangle rect, std::vector&lt;Point*&gt;&amp; vector) {
        if (children_ == nullptr) {
          for (Point* pt : items_) {
              if (rect.pointWithinBounds(pt-&gt;getX(),pt-&gt;getY())) {
                  vector.push_back(pt);
              }
          }
        } else {
          for (QuadTreeNode* child : *children_) {
              if (child-&gt;bounds_.within(rect)) {
                  child-&gt;get(rect, vector);
              }
          }
        }
        return vector;
  }
  
      std::vector&lt;Point*&gt; items_;
  
      unsigned int maxItems_;
  
      std::array&lt;QuadTreeNode*,4&gt;* children_ = nullptr;
  
      QuadRectangle bounds_;    
  };
  </code></pre>