四叉树移动存储点

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;

};

以下是QuadTreeNode接口的get和put方法实现，以展示如何存储Point。

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_;    
};

- tune2fs

---

请提供更多关于您的四叉树的信息，最好附带一些代码片段。 - Kirill Kobelev

您可以重复使用先前分配的存储空间，避免重新分配。 - Walter

如果你的点几乎是均匀分布的，那么最好使用一个简单的搜索网格（桶），使用坐标本身的位模式作为索引。 - Walter

我不确定如何做，因为四叉树的结构可能完全不同。存储的点不会被重新分配，但四叉树可能会重新分配。 - tune2fs

我认为沃尔特在他的第一篇帖子中所指的是尽可能地重用四叉树节点，通过重新链接节点指针并根据需要调整图形。你也可以维护一个未使用节点的“池”。实现其中任何一个都会增加一些复杂性，但如果你的问题在于reallocs，那么或许值得考虑。 - WeirdlyCheezy

Answer 1

一些想法：

1. 对于每个移动的点，检查它是否移出了边界矩形（bounds_）。如果是，则从树中删除它。在移动所有点之后，将它们插入到同一棵树中或另一棵树中。定期（例如当另一棵树的大小变为主树的1/10时）重建所有内容。
2. 在拆分节点时，您可能会为每个子节点中的点计算一个边界矩形。在执行此操作时，允许一些余量进入边界，以便可以将每个点移动几次而不使其超出边界。

这些想法并没有改变复杂度（它仍然是O(n*log(n))），但可能会提高速度。

- anatolyg

---

我在代码中实现了第一个想法。然而，它比重建整个树要慢，因为几乎每个节点都离开了它的矩形 :( - tune2fs