Luanti 5.16.0-dev
Loading...
Searching...
No Matches
k_d_tree::KdTree< Dim, Component, Id > Class Template Reference

#include <k_d_tree.h>

Collaboration diagram for k_d_tree::KdTree< Dim, Component, Id >:

Public Types

using Point = std::array<Component, Dim>

Public Member Functions

 KdTree ()
 Empty tree.
 KdTree (const Point &point, const Id &id)
 Build a tree containing just a single point.
 KdTree (size_t n, Id const *ids, std::array< Component const *, Dim > pts)
 Build a tree.
 KdTree (const KdTree &a, const KdTree &b)
 Merge two trees. Both trees are assumed to have a power of two size.
template<typename F>
void rangeQuery (const Point &min, const Point &max, const F &cb) const
void remove (Idx internalIdx)
template<class F>
void foreach (F cb) const
size_t cap () const
 Capacity, not size, since some items may be marked as deleted.

Private Member Functions

void init (Idx root, uint8_t axis, const SortedIndices< Dim > &sorted)
template<typename F>
void rangeQuery (size_t root, uint8_t split, const Point &min, const Point &max, const F &cb) const

Private Attributes

SortedPoints< Dim, Component > items
std::unique_ptr< Id[]> ids
std::unique_ptr< Idx[]> tree
std::vector< bool > deleted

Member Typedef Documentation

◆ Point

template<uint8_t Dim, class Component, class Id>
using k_d_tree::KdTree< Dim, Component, Id >::Point = std::array<Component, Dim>

Constructor & Destructor Documentation

◆ KdTree() [1/4]

template<uint8_t Dim, class Component, class Id>
k_d_tree::KdTree< Dim, Component, Id >::KdTree ( )
inline

Empty tree.

References deleted, ids, items, and tree.

Referenced by KdTree().

Here is the caller graph for this function:

◆ KdTree() [2/4]

template<uint8_t Dim, class Component, class Id>
k_d_tree::KdTree< Dim, Component, Id >::KdTree ( const Point & point,
const Id & id )
inline

Build a tree containing just a single point.

References deleted, ids, items, and tree.

◆ KdTree() [3/4]

template<uint8_t Dim, class Component, class Id>
k_d_tree::KdTree< Dim, Component, Id >::KdTree ( size_t n,
Id const * ids,
std::array< Component const *, Dim > pts )
inline

Build a tree.

References deleted, ids, init(), items, and tree.

Here is the call graph for this function:

◆ KdTree() [4/4]

template<uint8_t Dim, class Component, class Id>
k_d_tree::KdTree< Dim, Component, Id >::KdTree ( const KdTree< Dim, Component, Id > & a,
const KdTree< Dim, Component, Id > & b )
inline

Merge two trees. Both trees are assumed to have a power of two size.

References KdTree(), cap(), deleted, ids, init(), items, and tree.

Here is the call graph for this function:

Member Function Documentation

◆ cap()

template<uint8_t Dim, class Component, class Id>
size_t k_d_tree::KdTree< Dim, Component, Id >::cap ( ) const
inline

Capacity, not size, since some items may be marked as deleted.

References items.

Referenced by KdTree(), foreach(), and rangeQuery().

Here is the caller graph for this function:

◆ foreach()

template<uint8_t Dim, class Component, class Id>
template<class F>
void k_d_tree::KdTree< Dim, Component, Id >::foreach ( F cb) const
inline

References cap(), deleted, ids, and items.

Here is the call graph for this function:

◆ init()

template<uint8_t Dim, class Component, class Id>
void k_d_tree::KdTree< Dim, Component, Id >::init ( Idx root,
uint8_t axis,
const SortedIndices< Dim > & sorted )
inlineprivate

References deleted, init(), k_d_tree::SortedIndices< Dim >::split(), split(), and tree.

Referenced by KdTree(), KdTree(), and init().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ rangeQuery() [1/2]

template<uint8_t Dim, class Component, class Id>
template<typename F>
void k_d_tree::KdTree< Dim, Component, Id >::rangeQuery ( const Point & min,
const Point & max,
const F & cb ) const
inline

References rangeQuery().

Referenced by rangeQuery(), and rangeQuery().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ rangeQuery() [2/2]

template<uint8_t Dim, class Component, class Id>
template<typename F>
void k_d_tree::KdTree< Dim, Component, Id >::rangeQuery ( size_t root,
uint8_t split,
const Point & min,
const Point & max,
const F & cb ) const
inlineprivate

References cap(), deleted, ids, items, rangeQuery(), split(), and tree.

Here is the call graph for this function:

◆ remove()

template<uint8_t Dim, class Component, class Id>
void k_d_tree::KdTree< Dim, Component, Id >::remove ( Idx internalIdx)
inline

References deleted.

Member Data Documentation

◆ deleted

template<uint8_t Dim, class Component, class Id>
std::vector<bool> k_d_tree::KdTree< Dim, Component, Id >::deleted
private

Referenced by KdTree(), KdTree(), KdTree(), KdTree(), foreach(), init(), rangeQuery(), and remove().

◆ ids

template<uint8_t Dim, class Component, class Id>
std::unique_ptr<Id[]> k_d_tree::KdTree< Dim, Component, Id >::ids
private

Referenced by KdTree(), KdTree(), KdTree(), KdTree(), foreach(), and rangeQuery().

◆ items

template<uint8_t Dim, class Component, class Id>
SortedPoints<Dim, Component> k_d_tree::KdTree< Dim, Component, Id >::items
private

Referenced by KdTree(), KdTree(), KdTree(), KdTree(), cap(), foreach(), and rangeQuery().

◆ tree

template<uint8_t Dim, class Component, class Id>
std::unique_ptr<Idx[]> k_d_tree::KdTree< Dim, Component, Id >::tree
private

Referenced by KdTree(), KdTree(), KdTree(), KdTree(), init(), and rangeQuery().

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