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 } +

+

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:

pacs/quad_grid.h

Generated on Tue Mar 16 14:21:31 2004 for NeL by + +

+1.3.6

+ + -- cgit v1.2.1


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

NLPACS::CQuadGrid< T > Class Template Reference

Detailed Description

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

Public Member Functions

Private Member Functions

Private Attributes

Friends

Constructor & Destructor Documentation

Member Function Documentation

Friends And Related Function Documentation

Field Documentation

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