gzSpatial.h

Go to the documentation of this file.

// *****************************************************************************
// File         : gzSpatial.h
// Module       : gzSpatial
// Description  : Class definition of spatial data storage templates
// Author       : Anders Modén      
// Product      : GizmoBase 2.1.1
//      
// Copyright © 2003- Saab Training Systems AB, Sweden
//          
// NOTE:    GizmoBase is a platform abstraction utility layer for C++. It contains 
//          design patterns and C++ solutions for the advanced programmer.
//
//
// Revision History...                          
//                                  
// Who  Date    Description                     
//                                  
// AMO  050222  Created file 
//
// ******************************************************************************

#ifndef __GZ_SPATIAL_H__
#define __GZ_SPATIAL_H__

#include "gzBasicTypes.h"
#include "gzXYZ.h"

// Forward decl
template <class T> class gzSpatialDataIterator;

//******************************************************************************
// Class    : gzSpatialData
//                                  
// Purpose  : Template for spatial located data
//                                  
// Notes    : - 
//                                  
// Revision History...                          
//                                  
// Who  Date    Description                     
//                                  
// AMO  050222  Created 
//                                  
//******************************************************************************
template <class T> class gzSpatialData
{
public:

    gzSpatialData(const gzDoubleXYZ& position_1=gzDoubleXYZ(0,0,0) , const gzDoubleXYZ& position_2=gzDoubleXYZ(1,1,1),gzULong divisions=3,gzULong splitItems=0);

    ~gzSpatialData();

    gzVoid      insert(const gzDoubleXYZ &position,const T &data,const gzDoubleXYZ &delta=gzDoubleXYZ(0,0,0));

    gzULong     entries();

    gzVoid      clear();

private:

    friend class gzSpatialDataIterator<T>;

    class _item;

    class _holder
    {
    public:

        _holder(const gzDoubleXYZ &min , const gzDoubleXYZ &max,_holder *parent,gzULong index):m_min(min),m_max(max),m_parent(parent),m_subspace(NULL),m_index(index)
        {
            m_itemList.reuseLinks(TRUE);
        }

        ~_holder()
        {
            if(m_subspace)
            {
                for(gzULong i=0;i<m_size;i++)
                    if(m_subspace[i])
                        delete m_subspace[i];

                delete [] m_subspace;
            }

            m_itemList.clearAndDestroy();
        }

        gzVoid createSubspace(gzULong divisions)
        {
            if(!m_subspace)
            {
                m_size=divisions*divisions*divisions;
                m_firstIndex=m_size;

                m_subspace=new _holder *[m_size];
                memset(m_subspace,0,m_size*sizeof(_holder *));
            }
        }

        gzList<_item>       m_itemList;
        _holder **          m_subspace;
        _holder *           m_parent;
        gzULong             m_index;
        gzDoubleXYZ         m_max;
        gzDoubleXYZ         m_min;
        gzULong             m_size;
        gzULong             m_firstIndex;
    };

    class _item
    {
    public:

        T                   m_data;
        gzDoubleXYZ         m_position;
        gzDoubleXYZ         m_delta;
    };

    _holder *       m_space;

    gzDoubleXYZ         m_minPosition;

    gzDoubleXYZ         m_stepping;

    gzULong         m_divisions;

    gzULong         m_splitItems;

    gzULong         m_entries;
};

template <class T> inline gzSpatialData<T>::gzSpatialData(const gzDoubleXYZ& position_1 , const gzDoubleXYZ& position_2,gzULong divisions,gzULong splitItems)
{
    m_minPosition=gzDoubleXYZ(gzMin(position_1.x,position_2.x),gzMin(position_1.y,position_2.y),gzMin(position_1.z,position_2.z));

    m_stepping=(gzDoubleXYZ(gzMax(position_1.x,position_2.x),gzMax(position_1.y,position_2.y),gzMax(position_1.z,position_2.z))-m_minPosition)/divisions;

    if(!m_stepping.x)
        m_stepping.x=1;

    if(!m_stepping.y)
        m_stepping.y=1;

    if(!m_stepping.z)
        m_stepping.z=1;

    m_divisions=divisions;

    m_splitItems=splitItems;

    m_space=NULL;

    m_entries=0;
}

template <class T> inline gzSpatialData<T>::~gzSpatialData()
{
    if(m_space)
        delete m_space;
}

template <class T> inline gzVoid gzSpatialData<T>::clear()
{
    if(m_space)
        delete m_space;

    m_space=NULL;
    m_entries=0;
}

template <class T> inline gzULong gzSpatialData<T>::entries()
{
    return m_entries;
}

template <class T> inline gzVoid gzSpatialData<T>::insert(const gzDoubleXYZ &position,const T &data,const gzDoubleXYZ &delta)
{
    if(     ((position.x+delta.x)>=(m_minPosition.x+m_divisions*m_stepping.x))  // We are located outside max extent. Need to rebuild tree
        ||  ((position.y+delta.y)>=(m_minPosition.y+m_divisions*m_stepping.y))
        ||  ((position.z+delta.z)>=(m_minPosition.z+m_divisions*m_stepping.z)) )
    {
        _holder *old=m_space;
        gzULong index=(m_divisions-1)/2;

        gzULong mixIndex=index*(m_divisions*m_divisions)+index*m_divisions+index;
        

        m_stepping=m_stepping*m_divisions;
        m_minPosition=m_minPosition-m_stepping*index;

        m_space=new _holder(m_minPosition,m_minPosition+m_stepping*m_divisions,NULL,0);
        
        if(old)
        {
            m_space->createSubspace(m_divisions);
            m_space->m_subspace[mixIndex]=old;
            m_space->m_firstIndex=mixIndex;
            old->m_parent=m_space;
            old->m_index=mixIndex;
        }

        insert(position,data,delta);
        return;
    }

    if(     ((position.x-delta.x)<m_minPosition.x)
        ||  ((position.y-delta.y)<m_minPosition.y)
        ||  ((position.z-delta.z)<m_minPosition.z)  )
    {
        _holder *old=m_space;
        gzULong index=m_divisions/2;
        gzULong mixIndex=index*(m_divisions*m_divisions)+index*m_divisions+index;
        
        m_stepping=m_stepping*m_divisions;
        m_minPosition=m_minPosition-m_stepping*index;

        m_space=new _holder(m_minPosition,m_minPosition+m_stepping*m_divisions,NULL,0);

        if(old)
        {
            m_space->createSubspace(m_divisions);
            m_space->m_subspace[mixIndex]=old;
            m_space->m_firstIndex=mixIndex;
            old->m_parent=m_space;
            old->m_index=mixIndex;
        }
    
        insert(position,data,delta);
        return;
    }

    gzULong index_x=0,index_y=0,index_z=0;

    _holder *holder=m_space,*parent=NULL;

    gzDoubleXYZ stepping=m_stepping;
    gzDoubleXYZ minPosition=m_minPosition;

    while(holder)
    {
        index_x=(gzULong)((position.x-delta.x-minPosition.x)/stepping.x);
        index_y=(gzULong)((position.y-delta.y-minPosition.y)/stepping.y);
        index_z=(gzULong)((position.z-delta.z-minPosition.z)/stepping.z);

        if( ((gzULong)((position.x+delta.x-minPosition.x)/stepping.x))!=index_x)
            break;

        if( ((gzULong)((position.y+delta.y-minPosition.y)/stepping.y))!=index_y)
            break;

        if( ((gzULong)((position.z+delta.z-minPosition.z)/stepping.z))!=index_z)
            break;

        if(holder->m_itemList.entries()>=m_splitItems)  // go to subchild
        {
            minPosition.x=minPosition.x+index_x*stepping.x;
            minPosition.y=minPosition.y+index_y*stepping.y;
            minPosition.z=minPosition.z+index_z*stepping.z;

            stepping=stepping/m_divisions;

            if(!holder->m_subspace)
                holder->createSubspace(m_divisions);


            parent=holder;
            holder=holder->m_subspace[index_x*(m_divisions*m_divisions)+index_y*m_divisions+index_z];

            continue;
        }
        else
            break;
    }

    if(!holder)
    {
        gzULong mixIndex=index_x*(m_divisions*m_divisions)+index_y*m_divisions+index_z;

        holder=new _holder(minPosition,minPosition+stepping*m_divisions,parent,mixIndex);

        if(!parent)
            m_space=holder;
        else
        {
            if(parent->m_firstIndex>mixIndex)
                parent->m_firstIndex=mixIndex;
            parent->m_subspace[mixIndex]=holder;
        }
    }

    // Insert item

    _item *item=new _item;

    holder->m_itemList.insert(item);

    item->m_data=data;
    item->m_position=position;
    item->m_delta=delta;

    ++m_entries;
}


//******************************************************************************
// Class    : gzSpatialDataIterator
//                                  
// Purpose  : Box iterator for spatial located data
//                                  
// Notes    : - 
//                                  
// Revision History...                          
//                                  
// Who  Date    Description                     
//                                  
// AMO  050222  Created 
//                                  
//******************************************************************************
template <class T> class gzSpatialDataIterator
{
public:

    gzSpatialDataIterator(gzSpatialData<T> &owner,const gzDoubleXYZ& position=gzDoubleXYZ(0,0,0) , const gzDoubleXYZ& delta=gzDoubleXYZ(DBL_MAX,DBL_MAX,DBL_MAX));

    ~gzSpatialDataIterator();

    gzBool operator()(T &data,gzDoubleXYZ *pos=NULL,gzDoubleXYZ *delta=NULL);

    gzVoid remove();

private:

    gzSpatialData<T> &          m_owner;

    const gzDoubleXYZ           m_position;
    const gzDoubleXYZ           m_delta;
    const gzDouble              dx_p,dy_p,dz_p,dx_m,dy_m,dz_m;
    
    typename gzSpatialData<T>::_holder *                m_currentHolder;
    gzULong                                             m_maxIndex;
    gzListIterator<typename gzSpatialData<T>::_item>    m_iterator;
    gzBool                                              m_validIterator;
};

template <class T> inline gzSpatialDataIterator<T>::gzSpatialDataIterator(gzSpatialData<T> &owner,const gzDoubleXYZ& position , const gzDoubleXYZ& delta)
        :m_owner(owner),
        m_position(position),
        m_delta(delta),
        m_iterator(NULL),
        dx_m(position.x-delta.x),
        dy_m(position.y-delta.y),
        dz_m(position.z-delta.z),
        dx_p(position.x+delta.x),
        dy_p(position.y+delta.y),
        dz_p(position.z+delta.z)
{
    m_maxIndex=m_owner.m_divisions*m_owner.m_divisions*m_owner.m_divisions;
    m_currentHolder=m_owner.m_space;
    m_validIterator=FALSE;
}

template <class T> inline gzSpatialDataIterator<T>::~gzSpatialDataIterator()
{
}

template <class T> inline gzVoid gzSpatialDataIterator<T>::remove()
{
    if(m_validIterator)
    {
        delete m_iterator.remove();
        --m_owner.m_entries;
    }
}

template <class T> inline gzBool gzSpatialDataIterator<T>::operator()(T &data,gzDoubleXYZ *pos,gzDoubleXYZ *delta)
{
    if(!m_currentHolder)        // Assume a valid holder
        return FALSE;

    gzBool isValid;

    typename gzSpatialData<T>::_holder *parent;
    typename gzSpatialData<T>::_item *item;

    gzULong offset;

    while(TRUE)
    {
        // Check to see if holder is valid first time

        if(!m_validIterator)
        {
            isValid=TRUE;

            if( m_currentHolder->m_max.x < dx_m ) // left of us
                isValid=FALSE;
            else if( m_currentHolder->m_min.x > dx_p ) // right of us
                isValid=FALSE;
            else if( m_currentHolder->m_max.y < dy_m) // under us
                isValid=FALSE;
            else if( m_currentHolder->m_min.y > dy_p) // top of us
                isValid=FALSE;
            else if( m_currentHolder->m_max.z < dz_m) 
                isValid=FALSE;
            else if( m_currentHolder->m_min.z > dz_p) 
                isValid=FALSE;

            if(!isValid)
            {
                // Go to next neighbour

                while(TRUE)
                {
                    if(!m_currentHolder->m_parent)  // check if we hit top
                    {
                        return FALSE;
                    }

                    offset=m_currentHolder->m_index+1;

                    parent=NULL;

                    while(offset<m_maxIndex)
                    {
                        parent=m_currentHolder->m_parent->m_subspace[offset];

                        if(parent)
                        {
                            m_currentHolder=parent;
                            break;
                        }

                        ++offset;
                    }

                    if(parent)
                        break;

                    // We have no neighbour; check parent neighbour
                    m_currentHolder=m_currentHolder->m_parent;
                }

                // we have a new holder

                continue;
            }

            // Set up valid iterator for holder

            m_validIterator=TRUE;
            m_iterator.setList(m_currentHolder->m_itemList);
        }

        // Iterate over list for a valid holder

        item=m_iterator();

        if(!item)       // End of list
        {
            // Clean up
            m_validIterator=FALSE;

            // go to first sibling

            if(m_currentHolder->m_subspace)
            {
                // Select first child
                m_currentHolder=m_currentHolder->m_subspace[m_currentHolder->m_firstIndex];
            }
            else
            {
                // go to next neighour

                while(TRUE)
                {
                    if(!m_currentHolder->m_parent)  // check if we hit top
                    {
                        return FALSE;
                    }

                    offset=m_currentHolder->m_index+1;

                    parent=NULL;

                    while(offset<m_maxIndex)
                    {
                        parent=m_currentHolder->m_parent->m_subspace[offset];

                        if(parent)
                        {
                            m_currentHolder=parent;
                            break;
                        }

                        ++offset;
                    }

                    if(parent)
                        break;

                    // We have no neighbour; check parent neighbour
                    m_currentHolder=m_currentHolder->m_parent;
                }

                // we have a new holder

                continue;
            }
        }
        else    // Check to se if valid
        {
            if( (item->m_position.x+item->m_delta.x) < dx_m ) // left of us
                continue;

            if( (item->m_position.x-item->m_delta.x) > dx_p ) // right of us
                continue;

            if( (item->m_position.y+item->m_delta.y) < dy_m ) // bottom of us
                continue;

            if( (item->m_position.y-item->m_delta.y) > dy_p ) // top of us
                continue;

            if( (item->m_position.z+item->m_delta.z) < dz_m ) // left of us
                continue;

            if( (item->m_position.z-item->m_delta.z) > dz_p ) // right of us
                continue;

            // We have an intersection

            if(pos)
                *pos=item->m_position;

            if(delta)
                *delta=item->m_delta;

            data=item->m_data;

            return TRUE;
        }
    } 
}

#endif // __GZ_SPATIAL_H__

---