cheshirekow  v0.1.0
KNearest.hpp
Go to the documentation of this file.
1 /*
2  * Copyright (C) 2012 Josh Bialkowski (jbialk@mit.edu)
3  *
4  * This file is part of mpblocks.
5  *
6  * mpblocks is free software: you can redistribute it and/or modify
7  * it under the terms of the GNU General Public License as published by
8  * the Free Software Foundation, either version 3 of the License, or
9  * (at your option) any later version.
10  *
11  * mpblocks is distributed in the hope that it will be useful,
12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14  * GNU General Public License for more details.
15  *
16  * You should have received a copy of the GNU General Public License
17  * along with mpblocks. If not, see <http://www.gnu.org/licenses/>.
18  */
27 #ifndef MPBLOCKS_KD_TREE_EUCLIDEAN_KNEAREST_HPP_
28 #define MPBLOCKS_KD_TREE_EUCLIDEAN_KNEAREST_HPP_
29 
30 
31 namespace mpblocks {
32 namespace kd_tree {
33 namespace euclidean {
34 
35 
36 template <class Traits,template<class> class Allocator>
38 {
39  m_k = k;
40 }
41 
42 
43 template <class Traits,template<class> class Allocator>
45 {
46  m_queue.clear();
47 }
48 
49 
50 template <class Traits,template<class> class Allocator>
52 {
53  m_queue.clear();
54  m_k = k;
55 }
56 
57 
58 
59 template <class Traits,template<class> class Allocator>
62 {
63  return m_queue;
64 }
65 
66 
67 
68 
69 template <class Traits,template<class> class Allocator>
71  const Point_t& q, const Point_t& p, Node_t* n)
72 {
73  Key_t key;
74  key.d2 = m_dist2Fn(q,p);
75  key.n = n;
76 
77  m_queue.insert(key);
78 
79  if( m_queue.size() > m_k )
80  m_queue.erase( --m_queue.end() );
81 }
82 
83 
84 
85 
86 template <class Traits,template<class> class Allocator>
88  const Point_t& q, const HyperRect_t& r )
89 {
90  Format_t d2 = m_dist2Fn(q,r);
91  return (d2 < m_queue.rbegin()->d2 || m_queue.size() < m_k);
92 }
93 
94 
95 
96 
97 
98 
99 } // namespace euclidean
100 } // namespace kd_tree
101 } // namespace mpblocks
102 
103 
104 
105 
106 
107 
108 
109 
110 #endif // NEARESTNEIGHBOR_H_
void insert(Node_t *)
recursively inserts point as a new node in the tree
Definition: Node.hpp:71
std::set< Key_t, KeyCompare_t, Allocator_t > PQueue_t
Definition: KNearest.h:53
virtual bool shouldRecurse(const Point_t &q, const HyperRect_t &r)
evaluate the Euclidean distance from q to it's closest point in r and if that distance is less than t...
Definition: KNearest.hpp:87
the node class must be defined in traits since it uses the CTRP, it must derive from kd_tree::Node<Tr...
Definition: Traits.h:49
virtual void evaluate(const Point_t &q, const Point_t &p, Node_t *n)
calculates Euclidean distance from q to p, and if its less than the current best replaces the current...
Definition: KNearest.hpp:70
Eigen::Matrix< Format_t, Traits::NDim, 1 > Point_t
Definition: KNearest.h:52
an NDim dimensional hyperrectangle, represented as a min and max extent
Definition: HyperRect.h:23