优雅的实现一颗四叉树
具备功能
- 创建树
- 插入节点
- 删除节点
- 遍历节点
类的定义
template <class Value>
class Tree4 {
public:
// 在范围内, 创建一颗指定层次的四叉树
Tree4(const MATH Rect &, size_t);
// 判断某一区域是否包含在四叉树内
template <class Range>
Tree4 * Contain(const Range &);
// 根据给定区域, 插入一个节点
template <class Range>
bool Insert(const Value *, const Range &);
// 根据给定区域, 删除一个节点
template <class Range>
bool Remove(const Value *, const Range &);
// 根据给定区域, 遍历匹配节点
template <class Range>
bool Match(const Range &, const STD function<bool(Value *)> &);
}
- 通过
template <class Value>来实例化特定类型的四叉树.
// 构造一颗范围在 [0, 0, 100, 100], 4 层, 用于存储 C1 对象的四叉树
Tree4<C1> tree41(MATH Rect(0,0,100,100), 4);
// 构造一颗范围在 [0, 0, 100, 100], 4 层, 用于存储 C2 对象的四叉树
Tree4<C2> tree42(MATH Rect(0,0,100,100), 4);
- 通过
template <class Range>来支持任意形状区域.
// 插入一个节点, 该节点占用范围 点[0, 0]
tree41.Insert(new C1(), MATH Vec2(0, 0));
// 插入一个节点, 该节点占用范围 矩形(原点[0, 0], 宽高[100, 100])
tree41.Insert(new C1(), MATH Rect(0, 0, 100, 100));
// 插入一个节点, 该节点占用范围 圆形(半径[100], 坐标[0, 0])
tree41.Insert(new C1(), MATH Circular(100, MATH Vec2(0, 0)));
类的实现
#pragma once
#include "base.h"
#include "math.h"
template <class Value>
class Tree4 {
private:
struct Pointer {
Tree4 *LT, *RT, *LB, *RB;
Pointer() :LT(nullptr), RT(nullptr), LB(nullptr), RB(nullptr)
{ }
~Pointer()
{
SAFE_DELETE(LT);
SAFE_DELETE(RT);
SAFE_DELETE(LB);
SAFE_DELETE(RB);
}
};
public:
Tree4(const MATH Rect &rect, size_t n = 0): _rect(rect)
{
STD queue<Tree4 *> queue;
queue.push(this);
for (auto c = 1; n != 0; --n, c *= 4)
{
for (auto i = 0; i != c; ++i)
{
auto tree = queue.front();
tree->Root();
queue.pop();
queue.push(tree->_pointer.LT);
queue.push(tree->_pointer.RT);
queue.push(tree->_pointer.LB);
queue.push(tree->_pointer.RB);
}
}
}
template <class Range>
bool Insert(const Value * value, const Range & range)
{
auto tree = Contain(range);
auto ret = nullptr != tree;
if (ret) { tree->_values.emplace_back(value); }
return ret;
}
template <class Range>
bool Remove(const Value * value, const Range & range)
{
auto tree = Contain(range);
auto ret = nullptr != tree;
if (ret) { ret = tree->Remove(value); }
return ret;
}
template <class Range>
bool Match(const Range & range, const STD function<bool(Value *)> & func)
{
if (!MATH intersect(_rect, range))
{
return true;
}
for (auto & value : _values)
{
if (!func(const_cast<Value *>(value)))
{
return false;
}
}
auto ret = true;
if (!IsLeaf())
{
if (ret) ret = _pointer.LT->Match(range, func);
if (ret) ret = _pointer.RT->Match(range, func);
if (ret) ret = _pointer.LB->Match(range, func);
if (ret) ret = _pointer.RB->Match(range, func);
}
return ret;
}
template <class Range>
Tree4 * Contain(const Range & range)
{
Tree4<Value> * ret = nullptr;
if (MATH contain(STD cref(_rect), range))
{
if (!IsLeaf())
{
if (nullptr == ret) ret = _pointer.LT->Contain(range);
if (nullptr == ret) ret = _pointer.RT->Contain(range);
if (nullptr == ret) ret = _pointer.LB->Contain(range);
if (nullptr == ret) ret = _pointer.RB->Contain(range);
}
if (nullptr == ret)
ret = this;
}
return ret;
}
private:
void Root()
{
_pointer.LT = new Tree4(MATH Rect(_rect.x, _rect.y, _rect.w * 0.5f, _rect.h * 0.5f));
_pointer.LB = new Tree4(MATH Rect(_rect.x, _rect.y + _rect.h * 0.5f, _rect.w * 0.5f, _rect.h * 0.5f));
_pointer.RT = new Tree4(MATH Rect(_rect.x + _rect.w * 0.5f, _rect.y, _rect.w * 0.5f, _rect.h * 0.5f));
_pointer.RB = new Tree4(MATH Rect(_rect.x + _rect.w * 0.5f, _rect.y + _rect.h * 0.5f, _rect.w * 0.5f, _rect.h * 0.5f));
}
bool Remove(const Value * value)
{
auto iter = STD find(_values.begin(), _values.end(), value);
auto ret = _values.end() != iter;
if (ret) { _values.erase(iter); }
return ret;
}
bool IsLeaf()
{
return nullptr == _pointer.LT
|| nullptr == _pointer.RT
|| nullptr == _pointer.LB
|| nullptr == _pointer.RB;
}
Tree4(const Tree4 &) = delete;
Tree4(Tree4 &&) = delete;
Tree4 &operator=(const Tree4 &) = delete;
Tree4 &operator=(Tree4 &&) = delete;
private:
MATH Rect _rect;
Pointer _pointer;
STD list<const Value *> _values;
};
DEMO效果
左侧 无四叉树，右侧 四叉树
