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

Public Member Functions

 Quadtree (const Box2f &bbox, int max_depth=16)
 
const Box2fbbox () 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.



©2021 The Foundry Visionmongers, Ltd. All Rights Reserved.
www.thefoundry.co.uk