什么是四叉樹？
如圖，設(shè)想，
紅框表示地圖，星星表示單位，黃框表現(xiàn)范圍，
要處理地圖中范圍內(nèi)的單位，最直接的做法是篩選所有單位。
通過上圖可以看到一個顯而易見的問題，大部分單位都不需要被處理。
如果把地圖分成塊，只篩選范圍覆蓋的塊中的單位，這樣就可以減少很多不必要的篩選。
四叉樹可以有效解決這個問題。
樹的每一層都把地圖劃分四塊，根據(jù)地圖尺寸來決定樹的層數(shù)，層數(shù)越大劃分越細。
當需要對某一范圍的單位篩選時，只需要定位到與范圍相交的樹區(qū)域，再對其區(qū)域內(nèi)的對象篩選即可。
四叉樹的實現(xiàn)
1 #pragma once 2 3 #include "base.h" 4 #include "math.h" 5 6 template <class Value> 7 class Tree4 { 8 private: 9 struct Pointer { 10 Tree4 *LT, *RT, *LB, *RB; 11 Pointer() :LT(nullptr), RT(nullptr), LB(nullptr), RB(nullptr) 12 { } 13 ~Pointer() 14 { 15 SAFE_DELETE(LT); 16 SAFE_DELETE(RT); 17 SAFE_DELETE(LB); 18 SAFE_DELETE(RB); 19 } 20 }; 21 22 public: 23 Tree4(const MATH Rect &rect, size_t n = 0): _rect(rect) 24 { 25 STD queue<Tree4 *> queue; 26 queue.push(this); 27 for (auto c = 1; n != 0; --n, c *= 4) 28 { 29 for (auto i = 0; i != c; ++i) 30 { 31 auto tree = queue.front(); 32 tree->Root(); 33 queue.pop(); 34 queue.push(tree->_pointer.LT); 35 queue.push(tree->_pointer.RT); 36 queue.push(tree->_pointer.LB); 37 queue.push(tree->_pointer.RB); 38 } 39 } 40 } 41 42 template <class Range> 43 bool Insert(const Value * value, const Range & range) 44 { 45 auto tree = Contain(range); 46 auto ret = nullptr != tree; 47 if (ret) { tree->_values.emplace_back(value); } 48 return ret; 49 } 50 51 template <class Range> 52 bool Remove(const Value * value, const Range & range) 53 { 54 auto tree = Contain(range); 55 auto ret = nullptr != tree; 56 if (ret) { ret = tree->Remove(value); } 57 return ret; 58 } 59 60 template <class Range> 61 bool Match(const Range & range, const STD function<bool(Value *)> & func) 62 { 63 if (!MATH intersect(_rect, range)) 64 { 65 return true; 66 } 67 68 for (auto & value : _values) 69 { 70 if (!func(const_cast<Value *>(value))) 71 { 72 return false; 73 } 74 } 75 76 auto ret = true; 77 if (!IsLeaf()) 78 { 79 if (ret) ret = _pointer.LT->Match(range, func); 80 if (ret) ret = _pointer.RT->Match(range, func); 81 if (ret) ret = _pointer.LB->Match(range, func); 82 if (ret) ret = _pointer.RB->Match(range, func); 83 } 84 return ret; 85 } 86 87 template <class Range> 88 Tree4 * Contain(const Range & range) 89 { 90 Tree4<Value> * ret = nullptr; 91 if (MATH contain(STD cref(_rect), range)) 92 { 93 if (!IsLeaf()) 94 { 95 if (nullptr == ret) ret = _pointer.LT->Contain(range); 96 if (nullptr == ret) ret = _pointer.RT->Contain(range); 97 if (nullptr == ret) ret = _pointer.LB->Contain(range); 98 if (nullptr == ret) ret = _pointer.RB->Contain(range); 99 }100 if (nullptr == ret)101 ret = this;102 }103 return ret;104 }105 106 private:107 void Root()108 {109 _pointer.LT = new Tree4(MATH Rect(_rect.x, _rect.y, _rect.w * 0.5f, _rect.h * 0.5f));110 _pointer.LB = new Tree4(MATH Rect(_rect.x, _rect.y + _rect.h * 0.5f, _rect.w * 0.5f, _rect.h * 0.5f));111 _pointer.RT = new Tree4(MATH Rect(_rect.x + _rect.w * 0.5f, _rect.y, _rect.w * 0.5f, _rect.h * 0.5f));112 _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));113 }114 115 bool Remove(const Value * value)116 {117 auto iter = STD find(_values.begin(), _values.end(), value);118 auto ret = _values.end() != iter;119 if (ret) { _values.erase(iter); }120 return ret;121 }122 123 bool IsLeaf()124 {125 return nullptr == _pointer.LT126 || nullptr == _pointer.RT127 || nullptr == _pointer.LB128 || nullptr == _pointer.RB;129 }130 131 Tree4(const Tree4 &) = delete;132 Tree4(Tree4 &&) = delete;133 Tree4 &operator=(const Tree4 &) = delete;134 Tree4 &operator=(Tree4 &&) = delete;135 136 private:137 MATH Rect _rect;138 Pointer _pointer;139 STD list<const Value *> _values;140 };
代碼簡潔，通俗易懂，承讓。
效果圖
左側(cè)全圖遍歷，右側(cè)四叉樹遍歷，通過左上角的開銷時間，差異很明顯。
延伸閱讀
- 友誼之樹上將垂下豐碩的果實 2022-07-13
- 沉舟側(cè)畔千帆過，病樹前頭萬木春 】 2022-07-13
- 友誼之樹上將垂下豐碩的果實 2022-02-07
- 沉舟側(cè)畔千帆過，病樹前頭萬木春 2022-02-07
- 突破迷茫，實現(xiàn)自我 ——王*鑫 2020-06-11
- 種一棵樹，最好的時間是十年前，其次是現(xiàn)在 2019-12-05
- 黑暗四劍客日志——劉*行 2019-04-13
- 在萬碼學堂實現(xiàn)了我的人生夢想 2017-11-29
- Swift實現(xiàn)JSON轉(zhuǎn)Model - HandyJSON使用講解 2017-07-26
- Android高仿qq及微信底部菜單的幾種實現(xiàn)方式 2017-07-26
友誼之樹上將垂下豐碩的果實