22template <
typename T,
typename DistanceMethod>
30template <
typename T,
typename DistanceMethod>
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)) {
59template <
typename T,
typename DistanceMethod>
65 [axis](
const T& a,
const T& b) ->
bool { return Traits::getCoord(a, axis) < Traits::getCoord(b, axis); });
67 double a = Traits::getCoord(data.
at(data.
size() / 2 - 1), axis);
68 double b = Traits::getCoord(data.
at(data.
size() / 2), axis);
74 m_split_value = (a + b) / 2.0;
80 if (left.size() > leaf_size) {
85 if (right.size() > leaf_size) {
93 if (Traits::getCoord(coord, m_axis) + radius < m_split_value) {
94 m_left_child->findPointsWithinRadius(coord, radius, selection);
95 }
else if (Traits::getCoord(coord, m_axis) - radius > m_split_value) {
96 m_right_child->findPointsWithinRadius(coord, radius, selection);
98 m_left_child->findPointsWithinRadius(coord, radius, selection);
99 m_right_child->findPointsWithinRadius(coord, radius, selection);
104 if (Traits::getCoord(coord, m_axis) + radius < m_split_value) {
105 return m_left_child->countPointsWithinRadius(coord, radius);
106 }
else if (Traits::getCoord(coord, m_axis) - radius > m_split_value) {
107 return m_right_child->countPointsWithinRadius(coord, radius);
109 return m_left_child->countPointsWithinRadius(coord, radius) +
110 m_right_child->countPointsWithinRadius(coord, radius);
122template <
typename T,
typename DistanceMethod>
125 m_dimensionality = Traits::getDimensions(data.
front());
127 m_dimensionality = 0;
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::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)