算法 & 数据结构——四叉树

优雅的实现一颗四叉树

具备功能

• 创建树
• 插入节点
• 删除节点
• 遍历节点

类的定义

template <class Value>
class Tree4 {
    public:
        //  在范围内, 创建一颗指定层次的四叉树
        Tree4(const MATH Rect &, size_t);

        //  判断某一区域是否包含在四叉树内
        template <class Range>
        Tree4 * Contain(const Range &);

        //  根据给定区域, 插入一个节点
        template <class Range>
        bool Insert(const Value *, const Range &);

        //  根据给定区域, 删除一个节点
        template <class Range>
        bool Remove(const Value *, const Range &);

        //  根据给定区域, 遍历匹配节点
        template <class Range>
        bool Match(const Range &, const STD function<bool(Value *)> &);
}

• 通过template <class Value>来实例化特定类型的四叉树.

//  构造一颗范围在 [0, 0, 100, 100], 4 层, 用于存储 C1 对象的四叉树
Tree4<C1> tree41(MATH Rect(0,0,100,100), 4);
//  构造一颗范围在 [0, 0, 100, 100], 4 层, 用于存储 C2 对象的四叉树
Tree4<C2> tree42(MATH Rect(0,0,100,100), 4);

• 通过template <class Range>来支持任意形状区域.

//  插入一个节点, 该节点占用范围 点[0, 0]
tree41.Insert(new C1(), MATH Vec2(0, 0));
//  插入一个节点, 该节点占用范围 矩形(原点[0, 0], 宽高[100, 100])
tree41.Insert(new C1(), MATH Rect(0, 0, 100, 100));
//  插入一个节点, 该节点占用范围 圆形(半径[100], 坐标[0, 0])
tree41.Insert(new C1(), MATH Circular(100, MATH Vec2(0, 0)));

类的实现

#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;
};

左侧 无四叉树，右侧 四叉树

DEMO下载