C++实现四叉树效果的方法-创新互联
这篇文章主要介绍了C++实现四叉树效果的方法,具有一定借鉴价值,感兴趣的朋友可以参考下,希望大家阅读完这篇文章之后大有收获,下面让小编带着大家一起了解一下。
创新互联建站服务项目包括噶尔网站建设、噶尔网站制作、噶尔网页制作以及噶尔网络营销策划等。多年来,我们专注于互联网行业,利用自身积累的技术优势、行业经验、深度合作伙伴关系等,向广大中小型企业、政府机构等提供互联网行业的解决方案,噶尔网站推广取得了明显的社会效益与经济效益。目前,我们服务的客户以成都为中心已经辐射到噶尔省份的部分城市,未来相信会继续扩大服务区域并继续获得客户的支持与信任!什么是四叉树?
如图,设想,
红框表示地图,星星表示单位,黄框表现范围,
要处理地图中范围内的单位,最直接的做法是筛选所有单位。
通过上图可以看到一个显而易见的问题,大部分单位都不需要被处理。
如果把地图分成块,只筛选范围覆盖的块中的单位,这样就可以减少很多不必要的筛选。
四叉树可以有效解决这个问题。
树的每一层都把地图划分四块,根据地图尺寸来决定树的层数,层数越大划分越细。
当需要对某一范围的单位筛选时,只需要定位到与范围相交的树区域,再对其区域内的对象筛选即可。
四叉树的实现
#pragma once #include "base.h" #include "math.h" templateclass 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 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 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 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 bool Match(const Range & range, const STD function & func) { if (!MATH intersect(_rect, range)) { return true; } for (auto & value : _values) { if (!func(const_cast (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 Tree4 * Contain(const Range & range) { Tree4 * 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 _values; };
代码简洁,通俗易懂,承让。
效果图
左侧全图遍历,右侧四叉树遍历,通过左上角的开销时间,差异很明显。
感谢你能够认真阅读完这篇文章,希望小编分享的“C++实现四叉树效果的方法”这篇文章对大家有帮助,同时也希望大家多多支持创新互联建站,关注创新互联网站建设公司行业资讯频道,更多相关知识等着你来学习!
另外有需要云服务器可以了解下创新互联建站www.cdcxhl.com,海内外云服务器15元起步,三天无理由+7*72小时售后在线,公司持有idc许可证,提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案,具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势,专为企业上云打造定制,能够满足用户丰富、多元化的应用场景需求。
网页名称:C++实现四叉树效果的方法-创新互联
文章路径:http://scyanting.com/article/dcsogs.html