Alexandria  2.27.0
SDC-CH common library for the Euclid project
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
KdTree.h
Go to the documentation of this file.
1 
18 #ifndef _KDTREE_KDTREE_H_
19 #define _KDTREE_KDTREE_H_
20 
21 #include <algorithm>
22 #include <memory>
23 #include <vector>
24 
25 namespace KdTree {
26 
27 template <typename T>
28 struct KdTreeTraits {
32  static std::size_t getDimensions(const T& t);
33 
37  static double getCoord(const T& t, size_t index);
38 };
39 
44 template <typename T>
46  static bool isCloserThan(const T& a, const T& b, double distance);
47 };
48 
53 template <typename T>
55  static bool isCloserThan(const T& a, const T& b, double distance);
56 };
57 
67 template <typename T, typename DistanceMethod = EuclideanDistance<T>>
68 class KdTree {
69 public:
71 
72  explicit KdTree(const std::vector<T>& data, std::size_t leaf_size = 100);
73 
80  std::vector<T> findPointsWithinRadius(const T& coord, double radius) const;
81 
88  std::size_t countPointsWithinRadius(const T& coord, double radius) const;
89 
90 private:
91  class Node;
92  class Leaf;
93  class Split;
94 
97 };
98 
102 template <typename U>
103 struct KdTreeTraits<std::vector<U>> {
105  return t.size();
106  }
107 
108  static double getCoord(const std::vector<U>& t, size_t index) {
109  return t[index];
110  }
111 };
112 
116 template <typename U, std::size_t S>
117 struct KdTreeTraits<std::array<U, S>> {
119  return S;
120  }
121 
122  static double getCoord(const std::array<U, S>& t, size_t index) {
123  return t[index];
124  }
125 };
126 
127 } // namespace KdTree
128 
129 #include "_impl/KdTree.icpp"
130 
131 #endif /* _KDTREE_KDTREE_H_ */
A simple N-dimensional KdTree for speeding-up elements within range types of queries.
static double getCoord(const std::vector< U > &t, size_t index)
Definition: KdTree.h:108
std::vector< T > findPointsWithinRadius(const T &coord, double radius) const
Definition: KdTree.icpp:139
std::size_t m_dimensionality
Definition: KdTree.h:93
static std::size_t getDimensions(const std::vector< U > &t)
Definition: KdTree.h:104
std::size_t countPointsWithinRadius(const T &coord, double radius) const
Definition: KdTree.icpp:146
static bool isCloserThan(const T &a, const T &b, double distance)
Definition: KdTree.icpp:151
static double getCoord(const std::array< U, S > &t, size_t index)
Definition: KdTree.h:122
std::shared_ptr< Node > m_root
Definition: KdTree.h:96
static std::size_t getDimensions(const T &t)
T size(T...args)
STL class.
KdTree(const std::vector< T > &data, std::size_t leaf_size=100)
Definition: KdTree.icpp:123
STL class.
static bool isCloserThan(const T &a, const T &b, double distance)
Definition: KdTree.icpp:163
static double getCoord(const T &t, size_t index)
static std::size_t getDimensions(const std::array< U, S > &t)
Definition: KdTree.h:118