1
我无法递归倒塌一组子节点的四叉树到他们的父母。添加，删除和分区工作正常，但是当从树中删除足够的元素时，树不会将未满的节点折叠到父级中，然后将其删除。递归地将一组QuadTree节点折叠到它们的父节点中？
谢谢。
[编辑]
问题解决这里的最终代码。多谢你们。
#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
注意，你通常要为大家介绍的折叠节点另一阈值。设想一个包含“MAX_ELEMENTS”元素的树节点。如果添加并删除元素，则会将该节点分成四个子节点并再次折叠它们。重复这一点，你的表现不佳。我建议允许元素的数量低于（比方说）MAX_ELEMENTS/2来避免这种行为。 – leemes
改进代码的建议：不要给子节点一个名称，而是将它们放在一个大小为4的简单数组中。每当您访问子节点时，都应该在这四个元素的循环中发生，而不是通过将代码复制到分别处理每个子节点。此外，您不必清除'UnSubDivide'中的元素矢量，因为您仍然会删除这些节点。 – leemes
粘贴您的测试数据，在这里重现您的问题。 –