KrisLibrary  1.0.0
Public Types | Public Member Functions | Public Attributes | List of all members
Geometry::BallTree Class Reference

Public Types

typedef std::function< double(const Vector &, const Vector &)> Metric
 
typedef std::function< void(const Vector &, const Vector &, Real, Vector &)> Interpolator
 

Public Member Functions

 BallTree (Metric metric, int numSplitsPerNode=2)
 
 BallTree (Metric metric, Interpolator interpolator, int numSplitsPerNode=2)
 
int MaxDepth () const
 depth statistics
 
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.
 
void Build (const std::vector< Vector > &p, int maxDepth)
 Creates the data structure with the given points and max depth.
 
BallTreeNodeInsert (const Vector &p, int id, int maxLeafPoints=-1)
 inserts a point, splitting leaf nodes with the indicated number of points More...
 
bool Split (BallTreeNode *node)
 Splits the points in a leaf node. More...
 
void Join (BallTreeNode *node)
 Joins the point lists in subtrees of node so that this node becomes a leaf.
 
void Fit (BallTreeNode *node, bool tight)
 Re-fits the node to the points therein.
 
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 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 KClosestPoints (const Vector &pt, int k, Real *dist, int *idx) const
 

Public Attributes

Metric metric
 
BallTreeNode root
 
Interpolator interpolator
 
bool cartesian
 
int splitsPerNode
 

Member Function Documentation

BallTreeNode * BallTree::Insert ( const Vector p,
int  id,
int  maxLeafPoints = -1 
)

inserts a point, splitting leaf nodes with the indicated number of points

inserts a point, splitting leaf nodes with the indicated number of points. If maxLeafPoints = -1, then this is split when 2*splitsPerNode points are in each node.

void BallTree::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.

int BallTree::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 BallTree::Split ( BallTreeNode node)

Splits the points in a leaf node.

Splits the points in a leaf node. right now this is really simple, and only splits on the longest axis. More sophisticated schemes would use SVD, or K-means

References Math::AABBGrow().


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