-
Notifications
You must be signed in to change notification settings - Fork 0
/
SplitAxisRoundRobinStrategy.hpp
executable file
·44 lines (31 loc) · 1.17 KB
/
SplitAxisRoundRobinStrategy.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
43
44
#ifndef ROSSB83_SPLIT_AXIS_ROUND_ROBIN_STRATEGY_HPP
#define ROSSB83_SPLIT_AXIS_ROUND_ROBIN_STRATEGY_HPP
#include <vector>
#include <iostream>
#include "SplitAxisStrategy.hpp"
namespace rossb83 {
// this split axis strategy will split the axis based on the tree level, every level will have the
// the same axis split, and the axis split will increment by one each level and then start over
template<typename T>
class SplitAxisRoundRobinStrategy : public SplitAxisStrategy<T> {
private:
// the number of nodes so far
std::size_t nodes_;
// the number of levels so far
std::size_t level_;
// the previous axis split used
std::size_t axis_;
public:
SplitAxisRoundRobinStrategy() : nodes_(0), axis_(0), level_(1) {}
// since a kdtree is always balanced, this algorithm can tell what level it is on based
// on the number of nodes processed so far and the previous level
std::size_t splitAxis(const std::vector<Point<T>>& points, const std::size_t& begin, const std::size_t& end) {
if (++nodes_ >= pow(2,level_)) {
level_++;
axis_ = ++axis_ % points[begin].dims();
}
return axis_;
}
};// class Split
} // namespace rossb83
#endif