Collapsing a set of QuadTree nodes into their parent recursively?

Question

I'm having trouble recursively collapsing a set of child nodes in a quad tree into their parent. Adding, Removing, and SubDividing is working just fine, but when enough elements are removed from the tree, the tree does not collapse the less-than-full nodes into the parent then delete them.

Thanks.

[EDIT]

Issue Resolved here's the final code. Thanks guys.

#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

Your Remove code is wrong. You first make a recursive call on the child nodes if this is not a leaf. However, only non-leafs can be collapsed. You check if you have to collapse when this is a leaf.

To solve this issue, move the "possibly collapse nodes"-code between the recursive calls and return true.

The next issue is that you check the number of elements of this. However, as already said, it is not a leaf and thus doesn't host the elements. Instead, the elements are located in the child nodes.

To solve this issue, we have to sum up the number of elements of the children. We can show that, if we have to collapse this, all 4 child nodes are leafs, since otherwise we already had collapsed them (you can prove this by recursion). So we first have to check if all 4 child nodes are leafs. If no, we don't have to collapse. If yes, we sum up their _elements.size() and compare this with the threshold value (see my 1st comment to your question for why this shouldn't be MAX_ELEMENTS).

I think your method UnSubDivide should be correct.