Generic quadtree data structure. More...

#include <jet/quadtree.h>

Inheritance diagram for jet::Quadtree< T >:

Public Types
typedef std::vector< T >	ContainerType

typedef ContainerType::iterator	Iterator

typedef ContainerType::const_iterator	ConstIterator

Public Member Functions
	Quadtree ()
	Default constructor. More...

void	build (const std::vector< T > &items, const BoundingBox2D &bound, const BoxIntersectionTestFunc2< T > &testFunc, size_t maxDepth)

void	clear ()
	Clears all the contents of this instance. More...

NearestNeighborQueryResult2< T >	nearest (const Vector2D &pt, const NearestNeighborDistanceFunc2< T > &distanceFunc) const override

bool	intersects (const BoundingBox2D &box, const BoxIntersectionTestFunc2< T > &testFunc) const override
	Returns true if given `box` intersects with any of the stored items. More...

bool	intersects (const Ray2D &ray, const RayIntersectionTestFunc2< T > &testFunc) const override
	Returns true if given `ray` intersects with any of the stored items. More...

void	forEachIntersectingItem (const BoundingBox2D &box, const BoxIntersectionTestFunc2< T > &testFunc, const IntersectionVisitorFunc2< T > &visitorFunc) const override
	Invokes `visitorFunc` for every intersecting items. More...

void	forEachIntersectingItem (const Ray2D &ray, const RayIntersectionTestFunc2< T > &testFunc, const IntersectionVisitorFunc2< T > &visitorFunc) const override
	Invokes `visitorFunc` for every intersecting items. More...

ClosestIntersectionQueryResult2< T >	closestIntersection (const Ray2D &ray, const GetRayIntersectionFunc2< T > &testFunc) const override
	Returns the closest intersection for given `ray`. More...

Iterator	begin ()
	Returns the begin iterator of the item. More...

Iterator	end ()
	Returns the end iterator of the item. More...

ConstIterator	begin () const
	Returns the immutable begin iterator of the item. More...

ConstIterator	end () const
	Returns the immutable end iterator of the item. More...

size_t	numberOfItems () const
	Returns the number of items. More...

const T &	item (size_t i) const
	Returns the item at `i`. More...

size_t	numberOfNodes () const
	Returns the number of quadtree nodes. More...

const std::vector< size_t > &	itemsAtNode (size_t nodeIdx) const
	Returns the list of the items for given noide index. More...

size_t	childIndex (size_t nodeIdx, size_t childIdx) const
	Returns a child's index for given node. More...

const BoundingBox2D &	boundingBox () const
	Returns the bounding box of this quadtree. More...

size_t	maxDepth () const
	Returns the maximum depth of the tree. More...

Detailed Description

template<typename T>
class jet::Quadtree< T >

Generic quadtree data structure.

This class is a generic quadtree representation to store arbitrary spatial data. The quadtree supports closest neighbor search, overlapping test, and ray intersection test.

Template Parameters

T	Value type.

Member Typedef Documentation

◆ ConstIterator

template<typename T >

typedef ContainerType::const_iterator jet::Quadtree< T >::ConstIterator

◆ ContainerType

template<typename T >

typedef std::vector<T> jet::Quadtree< T >::ContainerType

◆ Iterator

template<typename T >

typedef ContainerType::iterator jet::Quadtree< T >::Iterator

Constructor & Destructor Documentation

◆ Quadtree()

template<typename T >

jet::Quadtree< T >::Quadtree ( )

Default constructor.

Member Function Documentation

◆ begin() [1/2]

template<typename T >

Iterator jet::Quadtree< T >::begin ( )

Returns the begin iterator of the item.

◆ begin() [2/2]

template<typename T >

ConstIterator jet::Quadtree< T >::begin ( ) const

Returns the immutable begin iterator of the item.

◆ boundingBox()

template<typename T >

const BoundingBox2D& jet::Quadtree< T >::boundingBox ( ) const

Returns the bounding box of this quadtree.

◆ build()

template<typename T >

void jet::Quadtree< T >::build	(	const std::vector< T > &	items,
		const BoundingBox2D &	bound,
		const BoxIntersectionTestFunc2< T > &	testFunc,
		size_t	maxDepth
	)

Builds an quadtree with given list of items, bounding box of the items, overlapping test function, and max depth of the tree.

◆ childIndex()

template<typename T >

size_t jet::Quadtree< T >::childIndex	(	size_t	nodeIdx,
		size_t	childIdx
	)		const

Returns a child's index for given node.

For a given node, its children is stored continuously, such that if the node's first child's index is i, then i + 1, i + 2, ... , i + 7 are the indices for its children. The order of octant is x-major.

Parameters

[in]	nodeIdx	The node index.
[in]	childIdx	The child index (0 to 7).

Returns: Index of the selected child.

◆ clear()

template<typename T >

void jet::Quadtree< T >::clear ( )

Clears all the contents of this instance.

◆ closestIntersection()

template<typename T >

ClosestIntersectionQueryResult2<T> jet::Quadtree< T >::closestIntersection	(	const Ray2D &	ray,
		const GetRayIntersectionFunc2< T > &	testFunc
	)		const

overridevirtual

Returns the closest intersection for given ray.

Implements jet::IntersectionQueryEngine2< T >.

◆ end() [1/2]

template<typename T >

Iterator jet::Quadtree< T >::end ( )

Returns the end iterator of the item.

◆ end() [2/2]

template<typename T >

ConstIterator jet::Quadtree< T >::end ( ) const

Returns the immutable end iterator of the item.

◆ forEachIntersectingItem() [1/2]

template<typename T >

void jet::Quadtree< T >::forEachIntersectingItem	(	const BoundingBox2D &	box,
		const BoxIntersectionTestFunc2< T > &	testFunc,
		const IntersectionVisitorFunc2< T > &	visitorFunc
	)		const

overridevirtual

Invokes visitorFunc for every intersecting items.

Implements jet::IntersectionQueryEngine2< T >.

◆ forEachIntersectingItem() [2/2]

template<typename T >

void jet::Quadtree< T >::forEachIntersectingItem	(	const Ray2D &	ray,
		const RayIntersectionTestFunc2< T > &	testFunc,
		const IntersectionVisitorFunc2< T > &	visitorFunc
	)		const

overridevirtual

Invokes visitorFunc for every intersecting items.

Implements jet::IntersectionQueryEngine2< T >.

◆ intersects() [1/2]

template<typename T >

bool jet::Quadtree< T >::intersects	(	const BoundingBox2D &	box,
		const BoxIntersectionTestFunc2< T > &	testFunc
	)		const

overridevirtual

Returns true if given box intersects with any of the stored items.

Implements jet::IntersectionQueryEngine2< T >.

◆ intersects() [2/2]

template<typename T >

bool jet::Quadtree< T >::intersects	(	const Ray2D &	ray,
		const RayIntersectionTestFunc2< T > &	testFunc
	)		const

overridevirtual

Returns true if given ray intersects with any of the stored items.

Implements jet::IntersectionQueryEngine2< T >.

◆ item()

template<typename T >

const T& jet::Quadtree< T >::item ( size_t i ) const

Returns the item at i.

◆ itemsAtNode()

template<typename T >

const std::vector<size_t>& jet::Quadtree< T >::itemsAtNode ( size_t nodeIdx ) const

Returns the list of the items for given noide index.

◆ maxDepth()

template<typename T >

size_t jet::Quadtree< T >::maxDepth ( ) const

Returns the maximum depth of the tree.

◆ nearest()

template<typename T >

NearestNeighborQueryResult2<T> jet::Quadtree< T >::nearest	(	const Vector2D &	pt,
		const NearestNeighborDistanceFunc2< T > &	distanceFunc
	)		const

overridevirtual

Returns the nearest neighbor for given point and distance measure function.

Implements jet::NearestNeighborQueryEngine2< T >.

◆ numberOfItems()

template<typename T >

size_t jet::Quadtree< T >::numberOfItems ( ) const

Returns the number of items.

◆ numberOfNodes()

template<typename T >

size_t jet::Quadtree< T >::numberOfNodes ( ) const

Returns the number of quadtree nodes.

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

jet/quadtree.h

Public Types

Public Member Functions

Detailed Description

template<typename T> class jet::Quadtree< T >

Member Typedef Documentation

◆ ConstIterator

◆ ContainerType

◆ Iterator

Constructor & Destructor Documentation

◆ Quadtree()

Member Function Documentation

◆ begin() [1/2]

◆ begin() [2/2]

◆ boundingBox()

◆ build()

◆ childIndex()

◆ clear()

◆ closestIntersection()

◆ end() [1/2]

◆ end() [2/2]

◆ forEachIntersectingItem() [1/2]

◆ forEachIntersectingItem() [2/2]

◆ intersects() [1/2]

◆ intersects() [2/2]

◆ item()

◆ itemsAtNode()

◆ maxDepth()

◆ nearest()

◆ numberOfItems()

◆ numberOfNodes()

template<typename T>
class jet::Quadtree< T >