Home

nevrax.com

Nevrax.org News Mailing-list Documentation CVS Bugs License

Documentation                       Search   NLPACS::CQuadGrid Class Template Reference This container is a simple grid, used to quickly find elements. More... #include <quad_grid.h> List of all members. Public Methods   CQuadGrid ()   Default constructor, use axes XY!!!, has a size of 16, and EltSize is 1. More...   ~CQuadGrid ()   dtor. More... Initialization void  changeBase (const NLMISC::CMatrix &base)   Change the base matrix of the quad grid. More... void  create (uint size, float eltSize)   Init the container. More... Container operation void  clear ()   Clear the container. Elements are deleted, but the quadgrid is not erased. More... CIterator  erase (CIterator it)   Erase an interator from the container. More... CIterator  insert (const NLMISC::CVector &bboxmin, const NLMISC::CVector &bboxmax, const T &val)   Insert a new element in the container. More... Selection void  clearSelection ()   Clear the selection list. More... void  selectAll ()   Select all the container. More... void  select (const NLMISC::CVector &bboxmin, const NLMISC::CVector &bboxmax)   Select element intersecting a bounding box. More... CIterator  begin ()   Return the first iterator of the selected element list. More... CIterator  end ()   Return the end iterator of the selected element list. More... Private Methods void  selectQuads (CVector bmin, CVector bmax, sint &x0, sint &x1, sint &y0, sint &y1) void  addToSelection (CNode *ptr) void  addQuadNodeToSelection (CQuadNode &quad) Private Attributes std::vector< CQuadNode >  _Grid sint  _Size sint  _SizePower float  _EltSize NLMISC::CMatrix  _ChangeBasis CBaseNode  _Selection Friends class  CIterator 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. 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 _ChangeBasis, _EltSize, _Size, _SizePower, and NLMISC::CMatrix::identity. template<class T> NLPACS::CQuadGrid< T >::~CQuadGrid (    )    dtor. Definition at line 353 of file pacs/quad_grid.h. References clear. 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 select, and selectAll. 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. 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 _Selection, CIterator, and NLPACS::CQuadGrid::CBaseNode::Next. Referenced by clear. 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. References _ChangeBasis. 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 _Selection, begin, CIterator, end, erase, NLPACS::CQuadGrid::CBaseNode::Next, and selectAll. Referenced by create, and ~CQuadGrid. template<class T> void NLPACS::CQuadGrid< T >::clearSelection (    )    Clear the selection list. Definition at line 489 of file pacs/quad_grid.h. References _Selection, and NLPACS::CQuadGrid::CBaseNode::Next. Referenced by select, and selectAll. 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 _EltSize, _Grid, _Size, _SizePower, clear, NLMISC::getPowerOf2, NLMISC::isPowerOf2, and nlassert. 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 CIterator. Referenced by clear, and erase. 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 _Grid, _Size, _SizePower, CIterator, end, x, and y. Referenced by clear. 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 _ChangeBasis, _Grid, _Size, _SizePower, CIterator, selectQuads, x, and y. 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 _ChangeBasis, _Grid, _Size, _SizePower, addQuadNodeToSelection, clearSelection, selectQuads, x, and y. template<class T> void NLPACS::CQuadGrid< T >::selectAll (    )    Select all the container. Definition at line 503 of file pacs/quad_grid.h. References _Grid, addQuadNodeToSelection, and clearSelection. Referenced by clear. 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 insert, and select. Friends And Related Function Documentation template<class T> friend class CIterator [friend]   Definition at line 69 of file pacs/quad_grid.h. Referenced by begin, clear, end, erase, and insert. Member Data Documentation template<class T> NLMISC::CMatrix NLPACS::CQuadGrid::_ChangeBasis [private]   Definition at line 191 of file pacs/quad_grid.h. Referenced by changeBase, CQuadGrid, insert, and select. template<class T> float NLPACS::CQuadGrid::_EltSize [private]   Definition at line 190 of file pacs/quad_grid.h. Referenced by CQuadGrid, create, and NLPACS::CQuadGrid< uint32 >::selectQuads. template<class T> std::vector<CQuadNode> NLPACS::CQuadGrid::_Grid [private]   Definition at line 187 of file pacs/quad_grid.h. Referenced by create, erase, insert, select, and selectAll. template<class T> CBaseNode NLPACS::CQuadGrid::_Selection [private]   Definition at line 193 of file pacs/quad_grid.h. Referenced by begin, clear, and clearSelection. template<class T> sint NLPACS::CQuadGrid::_Size [private]   Definition at line 188 of file pacs/quad_grid.h. Referenced by CQuadGrid, create, erase, insert, select, and NLPACS::CQuadGrid< uint32 >::selectQuads. template<class T> sint NLPACS::CQuadGrid::_SizePower [private]   Definition at line 189 of file pacs/quad_grid.h. Referenced by CQuadGrid, create, erase, insert, and select. The documentation for this class was generated from the following file: pacs/quad_grid.h