1

クワッドツリー内の子ノードのセットを親に再帰的に折りたたむのに問題があります。追加、削除、および細分割は問題なく機能しますが、ツリーから十分な要素が削除されても、ツリーは満杯に満たないノードを親に折りたたんでから削除することはありません。

ありがとう。

[編集]

問題が解決しました。これが最終的なコードです。みんなありがとう。

#ifndef QUADTREETEST_QUADTREE_H
#define QUADTREETEST_QUADTREE_H

#include <algorithm>
#include <vector>
#include <a2de_graphics.h>
#include <a2de_math.h>

template<typename T>
class QuadTree {

public:
    QuadTree(a2de::Rectangle bounds);
    ~QuadTree();

    bool Add(std::vector<T>& elems);
    bool Add(T& elem);
    bool Remove(T& elem);
    bool Move(T& elem);
    unsigned long Height();
    unsigned long Divisions();
    void Draw(BITMAP* dest);
    unsigned long NumberOfElementsInTree();

    std::vector<T> Query(a2de::Rectangle area);

    std::vector<QuadTree<T>*> GetSiblings(QuadTree<T>* node);
    static unsigned long GetMaxElementsPerNode();
    static void SetMaxElementsPerNode(unsigned long max_elements);

protected:
private:
    enum CHILD_ELEMENTS {
        CHILD_UPPER_LEFT,
        CHILD_UPPER_RIGHT,
        CHILD_LOWER_LEFT,
        CHILD_LOWER_RIGHT,
    };
    static unsigned long MAX_ELEMENTS;
    QuadTree(QuadTree<T>* parent_node, a2de::Rectangle bounds);
    QuadTree(QuadTree<T>* parent_node, a2de::Rectangle bounds, std::vector<T>& elems);
    void SubDivide();
    void UnSubDivide();
    bool IsLeaf(QuadTree<T>* node);
    std::vector<T> QueryNode(QuadTree<T>* node, a2de::Rectangle area);
    bool RemoveElement(T& elem);

    std::vector<T> _elements;
    a2de::Rectangle _bounds;
    QuadTree<T>* _parent;
    std::vector<QuadTree<T>*> _children;

};

template<typename T>
bool QuadTree<T>::Add(std::vector<T>& elems) {
    for(std::vector<T>::iterator _iter = elems.begin(); _iter != elems.end(); ++_iter) {
        this->Add(*_iter);
    }
}

template<typename T>
std::vector<QuadTree<T>*> QuadTree<T>::GetSiblings(QuadTree<T>* node) {

    std::vector<QuadTree<T>*> siblings;

    //Bad pointer.
    if(node == nullptr) return siblings;

    //Root node can't have siblings. Return queried node.
    if(node->_parent == nullptr) {
        siblings.push_back(node);
        return siblings;
    }
    for(std::size_t i = 0; i < 4; ++i) {
        siblings.push_back(_parent->_children[i]);
    }
    return siblings;

}

template<typename T>
std::vector<T> QuadTree<T>::QueryNode(QuadTree<T>* node, a2de::Rectangle area) {
    std::vector<T> contained_elements;
    if(node->_bounds.Intersects(area)) {
        for(std::vector<T>::iterator _iter = _elements.begin(); _iter != _elements.end(); ++_iter) {
            contained_elements.push_back(*_iter);
        }
        if(IsLeaf(node) == false) {
            std::vector<T> ul_elements = QueryNode(_children[CHILD_UPPER_LEFT], area);
            std::vector<T> ur_elements = QueryNode(_children[CHILD_UPPER_RIGHT], area);
            std::vector<T> ll_elements = QueryNode(_children[CHILD_LOWER_LEFT], area);
            std::vector<T> lr_elements = QueryNode(_children[CHILD_LOWER_RIGHT], area);
            for(std::vector<T>::iterator _iter = ul_elements.begin(); _iter != ul_elements.end(); ++_iter) {
                contained_elements.push_back(*_iter);
            }
            ul_elements.clear();

            for(std::vector<T>::iterator _iter = ur_elements.begin(); _iter != ur_elements.end(); ++_iter) {
                contained_elements.push_back(*_iter);
            }
            ur_elements.clear();

            for(std::vector<T>::iterator _iter = ll_elements.begin(); _iter != ll_elements.end(); ++_iter) {
                contained_elements.push_back(*_iter);
            }
            ll_elements.clear();

            for(std::vector<T>::iterator _iter = lr_elements.begin(); _iter != lr_elements.end(); ++_iter) {
                contained_elements.push_back(*_iter);
            }
            lr_elements.clear();
        }
    }
    return contained_elements;
}

template<typename T>
std::vector<T> QuadTree<T>::Query(a2de::Rectangle area) {
    return QueryNode(this, area);
}

template<typename T>
unsigned long QuadTree<T>::MAX_ELEMENTS = 2;

template<typename T>
unsigned long QuadTree<T>::GetMaxElementsPerNode() {
    return MAX_ELEMENTS;
}

template<typename T>
void QuadTree<T>::SetMaxElementsPerNode(unsigned long max_elements) {
    MAX_ELEMENTS = max_elements;
}

template<typename T>
unsigned long QuadTree<T>::NumberOfElementsInTree() {
    if(IsLeaf(this)) return _elements.size();
    unsigned long num_elements = _elements.size();
    for(std::size_t i = 0; i < 4; ++i) {
        num_elements += _children[i]->NumberOfElementsInTree();
    }
    return num_elements;
}

template<typename T>
unsigned long QuadTree<T>::Divisions() {
    if(IsLeaf(this)) return 0;
    unsigned long num_divisions = 4;
    for(std::size_t i = 0; i < 4; ++i) {
        num_divisions += _children[i]->Divisions();
    }
    return num_divisions;
}

template<typename T>
unsigned long QuadTree<T>::Height() {

    if(IsLeaf(this)) return 0;
    unsigned long height = 1;
    for(std::size_t i = 0; i < 4; ++i) {
        height += _children[i]->Height();
    }
    return height;
}

template<typename T>
bool QuadTree<T>::IsLeaf(QuadTree<T>* node) {
    for(std::size_t i = 0; i < 4; ++i) {
        if(node->_children[i] == false) continue;
        return false;
    }
    return true;
}

template<typename T>
QuadTree<T>::~QuadTree() {
    _elements.clear();
    _parent = nullptr;
    for(std::size_t i = 0; i < 4; ++i) {
        delete _children[i];
        _children[i] = nullptr;
    }
}

template<typename T>
void QuadTree<T>::Draw(BITMAP* dest) {
    if(IsLeaf(this)) {
        _bounds.Draw(dest, _bounds.GetColor(), _bounds.IsFilled());
        return;
    }
    for(std::size_t i = 0; i < 4; ++i) {
        _children[i]->Draw(dest);
    }
}

template<typename T>
QuadTree<T>::QuadTree(a2de::Rectangle bounds) : _elements(), _bounds(bounds), _parent(nullptr), _children(4) {
    _bounds.SetColor(a2de::LIME_GREEN);
    _bounds.SetFill(false);
}

template<typename T>
QuadTree<T>::QuadTree(QuadTree<T>* parent_node, a2de::Rectangle bounds) : _elements(), _bounds(bounds), _parent(parent_node), _children(4) {
    _bounds.SetColor(a2de::LIME_GREEN);
    _bounds.SetFill(false);
}

template<typename T>
QuadTree<T>::QuadTree(QuadTree<T>* parent_node, a2de::Rectangle bounds, std::vector<T>& elems) : _elements(elems), _bounds(bounds), _parent(parent_node), _children(4) {
    _bounds.SetColor(a2de::LIME_GREEN);
    _bounds.SetFill(false);
    Add(elems);
}

template<typename T>
void QuadTree<T>::SubDivide() {
    try {
        //Define 
        double half_width = _bounds.GetWidth() / 2.0;
        double half_height = _bounds.GetHeight() / 2.0;
        if(half_width <= 1.0 || half_height <= 1.0) return;

        a2de::Vector2D dimensions(half_width, half_height);
        a2de::Vector2D ul_pos(this->_bounds.GetPosition());
        a2de::Vector2D ur_pos(ul_pos + a2de::Vector2D(half_width, 0.0));
        a2de::Vector2D ll_pos(ul_pos + a2de::Vector2D(0.0, half_height));
        a2de::Vector2D lr_pos(ul_pos + dimensions);
        int color = _bounds.GetColor();
        bool filled = _bounds.IsFilled();

        a2de::Rectangle ul(ul_pos, dimensions, color, filled);
        a2de::Rectangle ur(ur_pos, dimensions, color, filled);
        a2de::Rectangle ll(ll_pos, dimensions, color, filled);
        a2de::Rectangle lr(lr_pos, dimensions, color, filled);

        _children[CHILD_UPPER_LEFT] = new QuadTree(this, ul);
        _children[CHILD_UPPER_RIGHT] = new QuadTree(this, ur);
        _children[CHILD_LOWER_LEFT] = new QuadTree(this, ll);
        _children[CHILD_LOWER_RIGHT] = new QuadTree(this, lr);

        //Give elements of mine to children, may or may not accept them.
        for(std::size_t i = 0; i < 4; ++i) {
            for(std::vector<T>::iterator _iter = _elements.begin(); _iter != _elements.end(); ++_iter) {
                _children[i]->Add(*_iter);
            }
        }
        _elements.clear();

    } catch(...) {
        for(std::size_t i = 0; i < 4; ++i) {
            if(_children[i]) {
                delete _children[i];
                _children[i] = nullptr;
            }
        }
    }
}

template<typename T>
void QuadTree<T>::UnSubDivide() {

    for(std::size_t i = 0; i < 4; ++i) {
        QuadTree<T>* curNode = _children[i];
        QuadTree<T>* curNodeParent = curNode->_parent;
        for(std::vector<T>::iterator _iter = curNode->_elements.begin(); _iter != curNode->_elements.end(); ++_iter) {
            curNodeParent->_elements.push_back(*_iter);
        }
        delete _children[i];
        _children[i] = nullptr;
    }
}

template<typename T>
bool QuadTree<T>::Add(T& elem) {

    if(elem.Intersects(_bounds) == false) return false;

    if(IsLeaf(this) == false) {
        for(std::size_t i = 0; i < 4; ++i) {
            _children[i]->Add(elem);
        }
        return false;
    }
    _elements.push_back(elem);
    if(_elements.size() > MAX_ELEMENTS) {
        SubDivide();
    }
    return true;

}


template<typename T>
bool QuadTree<T>::RemoveElement(T& elem) {
    std::vector<T>::iterator _iter = _elements.begin();
    _iter = std::find(_elements.begin(), _elements.end(), elem);
    if(_iter != _elements.end()) {
        _elements.erase(_iter);
        return true;
    }
    return false;
}


template<typename T>
bool QuadTree<T>::Remove(T& elem) {

    if(elem.Intersects(_bounds) == false) return false;

    if(IsLeaf(this)) {
        return RemoveElement(elem);
    }

    for(std::size_t i = 0; i < 4; ++i) {
        _children[i]->Remove(elem);
    }

    bool all_children_are_leaves = true;
    for(std::size_t i = 0; i < 4; ++i) {
        if(IsLeaf(_children[i])) continue;
        all_children_are_leaves = false;
        break;
    }

    if(all_children_are_leaves) {
        unsigned long elements_in_children = 0;
        for(std::size_t i = 0; i < 4; ++i) {
            elements_in_children += _children[i]->NumberOfElementsInTree();
        }
        if(elements_in_children < MAX_ELEMENTS) {
            UnSubDivide();
        }
    }
    return true;
}

template<typename T>
bool QuadTree<T>::Move(T& elem) {

    return false;
}

#endif
4

1 に答える 1

1

あなたのRemoveコードは間違っています。thisがリーフでない場合は、最初に子ノードで再帰呼び出しを行います。ただし、折りたたむことができるのは非リーフのみです。thisが葉のときに倒れる必要があるかどうかを確認します。

この問題を解決するには、「ノードを折りたたむ可能性がある」コードを再帰呼び出しとの間で移動しreturn trueます。

次の問題は、の要素の数を確認することですthis。ただし、すでに述べたように、それは葉ではないため、要素をホストしません。代わりに、要素は子ノードに配置されます。

この問題を解決するには、子の要素の数を合計する必要があります。折りたたむ必要がある場合はthis、4つの子ノードすべてがリーフであることを示すことができます。それ以外の場合は、すでに折りたたまれているためです（再帰によってこれを証明できます）。したがって、最初に4つの子ノードすべてがリーフであるかどうかを確認する必要があります。いいえの場合、崩壊する必要はありません。はいの場合、それらを合計し、_elements.size()これをしきい値と比較します（これがすべきでない理由については、質問に対する私の最初のコメントを参照してくださいMAX_ELEMENTS）。

あなたの方法UnSubDivideは正しいはずだと思います。

于 2012-12-09T22:15:13.317 に答える