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.
|CoverTree (const double &maxDist, const std::vector< Point > &points=std::vector< Point >())|
|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 const double||base = 2.0|
|CoverTree||(||const double &||maxDist,|
|const std::vector< Point > &||points =
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.
|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.
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.
|std::vector< Point > kNearestNeighbors||(||const Point &||p,|
|const unsigned int &||k|
|void remove||(||const Point &||p||)|