62 std::map<int,std::vector<CoverTreeNode*> > _childMap;
64 std::vector<Point> _points;
66 CoverTreeNode(
const Point& p);
74 std::vector<CoverTreeNode*> getChildren(
int level)
const;
75 void addChild(
int level, CoverTreeNode* p);
76 void removeChild(
int level, CoverTreeNode* p);
77 void addPoint(
const Point& p);
78 void removePoint(
const Point& p);
79 const std::vector<Point>& getPoints() {
return _points; }
80 double distance(
const CoverTreeNode& p)
const;
82 bool isSingle()
const;
83 bool hasPoint(
const Point& p)
const;
85 const Point& getPoint()
const;
91 std::vector<CoverTreeNode*> getAllChildren()
const;
94 typedef std::pair<double, CoverTreeNode*> distNodePair;
97 unsigned int _numNodes;
102 std::vector<CoverTreeNode*>
103 kNearestNodes(
const Point& p,
const unsigned int& k)
const;
107 bool insert_rec(
const Point& p,
108 const std::vector<distNodePair>& Qi,
115 distNodePair distance(
const Point& p,
116 const std::vector<CoverTreeNode*>& Q);
119 void remove_rec(
const Point& p,
120 std::map<
int,std::vector<distNodePair> >& coverSets,
138 const std::vector<Point>& points=std::vector<Point>());
157 void insert(
const Point& newPoint);
164 void remove(
const Point& p);
171 std::vector<Point>
kNearestNeighbors(
const Point& p,
const unsigned int& k)
const;
177 CoverTreeNode*
getRoot()
const;
181 template<
class Po
int>
184 template<
class Po
int>
186 const std::vector<Point>& points)
190 _maxLevel=ceilf(log(maxDist)/log(
base));
191 _minLevel=_maxLevel-1;
192 typename std::vector<Point>::const_iterator it;
193 for(it=points.begin(); it!=points.end(); ++it) {
198 template<
class Po
int>
201 if(_root==NULL)
return;
204 std::vector<CoverTreeNode*> nodes;
205 nodes.push_back(_root);
206 while(!nodes.empty()) {
207 CoverTreeNode* byeNode = nodes[0];
208 nodes.erase(nodes.begin());
209 std::vector<CoverTreeNode*> children = byeNode->getAllChildren();
210 nodes.insert(nodes.begin(),children.begin(),children.end());
217 template<
class Po
int>
218 std::vector<typename CoverTree<Point>::CoverTreeNode*>
221 if(_root==NULL)
return std::vector<CoverTreeNode*>();
224 double maxDist = p.distance(_root->getPoint());
226 std::set<distNodePair> minNodes;
228 minNodes.insert(std::make_pair(maxDist,_root));
229 std::vector<distNodePair> Qj(1,std::make_pair(maxDist,_root));
230 for(
int level = _maxLevel; level>=_minLevel;level--) {
231 typename std::vector<distNodePair>::const_iterator it;
232 int size = Qj.size();
233 for(
int i=0; i<size; i++) {
234 std::vector<CoverTreeNode*> children =
235 Qj[i].second->getChildren(level);
236 typename std::vector<CoverTreeNode*>::const_iterator it2;
237 for(it2=children.begin(); it2!=children.end(); ++it2) {
238 double d = p.distance((*it2)->getPoint());
239 if(d < maxDist || minNodes.size() < k) {
240 minNodes.insert(std::make_pair(d,*it2));
243 if(minNodes.size() > k) minNodes.erase(--minNodes.end());
244 maxDist = (--minNodes.end())->first;
246 Qj.push_back(std::make_pair(d,*it2));
249 double sep = maxDist + pow(
base, level);
251 for(
int i=0; i<size; i++) {
252 if(Qj[i].first > sep) {
260 std::vector<CoverTreeNode*> kNN;
261 typename std::set<distNodePair>::const_iterator it;
262 for(it=minNodes.begin();it!=minNodes.end();++it) {
263 kNN.push_back(it->second);
267 template<
class Po
int>
268 bool CoverTree<Point>::insert_rec(
const Point& p,
269 const std::vector<distNodePair>& Qi,
272 std::vector<std::pair<double, CoverTreeNode*> > Qj;
273 double sep = pow(
base,level);
274 double minDist = DBL_MAX;
275 std::pair<double,CoverTreeNode*> minQiDist(DBL_MAX,NULL);
276 typename std::vector<std::pair<double, CoverTreeNode*> >::const_iterator it;
277 for(it=Qi.begin(); it!=Qi.end(); ++it) {
278 if(it->first<minQiDist.first) minQiDist = *it;
279 if(it->first<minDist) minDist=it->first;
280 if(it->first<=sep) Qj.push_back(*it);
281 std::vector<CoverTreeNode*> children = it->second->getChildren(level);
282 typename std::vector<CoverTreeNode*>::const_iterator it2;
283 for(it2=children.begin();it2!=children.end();++it2) {
284 double d = p.distance((*it2)->getPoint());
285 if(d<minDist) minDist = d;
287 Qj.push_back(std::make_pair(d,*it2));
295 bool found = insert_rec(p,Qj,level-1);
297 if(found && minQiDist.first <= sep) {
298 if(level-1<_minLevel) _minLevel=level-1;
299 minQiDist.second->addChild(level,
300 new CoverTreeNode(p));
311 template<
class Po
int>
312 void CoverTree<Point>::remove_rec(
const Point& p,
313 std::map<
int,std::vector<distNodePair> >& coverSets,
317 std::vector<distNodePair>& Qi = coverSets[level];
318 std::vector<distNodePair>& Qj = coverSets[level-1];
319 double minDist = DBL_MAX;
320 CoverTreeNode* minNode = _root;
321 CoverTreeNode* parent = 0;
322 double sep = pow(
base, level);
323 typename std::vector<distNodePair>::const_iterator it_;
328 for(it_=Qi.begin();it_!=Qi.end();++it_) {
329 std::vector<CoverTreeNode*> children = it_->second->getChildren(level);
330 double dist = it_->first;
333 minNode = it_->second;
338 typename std::vector<CoverTreeNode*>::const_iterator it2;
339 for(it2=children.begin();it2!=children.end();++it2) {
340 dist = p.distance((*it2)->getPoint());
344 if(dist == 0.0) parent = it_->second;
347 Qj.push_back(std::make_pair(dist,*it2));
351 if(level>_minLevel) remove_rec(p,coverSets,level-1,multi);
352 if(minNode->hasPoint(p)) {
357 if(!minNode->isSingle()) {
358 minNode->removePoint(p);
362 if(parent!=NULL) parent->removeChild(level, minNode);
363 std::vector<CoverTreeNode*> children = minNode->getChildren(level-1);
364 std::vector<distNodePair>& Q = coverSets[level-1];
365 if(Q.size()==1 && Q[0].second==minNode) {
368 for(
unsigned int i=0;i<Q.size();i++) {
369 if(Q[i].second==minNode) {
376 typename std::vector<CoverTreeNode*>::const_iterator it;
377 for(it=children.begin();it!=children.end();++it) {
379 Point q = (*it)->getPoint();
380 double minDQ = DBL_MAX;
381 CoverTreeNode* minDQNode;
382 double sep_ = pow(
base,i);
385 std::vector<distNodePair>&
387 typename std::vector<distNodePair>::const_iterator it2;
389 for(it2=Q_.begin();it2!=Q_.end();++it2) {
390 double d = q.distance(it2->second->getPoint());
393 minDQNode = it2->second;
402 Q_.push_back(std::make_pair((*it)->distance(p),*it));
409 minDQNode->addChild(i,*it);
418 template<
class Po
int>
419 std::pair<double, typename CoverTree<Point>::CoverTreeNode*>
421 const std::vector<CoverTreeNode*>& Q)
423 double minDist = DBL_MAX;
424 CoverTreeNode* minNode;
425 typename std::vector<CoverTreeNode*>::const_iterator it;
426 for(it=Q.begin();it!=Q.end();++it) {
427 double dist = p.distance((*it)->getPoint());
433 return std::make_pair(minDist,minNode);
436 template<
class Po
int>
440 _root =
new CoverTreeNode(newPoint);
446 CoverTreeNode* n = kNearestNodes(newPoint,1)[0];
447 if(newPoint.distance(n->getPoint())==0.0) {
448 n->addPoint(newPoint);
453 std::vector<distNodePair>
454 (1,std::make_pair(_root->distance(newPoint),_root)),
459 template<
class Po
int>
463 if(_root==NULL)
return;
464 bool removingRoot=_root->hasPoint(p);
465 if(removingRoot && !_root->isSingle()) {
466 _root->removePoint(p);
469 CoverTreeNode* newRoot=NULL;
478 for(
int i=_maxLevel;i>_minLevel;i--) {
479 if(!(_root->getChildren(i).empty())) {
480 newRoot = _root->getChildren(i).back();
481 _root->removeChild(i,newRoot);
487 std::map<int, std::vector<distNodePair> > coverSets;
488 coverSets[_maxLevel].push_back(std::make_pair(_root->distance(p),_root));
490 coverSets[_maxLevel].push_back(std::make_pair(newRoot->distance(p),newRoot));
492 remove_rec(p,coverSets,_maxLevel,multi);
500 template<
class Po
int>
502 const unsigned int& k)
const
504 if(_root==NULL)
return std::vector<Point>();
505 std::vector<CoverTreeNode*> v = kNearestNodes(p, k);
506 std::vector<Point> kNN;
507 typename std::vector<CoverTreeNode*>::const_iterator it;
508 for(it=v.begin();it!=v.end();++it) {
509 const std::vector<Point>& po = (*it)->getPoints();
510 kNN.insert(kNN.end(),po.begin(),po.end());
511 if(kNN.size() >= k)
break;
516 template<
class Po
int>
522 template<
class Po
int>
524 _points.push_back(p);
527 template<
class Po
int>
528 std::vector<typename CoverTree<Point>::CoverTreeNode*>
529 CoverTree<Point>::CoverTreeNode::getChildren(
int level)
const
531 typename std::map<int,std::vector<CoverTreeNode*> >::const_iterator
532 it = _childMap.find(level);
533 if(it!=_childMap.end()) {
536 return std::vector<CoverTreeNode*>();
539 template<
class Po
int>
540 void CoverTree<Point>::CoverTreeNode::addChild(
int level, CoverTreeNode* p)
542 _childMap[level].push_back(p);
545 template<
class Po
int>
546 void CoverTree<Point>::CoverTreeNode::removeChild(
int level, CoverTreeNode* p)
548 std::vector<CoverTreeNode*>& v = _childMap[level];
549 for(
unsigned int i=0;i<v.size();i++) {
558 template<
class Po
int>
559 void CoverTree<Point>::CoverTreeNode::addPoint(
const Point& p)
561 if(find(_points.begin(), _points.end(), p) == _points.end())
562 _points.push_back(p);
565 template<
class Po
int>
566 void CoverTree<Point>::CoverTreeNode::removePoint(
const Point& p)
568 typename std::vector<Point>::iterator it =
569 find(_points.begin(), _points.end(), p);
570 if(it != _points.end())
574 template<
class Po
int>
577 return _points[0].distance(p.getPoint());
580 template<
class Po
int>
581 bool CoverTree<Point>::CoverTreeNode::isSingle()
const
583 return _points.size() == 1;
586 template<
class Po
int>
587 bool CoverTree<Point>::CoverTreeNode::hasPoint(
const Point& p)
const
589 return find(_points.begin(), _points.end(), p) != _points.end();
592 template<
class Po
int>
593 const Point& CoverTree<Point>::CoverTreeNode::getPoint()
const {
return _points[0]; }
595 template<
class Po
int>
596 std::vector<typename CoverTree<Point>::CoverTreeNode*>
597 CoverTree<Point>::CoverTreeNode::getAllChildren()
const
599 std::vector<CoverTreeNode*> children;
600 typename std::map<int,std::vector<CoverTreeNode*> >::const_iterator it;
601 for(it=_childMap.begin();it!=_childMap.end();++it) {
602 children.insert(children.end(), it->second.begin(), it->second.end());
607 template<
class Po
int>
612 std::vector<CoverTreeNode*> nodes;
613 nodes.push_back(_root);
614 for(
int i=_maxLevel;i>_minLevel;i--) {
615 double sep = pow(
base,i);
616 typename std::vector<CoverTreeNode*>::const_iterator it, it2;
619 for(it=nodes.begin(); it!=nodes.end(); ++it) {
620 for(it2=nodes.begin(); it2!=nodes.end(); ++it2) {
621 double dist=(*it)->distance((*it2)->getPoint());
622 if(dist<=sep && dist!=0.0) {
623 std::cout <<
"Level " << i <<
" Separation invariant failed.\n";
628 std::vector<CoverTreeNode*> allChildren;
629 for(it=nodes.begin(); it!=nodes.end(); ++it) {
630 std::vector<CoverTreeNode*> children = (*it)->getChildren(i);
633 for(it2=children.begin(); it2!=children.end(); ++it2) {
634 double dist = (*it2)->distance((*it)->getPoint());
636 std::cout <<
"Level" << i <<
" covering tree invariant failed.n";
641 (allChildren.end(),children.begin(),children.end());
643 nodes.insert(nodes.begin(),allChildren.begin(),allChildren.end());
648 #endif // _COVER_TREE_H