Main Page | Namespace List | Class Hierarchy | Alphabetical List | Data Structures | File List | Namespace Members | Data Fields | Globals | Related Pages | Search for 

NLPACS::CQuadGrid< T > Class Template Reference

#include <quad_grid.h>

Detailed Description

template<class T>
class NLPACS::CQuadGrid< T >

This container is a simple grid, used to quickly find elements. His purpose is similiar to CQuadTree, but it is a simple grid, so test are in O(1), not in O(log n). It is perfect for local lookup (like in collisions). Use it if you want to select small area, not large. Also, for best use, elements should have approximatively the same size, and this size should be little smaller than the size of a grid element...

By default, the quad grid is aligned on XY. (unlike the quadtree!!!)

Unlike the quadtree, the quadgrid is NOT geographicly delimited, ie, its limits "tiles"!! This is why no "center" is required. As a direct consequence, when you select something, you are REALLY not sure that what you select is not a mile away from your selection :) ....

Also, for memory optimisation, no bbox is stored in the quadgrid. Hence no particular selection is made on the Z components...

Author:
Lionel Berenguier

Nevrax France

Date:
2000

Definition at line 64 of file pacs/quad_grid.h.

Public Member Functions

 CQuadGrid ()
 Default constructor, use axes XY!!!, has a size of 16, and EltSize is 1.

 ~CQuadGrid ()
 dtor.

Selection
CIterator begin ()
void clearSelection ()
CIterator end ()
void select (const NLMISC::CVector &bboxmin, const NLMISC::CVector &bboxmax)
void selectAll ()
Initialization
void changeBase (const NLMISC::CMatrix &base)
void create (uint size, float eltSize)
Container operation
void clear ()
 Clear the container. Elements are deleted, but the quadgrid is not erased.

CIterator erase (CIterator it)
CIterator insert (const NLMISC::CVector &bboxmin, const NLMISC::CVector &bboxmax, const T &val)

Private Member Functions

void addQuadNodeToSelection (CQuadNode &quad)
void addToSelection (CNode *ptr)
void selectQuads (CVector bmin, CVector bmax, sint &x0, sint &x1, sint &y0, sint &y1)

Private Attributes

NLMISC::CMatrix _ChangeBasis
float _EltSize
std::vector< CQuadNode > _Grid
CBaseNode _Selection
sint _Size
sint _SizePower

Friends

class CIterator

Constructor & Destructor Documentation

template<class T>
NLPACS::CQuadGrid< T >::CQuadGrid (   ) 
 

Default constructor, use axes XY!!!, has a size of 16, and EltSize is 1.

Definition at line 345 of file pacs/quad_grid.h.

References NLMISC::CMatrix::identity(). 

00346 {
00347         _SizePower=4;
00348         _Size=1<<_SizePower;
00349         _EltSize=1;
00350         _ChangeBasis.identity();
00351 }

template<class T>
NLPACS::CQuadGrid< T >::~CQuadGrid (   ) 
 

dtor.

Definition at line 353 of file pacs/quad_grid.h.

References NLPACS::CQuadGrid< T >::clear(). 

00354 {
00355         clear();
00356 }

Member Function Documentation

template<class T>
void NLPACS::CQuadGrid< T >::addQuadNodeToSelection (  CQuadNode &  quad  )  [inline, private]
 

Definition at line 255 of file pacs/quad_grid.h.

Referenced by NLPACS::CQuadGrid< T >::select(), and NLPACS::CQuadGrid< T >::selectAll(). 

00256         {
00257                 typename std::list<CNode*>::iterator    itNode;
00258                 for(itNode= quad.Nodes.begin();itNode!=quad.Nodes.end();itNode++)
00259                 {
00260                         addToSelection(*itNode);
00261                 }
00262         }

template<class T>
void NLPACS::CQuadGrid< T >::addToSelection (  CNode *  ptr  )  [inline, private]
 

Definition at line 241 of file pacs/quad_grid.h.

Referenced by NLPACS::CQuadGrid< uint32 >::addQuadNodeToSelection(). 

00242         {
00243                 if(ptr->Prev==NULL)
00244                 {
00245                         // Append to front of the list.
00246                         ptr->Prev= &_Selection;
00247                         ptr->Next= _Selection.Next;
00248                         if(_Selection.Next)
00249                                 _Selection.Next->Prev= ptr;
00250                         _Selection.Next= ptr;
00251                 }
00252         }

template<class T>
CQuadGrid< T >::CIterator NLPACS::CQuadGrid< T >::begin (   ) 
 

Return the first iterator of the selected element list. begin and end are valid till the next insert.

Definition at line 541 of file pacs/quad_grid.h.

References NLPACS::CQuadGrid< T >::CIterator, and NLPACS::CQuadGrid< T >::CBaseNode::Next.

Referenced by NLPACS::CQuadGrid< T >::clear(). 

00542 {
00543         return CIterator((CNode*)(_Selection.Next));
00544 }

template<class T>
void NLPACS::CQuadGrid< T >::changeBase (  const NLMISC::CMatrix &  base  ) 
 

Change the base matrix of the quad grid. For exemple this code init the grid tree in the plane XZ: 

 CQuadGrid                      grid;
 NLMISC::CMatrix                tmp;
 NLMISC::CVector                I(1,0,0);
 NLMISC::CVector                J(0,0,1);
 NLMISC::CVector                K(0,-1,0);
 
 tmp.identity();
 tmp.setRot(I,J,K, true);
 quadTree.changeBase (tmp);

Parameters:
base Base of the quad grid

Definition at line 358 of file pacs/quad_grid.h. 

00359 {
00360         _ChangeBasis= base;
00361 }

template<class T>
void NLPACS::CQuadGrid< T >::clear (   ) 
 

Clear the container. Elements are deleted, but the quadgrid is not erased.

Definition at line 384 of file pacs/quad_grid.h.

References NLPACS::CQuadGrid< T >::begin(), NLPACS::CQuadGrid< T >::end(), NLPACS::CQuadGrid< T >::erase(), NLPACS::CQuadGrid< T >::CBaseNode::Next, and NLPACS::CQuadGrid< T >::selectAll().

Referenced by NLPACS::CQuadGrid< T >::create(), and NLPACS::CQuadGrid< T >::~CQuadGrid(). 

00385 {
00386         CIterator       it;
00387         selectAll();
00388         while( (it=begin())!=end())
00389         {
00390                 erase(it);
00391         }
00392 
00393         // Clear the selection...
00394         _Selection.Next= NULL;
00395 }

template<class T>
void NLPACS::CQuadGrid< T >::clearSelection (   ) 
 

Clear the selection list

Definition at line 489 of file pacs/quad_grid.h.

References NLPACS::CQuadGrid< T >::CBaseNode::Next, and NLPACS::CQuadGrid< T >::CBaseNode::Prev.

Referenced by NLPACS::CQuadGrid< T >::select(), and NLPACS::CQuadGrid< T >::selectAll(). 

00490 {
00491         CBaseNode       *ptr= _Selection.Next;
00492         while(ptr)
00493         {
00494                 ptr->Prev= NULL;
00495                 CBaseNode       *next= ptr->Next;
00496                 ptr->Next= NULL;
00497                 ptr= next;
00498         }
00499 
00500         _Selection.Next= NULL;
00501 }

template<class T>
void NLPACS::CQuadGrid< T >::create (  uint  size,
float  eltSize
) 
 

Init the container. container is first clear() ed.

Parameters:
size is the width and the height of the initial quad tree, in number of square. For performance view, this should be a power of 2, and <=32768. (eg: 256,512, 8, 16 ...)
eltSize is the width and height of an element. Must be >0. Notice that the quadgrid MUST be square!!

Definition at line 363 of file pacs/quad_grid.h.

References NLPACS::CQuadGrid< T >::clear(), nlassert, size, and uint. 

00364 {
00365         clear();
00366 
00367         nlassert(isPowerOf2(size));
00368         nlassert(size<=32768);
00369         _SizePower= getPowerOf2(size);
00370         _Size=1<<_SizePower;
00371         _Grid.resize(_Size*_Size);
00372 
00373         nlassert(eltSize>0);
00374         _EltSize= eltSize;
00375 }

template<class T>
CQuadGrid< T >::CIterator NLPACS::CQuadGrid< T >::end (   ) 
 

Return the end iterator of the selected element list. begin and end are valid till the next insert.

Definition at line 546 of file pacs/quad_grid.h.

References NLPACS::CQuadGrid< T >::CIterator.

Referenced by NLPACS::CQuadGrid< T >::clear(), and NLPACS::CQuadGrid< T >::erase(). 

00547 {
00548         return CIterator(NULL);
00549 }

template<class T>
CQuadGrid< T >::CIterator NLPACS::CQuadGrid< T >::erase (  CIterator  it  ) 
 

Erase an interator from the container

Parameters:
it is the iterator to erase.
Returns:
if element is currently selected, the next selected element is returned, (or end()). if the element is not selected, end() is returned.

Definition at line 397 of file pacs/quad_grid.h.

References NLPACS::CQuadGrid< T >::CIterator, NLPACS::CQuadGrid< T >::end(), NLPACS::CQuadGrid< T >::CBaseNode::Next, NLPACS::CQuadGrid< T >::CQuadNode::Nodes, NLPACS::CQuadGrid< T >::CBaseNode::Prev, sint, x, NLPACS::CQuadGrid< T >::CNode::x0, NLPACS::CQuadGrid< T >::CNode::x1, y, NLPACS::CQuadGrid< T >::CNode::y0, and NLPACS::CQuadGrid< T >::CNode::y1.

Referenced by NLPACS::CQuadGrid< T >::clear(). 

00398 {
00399         sint    x,y;
00400         CNode   *ptr= it._Ptr;
00401 
00402         if(!ptr)
00403                 return end();
00404 
00405         // First erase all references to it.
00406         //==================================
00407         for(y= ptr->y0;y<ptr->y1;y++)
00408         {
00409                 sint    xe,ye;
00410                 ye= y &(_Size-1);
00411                 for(x= ptr->x0;x<ptr->x1;x++)
00412                 {
00413                         xe= x &(_Size-1);
00414                         CQuadNode       &quad= _Grid[(ye<<_SizePower)+xe];
00415                         typename std::list<CNode*>::iterator    itNode;
00416                         for(itNode= quad.Nodes.begin();itNode!=quad.Nodes.end();itNode++)
00417                         {
00418                                 if((*itNode)==ptr)
00419                                 {
00420                                         quad.Nodes.erase(itNode);
00421                                         break;
00422                                 }
00423                         }
00424                 }
00425         }
00426 
00427         // Then delete it..., and update selection linked list.
00428         //=====================================================
00429         // if selected.
00430         CBaseNode       *next= NULL;
00431         if(ptr->Prev)
00432         {
00433                 next= ptr->Next;
00434                 if(next)
00435                         next->Prev=ptr->Prev;
00436                 ptr->Prev->Next= next;
00437         }
00438         delete ptr;
00439 
00440 
00441         return CIterator((CNode*)next);
00442 }

template<class T>
CQuadGrid< T >::CIterator NLPACS::CQuadGrid< T >::insert (  const NLMISC::CVector &  bboxmin,
const NLMISC::CVector &  bboxmax,
const T &  val
) 
 

Insert a new element in the container.

Parameters:
bboxmin is the corner of the bounding box of the element to insert with minimal coordinates.
bboxmax is the corner of the bounding box of the element to insert with maximal coordinates.
val is a reference on the value to insert.

Definition at line 444 of file pacs/quad_grid.h.

References NLPACS::CQuadGrid< T >::CIterator, NLPACS::CQuadGrid< T >::CNode::Elt, NLPACS::CQuadGrid< T >::CQuadNode::Nodes, NLPACS::CQuadGrid< T >::selectQuads(), sint, x, NLPACS::CQuadGrid< T >::CNode::x0, NLPACS::CQuadGrid< T >::CNode::x1, y, NLPACS::CQuadGrid< T >::CNode::y0, and NLPACS::CQuadGrid< T >::CNode::y1. 

00445 {
00446         CVector         bmin,bmax;
00447         bmin= _ChangeBasis*bboxmin;
00448         bmax= _ChangeBasis*bboxmax;
00449 
00450         CNode   *ptr= new CNode;
00451         ptr->Elt= val;
00452 
00453         // Find which quad include the object.
00454         //===================================
00455         sint    x0,y0;
00456         sint    x1,y1;
00457         selectQuads(bmin, bmax, x0,x1, y0,y1);
00458 
00459         ptr->x0= x0;
00460         ptr->x1= x1;
00461         ptr->y0= y0;
00462         ptr->y1= y1;
00463 
00464         // Then for all of them, insert the node in their list.
00465         //=====================================================
00466         sint    x,y;
00467         for(y= ptr->y0;y<ptr->y1;y++)
00468         {
00469                 sint    xe,ye;
00470                 ye= y &(_Size-1);
00471                 for(x= ptr->x0;x<ptr->x1;x++)
00472                 {
00473                         xe= x &(_Size-1);
00474                         CQuadNode       &quad= _Grid[(ye<<_SizePower)+xe];
00475                         quad.Nodes.push_back(ptr);
00476                 }
00477         }
00478 
00479         return CIterator(ptr);
00480 }

template<class T>
void NLPACS::CQuadGrid< T >::select (  const NLMISC::CVector &  bboxmin,
const NLMISC::CVector &  bboxmax
) 
 

Select element intersecting a bounding box. Clear the selection first.

Parameters:
bboxmin is the corner of the bounding box used to select
bboxmax is the corner of the bounding box used to select

Definition at line 513 of file pacs/quad_grid.h.

References NLPACS::CQuadGrid< T >::addQuadNodeToSelection(), NLPACS::CQuadGrid< T >::clearSelection(), NLPACS::CQuadGrid< T >::selectQuads(), sint, x, and y. 

00514 {
00515         CVector         bmin,bmax;
00516         bmin= _ChangeBasis*bboxmin;
00517         bmax= _ChangeBasis*bboxmax;
00518 
00519         clearSelection();
00520 
00521         // What are the quads to access?
00522         sint    x0,y0;
00523         sint    x1,y1;
00524         selectQuads(bmin, bmax, x0,x1, y0,y1);
00525 
00526         sint    x,y;
00527         for(y= y0;y<y1;y++)
00528         {
00529                 sint    xe,ye;
00530                 ye= y &(_Size-1);
00531                 for(x= x0;x<x1;x++)
00532                 {
00533                         xe= x &(_Size-1);
00534                         CQuadNode       &quad= _Grid[(ye<<_SizePower)+xe];
00535                         addQuadNodeToSelection(quad);
00536                 }
00537         }
00538 
00539 }

template<class T>
void NLPACS::CQuadGrid< T >::selectAll (   ) 
 

Select all the container

Definition at line 503 of file pacs/quad_grid.h.

References NLPACS::CQuadGrid< T >::addQuadNodeToSelection(), NLPACS::CQuadGrid< T >::clearSelection(), and sint.

Referenced by NLPACS::CQuadGrid< T >::clear(). 

00504 {
00505         clearSelection();
00506         for(sint i=0;i<(sint)_Grid.size();i++)
00507         {
00508                 CQuadNode       &quad= _Grid[i];
00509                 addQuadNodeToSelection(quad);
00510         }
00511 }

template<class T>
void NLPACS::CQuadGrid< T >::selectQuads (  CVector  bmin,
CVector  bmax,
sint &  x0,
sint &  x1,
sint &  y0,
sint &  y1
)  [inline, private]
 

Definition at line 199 of file pacs/quad_grid.h.

Referenced by NLPACS::CQuadGrid< T >::insert(), and NLPACS::CQuadGrid< T >::select(). 

00200         {
00201                 CVector         bminp, bmaxp;
00202                 bminp= bmin;
00203                 bmaxp= bmax;
00204                 bmin.minof(bminp, bmaxp);
00205                 bmax.maxof(bminp, bmaxp);
00206                 bmin/= _EltSize;
00207                 bmax/= _EltSize;
00208                 x0= (sint)(floor(bmin.x));
00209                 x1= (sint)(ceil(bmax.x));
00210                 y0= (sint)(floor(bmin.y));
00211                 y1= (sint)(ceil(bmax.y));
00212 
00213                 // Very special case where the bbox.size==0 AND position is JUST on an edge of a case.
00214                 if(x0==x1)
00215                         x1++;
00216                 if(y0==y1)
00217                         y1++;
00218 
00219                 // Manage tiling.
00220                 if(x1-x0>=_Size)
00221                         x0=0, x1= _Size;
00222                 else
00223                 {
00224                         x0&= _Size-1;
00225                         x1&= _Size-1;
00226                         if(x1<=x0)
00227                                 x1+=_Size;
00228                 }
00229                 if(y1-y0>=_Size)
00230                         y0=0, y1= _Size;
00231                 else
00232                 {
00233                         y0&= _Size-1;
00234                         y1&= _Size-1;
00235                         if(y1<=y0)
00236                                 y1+=_Size;
00237                 }
00238         }

Friends And Related Function Documentation

template<class T>
friend class CIterator [friend]
 

Definition at line 69 of file pacs/quad_grid.h.

Referenced by NLPACS::CQuadGrid< T >::begin(), NLPACS::CQuadGrid< T >::end(), NLPACS::CQuadGrid< T >::erase(), and NLPACS::CQuadGrid< T >::insert().

Field Documentation

template<class T>
NLMISC::CMatrix NLPACS::CQuadGrid< T >::_ChangeBasis [private]
 

Definition at line 191 of file pacs/quad_grid.h.

template<class T>
float NLPACS::CQuadGrid< T >::_EltSize [private]
 

Definition at line 190 of file pacs/quad_grid.h.

template<class T>
std::vector<CQuadNode> NLPACS::CQuadGrid< T >::_Grid [private]
 

Definition at line 187 of file pacs/quad_grid.h.

template<class T>
CBaseNode NLPACS::CQuadGrid< T >::_Selection [private]
 

Definition at line 193 of file pacs/quad_grid.h.

template<class T>
sint NLPACS::CQuadGrid< T >::_Size [private]
 

Definition at line 188 of file pacs/quad_grid.h.

template<class T>
sint NLPACS::CQuadGrid< T >::_SizePower [private]
 

Definition at line 189 of file pacs/quad_grid.h.

The documentation for this class was generated from the following file:
Generated on Tue Mar 16 14:21:31 2004 for NeL by doxygen 1.3.6