Geometry::KDTree Class Reference

A kd-tree or a node of one. More...

#include <KDTree.h>

Classes
struct	Point

Public Member Functions
	KDTree (const std::vector< Point > &pts, int k, int depth=0, int maxDepth=100)
	KDTree (const KDTree &)=delete
	can't use copy constructor or assignment operation
const KDTree &	operator= (const KDTree &) const =delete
bool	IsLeaf () const
int	MaxDepth () const
int	MinDepth () const
int	MaxLeafSize () const
	max/min number of points in leaves of tree
int	MinLeafSize () const
int	TreeSize () const
	Number of nodes in tree.
KDTree *	Insert (const Vector &p, int id, int maxLeafPoints=2)
	inserts a point, splitting leaf nodes with the indicated number of points
KDTree *	Locate (const Vector &p)
	finds the kdtree leaf in which this point is located
bool	Split (int dimension=-1)
void	Join ()
	Joints the point lists in two subtrees so that this node becomes a leaf.
void	Clear ()
	Clears the tree.
int	ClosestPoint (const Vector &pt, Real &dist) const
	returns the index of the closest point to pt, and its distance in dist
int	ClosestPoint (const Vector &pt, Real n, const Vector &w, Real &dist) const
	same, but uses the L-n norm with optional weights w
int	PointWithin (const Vector &pt, Real &dist) const
void	ClosePoints (const Vector &pt, Real radius, std::vector< Real > &distances, std::vector< int > &ids) const
	computes the set of points within the given radius
void	ClosePoints (const Vector &pt, Real radius, Real n, const Vector &w, std::vector< Real > &distances, std::vector< int > &ids) const
	same, but uses the L-n norm with weights w
void	KClosestPoints (const Vector &pt, int k, Real *dist, int *idx) const
void	KClosestPoints (const Vector &pt, int k, Real n, const Vector &w, Real *dist, int *idx) const
	same, but uses the L-n norm with weights w

Static Public Member Functions
static KDTree *	Create (const std::vector< Vector > &p, int k, int maxDepth)
	Creates a kdtree with the given points, dimension k, and max depth.
static Real	Select (const std::vector< Point > &S, int d, int k)
	gives a split value (in dim d) that gives the k'th value in the list

Detailed Description

A kd-tree or a node of one.

A whole kd-tree is created from the return value of KDTree::Create(). At the end of its life, delete it.

Members:

• splitDim: the split dimension
• splitVal: the split value
• pos: the node on the positive side of val (that is, the node storing all points x with x(d)>val)
• neg: the node on the negative side of val
• pts: if this is a leaf, the set of points contained within

XXXXX this note doesnt apply anymore... referencing was problematic XXXXX NOTE: To avoid unnecessary copying, kd-trees only store REFERENCES to the Vectors that are given as input. As a result you must store them in some auxiliary data structure. XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Member Function Documentation

void KDTree::KClosestPoints	(	const Vector &	pt,
		int	k,
		Real *	dist,
		int *	idx
	)		const

returns the indices and distances of the k closest points to pt. dist and idx are assumed to point to arrays of length k.

Referenced by Geometry::NearestNeighborGraph().

int KDTree::PointWithin	(	const Vector &	pt,
		Real &	dist
	)		const

returns the index of the closest point within distance dist of pt. dist is set to the distance of the new closest point. returns -1 if there is no point within dist.

bool KDTree::Split

(

int

dimension = -1

)

Splits the points along the given dimension, returns true if there's actually a split. If dimension is left default, one is picked at random

References Math::RandInt().

Referenced by Insert().

---

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

• KDTree.h
• KDTree.cpp