numeric::kdtree Namespace Reference

Classes
class	CompareKDPoints
class	HyperRectangle
class	KDNode
class	KDPoint
struct	KDPoint_MinDist
class	KDPointList
	Class for keeping track of the closest N KDPoint objects by distance. More...
class	KDTree
class	WrappedPrimitive

Typedefs
typedef utility::pointer::shared_ptr < HyperRectangle >	HyperRectangleOP
typedef utility::pointer::shared_ptr < KDNode >	KDNodeOP
typedef utility::pointer::shared_ptr < KDNode const >	KDNodeCOP
typedef utility::pointer::shared_ptr < KDPoint >	KDPointOP
typedef utility::pointer::shared_ptr < KDPoint const >	KDPointCOP
typedef utility::pointer::shared_ptr < KDTree >	KDTreeOP
typedef utility::pointer::shared_ptr < KDTree const >	KDTreeCOP
typedef WrappedPrimitive < numeric::Real >	WrappedReal
typedef utility::pointer::shared_ptr < WrappedReal >	WrappedRealOP

Functions
numeric::Real	sq_vec_distance (utility::vector1< numeric::Real > const &vec1, utility::vector1< numeric::Real > const &vec2)
	distance metrics for real-valued points More...
numeric::Real	vec_distance (utility::vector1< numeric::Real > const &vec1, utility::vector1< numeric::Real > const &vec2)
	Returns the Euclidean distance between the two points vec1 and vec2. More...
const numeric::Real	REALLY_BIG_DISTANCE (1e20)
KDNodeOP	construct_kd_tree (utility::vector1< KDPointOP > &points, numeric::Size depth, KDTree &tree)
	Function for constructing a KDTree. Returns a KDNodeOP that represents the root of the tree. Points need to be sorted as the tree is being constructed, so the reference to the points is non-const. More...
std::ostream &	operator<< (std::ostream &out, const utility::vector1< numeric::Real > &points)
	output operator for vector1< Real > More...
void	nearest_neighbor (KDTree &tree, utility::vector1< numeric::Real > const &pt,KDNodeOP &nearest, numeric::Real &dist_sq)
	Searches the KDtree for the nearest neigbor to a given input point, returns nearest neighbor and distance-squared to nearest neigbor by reference. More...
KDPointList	nearest_neighbors (KDTree &tree, utility::vector1< numeric::Real > const &pt, Size const wanted)
	Returns a KDPointList of the N nearest neighbors from the KDTree to the given input point. More...
KDPointList	nearest_neighbors (KDTree &tree, utility::vector1< numeric::Real > const &pt, Size const wanted, numeric::Real const max_dist_allowed)
void	nearest_neighbors (KDNodeOP &current, utility::vector1< numeric::Real > const &pt, HyperRectangle &bounds, numeric::Real max_dist_sq,KDPointList &neighbors)
	Recursive function definition for search for a list of the N nearest neighbors, where N is defined as a member variable of the KDPointList object. More...
void	nearest_neighbor (KDNodeOP &current, utility::vector1< numeric::Real > const &pt, HyperRectangle &bounds, numeric::Real max_dist_sq,KDNodeOP &nearest, numeric::Real &dist_sq)
	returns the nearest neighbor to the given point. More...
HyperRectangleOP	get_percentile_bounds (utility::vector1< utility::vector1< numeric::Real > > &points)
void	transform_percentile_single_pt (utility::vector1< numeric::Real > &point, HyperRectangleOP bounds)
void	transform_percentile (utility::vector1< utility::vector1< numeric::Real > > &points, HyperRectangleOP bounds)
void	transform_percentile (utility::vector1< utility::vector1< numeric::Real > > &points)
	distance metrics for real-valued points More...
utility::vector1< KDPointOP >	make_points (utility::vector1< utility::vector1< numeric::Real > > const &points)
	Makes a vector of KDPoints. More...
utility::vector1< KDPointOP >	make_points (utility::vector1< utility::vector1< numeric::Real > > const &points, utility::vector1< utility::pointer::ReferenceCountOP > const &data)
	Makes a vector1 of KDPoints, associating the nth entry in data with the nth entry in points. More...
void	print_points (std::ostream &out, utility::vector1< utility::vector1< numeric::Real > > const &points)
void	print_point (std::ostream &out, utility::vector1< numeric::Real > const &point)
bool	hr_intersects_hs (HyperRectangle hr, utility::vector1< numeric::Real > const &pt, numeric::Real const r)
	returns true if the given hyper-rectangle intersects with the given hypersphere. More...
void	print_tree (std::ostream &out, KDNodeOP const &current, Size current_depth, Size const width)
bool	is_legal_kdtree_below_node (KDNodeOP const &current)
bool	is_legal_less_than (KDNodeOP const &current, Size const axis, Real const value)
bool	is_legal_greater_than (KDNodeOP const &current, Size const axis, Real const value)

Typedef Documentation

typedef utility::pointer::shared_ptr< HyperRectangle > numeric::kdtree::HyperRectangleOP

typedef utility::pointer::shared_ptr< KDNode const > numeric::kdtree::KDNodeCOP

typedef utility::pointer::shared_ptr< KDNode > numeric::kdtree::KDNodeOP

typedef utility::pointer::shared_ptr< KDPoint const > numeric::kdtree::KDPointCOP

typedef utility::pointer::shared_ptr< KDPoint > numeric::kdtree::KDPointOP

typedef utility::pointer::shared_ptr< KDTree const > numeric::kdtree::KDTreeCOP

typedef utility::pointer::shared_ptr< KDTree > numeric::kdtree::KDTreeOP

typedef WrappedPrimitive< numeric::Real > numeric::kdtree::WrappedReal

typedef utility::pointer::shared_ptr< WrappedReal > numeric::kdtree::WrappedRealOP

Function Documentation

KDNodeOP numeric::kdtree::construct_kd_tree	(	utility::vector1< KDPointOP > &	points,
		numeric::Size	depth,
		KDTree &	tree
	)

Function for constructing a KDTree. Returns a KDNodeOP that represents the root of the tree. Points need to be sorted as the tree is being constructed, so the reference to the points is non-const.

Referenced by numeric::kdtree::KDTree::KDTree().

HyperRectangleOP numeric::kdtree::get_percentile_bounds

(

utility::vector1< utility::vector1< numeric::Real > > &

points

)

References basic::options::OptionKeys::end, max(), and min().

Referenced by transform_percentile().

bool numeric::kdtree::hr_intersects_hs	(	HyperRectangle	hr,
		utility::vector1< numeric::Real > const &	pt,
		numeric::Real const	r
	)

returns true if the given hyper-rectangle intersects with the given hypersphere.

References numeric::kdtree::HyperRectangle::lower(), and numeric::kdtree::HyperRectangle::upper().

Referenced by nearest_neighbor(), and nearest_neighbors().

bool numeric::kdtree::is_legal_greater_than	(	KDNodeOP const &	current,
		Size const	axis,
		Real const	value
	)

References utility::io::oc::cout, and value.

Referenced by is_legal_kdtree_below_node().

bool numeric::kdtree::is_legal_kdtree_below_node

(

KDNodeOP const &

current

)

References is_legal_greater_than(), is_legal_less_than(), and value.

bool numeric::kdtree::is_legal_less_than	(	KDNodeOP const &	current,
		Size const	axis,
		Real const	value
	)

References utility::io::oc::cout, and value.

Referenced by is_legal_kdtree_below_node().

utility::vector1< KDPointOP > numeric::kdtree::make_points

(

utility::vector1< utility::vector1< numeric::Real > > const &

points

)

Makes a vector of KDPoints.

Referenced by numeric::kdtree::KDTree::KDTree().

utility::vector1< KDPointOP > numeric::kdtree::make_points	(	utility::vector1< utility::vector1< numeric::Real > > const &	points,
		utility::vector1< utility::pointer::ReferenceCountOP > const &	data
	)

Makes a vector1 of KDPoints, associating the nth entry in data with the nth entry in points.

void numeric::kdtree::nearest_neighbor	(	KDTree &	tree,
		utility::vector1< numeric::Real > const &	pt,
		KDNodeOP &	nearest,
		numeric::Real &	dist_sq
	)

Searches the KDtree for the nearest neigbor to a given input point, returns nearest neighbor and distance-squared to nearest neigbor by reference.

References numeric::kdtree::KDTree::bounds(), REALLY_BIG_DISTANCE(), and numeric::kdtree::KDTree::root().

Referenced by nearest_neighbor().

void numeric::kdtree::nearest_neighbor	(	KDNodeOP &	current,
		utility::vector1< numeric::Real > const &	pt,
		HyperRectangle &	bounds,
		numeric::Real	max_dist_sq,
		KDNodeOP &	nearest,
		numeric::Real &	dist_sq
	)

returns the nearest neighbor to the given point.

Parameters are (in order):

• current: the base of the tree
• pt: the point that is being searched against the tree
• bounds: hyper-rectangle in k-space that bounds all points in the tree
• max_dist_sq: maximum squared distance that we care about.
• nearest neighbor (returned by reference)
• squared distance to the nearest neighbor

References hr_intersects_hs(), numeric::kdtree::HyperRectangle::lower(), min(), nearest_neighbor(), REALLY_BIG_DISTANCE(), sq_vec_distance(), and numeric::kdtree::HyperRectangle::upper().

KDPointList numeric::kdtree::nearest_neighbors	(	KDTree &	tree,
		utility::vector1< numeric::Real > const &	pt,
		Size const	wanted
	)

Returns a KDPointList of the N nearest neighbors from the KDTree to the given input point.

References numeric::kdtree::KDTree::bounds(), numeric::nearest(), REALLY_BIG_DISTANCE(), and numeric::kdtree::KDTree::root().

Referenced by nearest_neighbors().

KDPointList numeric::kdtree::nearest_neighbors	(	KDTree &	tree,
		utility::vector1< numeric::Real > const &	pt,
		Size const	wanted,
		numeric::Real const	max_dist_allowed
	)

References numeric::kdtree::KDTree::bounds(), numeric::nearest(), nearest_neighbors(), and numeric::kdtree::KDTree::root().

void numeric::kdtree::nearest_neighbors	(	KDNodeOP &	current,
		utility::vector1< numeric::Real > const &	pt,
		HyperRectangle &	bounds,
		numeric::Real	max_dist_sq,
		KDPointList &	neighbors
	)

Recursive function definition for search for a list of the N nearest neighbors, where N is defined as a member variable of the KDPointList object.

References numeric::kdtree::KDPointList::distance_cutoff(), hr_intersects_hs(), numeric::kdtree::KDPointList::insert(), numeric::kdtree::HyperRectangle::lower(), numeric::kdtree::KDPointList::max_values(), numeric::kdtree::KDPointList::merge(), min(), nearest_neighbors(), sq_vec_distance(), numeric::kdtree::HyperRectangle::upper(), and numeric::kdtree::KDPointList::worst_distance().

std::ostream & numeric::kdtree::operator<<	(	std::ostream &	out,
		const utility::vector1< numeric::Real > &	points
	)

output operator for vector1< Real >

void numeric::kdtree::print_point	(	std::ostream &	out,
		utility::vector1< numeric::Real > const &	point
	)

Referenced by print_points(), and print_tree().

void numeric::kdtree::print_points	(	std::ostream &	out,
		utility::vector1< utility::vector1< numeric::Real > > const &	points
	)

References basic::options::OptionKeys::end, and print_point().

void numeric::kdtree::print_tree	(	std::ostream &	out,
		KDNodeOP const &	current,
		Size	current_depth,
		Size const	width
	)

References utility::io::oc::cout, and print_point().

const numeric::Real numeric::kdtree::REALLY_BIG_DISTANCE

(

1e20

)

Referenced by nearest_neighbor(), and nearest_neighbors().

numeric::Real numeric::kdtree::sq_vec_distance	(	utility::vector1< numeric::Real > const &	vec1,
		utility::vector1< numeric::Real > const &	vec2
	)

distance metrics for real-valued points

Returns the square of the Euclidean distance between the two points vec1 and vec2.

Referenced by nearest_neighbor(), nearest_neighbors(), and vec_distance().

void numeric::kdtree::transform_percentile	(	utility::vector1< utility::vector1< numeric::Real > > &	points,
		HyperRectangleOP	bounds
	)

References basic::options::OptionKeys::end, max(), and min().

Referenced by transform_percentile().

void numeric::kdtree::transform_percentile

(

utility::vector1< utility::vector1< numeric::Real > > &

points

)

distance metrics for real-valued points

Transforms the list of points given into percentiles using a linear mapping from the input space to percentile-space for each variable.

For each variable X in row R, replaces X with the quantity ( X - min(R) ) / ( max(R) - min(R) ). Runs in O(N) time.

References get_percentile_bounds(), and transform_percentile().

void numeric::kdtree::transform_percentile_single_pt	(	utility::vector1< numeric::Real > &	point,
		HyperRectangleOP	bounds
	)

numeric::Real numeric::kdtree::vec_distance	(	utility::vector1< numeric::Real > const &	vec1,
		utility::vector1< numeric::Real > const &	vec2
	)

Returns the Euclidean distance between the two points vec1 and vec2.

References sq_vec_distance().