The QuadTreeSub class each nide below QuadTree will be a QuadTreeSub type. More...

#include <quadtree.h>

Inheritance diagram for lc::QuadTreeSub< E >:

Collaboration diagram for lc::QuadTreeSub< E >:

Public Member Functions
	QuadTreeSub (int level, const geo::Area &pBounds, short maxLevels, short maxObjects)

	QuadTreeSub (const geo::Area &bounds)

	QuadTreeSub (const QuadTreeSub &other)

	QuadTreeSub ()

virtual	~QuadTreeSub ()

void	clear ()
	clear Clear the quad tree by removing all levels and removing all stored entities More...

void	insert (const E entity, const lc::geo::Area &entityBoundingBox)
	insert Insert entity into the qauad tree More...

void	insert (const E entity)

bool	erase (const E entity)
	remove Remove entity from quad tree More...

std::vector< E >	retrieve (const geo::Area &area, const short maxLevel=SHRT_MAX) const
	retrieve all object's that are located within a given area More...

std::vector< E >	retrieve (const short maxLevel=SHRT_MAX) const
	retrieve all object's within this QuadTree up until some level More...

unsigned int	size () const
	size all object's that are located within a given area More...

const E	entityByID (const ID_DATATYPE id) const
	entityByID returns a entity by its ID More...

geo::Area	bounds () const
	bounds of the root portion of the tree More...

short	level () const
	level returns the current level of this QuadTree More...

short	maxLevels () const
	maxLevels Maximum number of level's possible This value should be copied from one level to a other level within a single tree More...

short	maxObjects () const
	maxObjects Maximum number of objects on this level This value should be copied one level to a other level within a single tree More...

void	walkQuad (const std::function< void(const QuadTreeSub< E > &)> &func)
	walk Allows to walk over each node within the tree specifying a function that can be called for each QuadTreeSub More...

template<typename U , typename T >
void	each (T func)

bool	optimise ()
	optimise Optmise this tree. Current implementation will remove empty nodes up till the root node More...

Private Member Functions
void	_retrieve (std::vector< E > &list, const short maxLevel) const
	retrieve all object's that are located within a given area More...

void	_retrieve (std::vector< E > &list, const geo::Area &area, const short maxLevel) const
	retrieve all object's that are located within a given area More...

unsigned int	_size (unsigned int c) const

short	quadrantIndex (const geo::Area &pRect) const
	quadrantIndex located a possible quadrant index More...

bool	includes (const geo::Area &area) const

void	split ()
	split Create 4 new quads below the current quad More...

Private Attributes
const short	_level

std::vector< E >	_objects

const double	_verticalMidpoint

const double	_horizontalMidpoint

const geo::Area	_bounds

QuadTreeSub *	_nodes [4]

const unsigned short	_maxLevels

const unsigned short	_maxObjects

Detailed Description

template<typename E>
class lc::QuadTreeSub< E >

The QuadTreeSub class each nide below QuadTree will be a QuadTreeSub type.

Definition at line 25 of file quadtree.h.

Constructor & Destructor Documentation

template<typename E>

lc::QuadTreeSub< E >::QuadTreeSub	(	int	level,
		const geo::Area &	pBounds,
		short	maxLevels,
		short	maxObjects
	)

inline

Definition at line 27 of file quadtree.h.

                                                                                               :
                 _level(level) ,
                 _verticalMidpoint(pBounds.minP().x() + (pBounds.width() / 2.)),
                 _horizontalMidpoint(pBounds.minP().y() + (pBounds.height() / 2.)),
                 _bounds(pBounds), _maxLevels(maxLevels),
                 _maxObjects(maxObjects) {
                 _objects.reserve(maxObjects / 2);
                 _nodes[0] = nullptr;
                 _nodes[1] = nullptr;
                 _nodes[2] = nullptr;
                 _nodes[3] = nullptr;
 
 
             }

template<typename E>

lc::QuadTreeSub< E >::QuadTreeSub ( const geo::Area & bounds )

inline

Definition at line 42 of file quadtree.h.

                                                : QuadTreeSub(0, bounds, 10, 25) {
 
             }

template<typename E>

lc::QuadTreeSub< E >::QuadTreeSub ( const QuadTreeSub< E > & other )

inline

Definition at line 46 of file quadtree.h.

                                                   :
                     QuadTreeSub(0, other.bounds(), other.maxLevels(), other.maxObjects()) {
                 for (auto i : other.retrieve()) {
                     insert(i);
                 }
             }

template<typename E>

lc::QuadTreeSub< E >::QuadTreeSub ( )

inline

Definition at line 53 of file quadtree.h.

                           : QuadTreeSub(0, geo::Area(geo::Coordinate(0., 0.), geo::Coordinate(1., 1.)), 10, 25) {
 
             }

template<typename E>

virtual lc::QuadTreeSub< E >::~QuadTreeSub ( )

inlinevirtual

Definition at line 57 of file quadtree.h.

                                    {
                 if (_nodes[0] != nullptr) {
                     delete _nodes[0];
                     delete _nodes[1];
                     delete _nodes[2];
                     delete _nodes[3];
                 }
             }

Member Function Documentation

template<typename E>

void lc::QuadTreeSub< E >::_retrieve	(	std::vector< E > &	list,
		const short	maxLevel
	)		const

inlineprivate

retrieve all object's that are located within a given area

Parameters

list
area

Definition at line 326 of file quadtree.h.

                                                                            {
                 if (_nodes[0] != nullptr && maxLevel > _level) {
                     _nodes[0]->_retrieve(list, maxLevel);
                     _nodes[1]->_retrieve(list, maxLevel);
                     _nodes[2]->_retrieve(list, maxLevel);
                     _nodes[3]->_retrieve(list, maxLevel);
                 }
 
                 list.insert(list.end(), _objects.begin(), _objects.end());
             }

template<typename E>

void lc::QuadTreeSub< E >::_retrieve	(	std::vector< E > &	list,
		const geo::Area &	area,
		const short	maxLevel
	)		const

inlineprivate

retrieve all object's that are located within a given area

Parameters

list
area

Definition at line 342 of file quadtree.h.

                                                                                                 {
                 if (_nodes[0] != nullptr && maxLevel > _level) {
                     if (_nodes[0] -> includes(area)) {
                         _nodes[0]->_retrieve(list, area, maxLevel);
                     }
 
                     if (_nodes[1] -> includes(area)) {
                         _nodes[1]->_retrieve(list, area, maxLevel);
                     }
 
                     if (_nodes[2] -> includes(area)) {
                         _nodes[2]->_retrieve(list, area, maxLevel);
                     }
 
                     if (_nodes[3] -> includes(area)) {
                         _nodes[3]->_retrieve(list, area, maxLevel);
                     }
                 }
 
                 list.insert(list.end(), _objects.begin(), _objects.end());
             }

template<typename E>

unsigned int lc::QuadTreeSub< E >::_size ( unsigned int c ) const

inlineprivate

Return the number of items in this and lower nodes

Definition at line 366 of file quadtree.h.

                                                      {
                 if (_nodes[0] != nullptr) {
                     c += _nodes[0]->_size(_nodes[1]->_size(_nodes[2]->_size(_nodes[3]->_size(c))));
                 }
 
                 return c + _objects.size();
             }

template<typename E>

geo::Area lc::QuadTreeSub< E >::bounds ( ) const

inline

bounds of the root portion of the tree

Returns

Definition at line 223 of file quadtree.h.

                                    {
                 return _bounds;
             }

template<typename E>

void lc::QuadTreeSub< E >::clear ( )

inline

clear Clear the quad tree by removing all levels and removing all stored entities

Definition at line 70 of file quadtree.h.

                          {
                 if (_nodes[0] != nullptr) {
                     delete _nodes[0];
                     delete _nodes[1];
                     delete _nodes[2];
                     delete _nodes[3];
                     _nodes[0] = nullptr;
                     _nodes[1] = nullptr;
                     _nodes[2] = nullptr;
                     _nodes[3] = nullptr;
                 }
             }

template<typename E>

template<typename U , typename T >

void lc::QuadTreeSub< E >::each ( T func )

inline

Call a function for each entity within this node and it's sub nodes

Definition at line 274 of file quadtree.h.

                                                                {
                 if (_nodes[0] != nullptr) {
                     _nodes[0]->template each<U>(func);
                     _nodes[1]->template each<U>(func);
                     _nodes[2]->template each<U>(func);
                     _nodes[3]->template each<U>(func);
                 }
 
                 std::for_each(_objects.begin(), _objects.end(), [&](E item) {
                     std::shared_ptr<U> b = std::dynamic_pointer_cast<  U >(item);
                     func(b);
                 });
             }

template<typename E>

const E lc::QuadTreeSub< E >::entityByID ( const ID_DATATYPE id ) const

inline

entityByID returns a entity by its ID

Parameters

id

Returns

Definition at line 205 of file quadtree.h.

                                                            {
                 // // LOG4CXX_WARN(logger, "Using non optmised entityById method, this is going to be VERY slow. To solve please call the root QuadTreeSub to get a cached version!")
 
                 for (auto i : retrieve()) {
                     if (i->id() == id) {
                         return i;
                     }
                 }
 
                 return E();
             }

template<typename E>

bool lc::QuadTreeSub< E >::erase ( const E entity )

inline

remove Remove entity from quad tree

Parameters

pRect
entity

Definition at line 143 of file quadtree.h.

                                        {
                 // Find a Quad Tree area where this item might be located
                 if (_nodes[0] != nullptr) {
                     short index = quadrantIndex(entity->boundingBox());
 
                     if (index != -1) {
                         if (_nodes[index]->erase(entity)) {
                             return true;
                         }
                     }
                 }
 
                 for (typename std::vector<E>::iterator it = _objects.begin(); it != _objects.end(); it++) {
                     if ((*it)->id() == entity->id()) {
                         _objects.erase(it);
                         return true;
                     }
                 }
 
                 return false;
             }

template<typename E>

bool lc::QuadTreeSub< E >::includes ( const geo::Area & area ) const

inlineprivate

This if this node overlaps or includes a given area

Definition at line 414 of file quadtree.h.

                                                      {
 
                 if (area.maxP().x() <= _bounds.minP().x() ||
                     area.minP().x() >= _bounds.maxP().x() ||
                     area.maxP().y() <= _bounds.minP().y() ||
                     area.minP().y() >= _bounds.maxP().y()) {
                     return false;
                 } else {
                     return true;
                 }
             }

template<typename E>

void lc::QuadTreeSub< E >::insert	(	const E	entity,
		const lc::geo::Area &	entityBoundingBox
	)

inline

insert Insert entity into the qauad tree

Parameters

pRect
pRect
entity

Definition at line 90 of file quadtree.h.

                                                                             {
                 // Find a Quad Tree area where this item fits
                 if (_nodes[0] != nullptr) {
                     short entityIndex = quadrantIndex(entityBoundingBox);
 
                     if (entityIndex != -1) {
                         _nodes[entityIndex]->insert(entity, entityBoundingBox);
                         return;
                     }
                 }
 
                 _objects.push_back(entity);
 
                 // If it fits in this box, see if we can/must split this area into sub area's
                 // loop over the current container and see if the entities fit at a lower level
                 // So each entity is only tried once
                 if (_nodes[0] == nullptr && _objects.size() >= _maxObjects && _level < _maxLevels) {
                     split();
                     // Split two level's deep to reduce the number of object iterations
                     // This will help mostly when adding lots of little objects that would fit in 1/8 of the quad
                     _nodes[0]->split();
                     _nodes[1]->split();
                     _nodes[2]->split();
                     _nodes[3]->split();
 
                     for (auto it = _objects.begin() ; it != _objects.end();) {
                         auto sentityBoundingBox = (*it)->boundingBox();
                         short index = quadrantIndex(sentityBoundingBox);
 
                         if (index != -1) {
                             _nodes[index]->insert(*it, sentityBoundingBox);
                             it = _objects.erase(it);
                         }
                         else {
                             it++;
                         }
                     }
                 }
             }

template<typename E>

void lc::QuadTreeSub< E >::insert ( const E entity )

inline

Insert a nide into the quad tree,

See also: insert(const E entity, const lc::geo::Area &entityBoundingBox)

Definition at line 133 of file quadtree.h.

                                                {
                 insert(entity, entity->boundingBox());
             }

template<typename E>

short lc::QuadTreeSub< E >::level ( ) const

inline

level returns the current level of this QuadTree

Returns

Definition at line 232 of file quadtree.h.

                                 {
                 return _level;
             }

template<typename E>

short lc::QuadTreeSub< E >::maxLevels ( ) const

inline

maxLevels Maximum number of level's possible This value should be copied from one level to a other level within a single tree

Returns

Definition at line 242 of file quadtree.h.

                                     {
                 return _maxLevels;
             }

template<typename E>

short lc::QuadTreeSub< E >::maxObjects ( ) const

inline

maxObjects Maximum number of objects on this level This value should be copied one level to a other level within a single tree

Returns

Definition at line 251 of file quadtree.h.

                                      {
                 return _maxObjects;
             }

template<typename E>

bool lc::QuadTreeSub< E >::optimise ( )

inline

optimise Optmise this tree. Current implementation will remove empty nodes up till the root node

Returns: true if this node doesn't contain any entities

Definition at line 294 of file quadtree.h.

                             {
                 if (_nodes[0] != nullptr) {
                     bool ret1 = _nodes[0]->optimise();
                     bool ret2 = _nodes[1]->optimise();
                     bool ret3 = _nodes[2]->optimise();
                     bool ret4 = _nodes[3]->optimise();
 
                     if (ret1 && ret2 && ret3 && ret4) {
                         delete _nodes[0];
                         delete _nodes[1];
                         delete _nodes[2];
                         delete _nodes[3];
                         _nodes[0] = nullptr;
                         _nodes[1] = nullptr;
                         _nodes[2] = nullptr;
                         _nodes[3] = nullptr;
                     }
                     else {
                         return false;
                     }
                 }
 
                 return _objects.size() == 0;
             }

template<typename E>

short lc::QuadTreeSub< E >::quadrantIndex ( const geo::Area & pRect ) const

inlineprivate

quadrantIndex located a possible quadrant index

Parameters

pRect

Returns: -1 if it doesn't fit in any of the quadrants

Definition at line 380 of file quadtree.h.

                                                             {
 
                 bool topQuadrant = (pRect.minP().y() >= _horizontalMidpoint) &&
                                    (pRect.maxP().y() < _bounds.maxP().y());
                 bool bottomQuadrant = (pRect.minP().y() > _bounds.minP().y()) &&
                                       (pRect.maxP().y() <= _horizontalMidpoint);
 
                 if (!(topQuadrant || bottomQuadrant)) {
                     return -1;
                 }
 
                 bool leftQuadrant = (pRect.minP().x() > _bounds.minP().x()) &&
                                     (pRect.maxP().x() <= _verticalMidpoint);
                 bool rightQuandrant = (pRect.minP().x() >= _verticalMidpoint) &&
                                       (pRect.maxP().x() < _bounds.maxP().x());
 
                 if (!(leftQuadrant || rightQuandrant)) {
                     return -1;
                 }
                 else if (topQuadrant && rightQuandrant) {
                     return 0;
                 }
                 else if (topQuadrant && leftQuadrant) {
                     return 1;
                 }
                 else if (bottomQuadrant && leftQuadrant) {
                     return 2;
                 }
 
                 return 3;
             }

template<typename E>

std::vector<E> lc::QuadTreeSub< E >::retrieve	(	const geo::Area &	area,
		const short	maxLevel = `SHRT_MAX`
	)		const

inline

retrieve all object's that are located within a given area

Parameters

list
area

Definition at line 172 of file quadtree.h.

                                                                                               {
                 std::vector<E> list;
                 _retrieve(list, area, maxLevel);
                 return list;
             }

template<typename E>

std::vector<E> lc::QuadTreeSub< E >::retrieve ( const short maxLevel = SHRT_MAX ) const

inline

retrieve all object's within this QuadTree up until some level

Parameters

list
area

Definition at line 184 of file quadtree.h.

                                                                          {
                 std::vector<E> list;
                 _retrieve(list, maxLevel);
                 return list;
             }

template<typename E>

unsigned int lc::QuadTreeSub< E >::size ( ) const

inline

size all object's that are located within a given area

Parameters

list
area

Definition at line 195 of file quadtree.h.

                                       {
                 return _size(0);
             }

template<typename E>

void lc::QuadTreeSub< E >::split ( )

inlineprivate

split Create 4 new quads below the current quad

Definition at line 430 of file quadtree.h.

                          {
                 double subWidth = _bounds.width() / 2.;
                 double subHeight = _bounds.height() / 2.;
                 double x = _bounds.minP().x();
                 double y = _bounds.minP().y();
 
                 if (_nodes[0] != nullptr) {
                     // // LOG4CXX_DEBUG(logger, "Split is called on an already split node, please fix!");
                 } else {
                     _nodes[0] = new QuadTreeSub(
                             _level + 1,
                             geo::Area(geo::Coordinate(x + subWidth, y + subHeight),
                                       geo::Coordinate(_bounds.maxP().x(), _bounds.maxP().y())
                             ),
                             _maxLevels,
                             _maxObjects
                     );
 
                     _nodes[1] = new QuadTreeSub(
                             _level + 1,
                             geo::Area(geo::Coordinate(x, y + subHeight),
                                       geo::Coordinate(x + subWidth, _bounds.maxP().y())
                             ),
                             _maxLevels,
                             _maxObjects
                     );
 
                     _nodes[2] = new QuadTreeSub(
                             _level + 1,
                             geo::Area(geo::Coordinate(x, y),
                                       geo::Coordinate(x + subWidth, y + subHeight)
                             ),
                             _maxLevels,
                             _maxObjects
                     );
 
                     _nodes[3] = new QuadTreeSub(
                             _level + 1,
                             geo::Area(geo::Coordinate(x + subWidth, y),
                                       geo::Coordinate(_bounds.maxP().x(), y + subHeight)
                             ),
                             _maxLevels,
                             _maxObjects
                     );
                 }
 
             }

template<typename E>

void lc::QuadTreeSub< E >::walkQuad ( const std::function< void(const QuadTreeSub< E > &)> & func )

inline

walk Allows to walk over each node within the tree specifying a function that can be called for each QuadTreeSub

Parameters

foo

Definition at line 260 of file quadtree.h.

                                                                                 {
                 func(*this);
 
                 if (_nodes[0] != nullptr) {
                     _nodes[0]->walkQuad(func);
                     _nodes[1]->walkQuad(func);
                     _nodes[2]->walkQuad(func);
                     _nodes[3]->walkQuad(func);
                 }
             }

Member Data Documentation

template<typename E>

const geo::Area lc::QuadTreeSub< E >::_bounds

private

Definition at line 483 of file quadtree.h.

template<typename E>

const double lc::QuadTreeSub< E >::_horizontalMidpoint

private

Definition at line 482 of file quadtree.h.

template<typename E>

const short lc::QuadTreeSub< E >::_level

private

Definition at line 479 of file quadtree.h.

template<typename E>

const unsigned short lc::QuadTreeSub< E >::_maxLevels

private

Definition at line 485 of file quadtree.h.

template<typename E>

const unsigned short lc::QuadTreeSub< E >::_maxObjects

private

Definition at line 486 of file quadtree.h.

template<typename E>

QuadTreeSub* lc::QuadTreeSub< E >::_nodes[4]

private

Definition at line 484 of file quadtree.h.

template<typename E>

std::vector<E> lc::QuadTreeSub< E >::_objects

private

Definition at line 480 of file quadtree.h.

template<typename E>

const double lc::QuadTreeSub< E >::_verticalMidpoint

private

Definition at line 481 of file quadtree.h.

The documentation for this class was generated from the following file:

lckernel/cad/dochelpers/quadtree.h

Public Member Functions

Private Member Functions

Private Attributes

Detailed Description

template<typename E> class lc::QuadTreeSub< E >

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation

template<typename E>
class lc::QuadTreeSub< E >