什么是四叉树?
如图,设想,
红框表示地图,星星表示单位,黄框表现范围,
要处理地图中范围内的单位,最直接的做法是筛选所有单位。
通过上图可以看到一个显而易见的问题,大部分单位都不需要被处理。
如果把地图分成块,只筛选范围覆盖的块中的单位,这样就可以减少很多不必要的筛选。
四叉树可以有效解决这个问题。
树的每一层都把地图划分四块,根据地图尺寸来决定树的层数,层数越大划分越细。
当需要对某一范围的单位筛选时,只需要定位到与范围相交的树区域,再对其区域内的对象筛选即可。
四叉树的实现
#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++实现四叉树效果(附源码下载),希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对小牛知识库网站的支持!
本文向大家介绍jQuery打字效果实现方法(附demo源码下载),包括了jQuery打字效果实现方法(附demo源码下载)的使用技巧和注意事项,需要的朋友参考一下 本文实例讲述了jQuery打字效果实现方法。分享给大家供大家参考,具体如下: 运行效果截图如下: 点击此处查看在线演示效果。 1.前台页面代码: 2.jticker_split.js脚本代码: 完整实例代码点击此处本站下载。 希望本文所
本文向大家介绍jQuery实现的下雪动画效果示例【附源码下载】,包括了jQuery实现的下雪动画效果示例【附源码下载】的使用技巧和注意事项,需要的朋友参考一下 本文实例讲述了jQuery实现的下雪动画效果。分享给大家供大家参考,具体如下: html部分: jquery.snow.js: 不需要css样式 主要用到:setInterval-setInterval() 方法可按照指定的周期(以毫秒计)
本文向大家介绍php+jQuery+Ajax实现点赞效果的方法(附源码下载),包括了php+jQuery+Ajax实现点赞效果的方法(附源码下载)的使用技巧和注意事项,需要的朋友参考一下 本文实例讲述了php+jQuery+Ajax实现点赞效果的方法。分享给大家供大家参考,具体如下: 数据库设计 先准备两张表,pic表保存的是图片信息,包括图片对应的名称、路径以及图片“赞”总数,pic_ip则记录
四叉树是一个二维空间递归细分。它使用了平分划分实现,将每一个块平分成了四个同等大小的方块。每个点存在于一个唯一的节点中;如果同一位置包含多个点,那么这多个点中的其中一些点将存储于内部节点,而非叶子结点。四叉树可用于加速各种空间操作,例如计算正多边形的体积的Barnes-Hut近似算法或者冲突检验。 d3.geom.quadtree() 创建一个新的四叉树工厂使用默认的x访问器,y访问器及范围。返回
本文向大家介绍jQuery实现的表头固定效果实例【附完整demo源码下载】,包括了jQuery实现的表头固定效果实例【附完整demo源码下载】的使用技巧和注意事项,需要的朋友参考一下 本文实例讲述了jQuery实现的表头固定效果。分享给大家供大家参考,具体如下: 运行效果截图如下: 具体实现步骤如下: 一、新建一js文件jQuery_FixedTableHead.js 内容如下: 二、Html实例
本文向大家介绍jQuery插件FusionWidgets实现的Bulb图效果示例【附demo源码下载】,包括了jQuery插件FusionWidgets实现的Bulb图效果示例【附demo源码下载】的使用技巧和注意事项,需要的朋友参考一下 本文实例讲述了jQuery插件FusionWidgets实现的Bulb图效果。分享给大家供大家参考,具体如下: 1、数据源提供 Bulb.xml: 2、inde
本文向大家介绍利用jQuery实现滑动开关按钮效果(附demo源码下载),包括了利用jQuery实现滑动开关按钮效果(附demo源码下载)的使用技巧和注意事项,需要的朋友参考一下 首先来看看要实现的效果图: HTML结构如下: 初始化函数: 完整demo: HTML: JS: 实例下载:点击此处 总结 以上就是这篇文章的全部内容了,希望本文的内容对大家的学习或者工作能带来一定的帮助,如果有疑问大家
本文向大家介绍Android编程实现简易弹幕效果示例【附demo源码下载】,包括了Android编程实现简易弹幕效果示例【附demo源码下载】的使用技巧和注意事项,需要的朋友参考一下 本文实例讲述了Android编程实现简易弹幕效果。分享给大家供大家参考,具体如下: 首先上效果图,类似于360检测到骚扰电话页面: 布局很简单,上面是一个RelativeLayout,下面一个Button. 功能: