22 template <
typename T,
typename DistanceMethod>
27 virtual ~
Node() =
default;
30 template <
typename T,
typename DistanceMethod>
34 virtual ~
Leaf() =
default;
37 selection.
reserve(selection.
size() + m_data.size());
38 for (
auto& entry : m_data) {
39 if (DistanceMethod::isCloserThan(entry, coord, radius)) {
47 for (
auto& entry : m_data) {
48 if (DistanceMethod::isCloserThan(entry, coord, radius)) {
59 template <
typename T,
typename DistanceMethod>
62 virtual ~
Split() =
default;
74 m_split_value = (a + b) / 2.0;
80 if (left.size() > leaf_size) {
81 m_left_child = std::make_shared<Split>(dimensionality, leaf_size,
std::move(left), (axis + 1) % dimensionality);
83 m_left_child = std::make_shared<Leaf>(
std::move(left));
85 if (right.size() > leaf_size) {
86 m_right_child = std::make_shared<Split>(dimensionality, leaf_size,
std::move(right), (axis + 1) % dimensionality);
88 m_right_child = std::make_shared<Leaf>(
std::move(right));
94 m_left_child->findPointsWithinRadius(coord, radius, selection);
96 m_right_child->findPointsWithinRadius(coord, radius, selection);
98 m_left_child->findPointsWithinRadius(coord, radius, selection);
99 m_right_child->findPointsWithinRadius(coord, radius, selection);
105 return m_left_child->countPointsWithinRadius(coord, radius);
107 return m_right_child->countPointsWithinRadius(coord, radius);
109 return m_left_child->countPointsWithinRadius(coord, radius) +
110 m_right_child->countPointsWithinRadius(coord, radius);
122 template <
typename T,
typename DistanceMethod>
125 m_dimensionality = Traits::getDimensions(data.
front());
127 m_dimensionality = 0;
130 if (data.
size() > leaf_size) {
131 m_root = std::make_shared<Split>(m_dimensionality, leaf_size, data, 0);
134 m_root = std::make_shared<Leaf>(
std::move(data_copy));
138 template <
typename T,
typename DistanceMethod>
141 m_root->findPointsWithinRadius(coord, radius, output);
145 template <
typename T,
typename DistanceMethod>
150 template <
typename T>
153 double square_dist = 0.0;
156 double delta = Traits::getCoord(a, i) - Traits::getCoord(b, i);
157 square_dist += delta * delta;
159 return square_dist < distance * distance;
162 template <
typename T>
168 double delta = std::abs(Traits::getCoord(a, i) - Traits::getCoord(b, i));
173 return max_d <= distance;
Leaf(const std::vector< T > &&data)
std::vector< T > findPointsWithinRadius(const T &coord, double radius) const
std::size_t countPointsWithinRadius(const T &coord, double radius) const override
void findPointsWithinRadius(const T &coord, double radius, std::vector< T > &selection) const override
std::size_t countPointsWithinRadius(const T &coord, double radius) const
static bool isCloserThan(const T &a, const T &b, double distance)
std::size_t countPointsWithinRadius(const T &coord, double radius) const override
std::shared_ptr< Node > m_right_child
std::shared_ptr< Node > m_left_child
static bool isCloserThan(const T &a, const T &b, double distance)
Split(std::size_t dimensionality, std::size_t leaf_size, std::vector< T > data, size_t axis)
static double getCoord(const T &t, size_t index)
void findPointsWithinRadius(const T &coord, double radius, std::vector< T > &selection) const override