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

◆ 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 k_d_tree::KdTree< Dim, Component, Id >::ids, and k_d_tree::KdTree< Dim, Component, Id >::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 k_d_tree::KdTree< Dim, Component, Id >::ids, k_d_tree::KdTree< Dim, Component, Id >::init(), and k_d_tree::KdTree< Dim, Component, Id >::items.

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 k_d_tree::KdTree< Dim, Component, Id >::cap(), k_d_tree::KdTree< Dim, Component, Id >::deleted, k_d_tree::KdTree< Dim, Component, Id >::ids, k_d_tree::KdTree< Dim, Component, Id >::init(), k_d_tree::KdTree< Dim, Component, Id >::items, and k_d_tree::KdTree< Dim, Component, Id >::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 k_d_tree::KdTree< Dim, Component, Id >::items.

Referenced by k_d_tree::KdTree< Dim, Component, Id >::KdTree(), k_d_tree::KdTree< Dim, Component, Id >::foreach(), and k_d_tree::KdTree< Dim, Component, Id >::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 k_d_tree::KdTree< Dim, Component, Id >::cap(), k_d_tree::KdTree< Dim, Component, Id >::deleted, k_d_tree::KdTree< Dim, Component, Id >::ids, and k_d_tree::KdTree< Dim, Component, Id >::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 k_d_tree::KdTree< Dim, Component, Id >::deleted, k_d_tree::KdTree< Dim, Component, Id >::init(), k_d_tree::SortedIndices< Dim >::split(), split(), and k_d_tree::KdTree< Dim, Component, Id >::tree.

Referenced by k_d_tree::KdTree< Dim, Component, Id >::KdTree(), k_d_tree::KdTree< Dim, Component, Id >::KdTree(), and k_d_tree::KdTree< Dim, Component, Id >::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 k_d_tree::KdTree< Dim, Component, Id >::rangeQuery().

Referenced by k_d_tree::KdTree< Dim, Component, Id >::rangeQuery(), and k_d_tree::KdTree< Dim, Component, Id >::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 k_d_tree::KdTree< Dim, Component, Id >::cap(), k_d_tree::KdTree< Dim, Component, Id >::deleted, k_d_tree::KdTree< Dim, Component, Id >::ids, k_d_tree::KdTree< Dim, Component, Id >::items, k_d_tree::KdTree< Dim, Component, Id >::rangeQuery(), split(), and k_d_tree::KdTree< Dim, Component, Id >::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 k_d_tree::KdTree< Dim, Component, Id >::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 k_d_tree::KdTree< Dim, Component, Id >::KdTree(), k_d_tree::KdTree< Dim, Component, Id >::foreach(), k_d_tree::KdTree< Dim, Component, Id >::init(), k_d_tree::KdTree< Dim, Component, Id >::rangeQuery(), and k_d_tree::KdTree< Dim, Component, Id >::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 k_d_tree::KdTree< Dim, Component, Id >::KdTree(), k_d_tree::KdTree< Dim, Component, Id >::KdTree(), k_d_tree::KdTree< Dim, Component, Id >::KdTree(), k_d_tree::KdTree< Dim, Component, Id >::foreach(), and k_d_tree::KdTree< Dim, Component, Id >::rangeQuery().

◆ items

template<uint8_t Dim, class Component , class Id >

SortedPoints<Dim, Component> k_d_tree::KdTree< Dim, Component, Id >::items

private

Referenced by k_d_tree::KdTree< Dim, Component, Id >::KdTree(), k_d_tree::KdTree< Dim, Component, Id >::KdTree(), k_d_tree::KdTree< Dim, Component, Id >::cap(), k_d_tree::KdTree< Dim, Component, Id >::foreach(), and k_d_tree::KdTree< Dim, Component, Id >::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 k_d_tree::KdTree< Dim, Component, Id >::KdTree(), k_d_tree::KdTree< Dim, Component, Id >::KdTree(), k_d_tree::KdTree< Dim, Component, Id >::init(), and k_d_tree::KdTree< Dim, Component, Id >::rangeQuery().

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

util/k_d_tree.h

Public Types

Public Member Functions

Private Member Functions

Private Attributes

Member Typedef Documentation

◆ Point

Constructor & Destructor Documentation

◆ KdTree() [1/4]

◆ KdTree() [2/4]

◆ KdTree() [3/4]

◆ KdTree() [4/4]

Member Function Documentation

◆ cap()

◆ foreach()

◆ init()

◆ rangeQuery() [1/2]

◆ rangeQuery() [2/2]

◆ remove()

Member Data Documentation

◆ deleted

◆ ids

◆ items

◆ tree