Garfield::KDTree Class Reference

#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
void	n_nearest_around_point (const unsigned int idx, const unsigned int ndecorrel, const unsigned int nn, std::vector< KDTreeResult > &result) const
void	r_nearest (const std::vector< double > &qv, const double r2, std::vector< KDTreeResult > &result) const
void	r_nearest_around_point (const unsigned int idx, const unsigned int ndecorrel, const double r2, std::vector< KDTreeResult > &result) const

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

Friends
class	KDTreeNode

Detailed Description

Main k-d tree class. Fast search of points in k-dimensional Euclidean space.

Definition at line 34 of file KDTree.hh.

Constructor & Destructor Documentation

KDTree() [1/2]

Garfield::KDTree::KDTree ( )

delete

KDTree() [2/2]

Garfield::KDTree::KDTree

(

KDTreeArray &

data_in

)

Constructor.

Definition at line 35 of file KDTree.cc.

  : m_data(data_in) {
 
  const size_t n = data_in.size(); 
  if (!data_in.empty()) {
    m_dim = data_in[0].size();
  } 
 
  m_ind.resize(n);
  for (size_t i = 0; i < n; i++) m_ind[i] = i; 
  // Build the tree.
  m_root = build_tree_for_range(0, n - 1, 0); 
}

~KDTree()

Garfield::KDTree::~KDTree

(

)

Destructor.

Definition at line 50 of file KDTree.cc.

                {
  delete m_root;
}

Member Function Documentation

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

Definition at line 174 of file KDTree.cc.

                                                              {
  // Search for n nearest to a given query vector 'qv'.
  std::priority_queue<KDTreeResult> res; 
  double r2 = std::numeric_limits<double>::max();
  m_root->search_n(-1, 0, nn, r2, qv, *this, res);
  result.clear();
  while (!res.empty()) {
    result.push_back(res.top());
    res.pop();
  }
  if (sort_results) sort(result.begin(), result.end());
}

Referenced by Garfield::ComponentComsol::Initialise(), Garfield::ComponentComsol::SetDelayedWeightingPotential(), and Garfield::ComponentComsol::SetWeightingField().

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

Definition at line 189 of file KDTree.cc.

                                                                           {
 
  std::priority_queue<KDTreeResult> res;
  double r2 = std::numeric_limits<double>::max();
  m_root->search_n(idx, ndecorrel, nn, r2, m_data[idx], *this, res);
  result.clear(); 
  while (!res.empty()) {
    result.push_back(res.top());
    res.pop();
  }
  if (sort_results) sort(result.begin(), result.end());
}

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

Definition at line 205 of file KDTree.cc.

                                                              {
  // Search for all within a ball of a certain radius.
  result.clear(); 
  m_root->search_r(-1, 0, r2, qv, *this, result);
  if (sort_results) sort(result.begin(), result.end());
} 

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.

Definition at line 213 of file KDTree.cc.

                                                                           {
 
  result.clear(); 
  m_root->search_r(idx, ndecorrel, r2, m_data[idx], *this, result);
  if (sort_results) sort(result.begin(), result.end());
}

Friends And Related Function Documentation

KDTreeNode

friend class KDTreeNode

friend

Definition at line 83 of file KDTree.hh.

Member Data Documentation

m_data

const KDTreeArray& Garfield::KDTree::m_data

Definition at line 37 of file KDTree.hh.

Referenced by n_nearest_around_point(), and r_nearest_around_point().

m_dim

size_t Garfield::KDTree::m_dim

Definition at line 39 of file KDTree.hh.

Referenced by KDTree().

sort_results

bool Garfield::KDTree::sort_results = false

Definition at line 40 of file KDTree.hh.

Referenced by n_nearest(), n_nearest_around_point(), r_nearest(), and r_nearest_around_point().

---

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

• KDTree.hh
• KDTree.cc