QuadTree.h from palisma2d at Krugle

Show QuadTree.h syntax highlighted

#pragma once

#include <vector>
#include <map>
#include "vector.h"
#include "geom.h"

#pragma warning( disable : 4244)

//- temp
#include "../render/IRender.h"


template<class T>
bool SwapAndErase( std::vector< T > &list, T &object )
{
    std::vector< T >::iterator it = list.begin();
    for(; it != list.end(); ++it )
    {
        if ( (*it)->GetID() == object->GetID() )
        {
            list.erase( it );
            return true;
        }
    }
    return false;
    //for (size_t i=0;i < list.size(); ++i )
    //{
    //    if ( list[i] == object )
    //    {
    //        list[i] = list[ list.size()-1 ];
    //        list[list.size()-1 ] = object;
    //        list.pop_back();
    //        return;
    //    }
    //}
}

template<class T>
void AppendVector( std::vector< T >/*std::map<int, T >*/ &list, std::vector< T > &appendMe )
{
    for ( size_t i = 0; i < appendMe.size(); ++i )
    {
        //list[ appendMe[i]->GetID() ] = appendMe[i];
        list.push_back( appendMe[i] );
    }
}

template<class T>
void CloneVector( std::vector< T > &cloneMe, std::vector< T > &list )
{
    list.clear();
    for ( size_t i = 0; i < cloneMe.size(); ++i )
    {
        list.push_back( cloneMe[i] );
    }
}



/**
================================================================================
QuadTree Node
================================================================================
*/
template <class T>
class QuadTreeNode
{
public:
    QuadTreeNode(Rect r)
    {
        for ( int i = 0; i < 4;  ++i )
        {
            m_children[i] = NULL;
        }
        m_bounds.Set( r.x, r.y, r.width, r.height);
    }

    /** Put an item in the QuadTree */
    virtual bool Put(  T& object )
    {
        Rect &objectBounds = object->GetBounds();
        if ( m_bounds.Intersects( objectBounds ) )
        {
            // how many leafs does this fit into
            int counter = 0;
            int nodeToPlaceObjectIn = -1;
            for ( int i=0;i<4;i++)
            {
                if ( m_children[i]->GetBounds().Intersects( objectBounds ) ) {
                    nodeToPlaceObjectIn = i;
                    ++counter;
                }
    
                // if we are fitting in multiple leafs,
                // store in the parent node
                if ( counter >= 2 )
                {
                    m_objects.push_back( object );
                    return true;
                }

            }
            if ( nodeToPlaceObjectIn != -1 && counter < 2 )
            {
                m_children[ nodeToPlaceObjectIn ]->Put( object );
            }
            return true;
        }
        return false;
    }

    /** Pop an item in the QuadTree */
    virtual bool Pop( T& object )
    {
        Rect &objectBounds = object->GetBounds();
        if ( m_bounds.Intersects( objectBounds ) )
        {
            // how many leafs does this fit into
            int counter = 0;
            int nodeToRemoveObjectIn = -1;
            for ( int i=0;i<4;i++)
            {
                if ( m_children[i]->GetBounds().Intersects( objectBounds ) ) {
                    nodeToRemoveObjectIn = i;
                    ++counter;
                }
    
                // if it fits in multiple leafs,
                // this means it SHOULD be stored in
                // this node.
                if ( counter >= 2 )
                {
                    return SwapAndErase<T>( m_objects, object );
                }

            }
            // push work to a leaf node
            if ( nodeToRemoveObjectIn != -1 && counter < 2 )
            {
                return m_children[ nodeToRemoveObjectIn ]->Pop( object );
            }
            //return true;
        }
        return false;
    }

    /** Get all the objects contained in this region */
    virtual void GetObjects( const Rect &region, /*std::map<int, T > &list*/ std::vector< T > &list )
    {
        if ( m_bounds.Intersects( region ) )
        {
            bool NW = m_children[0]->GetBounds().Intersects( region );
            bool NE = m_children[1]->GetBounds().Intersects( region );
            bool SW = m_children[2]->GetBounds().Intersects( region );
            bool SE = m_children[3]->GetBounds().Intersects( region );

            
            // if this region fits in all quadrants
            // we have the highest node 
            if ( NW && NE && SW && SE )
                return AppendVector( list, m_objects );
            else
            {   
                AppendVector( list, m_objects );
                if ( NW )
                    m_children[0]->GetObjects( region, list ) ;
                if ( NE )
                    m_children[1]->GetObjects( region, list ) ;
                if ( SW )
                    m_children[2]->GetObjects( region, list ) ;
                if ( SE )
                    m_children[3]->GetObjects( region, list ) ;
            }
        }
    }

    /** Has this object in this region */
    bool    IsInBounds( const Rect &region ) { return m_bounds.Intersects( region ); };


    /** Get this nodes bounds */
    Rect    &GetBounds() { return m_bounds; };

    /** Number of objects */
    virtual int Size() {
        int j = m_objects.size();
        for ( int i=0;i<4;i++)
        {
            j += m_children[i]->Size();
        }
        return j;
    }

    static enum {
        NORTHWEST = 0,
        NORTHEAST = 1,
        SOUTHWEST = 2,
        SOUTHEAST = 3
    };
    
    // children
    QuadTreeNode*    m_children[4];
        // this nodes bounds 
    Rect    m_bounds;

    virtual void Draw(IRender *r)
    {
        r->SetColor( 0 , 0,  0 );
        r->DrawRect( m_bounds.x, m_bounds.y,m_bounds.width, m_bounds.height ); 
    }
protected:
    // list of objects in this node
    typedef std::vector< T > type_List;
    type_List m_objects;



public:
    virtual ~QuadTreeNode(void)
    {
        for ( int i = 0; i < 4;  ++i )
        {
            if ( m_children[i] ) delete m_children[i];
        }   
    };
};



/**
================================================================================
LeafNode
================================================================================
*/
template <class T>
class QuadTreeLeaf : public QuadTreeNode<T>
{
public:
    QuadTreeLeaf(Rect r) : QuadTreeNode(r) {};

    /** Put an item in the QuadTree */
    bool Put(  T& object )
    {
        Rect &objectBounds = object->GetBounds();
        if ( m_bounds.Intersects( objectBounds ) )
        {
            m_objects.push_back( object );
            return true;
        }
        return false;
    }

    /** Pop an item in the QuadTree */
    bool Pop( T& object )
    {
        Rect &objectBounds = object->GetBounds();
        if ( m_bounds.Intersects( objectBounds ) )
        {
            return SwapAndErase( m_objects, object );
        }
        return false;
    }

    /** Get all the objects contained in this region */
    void GetObjects( const Rect &region, /*std::map<int, T > &list*/ std::vector< T > &list )
    {
        return AppendVector( list, m_objects );
    }

    void Draw(IRender *r)
    {
        r->SetColor( 1 , 0,  0 );
        r->DrawRect( m_bounds.x, m_bounds.y,m_bounds.width, m_bounds.height ); 
    }

    int Size() { return m_objects.size(); };
public:
    virtual ~QuadTreeLeaf(void) {};
};






/**
================================================================================
Data Structure for holding
world data
================================================================================
*/
template <class T>
class QuadTree
{
public:
    QuadTree(float minw, float minh, float maxw, float maxh):  m_maxWidth(maxw), 
                                                                                m_maxHeight(maxw),
                                                                                m_minWidth(minw),
                                                                                m_minHeight(minh)
    {

        m_root = new QuadTreeNode<T>( Rect( 0, 0, m_maxWidth, m_maxHeight ) );
        BuildTree( m_root );

    }
    QuadTree();

    /** Put an item in the QuadTree */
    bool Put( T& object )
    {
        return m_root->Put( object );
    }
    /** Pop off an object */
    bool Pop( T& object )
    {
        return m_root->Pop( object );
    }

    /** Get all the objects contained in this region */
    void GetObjects( const Rect &region, /*std::map<int, T > &list */std::vector< T > &list )
    {
        return m_root->GetObjects( region, list );
    }

    /** Has this object in this region */
    bool    IsInBounds( const Rect &region ) { return m_root->IsInBounds(region); };

    /** Get this nodes bounds */
    Rect    &GetBounds() { return m_root->m_bounds; };

    /** Get the number of elements in the tree */
    int Size() { return m_root->Size(); };

    // TEMP
    void Draw(IRender *r) {
        m_root->Draw(r);
    }
private:
    /** BuildTree */
    template<class T>
    void BuildTree( QuadTreeNode<T>* root ) 
    {
        float h_width  = root->m_bounds.width / 2;
        float h_height = root->m_bounds.height / 2;

        
        if (  h_width < m_minWidth*2 && h_height < m_minHeight*2 ) 
        // build the leafs
        {
            root->m_children[ root->NORTHWEST ] = new QuadTreeLeaf<T>( Rect(root->GetBounds().x, root->GetBounds().y, h_width, h_height )                  );
            root->m_children[ root->NORTHEAST ] = new QuadTreeLeaf<T>( Rect(root->GetBounds().x+h_width, root->GetBounds().y,h_width, h_height )           );
            root->m_children[ root->SOUTHWEST ] = new QuadTreeLeaf<T>( Rect(root->GetBounds().x, root->GetBounds().y+h_height,h_width, h_height)           );
            root->m_children[ root->SOUTHEAST ] = new QuadTreeLeaf<T>( Rect(root->GetBounds().x+h_width, root->GetBounds().y+h_height, h_width, h_height ) );
        }
        else    // build the branches
        {
            root->m_children[ root->NORTHWEST ] = new QuadTreeNode<T>( Rect(root->GetBounds().x, root->GetBounds().y, h_width, h_height )                  );
            root->m_children[ root->NORTHEAST ] = new QuadTreeNode<T>( Rect(root->GetBounds().x+h_width, root->GetBounds().y,h_width, h_height )           );
            root->m_children[ root->SOUTHWEST ] = new QuadTreeNode<T>( Rect(root->GetBounds().x, root->GetBounds().y+h_height,h_width, h_height)           );
            root->m_children[ root->SOUTHEAST ] = new QuadTreeNode<T>( Rect(root->GetBounds().x+h_width, root->GetBounds().y+h_height, h_width, h_height ) );

            BuildTree ( root->m_children[ root->NORTHWEST ] );
            BuildTree ( root->m_children[ root->NORTHEAST ] );
            BuildTree ( root->m_children[ root->SOUTHWEST ] );
            BuildTree ( root->m_children[ root->SOUTHEAST ] );
        }
    }

    //  max size
    float   m_maxWidth,
            m_maxHeight;

    //  min size
    float   m_minWidth,
            m_minHeight;

    // list of objects in this node
    typedef std::vector< T > type_List;
    type_List objects;

    // root
    QuadTreeNode<T>*   m_root;

public:
    virtual ~QuadTree(void) { delete m_root; };
};
See more files for this project here