Generic quadtree data structure. More...

#include <Core/Geometry/Quadtree.hpp>

Inheritance diagram for CubbyFlow::Quadtree< T >:

Public Types
using	ContainerType = std::vector< T >

using	Iterator = typename ContainerType::iterator

using	ConstIterator = typename ContainerType::const_iterator

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

	Quadtree (const Quadtree &)=default
	Default copy constructor. More...

	Quadtree (Quadtree &&) noexcept=default
	Default move constructor. More...

virtual	~Quadtree ()=default
	Default virtual destructor. More...

Quadtree &	operator= (const Quadtree &)=default
	Default copy assignment operator. More...

Quadtree &	operator= (Quadtree &&) noexcept=default
	Default move assignment operator. 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 IntersectionVisitorFunc< T > &visitorFunc) const override
	Invokes `visitorFunc` for every intersecting items. More...

void	ForEachIntersectingItem (const Ray2D &ray, const RayIntersectionTestFunc2< T > &testFunc, const IntersectionVisitorFunc< 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	GetNumberOfItems () const
	Returns the number of items. More...

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

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

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

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

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

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

Public Member Functions inherited from CubbyFlow::IntersectionQueryEngine< T, N >
	IntersectionQueryEngine ()=default
	Default constructor. More...

virtual	~IntersectionQueryEngine ()=default
	Default virtual destructor. More...

	IntersectionQueryEngine (const IntersectionQueryEngine &other)=default
	Default copy constructor. More...

	IntersectionQueryEngine (IntersectionQueryEngine &&other) noexcept=default
	Default move constructor. More...

IntersectionQueryEngine &	operator= (const IntersectionQueryEngine &other)=default
	Default copy assignment operator. More...

IntersectionQueryEngine &	operator= (IntersectionQueryEngine &&other) noexcept=default
	Default move assignment operator. More...

virtual bool	Intersects (const BoundingBox< double, N > &box, const BoxIntersectionTestFunc< T, N > &testFunc) const =0
	Returns true if given `box` intersects with any of the stored items. More...

virtual bool	Intersects (const Ray< double, N > &ray, const RayIntersectionTestFunc< T, N > &testFunc) const =0
	Returns true if given `ray` intersects with any of the stored items. More...

virtual void	ForEachIntersectingItem (const BoundingBox< double, N > &box, const BoxIntersectionTestFunc< T, N > &testFunc, const IntersectionVisitorFunc< T > &visitorFunc) const =0
	Invokes `visitorFunc` for every intersecting items. More...

virtual void	ForEachIntersectingItem (const Ray< double, N > &ray, const RayIntersectionTestFunc< T, N > &testFunc, const IntersectionVisitorFunc< T > &visitorFunc) const =0
	Invokes `visitorFunc` for every intersecting items. More...

virtual ClosestIntersectionQueryResult< T, N >	ClosestIntersection (const Ray< double, N > &ray, const GetRayIntersectionFunc< T, N > &testFunc) const =0
	Returns the closest intersection for given `ray`. More...

Public Member Functions inherited from CubbyFlow::NearestNeighborQueryEngine< T, N >
	NearestNeighborQueryEngine ()=default
	Default constructor. More...

virtual	~NearestNeighborQueryEngine ()=default
	Default virtual destructor. More...

	NearestNeighborQueryEngine (const NearestNeighborQueryEngine &other)=default
	Default copy constructor. More...

	NearestNeighborQueryEngine (NearestNeighborQueryEngine &&other) noexcept=default
	Default move constructor. More...

NearestNeighborQueryEngine &	operator= (const NearestNeighborQueryEngine &other)=default
	Default copy assignment operator. More...

NearestNeighborQueryEngine &	operator= (NearestNeighborQueryEngine &&other) noexcept=default
	Default move assignment operator. More...

virtual NearestNeighborQueryResult< T, N >	Nearest (const Vector< double, N > &pt, const NearestNeighborDistanceFunc< T, N > &distanceFunc) const =0

Detailed Description

template<typename T>
class CubbyFlow::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>

using CubbyFlow::Quadtree< T >::ConstIterator = typename ContainerType::const_iterator

◆ ContainerType

template<typename T>

using CubbyFlow::Quadtree< T >::ContainerType = std::vector<T>

◆ Iterator

template<typename T>

using CubbyFlow::Quadtree< T >::Iterator = typename ContainerType::iterator

Constructor & Destructor Documentation

◆ Quadtree() [1/3]

template<typename T>

CubbyFlow::Quadtree< T >::Quadtree ( )

default

Default constructor.

◆ Quadtree() [2/3]

template<typename T>

CubbyFlow::Quadtree< T >::Quadtree ( const Quadtree< T > & )

default

Default copy constructor.

◆ Quadtree() [3/3]

template<typename T>

CubbyFlow::Quadtree< T >::Quadtree ( Quadtree< T > && )

defaultnoexcept

Default move constructor.

◆ ~Quadtree()

template<typename T>

virtual CubbyFlow::Quadtree< T >::~Quadtree ( )

virtualdefault

Default virtual destructor.

Member Function Documentation

◆ begin() [1/2]

template<typename T >

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

Returns the begin iterator of the item.

◆ begin() [2/2]

template<typename T >

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

Returns the immutable begin iterator of the item.

◆ Build()

template<typename T>

void CubbyFlow::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.

◆ Clear()

template<typename T >

void CubbyFlow::Quadtree< T >::Clear ( )

Clears all the contents of this instance.

◆ ClosestIntersection()

template<typename T>

ClosestIntersectionQueryResult2< T > CubbyFlow::Quadtree< T >::ClosestIntersection	(	const Ray2D &	ray,
		const GetRayIntersectionFunc2< T > &	testFunc
	)		const

override

Returns the closest intersection for given ray.

◆ end() [1/2]

template<typename T >

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

Returns the end iterator of the item.

◆ end() [2/2]

template<typename T >

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

Returns the immutable end iterator of the item.

◆ ForEachIntersectingItem() [1/2]

template<typename T>

void CubbyFlow::Quadtree< T >::ForEachIntersectingItem	(	const BoundingBox2D &	box,
		const BoxIntersectionTestFunc2< T > &	testFunc,
		const IntersectionVisitorFunc< T > &	visitorFunc
	)		const

override

Invokes visitorFunc for every intersecting items.

◆ ForEachIntersectingItem() [2/2]

template<typename T>

void CubbyFlow::Quadtree< T >::ForEachIntersectingItem	(	const Ray2D &	ray,
		const RayIntersectionTestFunc2< T > &	testFunc,
		const IntersectionVisitorFunc< T > &	visitorFunc
	)		const

override

Invokes visitorFunc for every intersecting items.

◆ GetBoundingBox()

template<typename T >

const BoundingBox2D & CubbyFlow::Quadtree< T >::GetBoundingBox ( ) const

Returns the bounding box of this quadtree.

◆ GetChildIndex()

template<typename T >

size_t CubbyFlow::Quadtree< T >::GetChildIndex	(	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.

◆ GetItem()

template<typename T >

const T & CubbyFlow::Quadtree< T >::GetItem ( size_t i ) const

Returns the item at i.

◆ GetItemsAtNode()

template<typename T >

const std::vector< size_t > & CubbyFlow::Quadtree< T >::GetItemsAtNode ( size_t nodeIdx ) const

Returns the list of the items for given node index.

◆ GetMaxDepth()

template<typename T >

size_t CubbyFlow::Quadtree< T >::GetMaxDepth ( ) const

Returns the maximum depth of the tree.

◆ GetNumberOfItems()

template<typename T >

size_t CubbyFlow::Quadtree< T >::GetNumberOfItems ( ) const

Returns the number of items.

◆ GetNumberOfNodes()

template<typename T >

size_t CubbyFlow::Quadtree< T >::GetNumberOfNodes ( ) const

Returns the number of quadtree nodes.

◆ Intersects() [1/2]

template<typename T>

bool CubbyFlow::Quadtree< T >::Intersects	(	const BoundingBox2D &	box,
		const BoxIntersectionTestFunc2< T > &	testFunc
	)		const

override

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

◆ Intersects() [2/2]

template<typename T>

bool CubbyFlow::Quadtree< T >::Intersects	(	const Ray2D &	ray,
		const RayIntersectionTestFunc2< T > &	testFunc
	)		const

override

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

◆ Nearest()

template<typename T>

NearestNeighborQueryResult2< T > CubbyFlow::Quadtree< T >::Nearest	(	const Vector2D &	pt,
		const NearestNeighborDistanceFunc2< T > &	distanceFunc
	)		const

override

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

◆ operator=() [1/2]

template<typename T>

Quadtree& CubbyFlow::Quadtree< T >::operator= ( const Quadtree< T > & )

default

Default copy assignment operator.

◆ operator=() [2/2]

template<typename T>

Quadtree& CubbyFlow::Quadtree< T >::operator= ( Quadtree< T > && )

defaultnoexcept

Default move assignment operator.

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

Core/Geometry/Quadtree.hpp
Core/Geometry/Quadtree-Impl.hpp

Public Types

Public Member Functions

Detailed Description

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

Member Typedef Documentation

◆ ConstIterator

◆ ContainerType

◆ Iterator

Constructor & Destructor Documentation

◆ Quadtree() [1/3]

◆ Quadtree() [2/3]

◆ Quadtree() [3/3]

◆ ~Quadtree()

Member Function Documentation

◆ begin() [1/2]

◆ begin() [2/2]

◆ Build()

◆ Clear()

◆ ClosestIntersection()

◆ end() [1/2]

◆ end() [2/2]

◆ ForEachIntersectingItem() [1/2]

◆ ForEachIntersectingItem() [2/2]

◆ GetBoundingBox()

◆ GetChildIndex()

◆ GetItem()

◆ GetItemsAtNode()

◆ GetMaxDepth()

◆ GetNumberOfItems()

◆ GetNumberOfNodes()

◆ Intersects() [1/2]

◆ Intersects() [2/2]

◆ Nearest()

◆ operator=() [1/2]

◆ operator=() [2/2]

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