35 #ifndef SHARK_ALGORITHMS_NEARESTNEIGHBORS_KDTREE_H 36 #define SHARK_ALGORITHMS_NEARESTNEIGHBORS_KDTREE_H 69 template <
class InputT>
83 : base_type(dataset.numberOfElements())
86 PointSet points(dataset);
88 std::vector<typename boost::range_iterator<PointSet>::type> elements(
m_size);
89 boost::iota(elements,boost::begin(points));
95 for(std::size_t i = 0; i !=
m_size; ++i){
103 double lower(std::size_t dim)
const{
105 if (parent == NULL)
return -1e100;
110 return parent->
lower(dim);
115 double upper(std::size_t dim)
const{
117 if (parent == NULL)
return +1e100;
122 return parent->
upper(dim);
140 for (std::size_t d = 0; d != reference.size(); d++)
142 double v = reference(d);
157 void print(
unsigned int ident = 0)
const 161 for (
unsigned int j=0; j<
m_size; j++)
163 for (
unsigned int i=0; i<ident; i++) printf(
" ");
164 printf(
"index: %d\n", (
int)this->
index(j));
169 for (
unsigned int i=0; i<ident; i++) printf(
" ");
171 for (
unsigned int i=0; i<ident; i++) printf(
" ");
173 ((self_type*)
mp_left)->print(ident + 1);
174 for (
unsigned int i=0; i<ident; i++) printf(
" ");
176 ((self_type*)
mp_right)->print(ident + 1);
191 : base_type(parent, list, size)
197 template<
class Range>
199 typedef typename boost::range_iterator<Range>::type iterator;
201 iterator begin = boost::begin(points);
202 iterator end = boost::end(points);
216 std::vector<double> distance(
m_size);
217 iterator point = begin;
218 for(std::size_t i = 0; i !=
m_size; ++i,++point){
223 iterator split = this->
splitList(distance,points);
224 std::size_t leftSize = split-begin;
231 boost::iterator_range<iterator>
left(begin,split);
232 boost::iterator_range<iterator>
right(split,end);
242 template<
class Range>
244 typedef typename boost::range_iterator<Range const>::type iterator;
246 iterator begin = boost::begin(points);
252 std::size_t dim = L.size();
253 iterator point = begin;
255 for (std::size_t i=1; i !=
m_size; ++i,++point){
256 for (std::size_t d = 0; d != dim; d++){
257 double v = (**point)[d];
258 if (v < L[d]) L[d] = v;
259 if (v > U[d]) U[d] = v;
264 std::size_t cutDim = 0;
265 double extent = U[0] - L[0];
266 for (std::size_t d = 1; d != dim; d++)
268 double e = U[d] - L[d];
285 double funct(InputT
const& reference)
const{