Quadtree-based space subdivision container, optimized for intersection queries between 2D axis-aligned boxes. More...

#include <donut/LooseQuadtree.hpp>

Public Types
using	value_type = T

using	reference = T &

using	const_reference = const T &

using	pointer = T *

using	const_pointer = const T *

using	size_type = std::size_t

using	iterator = Iterator< false >

using	const_iterator = Iterator< true >

using	difference_type = typename std::iterator_traits< iterator >::difference_type

Public Member Functions
	LooseQuadtree (const Box< 2, float > &worldBoundingBox, vec2 typicalBoxSize) noexcept
	Construct an empty tree.

void	reset (const Box< 2, float > &worldBoundingBox, vec2 typicalBoxSize) noexcept
	Reset the tree to an empty state with new world parameters.

void	clear () noexcept
	Erase all inserted elements from the tree.

template<typename... Args>
std::pair< iterator, bool >	emplace (const Box< 2, float > &elementBoundingBox, Args &&... args)
	Try to construct a new element in the tree.

std::pair< iterator, bool >	insert (const Box< 2, float > &elementBoundingBox, const T &value)
	Try to copy an element into the tree.

std::pair< iterator, bool >	insert (const Box< 2, float > &elementBoundingBox, T &&value)
	Try to move an element into the tree.

T &	operator[] (const Box< 2, float > &elementBoundingBox)
	Try to default-construct a new element in the tree and get a reference to it.

void	erase (const_iterator pos) noexcept
	Remove an element from the tree.

template<typename Callback , typename Predicate >
constexpr auto	traverseActiveNodes (Callback &&callback, Predicate &&predicate) const
	Execute a callback function for each active node of the tree, including empty branch nodes without an element.

template<typename Callback >
constexpr auto	traverseActiveNodes (Callback &&callback) const
	Execute a callback function for each active node of the tree, including empty branch nodes without an element.

template<typename Callback , typename Predicate >
constexpr auto	traverseElementNodes (Callback &&callback, Predicate &&predicate) const
	Execute a callback function for each active node of the tree that has an element.

template<typename Callback >
constexpr auto	traverseElementNodes (Callback &&callback) const
	Execute a callback function for each active node of the tree that has an element.

template<typename Callback , typename Predicate >
constexpr auto	traverseElements (Callback &&callback, Predicate &&predicate) const
	Execute a callback function for each element in the tree.

template<typename Callback >
constexpr auto	traverseElements (Callback &&callback) const
	Execute a callback function for each element in the tree.

template<typename Callback >
auto	test (vec2 point, Callback &&callback) const
	Execute a callback function for each element in the tree that might contain a given point.

bool	test (vec2 point) const noexcept
	Check if it is possible that some element in the tree contains a given point.

template<typename Callback >
auto	test (const Box< 2, float > &box, Callback &&callback) const
	Execute a callback function for each element in the tree that might be intersecting with a given axis-aligned box.

bool	test (const Box< 2, float > &box) const noexcept
	Check if it is possible that some element in the tree is intersecting with a given axis-aligned box.

Detailed Description

template<typename T>
class donut::LooseQuadtree< T >

Quadtree-based space subdivision container, optimized for intersection queries between 2D axis-aligned boxes.

Template Parameters

T	type of element to store in the tree.

Member Typedef Documentation

◆ value_type

template<typename T >

using donut::LooseQuadtree< T >::value_type = T

◆ reference

template<typename T >

using donut::LooseQuadtree< T >::reference = T&

◆ const_reference

template<typename T >

using donut::LooseQuadtree< T >::const_reference = const T&

◆ pointer

template<typename T >

using donut::LooseQuadtree< T >::pointer = T*

◆ const_pointer

template<typename T >

using donut::LooseQuadtree< T >::const_pointer = const T*

◆ size_type

template<typename T >

using donut::LooseQuadtree< T >::size_type = std::size_t

◆ iterator

template<typename T >

using donut::LooseQuadtree< T >::iterator = Iterator<false>

◆ const_iterator

template<typename T >

using donut::LooseQuadtree< T >::const_iterator = Iterator<true>

◆ difference_type

template<typename T >

using donut::LooseQuadtree< T >::difference_type = typename std::iterator_traits<iterator>::difference_type

Constructor & Destructor Documentation

◆ LooseQuadtree()

template<typename T >

donut::LooseQuadtree< T >::LooseQuadtree	(	const Box< 2, float > &	worldBoundingBox,
		vec2	typicalBoxSize
	)

inlinenoexcept

Construct an empty tree.

Parameters

worldBoundingBox	bounding box of the world, or the full region that contains all other possible axis-aligned boxes that may be inserted into the tree.
typicalBoxSize	minimum threshold for the size of a leaf quadrant. This should correspond roughly to the typical size of the boxes that will be inserted into the tree.

Member Function Documentation

◆ reset()

template<typename T >

void donut::LooseQuadtree< T >::reset	(	const Box< 2, float > &	worldBoundingBox,
		vec2	typicalBoxSize
	)

inlinenoexcept

Reset the tree to an empty state with new world parameters.

Parameters

worldBoundingBox	bounding box of the world, or the full region that contains all other possible axis-aligned boxes that may be inserted into the tree.
typicalBoxSize	minimum threshold for the size of a leaf quadrant. This should correspond roughly to the typical size of the boxes that will be inserted into the tree.

See also: clear()

◆ clear()

template<typename T >

void donut::LooseQuadtree< T >::clear ( )

inlinenoexcept

Erase all inserted elements from the tree.

See also: reset(); erase()

◆ emplace()

template<typename T >

template<typename... Args>

std::pair< iterator, bool > donut::LooseQuadtree< T >::emplace	(	const Box< 2, float > &	elementBoundingBox,
		Args &&...	args
	)

inline

Try to construct a new element in the tree.

Parameters

elementBoundingBox	axis-aligned bounding box of the element.
args	constructor arguments for the new element.

Returns

a pair where:

the first element contains an iterator to the newly inserted element, or to the existing element if one was already occupying the corresponding tree node, and
the second element contains a bool that is true if an element was successfully inserted, or false if an existing element was already occupying the corresponding tree node.

Exceptions

std::bad_alloc	on allocation failure.
any	exception thrown by the element constructor.

Note: To store multiple values in the same node of the tree, use a list-like type for the element type T, such as std::vector, std::forward_list or some intrusive linked list between the values.

See also: insert(); operator[]()

◆ insert() [1/2]

template<typename T >

std::pair< iterator, bool > donut::LooseQuadtree< T >::insert	(	const Box< 2, float > &	elementBoundingBox,
		const T &	value
	)

inline

Try to copy an element into the tree.

Parameters

elementBoundingBox	axis-aligned bounding box of the element.
value	value to be copied into the tree.

Returns

a pair where:

the first element contains an iterator to the newly inserted element, or to the existing element if one was already occupying the corresponding tree node, and
the second element contains a bool that is true if an element was successfully inserted, or false if an existing element was already occupying the corresponding tree node.

Exceptions

std::bad_alloc	on allocation failure.
any	exception thrown by the element copy constructor.

Note: To store multiple values in the same node of the tree, use a list-like type for the element type T, such as std::vector, std::forward_list or some intrusive linked list between the values.

See also: emplace(); operator[]()

◆ insert() [2/2]

template<typename T >

std::pair< iterator, bool > donut::LooseQuadtree< T >::insert	(	const Box< 2, float > &	elementBoundingBox,
		T &&	value
	)

inline

Try to move an element into the tree.

Parameters

elementBoundingBox	axis-aligned bounding box of the element.
value	value to be moved into the tree.

Returns

a pair where:

the first element contains an iterator to the newly inserted element, or to the existing element if one was already occupying the corresponding tree node, and
the second element contains a bool that is true if an element was successfully inserted, or false if an existing element was already occupying the corresponding tree node.

Exceptions

std::bad_alloc	on allocation failure.
any	exception thrown by the element move constructor.

Note: To store multiple values in the same node of the tree, use a list-like type for the element type T, such as std::vector, std::forward_list or some intrusive linked list between the values.

See also: emplace(); operator[]()

◆ operator[]()

template<typename T >

T & donut::LooseQuadtree< T >::operator[] ( const Box< 2, float > & elementBoundingBox )

inline

Try to default-construct a new element in the tree and get a reference to it.

Parameters

elementBoundingBox axis-aligned bounding box of the element.

Returns: a reference to the newly inserted element, or to the existing element if one was already occupying the corresponding tree node.

Exceptions

std::bad_alloc	on allocation failure.
any	exception thrown by the element default constructor.

Note: To store multiple values in the same node of the tree, use a list-like type for the element type T, such as std::vector, std::forward_list or some intrusive linked list between the values.

See also: emplace(); insert()

◆ erase()

template<typename T >

void donut::LooseQuadtree< T >::erase ( const_iterator pos )

inlinenoexcept

Remove an element from the tree.

Parameters

pos	iterator to the element to remove. Must be valid.

See also: clear()

◆ traverseActiveNodes() [1/2]

template<typename T >

template<typename Callback , typename Predicate >

constexpr auto donut::LooseQuadtree< T >::traverseActiveNodes	(	Callback &&	callback,
		Predicate &&	predicate
	)		const

inlineconstexpr

Execute a callback function for each active node of the tree, including empty branch nodes without an element.

Parameters

callback

function to execute, which should accept the following parameters (though they don't need to be used):

const donut::Box<2, float>& looseBounds: an axis-aligned box that defines the region that an element's bounding box must be fully contained within in order to belong to the node.
const T* element: a non-owning read-only pointer to the element occupying the node, or nullptr if it does not have one.

The callback function should return either void or a bool that specifies whether to stop the traversal or not. A value of true means to stop and return early, while a value of false means to continue traversing.

predicate

condition that must be met in order to traverse deeper into the tree. Should accept the following parameter:

const donut::Box<2, float>& looseBounds: an axis-aligned box that defines the region that an element's bounding box must be fully contained within in order to belong to the next node.

The predicate function should return a bool that is true if the next node should be traversed, or false if the branch should be ignored.

Returns: void if the callback function returns void, true if the callback returns bool and exited early, false if the callback function returns bool but didn't exit early.

Exceptions

std::bad_alloc	on allocation failure.
any	exception thrown by the callback function or predicate function.

Note: The order of traversal is unspecified, though it is guaranteed that outer nodes will be visited before their own inner nodes that they contain.

Warning: Although it is const, this function is not thread-safe since it mutates an internal memory cache. Exclusive access is therefore required for safety.

See also: traverseElementNodes(); traverseElements(); test()

◆ traverseActiveNodes() [2/2]

template<typename T >

template<typename Callback >

constexpr auto donut::LooseQuadtree< T >::traverseActiveNodes ( Callback && callback ) const

inlineconstexpr

Execute a callback function for each active node of the tree, including empty branch nodes without an element.

Parameters

callback

function to execute, which should accept the following parameters (though they don't need to be used):

const donut::Box<2, float>& looseBounds: an axis-aligned box that defines the region that an element's bounding box must be fully contained within in order to belong to the node.
const T* element: a non-owning read-only pointer to the element occupying the node, or nullptr if it does not have one.

The callback function should return either void or a bool that specifies whether to stop the traversal or not. A value of true means to stop and return early, while a value of false means to continue traversing.

Returns: void if the callback function returns void, true if the callback returns bool and exited early, false if the callback function returns bool but didn't exit early.

Exceptions

std::bad_alloc	on allocation failure.
any	exception thrown by the callback function.

Note: The order of traversal is unspecified, though it is guaranteed that outer nodes will be visited before their own inner nodes that they contain.

Warning: Although it is const, this function is not thread-safe since it mutates an internal memory cache. Exclusive access is therefore required for safety.

See also: traverseElementNodes(); traverseElements(); test()

◆ traverseElementNodes() [1/2]

template<typename T >

template<typename Callback , typename Predicate >

constexpr auto donut::LooseQuadtree< T >::traverseElementNodes	(	Callback &&	callback,
		Predicate &&	predicate
	)		const

inlineconstexpr

Execute a callback function for each active node of the tree that has an element.

Parameters

callback

function to execute, which should accept the following parameters (though they don't need to be used):

const donut::Box<2, float>& looseBounds: an axis-aligned box that defines the region that an element's bounding box must be fully contained within in order to belong to the node.
const T& element: a read-only reference to the element occupying the node.

The callback function should return either void or a bool that specifies whether to stop the traversal or not. A value of true means to stop and return early, while a value of false means to continue traversing.

predicate

condition that must be met in order to traverse deeper into the tree. Should accept the following parameter:

const donut::Box<2, float>& looseBounds: an axis-aligned box that defines the region that an element's bounding box must be fully contained within in order to belong to the next node.

The predicate function should return a bool that is true if the next node should be traversed, or false if the branch should be ignored.

Returns: void if the callback function returns void, true if the callback returns bool and exited early, false if the callback function returns bool but didn't exit early.

Exceptions

std::bad_alloc	on allocation failure.
any	exception thrown by the callback function or predicate function.

Note: The order of traversal is unspecified, though it is guaranteed that outer nodes will be visited before their own inner nodes that they contain.

Warning: Although it is const, this function is not thread-safe since it mutates an internal memory cache. Exclusive access is therefore required for safety.

See also: traverseActiveNodes(); traverseElements(); test()

◆ traverseElementNodes() [2/2]

template<typename T >

template<typename Callback >

constexpr auto donut::LooseQuadtree< T >::traverseElementNodes ( Callback && callback ) const

inlineconstexpr

Execute a callback function for each active node of the tree that has an element.

Parameters

callback

function to execute, which should accept the following parameters (though they don't need to be used):

const donut::Box<2, float>& looseBounds: an axis-aligned box that defines the region that an element's bounding box must be fully contained within in order to belong to the node.
const T& element: a read-only reference to the element occupying the node.

The callback function should return either void or a bool that specifies whether to stop the traversal or not. A value of true means to stop and return early, while a value of false means to continue traversing.

Returns: void if the callback function returns void, true if the callback returns bool and exited early, false if the callback function returns bool but didn't exit early.

Exceptions

std::bad_alloc	on allocation failure.
any	exception thrown by the callback function.

Note: The order of traversal is unspecified, though it is guaranteed that outer nodes will be visited before their own inner nodes that they contain.

Warning: Although it is const, this function is not thread-safe since it mutates an internal memory cache. Exclusive access is therefore required for safety.

See also: traverseActiveNodes(); traverseElements(); test()

◆ traverseElements() [1/2]

template<typename T >

template<typename Callback , typename Predicate >

constexpr auto donut::LooseQuadtree< T >::traverseElements	(	Callback &&	callback,
		Predicate &&	predicate
	)		const

inlineconstexpr

Execute a callback function for each element in the tree.

Parameters

callback

function to execute, which should accept the following parameter:

const T& element: a read-only reference to the element.

The callback function should return either void or a bool that specifies whether to stop the traversal or not. A value of true means to stop and return early, while a value of false means to continue traversing.

predicate

condition that must be met in order to traverse deeper into the tree. Should accept the following parameter:

const donut::Box<2, float>& looseBounds: an axis-aligned box that defines the region that an element's bounding box must be fully contained within in order to belong to the next node.

The predicate function should return a bool that is true if the next node should be traversed, or false if the branch should be ignored.

Returns: void if the callback function returns void, true if the callback returns bool and exited early, false if the callback function returns bool but didn't exit early.

Exceptions

std::bad_alloc	on allocation failure.
any	exception thrown by the callback function or predicate function.

Note: The order of traversal is unspecified, though it is guaranteed that outer nodes will be visited before their own inner nodes that they contain.

Warning: Although it is const, this function is not thread-safe since it mutates an internal memory cache. Exclusive access is therefore required for safety.

See also: traverseActiveNodes(); traverseElementNodes(); test()

◆ traverseElements() [2/2]

template<typename T >

template<typename Callback >

constexpr auto donut::LooseQuadtree< T >::traverseElements ( Callback && callback ) const

inlineconstexpr

Execute a callback function for each element in the tree.

Parameters

callback

function to execute, which should accept the following parameter:

const T& element: a read-only reference to the element.

The callback function should return either void or a bool that specifies whether to stop the traversal or not. A value of true means to stop and return early, while a value of false means to continue traversing.

Returns: void if the callback function returns void, true if the callback returns bool and exited early, false if the callback function returns bool but didn't exit early.

Exceptions

std::bad_alloc	on allocation failure.
any	exception thrown by the callback function.

Note: The order of traversal is unspecified, though it is guaranteed that outer nodes will be visited before their own inner nodes that they contain.

Warning: Although it is const, this function is not thread-safe since it mutates an internal memory cache. Exclusive access is therefore required for safety.

See also: traverseActiveNodes(); traverseElementNodes(); test()

◆ test() [1/4]

template<typename T >

template<typename Callback >

auto donut::LooseQuadtree< T >::test	(	vec2	point,
		Callback &&	callback
	)		const

inline

Execute a callback function for each element in the tree that might contain a given point.

Parameters

point	point to test.
callback	function to execute, which should accept the following parameter: `const T& element`: a read-only reference to the element. The callback function should return either void or a bool that specifies whether to stop the traversal or not. A value of true means to stop and return early, while a value of false means to continue traversing.

Returns: void if the callback function returns void, true if the callback returns bool and exited early, false if the callback function returns bool but didn't exit early.

Exceptions

std::bad_alloc	on allocation failure.
any	exception thrown by the callback function.

Note: The order of traversal is unspecified, though it is guaranteed that outer nodes will be visited before their own inner nodes that they contain.

Warning: Although it is const, this function is not thread-safe since it mutates an internal memory cache. Exclusive access is therefore required for safety.

See also: traverseActiveNodes(); traverseElementNodes(); traverseElements()

◆ test() [2/4]

template<typename T >

bool donut::LooseQuadtree< T >::test ( vec2 point ) const

inlinenoexcept

Check if it is possible that some element in the tree contains a given point.

Parameters

point point to test.

Returns: true if some element might contain the point, false otherwise.

Exceptions

std::bad_alloc on allocation failure.

Warning: Although it is const, this function is not thread-safe since it mutates an internal memory cache. Exclusive access is therefore required for safety.

See also: traverseActiveNodes(); traverseElementNodes(); traverseElements()

◆ test() [3/4]

template<typename T >

template<typename Callback >

auto donut::LooseQuadtree< T >::test	(	const Box< 2, float > &	box,
		Callback &&	callback
	)		const

inline

Execute a callback function for each element in the tree that might be intersecting with a given axis-aligned box.

Parameters

box	box to test.
callback	function to execute, which should accept the following parameter: `const T& element`: a read-only reference to the element. The callback function should return either void or a bool that specifies whether to stop the traversal or not. A value of true means to stop and return early, while a value of false means to continue traversing.

Returns: void if the callback function returns void, true if the callback returns bool and exited early, false if the callback function returns bool but didn't exit early.

Exceptions

std::bad_alloc	on allocation failure.
any	exception thrown by the callback function.

Note: The order of traversal is unspecified, though it is guaranteed that outer nodes will be visited before their own inner nodes that they contain.

Warning: Although it is const, this function is not thread-safe since it mutates an internal memory cache. Exclusive access is therefore required for safety.

See also: traverseActiveNodes(); traverseElementNodes(); traverseElements()

◆ test() [4/4]

template<typename T >

bool donut::LooseQuadtree< T >::test ( const Box< 2, float > & box ) const

inlinenoexcept

Check if it is possible that some element in the tree is intersecting with a given axis-aligned box.

Parameters

box	box to test.

Returns: true if some element might be intersecting with the box, false otherwise.

Exceptions

std::bad_alloc on allocation failure.

Warning: Although it is const, this function is not thread-safe since it mutates an internal memory cache. Exclusive access is therefore required for safety.

See also: traverseActiveNodes(); traverseElementNodes(); traverseElements()

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

include/donut/LooseQuadtree.hpp

Public Types

Public Member Functions

Detailed Description

Member Typedef Documentation

◆ value_type

◆ reference

◆ const_reference

◆ pointer

◆ const_pointer

◆ size_type

◆ iterator

◆ const_iterator

◆ difference_type

Constructor & Destructor Documentation

◆ LooseQuadtree()

Member Function Documentation

◆ reset()

◆ clear()

◆ emplace()

◆ insert() [1/2]

◆ insert() [2/2]

◆ operator[]()

◆ erase()

◆ traverseActiveNodes() [1/2]

◆ traverseActiveNodes() [2/2]

◆ traverseElementNodes() [1/2]

◆ traverseElementNodes() [2/2]

◆ traverseElements() [1/2]

◆ traverseElements() [2/2]

◆ test() [1/4]

◆ test() [2/4]

◆ test() [3/4]

◆ test() [4/4]