c++ - 递归地将一组 QuadTree 节点折叠到它们的父节点中？

Question

我无法递归地将四叉树中的一组子节点折叠到它们的父节点中。添加、删除和 segmentation 工作正常，但是当从树中删除足够多的元素时，树不会将未满节点折叠到父节点中然后删除它们。

谢谢。

[编辑]

问题已解决这是最终代码。谢谢大家。

#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

Answer 1

您的Remove 代码是错误的。如果 this 不是叶子，则首先对子节点进行递归调用。但是，只有非叶子可以折叠。当 this 是一片叶子时，您检查是否必须折叠。

要解决此问题，请在递归调用和return true 之间移动“可能崩溃的节点”代码。

下一个问题是检查this 的元素数量。但是，如前所述，它不是叶子，因此不承载元素。相反，元素位于子节点中。

要解决这个问题，我们要对 child 的元素个数求和。我们可以证明，如果我们必须折叠 this，所有 4 个子节点都是叶子，否则我们已经折叠了它们(您可以通过递归证明这一点)。所以我们首先必须检查所有 4 个子节点是否都是叶子节点。如果没有，我们不必崩溃。如果是，我们总结它们的 _elements.size() 并将其与阈值进行比较(请参阅我对您的问题的第一条评论，了解为什么这不应该是 MAX_ELEMENTS) .

我认为你的方法 UnSubDivide 应该是正确的。