20 template<
typename T,
size_t N,
size_t S>
24 virtual ~
Node() =
default;
27 template<
typename T,
size_t N,
size_t S>
31 virtual ~
Leaf() =
default;
35 for (
auto& entry : m_data) {
36 double square_dist = 0.0;
37 for (
size_t i =0; i < N; i++) {
39 square_dist += delta * delta;
41 if (square_dist < radius*radius) {
52 template<
typename T,
size_t N,
size_t S>
55 virtual ~
Split() =
default;
68 m_split_value = (a + b) / 2.0;
74 if (left.size() > S) {
75 m_left_child = std::make_shared<Split>(
std::move(left), (axis+1) % N);
77 m_left_child = std::make_shared<Leaf>(
std::move(left));
79 if (right.size() > S) {
80 m_right_child = std::make_shared<Split>(
std::move(right), (axis+1) % N);
82 m_right_child = std::make_shared<Leaf>(
std::move(right));
87 if (coord.
coord[m_axis] + radius < m_split_value) {
88 return m_left_child->findPointsWithinRadius(coord, radius);
89 }
else if (coord.
coord[m_axis] - radius > m_split_value) {
90 return m_right_child->findPointsWithinRadius(coord, radius);
92 auto left = m_left_child->findPointsWithinRadius(coord, radius);
93 auto right = m_right_child->findPointsWithinRadius(coord, radius);
96 merge.
reserve(left.size() + right.size());
97 merge.
insert(merge.
end(), left.begin(), left.end());
98 merge.
insert(merge.
end(), right.begin(), right.end());
112 template<
typename T,
size_t N,
size_t S>
114 if (data.
size() > S) {
115 m_root = std::make_shared<Split>(data, 0);
118 m_root = std::make_shared<Leaf>(
std::move(data_copy));
122 template<
typename T,
size_t N,
size_t S>
Split(std::vector< T > data, size_t axis)
const std::vector< T > m_data
std::vector< T > findPointsWithinRadius(Coord coord, double radius) const override
std::shared_ptr< Node > m_left_child
Leaf(const std::vector< T > &&data)
std::vector< T > findPointsWithinRadius(Coord coord, double radius) const override
std::vector< T > findPointsWithinRadius(Coord coord, double radius) const
static double getCoord(const T &t, size_t index)
std::shared_ptr< Node > m_right_child