您好,登錄后才能下訂單哦!
這篇文章主要介紹了C++實(shí)現(xiàn)四叉樹效果的方法,具有一定借鑒價(jià)值,感興趣的朋友可以參考下,希望大家閱讀完這篇文章之后大有收獲,下面讓小編帶著大家一起了解一下。
什么是四叉樹?
如圖,設(shè)想,
紅框表示地圖,星星表示單位,黃框表現(xiàn)范圍,
要處理地圖中范圍內(nèi)的單位,最直接的做法是篩選所有單位。
通過上圖可以看到一個(gè)顯而易見的問題,大部分單位都不需要被處理。
如果把地圖分成塊,只篩選范圍覆蓋的塊中的單位,這樣就可以減少很多不必要的篩選。
四叉樹可以有效解決這個(gè)問題。
樹的每一層都把地圖劃分四塊,根據(jù)地圖尺寸來決定樹的層數(shù),層數(shù)越大劃分越細(xì)。
當(dāng)需要對某一范圍的單位篩選時(shí),只需要定位到與范圍相交的樹區(qū)域,再對其區(qū)域內(nèi)的對象篩選即可。
四叉樹的實(shí)現(xiàn)
#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è)全圖遍歷,右側(cè)四叉樹遍歷,通過左上角的開銷時(shí)間,差異很明顯。
感謝你能夠認(rèn)真閱讀完這篇文章,希望小編分享的“C++實(shí)現(xiàn)四叉樹效果的方法”這篇文章對大家有幫助,同時(shí)也希望大家多多支持億速云,關(guān)注億速云行業(yè)資訊頻道,更多相關(guān)知識等著你來學(xué)習(xí)!
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場,如果涉及侵權(quán)請聯(lián)系站長郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。