DD::Image::Quadtree< T > Class Template Reference

Public Member Functions
	Quadtree (const Box2f &bbox, int max_depth=16)
const Box2f &	bbox () const
int	max_depth () const
const QuadtreeNode< T > &	root () const
void	add (const T &object, const Box2f &obj_bbox, float min_D=0.0f)
void	add_to_root (const T &object)
const std::vector< T, STL3DAllocator< T > > *	find (float x, float y) const
int	intersections (const Box2f &bbox, std::vector< const QuadtreeNode< T > * > &node_list) const

Protected Member Functions
void	_add (QuadtreeNode< T > *node, const Box2f &node_bbox, const T &object, const Box2f &obj_bbox, float D, int depth)
const std::vector< T, STL3DAllocator< T > > *	_find (const QuadtreeNode< T > *node, const Box2f &node_bbox, float x, float y) const
int	_intersections (const QuadtreeNode< T > *node, const Box2f &node_bbox, const Box2f &bbox, std::vector< const QuadtreeNode< T > * > &node_list) const

Detailed Description

template<class T>
class DD::Image::Quadtree< T >

This template class provides spatial subdivision functionality of a 2D rectangular area and methods to add to or return its contents.

Member Function Documentation

template<class T>

void DD::Image::Quadtree< T >::add ( const T &  object, const Box2f &  obj_bbox, float  min_D = 0.0f  )

inline

Add an object with its bounding box to all nodes in the tree that obj_bbox intersects, adding subdivisions until obj_bbox is larger than the subdivision size, or the maximum recursion level is reached.

template<class T>

void DD::Image::Quadtree< T >::add_to_root ( const T &  object )

inline

Add the object to the root with no further tests.

template<class T>

const std::vector< T, STL3DAllocator<T> >* DD::Image::Quadtree< T >::find ( float  x, float  y  ) const

inline

Find the last node in the tree that xy intersects, returning a pointer to the node's data vector.

template<class T>

int DD::Image::Quadtree< T >::intersections ( const Box2f &  bbox, std::vector< const QuadtreeNode< T > * > &  node_list  ) const

inline

Find all nodes in the tree that intersect bbox and add them to /b node_list.

Referenced by DD::Image::Render::draw_primitives().

template<class T>

void DD::Image::Quadtree< T >::_add ( QuadtreeNode< T > *  node, const Box2f &  node_bbox, const T &  object, const Box2f &  obj_bbox, float  D, int  depth  )

inlineprotected

Recursive version of add() that finds a node to add object to.

References DD::Image::QuadtreeNode< T >::child_nodes, DD::Image::QuadtreeNode< T >::data, and DD::Image::Vector2::distanceSquared().

template<class T>

const std::vector< T, STL3DAllocator< T > > * DD::Image::Quadtree< T >::_find ( const QuadtreeNode< T > *  node, const Box2f &  node_bbox, float  x, float  y  ) const

inlineprotected

Recursive version of find() that steps through the tree.

References DD::Image::QuadtreeNode< T >::child_nodes, and DD::Image::QuadtreeNode< T >::data.

template<class T>

int DD::Image::Quadtree< T >::_intersections ( const QuadtreeNode< T > *  node, const Box2f &  node_bbox, const Box2f &  bbox, std::vector< const QuadtreeNode< T > * > &  node_list  ) const

inlineprotected

Recursive version of intersections() that steps through the tree.

References DD::Image::QuadtreeNode< T >::child_nodes, and DD::Image::QuadtreeNode< T >::data.