Garfield::KDTree Class Reference

Main k-d tree class. More...

#include <KDTree.hh>

Public Member Functions
	KDTree ()=delete
	KDTree (KDTreeArray &data_in)
	Constructor.
	~KDTree ()
	Destructor.
void	n_nearest (const std::vector< double > &qv, const unsigned int nn, std::vector< KDTreeResult > &result) const
	Search for nn nearest neighbours around a point.
void	n_nearest_around_point (const unsigned int idx, const unsigned int ndecorrel, const unsigned int nn, std::vector< KDTreeResult > &result) const
	Search for nn nearest neighbours around a node of the input data, excluding neighbors within a decorrelation interval.
void	r_nearest (const std::vector< double > &qv, const double r2, std::vector< KDTreeResult > &result) const
	Search for all neighbors in a ball of size r2.
void	r_nearest_around_point (const unsigned int idx, const unsigned int ndecorrel, const double r2, std::vector< KDTreeResult > &result) const
	Like r_nearest, but around an existing point, with decorrelation interval.

Public Attributes
const KDTreeArray &	m_data
std::size_t	m_dim = 3
bool	sort_results = false

Private Member Functions
KDTreeNode *	build_tree_for_range (int l, int u, KDTreeNode *parent)
int	select_on_coordinate_value (int c, double alpha, int l, int u)
std::array< double, 2 >	spread_in_coordinate (const int c, const int l, const int u) const

Private Attributes
KDTreeNode *	m_root = nullptr
std::vector< std::size_t >	m_ind

Static Private Attributes
static constexpr int	bucketsize = 12

Friends
class	KDTreeNode

Detailed Description

Main k-d tree class.

Fast search of points in k-dimensional Euclidean space.

Definition at line 33 of file KDTree.hh.

Constructor & Destructor Documentation

KDTree() [1/2]

Garfield::KDTree::KDTree ( )

delete

KDTree() [2/2]

Garfield::KDTree::KDTree

(

KDTreeArray &

data_in

)

Constructor.

~KDTree()

Garfield::KDTree::~KDTree

(

)

Destructor.

Member Function Documentation

build_tree_for_range()

KDTreeNode * Garfield::KDTree::build_tree_for_range ( int l, int u, KDTreeNode * parent )

private

n_nearest()

void Garfield::KDTree::n_nearest	(	const std::vector< double > &	qv,
		const unsigned int	nn,
		std::vector< KDTreeResult > &	result ) const

Search for nn nearest neighbours around a point.

Parameters

qv	input point
nn	number of nearest neighbours
result	indices and distances of the nearest neighbours

n_nearest_around_point()

void Garfield::KDTree::n_nearest_around_point	(	const unsigned int	idx,
		const unsigned int	ndecorrel,
		const unsigned int	nn,
		std::vector< KDTreeResult > &	result ) const

Search for nn nearest neighbours around a node of the input data, excluding neighbors within a decorrelation interval.

Parameters

idx	index of the input point
ndecorrel	decorrelation interval
nn	number of nearest neighbours
result	indices and distances of the nearest neighbours

r_nearest()

void Garfield::KDTree::r_nearest	(	const std::vector< double > &	qv,
		const double	r2,
		std::vector< KDTreeResult > &	result ) const

Search for all neighbors in a ball of size r2.

Parameters

qv	input point
r2	ball size (square Euclidean distance)
result	indices and distances of the nearest neighbours

r_nearest_around_point()

void Garfield::KDTree::r_nearest_around_point	(	const unsigned int	idx,
		const unsigned int	ndecorrel,
		const double	r2,
		std::vector< KDTreeResult > &	result ) const

Like r_nearest, but around an existing point, with decorrelation interval.

select_on_coordinate_value()

int Garfield::KDTree::select_on_coordinate_value ( int c, double alpha, int l, int u )

private

spread_in_coordinate()

std::array< double, 2 > Garfield::KDTree::spread_in_coordinate ( const int c, const int l, const int u ) const

private

Friends And Related Symbol Documentation

KDTreeNode

friend class KDTreeNode

friend

Definition at line 82 of file KDTree.hh.

Member Data Documentation

bucketsize

int Garfield::KDTree::bucketsize = 12

staticconstexprprivate

Definition at line 91 of file KDTree.hh.

m_data

const KDTreeArray& Garfield::KDTree::m_data

Definition at line 36 of file KDTree.hh.

m_dim

std::size_t Garfield::KDTree::m_dim = 3

Definition at line 38 of file KDTree.hh.

m_ind

std::vector<std::size_t> Garfield::KDTree::m_ind

private

Definition at line 89 of file KDTree.hh.

m_root

KDTreeNode* Garfield::KDTree::m_root = nullptr

private

Definition at line 85 of file KDTree.hh.

sort_results

bool Garfield::KDTree::sort_results = false

Definition at line 39 of file KDTree.hh.

---

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

• /builds/garfield/docs/source/Include/Garfield/KDTree.hh