Generic quadtree data structure. More...

#include <Core/Geometry/Quadtree.h>

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 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 >	GetNearestNeighbor (const Vector2D &pt, const NearestNeighborDistanceFunc2< T > &distanceFunc) const override

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

bool	IsIntersects (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 >	GetClosestIntersection (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 noide 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...

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()

template<typename T >

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

Default constructor.

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.

◆ 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 IntersectionVisitorFunc2< T > &	visitorFunc
	)		const

overridevirtual

Invokes visitorFunc for every intersecting items.

Implements CubbyFlow::IntersectionQueryEngine2< T >.

◆ ForEachIntersectingItem() [2/2]

template<typename T >

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

overridevirtual

Invokes visitorFunc for every intersecting items.

Implements CubbyFlow::IntersectionQueryEngine2< T >.

◆ 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.

◆ GetClosestIntersection()

template<typename T >

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

overridevirtual

Returns the closest intersection for given ray.

Implements CubbyFlow::IntersectionQueryEngine2< T >.

◆ 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 noide index.

◆ GetMaxDepth()

template<typename T >

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

Returns the maximum depth of the tree.

◆ GetNearestNeighbor()

template<typename T >

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

overridevirtual

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

Implements CubbyFlow::NearestNeighborQueryEngine2< T >.

◆ 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.

◆ IsIntersects() [1/2]

template<typename T >

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

overridevirtual

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

Implements CubbyFlow::IntersectionQueryEngine2< T >.

◆ IsIntersects() [2/2]

template<typename T >

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

overridevirtual

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

Implements CubbyFlow::IntersectionQueryEngine2< T >.

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

Core/Geometry/Quadtree.h
Core/Geometry/Quadtree-Impl.h

Public Types

Public Member Functions

Detailed Description

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

Member Typedef Documentation

◆ ConstIterator

◆ ContainerType

◆ Iterator

Constructor & Destructor Documentation

◆ Quadtree()

Member Function Documentation

◆ begin() [1/2]

◆ begin() [2/2]

◆ Build()

◆ Clear()

◆ end() [1/2]

◆ end() [2/2]

◆ ForEachIntersectingItem() [1/2]

◆ ForEachIntersectingItem() [2/2]

◆ GetBoundingBox()

◆ GetChildIndex()

◆ GetClosestIntersection()

◆ GetItem()

◆ GetItemsAtNode()

◆ GetMaxDepth()

◆ GetNearestNeighbor()

◆ GetNumberOfItems()

◆ GetNumberOfNodes()

◆ IsIntersects() [1/2]

◆ IsIntersects() [2/2]

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