Rosetta  2020.46
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
Classes | Typedefs | Functions
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< KDPointOPmake_points (utility::vector1< utility::vector1< numeric::Real > > const &points)
 Makes a vector of KDPoints. More...
 
utility::vector1< KDPointOPmake_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

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

References basic::options::OptionKeys::mp::visualize::width.

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

HyperRectangleOP numeric::kdtree::get_percentile_bounds ( utility::vector1< utility::vector1< numeric::Real > > &  points)
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(), utility::lower(), ObjexxFCL::pow(), numeric::kdtree::HyperRectangle::upper(), and utility::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)
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::VirtualBaseOP > 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(), utility::lower(), min(), nearest_neighbor(), REALLY_BIG_DISTANCE(), sq_vec_distance(), numeric::kdtree::HyperRectangle::upper(), and utility::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 
)
void numeric::kdtree::nearest_neighbors ( KDNodeOP &  current,
utility::vector1< numeric::Real > const &  pt,
HyperRectangle &  bounds,
numeric::Real  max_dist_sq,
KDPointList &  neighbors 
)
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.

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

void numeric::kdtree::print_tree ( std::ostream &  out,
KDNodeOP const &  current,
Size  current_depth,
Size const  width 
)
const numeric::Real numeric::kdtree::REALLY_BIG_DISTANCE ( 1e20  )
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 
)
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().