lc::QuadTree< E > Class Template Reference

The QuadTree class Quad tree implementation to spatially store CADEntities Useful for area selections of large entities. More...

#include <quadtree.h>

Inheritance diagram for lc::QuadTree< E >:

Collaboration diagram for lc::QuadTree< E >:

Public Member Functions
	QuadTree (int level, const geo::Area &pBounds, short maxLevels, short maxObjects)
	QuadTree (const geo::Area &bounds)
	QuadTree (const QuadTree &other)
	QuadTree ()
void	clear ()
	clear Clear the quad tree by removing all levels and removing all stored entities More...
void	insert (const E entity)
	insert Insert entity into the quad tree More...
void	test () const
	test validy of the tree by comparing all nodes with the std::map More...
bool	erase (const E entity)
	remove Remove entity from quad tree More...
const E	entityByID (ID_DATATYPE id) const
Public Member Functions inherited from lc::QuadTreeSub< E >
	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 Attributes
std::unordered_map < ID_DATATYPE, const E >	_cadentities

Detailed Description

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

The QuadTree class Quad tree implementation to spatially store CADEntities Useful for area selections of large entities.

Considerations, speed vs memory consumption The more level's are created, the more memory it consumes, but the faster the tree will be for smaller objects The more object's per level the less memory it uses, but the more possiblew object's it will return during retrieve

We could change std::vector<E> _objects; into a std::map to speed up deletion of items within the tree At this moment we need to walk over the tree to find the item's location, then delete it However, this will consume more memory

mutable std::map<ID_DATATYPE, E> *_cadentities; can be removed all together, but this will slowdown testing the routine entityByID

Definition at line 17 of file quadtree.h.

Constructor & Destructor Documentation

template<typename E>

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

inline

Definition at line 509 of file quadtree.h.

                                                                                           :
                    QuadTreeSub<E>(level, pBounds, maxLevels, maxObjects) {

            }

template<typename E>

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

inline

Definition at line 514 of file quadtree.h.

                                            : QuadTreeSub<E>(bounds) {

            }

template<typename E>

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

inline

Definition at line 518 of file quadtree.h.

                                            : QuadTreeSub<E>(other), _cadentities(other._cadentities) {

            }

template<typename E>

lc::QuadTree< E >::QuadTree ( )

inline

Definition at line 522 of file quadtree.h.

                       : QuadTreeSub<E>(0, geo::Area(geo::Coordinate(0., 0.), geo::Coordinate(1., 1.)), 8, 25) {

            }

Member Function Documentation

template<typename E>

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

inline

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

Definition at line 530 of file quadtree.h.

                         {
                QuadTreeSub<E>::clear();
                _cadentities.clear();
            }

template<typename E>

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

inline

Definition at line 583 of file quadtree.h.

                                                     {
                if (_cadentities.count(id) > 0) {
                    return _cadentities.at(id);
                }

                return E();
            }

template<typename E>

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

inline

remove Remove entity from quad tree

Parameters

pRect
entity

Definition at line 571 of file quadtree.h.

                                       {
                if (_cadentities.count(entity->id()) == 0) {
                    // // LOG4CXX_DEBUG(logger, "It's bad that we end up here, normally we should call erase on entities we know that don't exists. ")
                    return false;
                }

                E work = _cadentities.at(entity->id());
                _cadentities.erase(entity->id());

                return QuadTreeSub<E>::erase(work);
            }

template<typename E>

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

inline

insert Insert entity into the quad tree

Parameters

pRect
entity

Definition at line 541 of file quadtree.h.

                                        {
                // LOG4CXX_DEBUG(logger, "level " << _level);
                //Update cache
                if (_cadentities.count(entity->id()) > 0) {
                    //LOG4CXX_DEBUG(logger, "This id was already added, please fix. It's not allowed to add the same ID twice");
                }

                _cadentities.insert(std::make_pair(entity->id(), entity));

                QuadTreeSub<E>::insert(entity);
            }

template<typename E>

void lc::QuadTree< E >::test ( ) const

inline

test validy of the tree by comparing all nodes with the std::map

Definition at line 557 of file quadtree.h.

                              {
                const auto list = QuadTreeSub<E>::retrieve();

                if (list.size() != _cadentities.size()) {
                    // // LOG4CXX_DEBUG(logger, "Cache size doesn't agree with QuadTreeSub size, this must be fixed ASAP difference : " << list.size() - _cadentities.size())
                }
            }

Member Data Documentation

template<typename E>

std::unordered_map<ID_DATATYPE, const E> lc::QuadTree< E >::_cadentities

private

Definition at line 595 of file quadtree.h.

---

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

• lckernel/cad/dochelpers/quadtree.h