什么是四叉树？

如图，设想，

红框表示地图，星星表示单位，黄框表现范围，

要处理地图中范围内的单位，最直接的做法是筛选所有单位。

通过上图可以看到一个显而易见的问题，大部分单位都不需要被处理。

如果把地图分成块，只筛选范围覆盖的块中的单位，这样就可以减少很多不必要的筛选。

四叉树可以有效解决这个问题。

树的每一层都把地图划分四块，根据地图尺寸来决定树的层数，层数越大划分越细。

当需要对某一范围的单位筛选时，只需要定位到与范围相交的树区域，再对其区域内的对象筛选即可。

四叉树的实现

#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;};

代码简洁，通俗易懂，承让。

效果图

左侧全图遍历，右侧四叉树遍历，通过左上角的开销时间，差异很明显。

下载源码点击此处

以上所述是小编给大家介绍的C++实现四叉树效果(附源码下载)，希望对大家有所帮助，如果大家有任何疑问请给我留言，小编会及时回复大家的。在此也非常感谢大家对网站的支持！