Cover Tree. Allows for insertion, removal, and k-nearest-neighbor queries.
The user should define double Point::distance(const Point& p) and bool Point::operator==(const Point& p), where p1.distance(p2)==0 doesn't necessarily mean that p1==p2).
For example, a point could consist of a vector and a string name, where their distance measure is simply euclidean distance but to be equal they must have the same name in addition to having distance 0.
Definition at line 52 of file CoverTree.h.
Classes | |
class | CoverTreeNode |
Public Member Functions | |
CoverTree (const double &maxDist, const std::vector< Point > &points=std::vector< Point >()) | |
~CoverTree () | |
bool | isValidTree () const |
void | insert (const Point &newPoint) |
void | remove (const Point &p) |
std::vector< Point > | kNearestNeighbors (const Point &p, const unsigned int &k) const |
CoverTreeNode * | getRoot () const |
Static Public Attributes | |
static const double | base = 2.0 |
CoverTree | ( | const double & | maxDist, | |
const std::vector< Point > & | points = std::vector<Point>() | |||
) |
Constructs a cover tree which begins with all points in points.
maxDist should be the maximum distance that any two points can have between each other. IE p.distance(q) < maxDist for all p,q that you will ever try to insert. The cover tree may be invalid if an inaccurate maxDist is given.
Definition at line 185 of file CoverTree.h.
~CoverTree | ( | ) |
Definition at line 199 of file CoverTree.h.
CoverTree< Point >::CoverTreeNode * getRoot | ( | ) | const |
void insert | ( | const Point & | newPoint | ) |
Insert newPoint into the cover tree. If newPoint is already present, (that is, newPoint==p for some p already in the tree), then the tree is unchanged. If p.distance(newPoint)==0.0 but newPoint!=p, then newPoint WILL be inserted and both points may be returned in k-nearest- neighbor searches.
Definition at line 437 of file CoverTree.h.
bool isValidTree | ( | ) | const |
Just for testing/debugging. Returns true iff the cover tree satisfies the the covering tree invariants (every node in level i is greater than base^i distance from every other node, and every node in level i is less than or equal to base^i distance from its children). See the cover tree papers for details.
Definition at line 608 of file CoverTree.h.
std::vector< Point > kNearestNeighbors | ( | const Point & | p, | |
const unsigned int & | k | |||
) | const |
Returns the k nearest points to p in order (the 0th element of the vector is closest to p, 1th is next, etc). It may return greater than k points if there is a tie for the kth place.
Definition at line 501 of file CoverTree.h.
void remove | ( | const Point & | p | ) |
Remove point p from the cover tree. If p is not present in the tree, it will remain unchanged. Otherwise, this will remove exactly one point q from the tree satisfying p==q.
Definition at line 460 of file CoverTree.h.
const double base = 2.0 [static] |
base level of cover tree
Definition at line 126 of file CoverTree.h.