Geometry::KDTree< KeyT, ValT > Class Template Reference

A classic K-D tree. More...

#include <KDTree.h>

List of all members.

Classes
class	Comp
struct	KDNode
	KDNode struct represents node in KD tree.
Public Member Functions
	KDTree ()
void	insert (const KeyT &key, const ValT &val)
void	build ()
bool	closest_point (const KeyT &p, ScalarType &dist, KeyT &k, ValT &v) const
int	in_sphere (const KeyType &p, ScalarType dist, std::vector< KeyT > &keys, std::vector< ValT > &vals) const

---

Detailed Description

template<class KeyT, class ValT>
class Geometry::KDTree< KeyT, ValT >

A classic K-D tree.

A K-D tree is a good data structure for storing points in space and for nearest neighbour queries. It is basically a generalized binary tree in K dimensions.

---

Constructor & Destructor Documentation

template<class KeyT , class ValT >

Geometry::KDTree< KeyT, ValT >::KDTree

(

)

[inline]

Build tree from vector of keys passed as argument.

---

Member Function Documentation

template<class KeyT , class ValT >

void Geometry::KDTree< KeyT, ValT >::build

(

)

[inline]

Build the tree. After this function has been called, it is no longer legal to insert elements, but you can perform searches.

template<class KeyT , class ValT >

bool Geometry::KDTree< KeyT, ValT >::closest_point	(	const KeyT &	p,
		ScalarType &	dist,
		KeyT &	k,
		ValT &	v
	)		const [inline]

Find the key value pair closest to the key given as first argument. The second argument is the maximum search distance. Upon return this value is changed to the distance to the found point. The final two arguments contain the closest key and its associated value upon return.

template<class KeyT , class ValT >

int Geometry::KDTree< KeyT, ValT >::in_sphere	(	const KeyType &	p,
		ScalarType	dist,
		std::vector< KeyT > &	keys,
		std::vector< ValT > &	vals
	)		const [inline]

Find all the elements within a given radius (second argument) of the key (first argument). The key value pairs inside the sphere are returned in a pair of vectors passed as the two last arguments. Note that we don't resize the two last arguments to zero - so either they should be empty vectors or you should desire appending the newly found elements onto these vectors.

template<class KeyT , class ValT >

void Geometry::KDTree< KeyT, ValT >::insert	(	const KeyT &	key,
		const ValT &	val
	)		[inline]

Insert a key value pair into the tree. Note that the tree needs to be built - by calling the build function - before you can search.

---

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

• /Users/jab/Documents/Teaching/02585/GEL2_and_demos/GEL/src/Geometry/KDTree.h