四叉樹移動存儲點

Question

我使用四叉樹作爲數據結構來存儲點。因爲我需要快速找到特定區域內的所有點。

但是我需要移動點。在我的C++程序中。由於運動發生在所有點上，但是對於不同方向上的每個點，我現在銷燬我的四叉樹並重建它，這會導致大量的分配和刪除。

因此，我的問題是這樣的問題有更好的數據結構嗎？

我有以下要求： 我有n點。

我需要快速獲得給定區域內的所有點。用我的四叉樹，這是關於O（log（n））。然而這個操作被稱爲m次，其中m> n因此它大約是O（m * log（n））。

我需要移動所有點。目前這個運行在O（n * logn）左右。對於所有的m，這個方法只被調用一次。

但是我覺得目前這個解決方案並不令人滿意。由於我總是銷燬我的四叉樹並重建它，導致由於分配而導致的開銷。

更新： 點不是均勻分佈的。有些位置是密集的，有些位置只有很少的點。

這是一些簡化的代碼。這其中存儲了指針的代碼：

class Point 
{ 
    public: 
    Point(double x, double y):x(x),y(y){}; 

    void movePoint(double ux, double uy); 

    double x; 
    double y; 
}; 

這裏是四叉樹

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<Point*> get(double north, double west, double south, double east); 
    // deletes everything in the quad tree 
    void clear(); 

private: 

    QuadTreeNode* top_=nullptr; 

}; 

，並在這裏與get和put方法實施QuadTreeNode的接口來說明如何的接口點被存儲。

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() > maxItems_) 
      split(); 
     return true; 
     } else { 
     QuadTreeNode* node = getChild(leaf->getX(), leaf->getY()); 
     if (node != nullptr) { 
      return node->put(leaf); 
     } 
     } 
     return false; 
    } 

    std::vector<Point*> QuadTreeNode::get(QuadRectangle rect, std::vector<Point*>& vector) { 
     if (children_ == nullptr) { 
     for (Point* pt : items_) { 
      if (rect.pointWithinBounds(pt->getX(),pt->getY())) { 
       vector.push_back(pt); 
      } 
     } 
     } else { 
     for (QuadTreeNode* child : *children_) { 
      if (child->bounds_.within(rect)) { 
       child->get(rect, vector); 
      } 
     } 
     } 
     return vector; 
} 

    std::vector<Point*> items_; 

    unsigned int maxItems_; 

    std::array<QuadTreeNode*,4>* children_ = nullptr; 

    QuadRectangle bounds_;  
}; 

Answer 1

浮現在腦海中的一些想法：

1. 對於每一個移動點，檢查它是否移出邊框（bounds_）的。如果是，請將其從樹中移除。移動所有點後，將它們插入同一棵樹或另一棵樹中。每隔一段時間（例如，當另一棵樹的大小變成主樹的1/10時），重建所有東西。
2. 在分割節點時，您可能計算每個子筆記中的點的邊界矩形。當這樣做時，允許一些邊界進入邊界，所以可以將每個點移動幾次迭代而不會超出邊界。

這些想法沒有幫助的複雜性（它仍然爲O（n *的log（n）），但也許一些因素提高速度。