C++實現四叉樹效果(附源碼下載)

2020-01-26 14:12:46

字體：大中小

來源：轉載

供稿：網友

什么是四叉樹？

如圖，設想，

紅框表示地圖，星星表示單位，黃框表現范圍，

要處理地圖中范圍內的單位，最直接的做法是篩選所有單位。

通過上圖可以看到一個顯而易見的問題，大部分單位都不需要被處理。

如果把地圖分成塊，只篩選范圍覆蓋的塊中的單位，這樣就可以減少很多不必要的篩選。

四叉樹可以有效解決這個問題。

樹的每一層都把地圖劃分四塊，根據地圖尺寸來決定樹的層數，層數越大劃分越細。

當需要對某一范圍的單位篩選時，只需要定位到與范圍相交的樹區域，再對其區域內的對象篩選即可。

四叉樹的實現

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

代碼簡潔，通俗易懂，承讓。

效果圖