From 0ea5fc66924303d1bf73ba283a383e2aadee02f2 Mon Sep 17 00:00:00 2001 From: neodarz Date: Sat, 11 Aug 2018 20:21:34 +0200 Subject: Initial commit --- docs/doxygen/nel/a03272.html | 1221 ++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 1221 insertions(+) create mode 100644 docs/doxygen/nel/a03272.html (limited to 'docs/doxygen/nel/a03272.html') diff --git a/docs/doxygen/nel/a03272.html b/docs/doxygen/nel/a03272.html new file mode 100644 index 00000000..6a1c1ffe --- /dev/null +++ b/docs/doxygen/nel/a03272.html @@ -0,0 +1,1221 @@ + + +NeL: TemplateNLPACS::CQuadGrid< T > class Reference + + + +
+

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
+ + -- cgit v1.2.1