numeric::kdtree Namespace Reference

Classes
class	HyperRectangle
class	KDNode
class	KDPoint
class	CompareKDPoints
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::VirtualBaseOP > 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

HyperRectangleOP

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

KDNodeCOP

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

KDNodeOP

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

KDPointCOP

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

KDPointOP

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

KDTreeCOP

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

KDTreeOP

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

WrappedReal

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

WrappedRealOP

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

Function Documentation

construct_kd_tree()

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.

References basic::options::OptionKeys::frags::depth, and basic::options::OptionKeys::mp::visualize::width.

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

get_percentile_bounds()

HyperRectangleOP numeric::kdtree::get_percentile_bounds

(

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

points

)

References test_terpenes::lower, max(), min(), p_end, and test_terpenes::upper.

Referenced by main(), and transform_percentile().

hr_intersects_hs()

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 test_terpenes::lower, numeric::kdtree::HyperRectangle::lower(), ObjexxFCL::pow(), create_a3b_hbs::r, test_terpenes::upper, and numeric::kdtree::HyperRectangle::upper().

Referenced by nearest_neighbor(), and nearest_neighbors().

is_legal_greater_than()

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().

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.

is_legal_less_than()

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().

make_points() [1/2]

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().

make_points() [2/2]

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

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

References data, and p_end.

nearest_neighbor() [1/2]

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(), test_terpenes::lower, numeric::kdtree::HyperRectangle::lower(), min(), numeric::nearest(), nearest_neighbor(), REALLY_BIG_DISTANCE(), sq_vec_distance(), test_terpenes::upper, and numeric::kdtree::HyperRectangle::upper().

nearest_neighbor() [2/2]

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(), numeric::nearest(), REALLY_BIG_DISTANCE(), and numeric::kdtree::KDTree::root().

Referenced by nearest_neighbor().

nearest_neighbors() [1/3]

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::HyperRectangle::lower(), min(), nearest_neighbors(), basic::options::OptionKeys::frags::contacts::neighbors, sq_vec_distance(), and numeric::kdtree::HyperRectangle::upper().

nearest_neighbors() [2/3]

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 main(), and nearest_neighbors().

nearest_neighbors() [3/3]

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().

operator<<()

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

output operator for vector1< Real >

References erraser_single_res_analysis::out.

print_point()

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

Referenced by print_points(), and print_tree().

print_points()

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

References print_point().

print_tree()

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

References utility::io::oc::cout, create_a3b_hbs::ii, print_point(), and basic::options::OptionKeys::mp::visualize::width.

REALLY_BIG_DISTANCE()

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

(

1e20

)

Referenced by nearest_neighbor(), and nearest_neighbors().

sq_vec_distance()

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.

References dist().

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

transform_percentile() [1/2]

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().

transform_percentile() [2/2]

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

References test_terpenes::lower, max(), min(), p_end, and test_terpenes::upper.

Referenced by main(), and transform_percentile().

transform_percentile_single_pt()

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

References test_terpenes::lower, p_end, and test_terpenes::upper.

Referenced by main().

vec_distance()

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().