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

List of all members.

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
	)		[inline, protected]

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 [inline, protected]

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 [inline, protected]

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

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