这篇文章主要介绍了C++实现四叉树效果的方法，具有一定借鉴价值，感兴趣的朋友可以参考下，希望大家阅读完这篇文章之后大有收获，下面让小编带着大家一起了解一下。
重庆网站制作公司哪家好，找成都创新互联！从网页设计、网站建设、微信开发、APP开发、成都响应式网站建设公司等网站项目制作，到程序开发，运营维护。成都创新互联公司2013年成立到现在10年的时间，我们拥有了丰富的建站经验和运维经验，来保证我们的工作的顺利进行。专注于网站建设就选成都创新互联。
什么是四叉树？
如图，设想，
红框表示地图，星星表示单位，黄框表现范围，
要处理地图中范围内的单位，最直接的做法是筛选所有单位。
通过上图可以看到一个显而易见的问题，大部分单位都不需要被处理。
如果把地图分成块，只筛选范围覆盖的块中的单位，这样就可以减少很多不必要的筛选。
四叉树可以有效解决这个问题。
树的每一层都把地图划分四块，根据地图尺寸来决定树的层数，层数越大划分越细。
当需要对某一范围的单位筛选时，只需要定位到与范围相交的树区域，再对其区域内的对象筛选即可。
四叉树的实现
#pragma once
#include "base.h"
#include "math.h"
template
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 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++实现四叉树效果的方法”这篇文章对大家有帮助，同时也希望大家多多支持创新互联，关注创新互联行业资讯频道，更多相关知识等着你来学习!
新闻名称：C++实现四叉树效果的方法
网站URL：
http://jkwzsj.com/article/gidcci.html
