一直发现很多人重复的在写quadtree,提供一个我写的比较简

gosix

// 希望能够给大家带来便利
// 以下为声明部分


/**
* 节点特性
*/
template<class T>
struct PL_NodeTrait
{
        // 释放节点对象
        int release(T* pNode)
        {
                return 0;
        }
};



/**
* 节点筛选器
*/
template<class T>
struct PL_NodeFilter
{
        int operator ()(const T& V1)
        {
                return 0;
        }
};

/**
* 节点管理方法: 4叉分割树
*/
template<
        class Node,
        class ValueType = float,
        class Trait = PL_NodeTrait<Node>,
        template <class> class Allocator = std::allocator
>
class PL_NodeManagerQuadTree
{
protected:
        int _count_node;                                                                                // 节点个数统计

        // 子管理节点
        typedef PL_NodeManagerQuadTree<Node, ValueType> ChildsType;
        Allocator<ChildsType> _childs_allocator;
        ChildsType* _childs;                                                                        // 子管理节点

        // 子节点
        typedef std::list<Node*> NodesType;
        NodesType* _nodes;

        ValueType _minx, _miny, _maxx, _maxy;
private:
        inline void _zero(void)
        {
                _count_node = 0;
                _childs = 0;
                _nodes = 0;
        }
        inline void _filter(Node* pNode, std::list<Node*>* pNodes, PL_NodeFilter<Node>** ppFilter, size_t nNumFilter)const
        {
                for(size_t i=0; i<nNumFilter; ++i, ++ppFilter, ++pNodes)
                {
                        if( (*(*ppFilter))( *pNode ) )
                        {
                                pNodes->push_back( pNode );
                        }
                }
        }
public:
        // 创建树
        void create(ValueType MinX, ValueType MinY, ValueType MaxX, ValueType MaxY, ValueType CellX, ValueType CellY)
        {
                clear();
                _nodes = new NodesType();
                _minx = MinX;
                _miny = MinY;
                _maxx = MaxX;
                _maxy = MaxY;

                // 判断是否需要创建子节点
                ValueType vx = (MaxX - MinX)/2;
                ValueType vy = (MaxY - MinY)/2;
                if( CellX <= vx && CellY <= vy )
                {
                        // 增加子管理节点
                        _childs = _childs_allocator.allocate( 4 );
                        _childs[0]._zero();
                        _childs[0].create( MinX, MinY, MinX + vx, MinY + vy, CellX, CellY );
                        _childs[1]._zero();
                        _childs[1].create( MinX + vx, MinY, MinX + vx + vx, MinY + vy, CellX, CellY );
                        _childs[2]._zero();
                        _childs[2].create( MinX, MinY + vy, MinX + vx, MinY + vy + vy, CellX, CellY );
                        _childs[3]._zero();
                        _childs[3].create( MinX + vx, MinY + vy, MinX + vx + vx, MinY + vy + vy, CellX, CellY );
                }
        }
        // 清除所有对象
        void clear(void)
        {
                if( _childs )
                {
                        _childs[0].clear();
                        _childs[1].clear();
                        _childs[2].clear();
                        _childs[3].clear();
                        _childs_allocator.deallocate( _childs, 4 );
                }
                if( _nodes )
                {
                        for(NodesType::iterator iter=_nodes->begin(); iter!=_nodes->end(); ++iter)
                        {
                                Trait().release( *iter );
                                //(*iter)->release();
                        }
                        delete _nodes;
                }

                _zero();
        }
        // 增加一个节点对象
        bool add_node(Node* pNode, ValueType X, ValueType Y)
        {
                // 是否能增加到子节点
                if( _childs )
                {
                        if( _childs[0].add_node( pNode, X, Y ) ||
                                _childs[1].add_node( pNode, X, Y ) ||
                                _childs[2].add_node( pNode, X, Y ) ||
                                _childs[3].add_node( pNode, X, Y ) )
                        {
                                ++ _count_node;
                                return true;
                        }
                }

                // 增加到当前位置
                if( _nodes && X >= _minx && X < _maxx && Y >= _miny && Y < _maxy )
                {
                        ++ _count_node;
                        _nodes->push_back( pNode );
                        return true;
                }

                return false;
        }
        // 删除一个节点
        bool del_node(Node* pNode, bool bAutoRelease=false)
        {
                if( !_count_node )
                        return false;

                // 当前节点查找
                if( _nodes )
                {
                        for(NodesType::iterator iter=_nodes->begin(); iter!=_nodes->end(); ++iter)
                        {
                                if( pNode == (*iter) )
                                {
                                        if( bAutoRelease )
                                                Trait().release( pNode );
                                        _nodes->erase( iter );
                                        -- _count_node;
                                        return true;
                                }
                        }
                }

                // 子节点查找
                if( _childs )
                {
                        if( _childs[0].del_node( pNode ) ||
                                _childs[1].del_node( pNode ) ||
                                _childs[2].del_node( pNode ) ||
                                _childs[3].del_node( pNode ) )
                        {
                                -- _count_node;
                                return true;
                        }
                }

                return false;
        }
        // 得到节点
        void get_nodes(std::list<Node*>* pNodes, PL_NodeFilter<Node>** ppFilter, size_t nNumFilter)const
        {
                // 当前节点查找
                if( _nodes )
                {
                        for(NodesType::iterator iter=_nodes->begin(); iter!=_nodes->end(); ++iter)
                        {
                                _filter( *iter, pNodes, ppFilter, nNumFilter );
                        }
                }

                // 子节点查找
                if( _childs )
                {
                        _childs[0].get_nodes( pNodes, ppFilter, nNumFilter );
                        _childs[1].get_nodes( pNodes, ppFilter, nNumFilter );
                        _childs[2].get_nodes( pNodes, ppFilter, nNumFilter );
                        _childs[3].get_nodes( pNodes, ppFilter, nNumFilter );
                }
        }

        PL_NodeManagerQuadTree()
        {
                _zero();
        }
        ~PL_NodeManagerQuadTree()
        {
                clear();
        }
};

gosix

// 测试部分
/**
* 场景节点
*/
class CSceneNode
{
public:
        int _value;
public:
        CSceneNode(int value=0):_value(value)
        {
        };
};




/**
* 场景节点特性
*/
template<>
struct PL_NodeTrait<CSceneNode>
{
        // 释放节点对象
        int release(CSceneNode* pNode)
        {
                delete pNode;
                return 0;
        }
};


// 过滤器
template<>
struct PL_NodeFilter<CSceneNode>
{
        virtual int operator ()(const CSceneNode& V1)
        {
                return ( V1._value > 20.0f );
        }
};


// 过滤器
struct PL_NodeFilter2:public PL_NodeFilter<CSceneNode>
{
        virtual int operator ()(const CSceneNode& V1)
        {
                return ( V1._value > 100.0f );
        }
};



// 场景管理器
typedef PL_NodeManagerQuadTree<CSceneNode> CSceneManager;

// test
        {
                float ftree[] = { 0.0f, 0.0f, 0.0f, 10.0f, 10.0f, 10.0f, 5.0f, 5.0f, 0.0f };
                float fpos[] = { 0.0f, 1.0f, 2.0f, 3.0f, 4.0f, 5.0f, 6.0f, 7.0f, 8.0f, 9.0f };
                float* ppos = fpos;

                CSceneManager SceneMan;
                SceneMan.create( 0.0f, 0.0f, 10.0f, 10.0f, 5.0f, 5.0f );

                // 增加节点
                SceneMan.add_node( new CSceneNode(rand()&0xff), *(++ppos), *(++ppos) );
                SceneMan.add_node( new CSceneNode(rand()&0xff), *(++ppos), *(++ppos) );
                SceneMan.add_node( new CSceneNode(rand()&0xff), *(++ppos), *(++ppos) );

                CSceneNode* pNode = new CSceneNode(rand()&0xff);
                SceneMan.add_node( pNode, *(++ppos), *(++ppos) );
                SceneMan.del_node( pNode );

                // 查找
                std::list<CSceneNode*> Nodes[2];
                PL_NodeFilter<CSceneNode> Filter1;
                PL_NodeFilter2 Filter2;
                PL_NodeFilter<CSceneNode>* pFilters[2];
                pFilters[0] = &Filter1;
                pFilters[1] = &Filter2;

                SceneMan.get_nodes( Nodes, pFilters, 2 );

                SceneMan.clear();
        }

tonykee

本来也不算太复杂，这么重要的东西当然要自己写了。
饭还得自己一口口的吃呢。

不过共享是好，只要是值得借鉴的东西。多多共享

顶一个！

superoil

顶!
感谢楼主的无私共享精神.

gosix

谢谢上面2位,但是有些话还是要说的
1.中国的软件开发技术为什么发展缓慢,和大家都在重复做同一件事情有关吧
2.原理虽然不是很复杂,但是要写的很通用就不是每个刚开始写就能轻松写出来的哦,呵呵(我还是比较提倡使用现成的,人的精力还是很有限的)

hwbnet

请问：这是干嘛用的？

tonykee

如果连这样基本的东西也要取用现成的，那基本上就不用写什么复杂的东西了。
并不是任何东西都可以拿来就用的。

特别是核心的东西，需要加入太多自己的元素，无法做成通用化也就没法直接拿来用

很多东西能拿来用的基本上只是一个思路
当然不是所有的东西都一定要自己去写，视情况而定吧。

总之：LZ的精神还是很值得提倡的。

hengle_lee

共享时代了，代码的重用，不是叫多少多少次的重写！！

大风歌

感谢你的无私～～

tonykee

上一个层次的说，真正能重用的是思想，而不仅仅只是代码