3

ポイントを格納するためのデータ構造として四分木を使用します。特定の領域内のすべてのポイントをすばやく見つける必要があるため。

ただし、ポイントを移動する必要があります。私のC++プログラムで。移動はすべてのポイントで発生しますが、すべてのポイントで異なる方向に移動するため、現在、クアッドツリーを破棄して再構築しているため、多くの割り当てと削除が発生します。

したがって、私の質問は、この種の問題のためのより良いデータ構造はありますか?

次の要件があります: n ポイントを持っています。

特定のエリア内のすべてのポイントをすばやく取得する必要があります。私の四分木では、これは約O（log（n））です。ただし、この操作は m > n の場合に m 回呼び出されるため、約 O(m*log(n)) になります。

すべてのポイントを移動する必要があります。現時点では、これは約 O(n*logn) で実行されます。このメソッドは、すべての m に対して 1 回だけ呼び出されます。

しかし、現時点ではこの解決策は不十分だと思います。私は常に四分木を破棄して再構築するため、割り当てによるオーバーヘッドが発生します。

更新: ポイントは均一に分散されていません。密集している場所と点数が少ない場所があります。

ここにいくつかの単純化されたコードがあります。格納されているポインターのコードは次のとおりです。

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;

};

ここでは、Point がどのように格納されるかを示す 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_;    
};
4

1 に答える 1

1

頭に浮かぶいくつかのアイデア：

  1. 移動したポイントごとに、境界矩形 ( bounds_) から移動したかどうかを確認します。はいの場合は、ツリーから削除します。すべての点を移動したら、それらを同じツリーまたは別のツリーに挿入します。ときどき (他のツリーのサイズがメイン ツリーの 1/10 になるときなど)、すべてを再構築します。
  2. ノードを分割するとき、おそらく各子ノートのポイントの境界矩形を計算します。それを行うときは、境界内にある程度の余裕を持たせてください。そうすれば、各ポイントを境界から外れることなく数回移動することができます。

これらのアイデアは複雑さには役立ちませんが (O(n*log(n)) のままです)、何らかの要因で速度が向上する可能性があります。

于 2012-10-10T20:09:11.657 に答える