libdonut
2.3.2
Application framework for cross-platform game development in C++20
|
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. More... | |
void | reset (const Box< 2, float > &worldBoundingBox, vec2 typicalBoxSize) noexcept |
Reset the tree to an empty state with new world parameters. More... | |
void | clear () noexcept |
Erase all inserted elements from the tree. More... | |
template<typename... Args> | |
std::pair< iterator, bool > | emplace (const Box< 2, float > &elementBoundingBox, Args &&... args) |
Try to construct a new element in the tree. More... | |
std::pair< iterator, bool > | insert (const Box< 2, float > &elementBoundingBox, const T &value) |
Try to copy an element into the tree. More... | |
std::pair< iterator, bool > | insert (const Box< 2, float > &elementBoundingBox, T &&value) |
Try to move an element into the tree. More... | |
T & | operator[] (const Box< 2, float > &elementBoundingBox) |
Try to default-construct a new element in the tree and get a reference to it. More... | |
void | erase (const_iterator pos) noexcept |
Remove an element from the tree. More... | |
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. More... | |
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. More... | |
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. More... | |
template<typename Callback > | |
constexpr auto | traverseElementNodes (Callback &&callback) const |
Execute a callback function for each active node of the tree that has an element. More... | |
template<typename Callback , typename Predicate > | |
constexpr auto | traverseElements (Callback &&callback, Predicate &&predicate) const |
Execute a callback function for each element in the tree. More... | |
template<typename Callback > | |
constexpr auto | traverseElements (Callback &&callback) const |
Execute a callback function for each element in the tree. More... | |
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. More... | |
bool | test (vec2 point) const noexcept |
Check if it is possible that some element in the tree contains a given point. More... | |
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. More... | |
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. More... | |
Quadtree-based space subdivision container, optimized for intersection queries between 2D axis-aligned boxes.
T | type of element to store in the tree. |
using donut::LooseQuadtree< T >::value_type = T |
using donut::LooseQuadtree< T >::reference = T& |
using donut::LooseQuadtree< T >::const_reference = const T& |
using donut::LooseQuadtree< T >::pointer = T* |
using donut::LooseQuadtree< T >::const_pointer = const T* |
using donut::LooseQuadtree< T >::size_type = std::size_t |
using donut::LooseQuadtree< T >::iterator = Iterator<false> |
using donut::LooseQuadtree< T >::const_iterator = Iterator<true> |
using donut::LooseQuadtree< T >::difference_type = typename std::iterator_traits<iterator>::difference_type |
|
inlinenoexcept |
Construct an empty tree.
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. |
|
inlinenoexcept |
Reset the tree to an empty state with new world 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. |
|
inlinenoexcept |
|
inline |
Try to construct a new element in the tree.
elementBoundingBox | axis-aligned bounding box of the element. |
args | constructor arguments for the new element. |
std::bad_alloc | on allocation failure. |
any | exception thrown by the element constructor. |
|
inline |
Try to copy an element into the tree.
elementBoundingBox | axis-aligned bounding box of the element. |
value | value to be copied into the tree. |
std::bad_alloc | on allocation failure. |
any | exception thrown by the element copy constructor. |
|
inline |
Try to move an element into the tree.
elementBoundingBox | axis-aligned bounding box of the element. |
value | value to be moved into the tree. |
std::bad_alloc | on allocation failure. |
any | exception thrown by the element move constructor. |
|
inline |
Try to default-construct a new element in the tree and get a reference to it.
elementBoundingBox | axis-aligned bounding box of the element. |
std::bad_alloc | on allocation failure. |
any | exception thrown by the element default constructor. |
|
inlinenoexcept |
Remove an element from the tree.
pos | iterator to the element to remove. Must be valid. |
|
inlineconstexpr |
Execute a callback function for each active node of the tree, including empty branch nodes without an element.
callback | function to execute, which should accept the following parameters (though they don't need to be used):
|
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:
|
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.
std::bad_alloc | on allocation failure. |
any | exception thrown by the callback function or predicate function. |
|
inlineconstexpr |
Execute a callback function for each active node of the tree, including empty branch nodes without an element.
callback | function to execute, which should accept the following parameters (though they don't need to be used):
|
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.
std::bad_alloc | on allocation failure. |
any | exception thrown by the callback function. |
|
inlineconstexpr |
Execute a callback function for each active node of the tree that has an element.
callback | function to execute, which should accept the following parameters (though they don't need to be used):
|
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:
|
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.
std::bad_alloc | on allocation failure. |
any | exception thrown by the callback function or predicate function. |
|
inlineconstexpr |
Execute a callback function for each active node of the tree that has an element.
callback | function to execute, which should accept the following parameters (though they don't need to be used):
|
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.
std::bad_alloc | on allocation failure. |
any | exception thrown by the callback function. |
|
inlineconstexpr |
Execute a callback function for each element in the tree.
callback | function to execute, which should accept the following parameter:
|
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:
|
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.
std::bad_alloc | on allocation failure. |
any | exception thrown by the callback function or predicate function. |
|
inlineconstexpr |
Execute a callback function for each element in the tree.
callback | function to execute, which should accept the following parameter:
|
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.
std::bad_alloc | on allocation failure. |
any | exception thrown by the callback function. |
|
inline |
Execute a callback function for each element in the tree that might contain a given point.
point | point to test. |
callback | function to execute, which should accept the following parameter:
|
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.
std::bad_alloc | on allocation failure. |
any | exception thrown by the callback function. |
|
inlinenoexcept |
Check if it is possible that some element in the tree contains a given point.
point | point to test. |
std::bad_alloc | on allocation failure. |
|
inline |
Execute a callback function for each element in the tree that might be intersecting with a given axis-aligned box.
box | box to test. |
callback | function to execute, which should accept the following parameter:
|
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.
std::bad_alloc | on allocation failure. |
any | exception thrown by the callback function. |
|
inlinenoexcept |
Check if it is possible that some element in the tree is intersecting with a given axis-aligned box.
box | box to test. |
std::bad_alloc | on allocation failure. |