source: issm/trunk-jpl/src/c/classes/kriging/Covertree.h@ 19153

Last change on this file since 19153 was 19153, checked in by Mathieu Morlighem, 11 years ago

BUG: fixed kriging for covertree
File size: 4.2 KB
Line 
1
2#ifndef _COVERTREE_H
3#define _COVERTREE_H
4
5#include <map>
6class Observation;
7
8class Covertree{
9
10 /* Cover tree node. Consists of arbitrarily many points P, as long as they
11 * have distance 0 to each other. Keeps track of its children. */
12 class CoverTreeNode{
13 private:
14 //_childMap[i] is a vector of the node's children at level i
15 std::map<int,std::vector<CoverTreeNode*> > _childMap;
16 //_observations is all of the points with distance 0 which are not equal.
17 std::vector<Observation> _observations;
18 public:
19 CoverTreeNode(const Observation& o);
20 /**
21 * Returns the children of the node at level i. Note that this means
22 * the children exist in cover set i-1, not level i.
23 *
24 * Does not include the node itself, though technically every node
25 * has itself as a child in a cover tree.
26 */
27 std::vector<CoverTreeNode*> getChildren(int level) const;
28 void addChild(int level, CoverTreeNode* p);
29 void removeChild(int level, CoverTreeNode* p);
30 void addObservation(const Observation& o);
31 void removeObservation(const Observation& o);
32 const std::vector<Observation>& getObservations() { return _observations; }
33 double distance(const CoverTreeNode& p) const;
34 bool isSingle() const;
35 bool hasObservation(const Observation& o) const;
36 const Observation& getObservation() const;
37
38 /**
39 * Return every child of the node from any level. This is handy for
40 * the destructor.
41 */
42 std::vector<CoverTreeNode*> getAllChildren() const;
43 }; // CoverTreeNode class
44 private:
45 typedef std::pair<double, CoverTreeNode*> distNodePair;
46
47 CoverTreeNode *_root;
48 unsigned int _numNodes;
49 int _maxLevel; //base^_maxLevel should be the max distance
50 //between any 2 points
51 int _minLevel; //A level beneath which there are no more new nodes.
52
53 std::vector<CoverTreeNode*> kNearestNodes(const Observation& o, const unsigned int& k) const;
54 /**
55 * Recursive implementation of the insert algorithm (see paper).
56 */
57 bool insert_rec(const Observation& p, const std::vector<distNodePair>& Qi,const int& level);
58
59 /* Finds the node in Q with the minimum distance to p. Returns a pair
60 * consisting of this node and the distance. */
61 distNodePair distance(const Observation& p,const std::vector<CoverTreeNode*>& Q);
62
63
64 void remove_rec(const Observation& p, std::map<int,std::vector<distNodePair> >& coverSets, int level, bool& multi);
65
66 public:
67 double base;
68
69 /**
70 * Constructs a cover tree which begins with all points in points.
71 *
72 * maxDist should be the maximum distance that any two points
73 * can have between each other. IE p.distance(q) < maxDist for all
74 * p,q that you will ever try to insert. The cover tree may be invalid
75 * if an inaccurate maxDist is given.
76 */
77
78 Covertree(int maxDist,const std::vector<Observation>& points=std::vector<Observation>());
79 ~Covertree();
80
81 /**
82 * Just for testing/debugging. Returns true iff the cover tree satisfies the
83 * the covering tree invariants (every node in level i is greater than base^i
84 * distance from every other node, and every node in level i is less than
85 * or equal to base^i distance from its children). See the cover tree
86 * papers for details.
87 */
88 bool isValidTree() const;
89
90 /**
91 * Insert newPoint into the cover tree. If newPoint is already present,
92 * (that is, newPoint==p for some p already in the tree), then the tree
93 * is unchanged. If p.distance(newPoint)==0.0 but newPoint!=p, then
94 * newPoint WILL be inserted and both points may be returned in k-nearest-
95 * neighbor searches.
96 */
97 void insert(const Observation& newObservation);
98
99 /**
100 * Remove point p from the cover tree. If p is not present in the tree,
101 * it will remain unchanged. Otherwise, this will remove exactly one
102 * point q from the tree satisfying p==q.
103 */
104 void remove(const Observation& p);
105
106 /**
107 * Returns the k nearest points to p in order (the 0th element of the vector
108 * is closest to p, 1th is next, etc). It may return greater than k points
109 * if there is a tie for the kth place.
110 */
111 std::vector<Observation> kNearestNeighbors(const Observation& p, const unsigned int& k) const;
112
113 int get_numberofobs();
114
115 CoverTreeNode* getRoot() const;
116
117 /**
118 * Print the cover tree.
119 */
120 void print() const;
121};
122#endif //_COVERTREE_H
Note: See TracBrowser for help on using the repository browser.