-
Notifications
You must be signed in to change notification settings - Fork 0
/
SplitPointSelectStrategy.hpp
executable file
·42 lines (30 loc) · 1.18 KB
/
SplitPointSelectStrategy.hpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#ifndef ROSSB83_SPLIT_POINT_SELECT_STRATEGY
#define ROSSB83_SPLIT_POINT_SELECT_STRATEGY
#include <unordered_map>
#include <tuple>
#include <regex>
#include <functional>
#include <algorithm>
#include <numeric>
#include <limits>
#include <math.h>
#include <complex>
#include <cmath>
#include "SplitPointStrategy.hpp"
namespace rossb83 {
// this strategy determines which point the kdtree will make the next node, it works by
// sorting the input vector
template<typename T>
class SplitPointSelectStrategy : public SplitPointStrategy<T> {
public:
// this method will re-arrange the input by sorting it placing the median between begin and end
Point<T> splitPoint(std::vector<Point<T>>& points, const std::size_t& dim, const std::size_t& begin, const std::size_t& end) {
auto mid = points.begin() + std::ceil((begin + end)/2.0);
// sort using the default operator<
std::nth_element(points.begin() + begin, mid, points.begin() + end + 1,
[dim](Point<T> p1, Point<T> p2) {return p1[dim] < p2[dim];});
return std::move(points[std::ceil((begin + end)/2.0)]);
}
}; // class SplitPointSelectStrategy
} // namespace rossb83
#endif // ROSSB83_SPLIT_POINT_SELECT_STRATEGY