22template <
typename T,
typename DistanceMethod>
30template <
typename T,
typename DistanceMethod>
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)) {
59template <
typename T,
typename DistanceMethod>
65 [axis](
const T& a,
const T& b) ->
bool { return Traits::getCoord(a, axis) < Traits::getCoord(b, axis); });
74 m_split_value = (a + b) / 2.0;
80 if (left.size() > leaf_size) {
85 if (right.size() > leaf_size) {
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) +
122template <
typename T,
typename DistanceMethod>
130 if (data.
size() > leaf_size) {
138template <
typename T,
typename DistanceMethod>
141 m_root->findPointsWithinRadius(coord, radius, output);
145template <
typename T,
typename DistanceMethod>
147 return m_root->countPointsWithinRadius(coord, radius);
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;
168 double delta = std::abs(Traits::getCoord(a, i) - Traits::getCoord(b, i));
173 return max_d <= distance;
void findPointsWithinRadius(const T &coord, double radius, std::vector< T > &selection) const override
std::size_t countPointsWithinRadius(const T &coord, double radius) const override
Leaf(const std::vector< T > &&data)
const std::vector< T > m_data
virtual std::size_t countPointsWithinRadius(const T &coord, double radius) const =0
virtual void findPointsWithinRadius(const T &coord, double radius, std::vector< T > &selection) const =0
void findPointsWithinRadius(const T &coord, double radius, std::vector< T > &selection) const override
std::size_t countPointsWithinRadius(const T &coord, double radius) const override
std::shared_ptr< Node > m_left_child
std::shared_ptr< Node > m_right_child
Split(std::size_t dimensionality, std::size_t leaf_size, std::vector< T > data, size_t axis)
std::vector< T > findPointsWithinRadius(const T &coord, double radius) const
std::shared_ptr< Node > m_root
std::size_t m_dimensionality
std::size_t countPointsWithinRadius(const T &coord, double radius) const
KdTree(const std::vector< T > &data, std::size_t leaf_size=100)
T emplace_back(T... args)
static bool isCloserThan(const T &a, const T &b, double distance)
static bool isCloserThan(const T &a, const T &b, double distance)
static double getCoord(const T &t, size_t index)
static std::size_t getDimensions(const T &t)