Рекурсивно сворачивает набор узлов QuadTree в своих родителей?
У меня возникают проблемы при рекурсивном сворачивании набора дочерних узлов в четырехугольном дереве в их родительский. Добавление, удаление и SubDividing работает очень хорошо, но когда из дерева удаляется достаточное количество элементов, дерево не сворачивает узлы с неполным заполнением в родительский узел, а затем удаляет их.
Благодарю.
[РЕДАКТИРОВАТЬ]Проблема решена вот окончательный код. Спасибо, парни.
#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
Решение
Ваш Remove код неверный. Сначала вы делаете рекурсивный вызов на дочерних узлах, если this это не лист Тем не менее, только не листья могут быть свернуты. Вы проверяете, должны ли вы рухнуть, когда this это лист.
Чтобы решить эту проблему, переместите код «возможно, коллапс узлов» между рекурсивными вызовами и return true,
Следующая проблема заключается в том, что вы проверяете количество элементов this, Однако, как уже говорилось, это не лист и, следовательно, не содержит элементов. Вместо этого элементы расположены в дочерних узлах.
Чтобы решить эту проблему, мы должны суммировать количество элементов детей. Мы можем показать это, если нам придется развалиться thisвсе 4 дочерних узла являются листами, так как в противном случае мы уже свернули их (вы можете доказать это с помощью рекурсии). Поэтому сначала нужно проверить, являются ли все 4 дочерних узла листьями. Если нет, нам не нужно рушиться. Если да, мы подводим итоги _elements.size() и сравните это с пороговым значением (см. мой 1-й комментарий на ваш вопрос, почему это не должно быть MAX_ELEMENTS).
Я думаю твой метод UnSubDivide должно быть правильно.
Другие решения
Других решений пока нет …