Template Class KdTree

Class Documentation

template<typename T>
class KdTree

The data for GaussianProcess is stored in a KD tree to facilitate nearest-neighbor searches

Note: I have removed the ability to arbitrarily specify a distance function. The KD Tree nearest neighbor search algorithm only makes sense in the case of Euclidean distances, so I have forced KdTree to use Euclidean distances.

Public Functions

KdTree(const KdTree&)
KdTree &operator=(const KdTree&)
KdTree(KdTree&&)
KdTree &operator=(KdTree&&)
KdTree()
void Initialize(ndarray::Array<T, 2, 2> const &dt)

Build a KD Tree to store the data for GaussianProcess

Parameters

  • [in] dt: an array, the rows of which are the data points (dt[i][j] is the jth component of the ith data point)

Exceptions

  • pex::exceptions::RuntimeError: if the tree is not properly constructed

void findNeighbors(ndarray::Array<int, 1, 1> neighdex, ndarray::Array<double, 1, 1> dd, ndarray::Array<const T, 1, 1> const &v, int n_nn) const

Find the nearest neighbors of a point

neighbors will be returned in ascending order of distance

Parameters

  • [out] neighdex: this is where the indices of the nearest neighbor points will be stored

  • [out] dd: this is where the distances to the nearest neighbors will be stored

  • [in] v: the point whose neighbors you want to find

  • [in] n_nn: the number of nearest neighbors you want to find

note that distance is forced to be the Euclidean distance

T getData(int ipt, int idim) const

Return one element of one node on the tree

Parameters

  • [in] ipt: the index of the node to return

  • [in] idim: the index of the dimension to return

ndarray::Array<T, 1, 1> getData(int ipt) const

Return an entire node from the tree

I currently have this as a return-by-value method. When I tried it as a return-by-reference, the compiler gave me

Parameters

  • [in] ipt: the index of the node to return

warning: returning reference to local temporary object

Based on my reading of Stack Overflow, this is because ndarray was implicitly creating a new ndarray::Array<T,1,1> object and passing a reference thereto. It is unclear to me whether or not this object would be destroyed once the call to getData was complete.

The code still compiled, ran, and passed the unit tests, but the above behavior seemed to me like it could be dangerous (and, because ndarray was still creating a new object, it did not seem like we were saving any time), so I reverted to return-by-value.

void addPoint(ndarray::Array<const T, 1, 1> const &v)

Add a point to the tree. Allot more space in _tree and data if needed.

Parameters

  • [in] v: the point you are adding to the tree

Exceptions

  • pex::exceptions::RuntimeError: if the branch ending in the new point is not properly constructed

void removePoint(int dex)

Remove a point from the tree. Reorganize what remains so that the tree remains self-consistent

Parameters

  • [in] dex: the index of the point you want to remove from the tree

Exceptions

  • pex::exceptions::RuntimeError: if the entire tree is not poperly constructed after the point has been removed

int getNPoints() const

return the number of data points stored in the tree

void getTreeNode(ndarray::Array<int, 1, 1> const &v, int dex) const

Return the _tree information for a given data point

Parameters

  • [out] v: the array in which to store the entry from _tree

  • [in] dex: the index of the node whose information you are requesting