Medusa  1.1
Coordinate Free Mehless Method implementation
KDTree.hpp
Go to the documentation of this file.
1 #ifndef MEDUSA_BITS_SPATIAL_SEARCH_KDTREE_HPP_
2 #define MEDUSA_BITS_SPATIAL_SEARCH_KDTREE_HPP_
3 
9 #include "KDTree_fwd.hpp"
12 
13 namespace mm {
14 
15 template <class vec_t>
16 std::pair<Range<int>, Range<typename vec_t::scalar_t>> KDTree<vec_t>::query(const vec_t& point,
17  int k) const {
18  assert_msg(point.array().isFinite().prod() == 1, "Invalid point.");
19  Range<int> ret_index(k);
20  Range<scalar_t> out_dist_sqr(k);
21  int actual_k = tree.knnSearch(point.data(), k, &ret_index[0], &out_dist_sqr[0]);
22  assert_msg(actual_k == k, "There were not enough points in the tree, you requested %d "
23  "points, the tree only contains %d points.", k, actual_k);
24  return {ret_index, out_dist_sqr};
25 }
26 
27 template <class vec_t>
29  const vec_t& point, const scalar_t& radius_squared) const {
30  assert_msg(point.array().isFinite().prod() == 1, "Invalid point.");
31  std::vector<std::pair<int, scalar_t>> idx_dist;
32  int k = tree.radiusSearch(point.data(), radius_squared, idx_dist, nanoflann::SearchParams());
33  Range<int> idx(k); Range<scalar_t> dists(k);
34  for (int i = 0; i < k; ++i) {
35  std::tie(idx[i], dists[i]) = idx_dist[i];
36  }
37  return {idx, dists};
38 }
39 
41 template <class V>
42 std::ostream& operator<<(std::ostream& os, const KDTree<V>& tree) {
43  return os << "KDTree:\n"
44  << " dimension: " << tree.dim << '\n'
45  << " num of points: " << tree.size() << "\n"
46  << " first point: " << tree.get(0) << "\n"
47  << " last point: " << tree.get(tree.size() - 1) << "\n";
48 }
49 
50 } // namespace mm
51 
52 #endif // MEDUSA_BITS_SPATIAL_SEARCH_KDTREE_HPP_
KDTree_fwd.hpp
mm
Root namespace for the whole library.
Definition: Gaussian.hpp:14
mm::KDTree
Class representing a static k-d tree data structure.
Definition: KDTree_fwd.hpp:36
mm::operator<<
std::ostream & operator<<(std::ostream &os, const Gaussian< S > &b)
Output basic information about given Gaussian RBF.
Definition: Gaussian.hpp:37
mm::KDTree::dim
@ dim
Dimensionality of the space.
Definition: KDTree_fwd.hpp:41
assert_msg
#define assert_msg(cond,...)
Assert with better error reporting.
Definition: assert.hpp:75
mm::KDTree::query
std::pair< Range< int >, Range< scalar_t > > query(const vec_t &point, int k=1) const
Find k nearest neighbors to given point.
Definition: KDTree.hpp:16
mm::KDTree::size
int size() const
Returns number of points in this tree.
Definition: KDTree_fwd.hpp:126
assert.hpp
memutils.hpp
mm::KDTree::scalar_t
vector_t::scalar_t scalar_t
Scalar type used.
Definition: KDTree_fwd.hpp:39
mm::KDTree::get
vec_t get(int index) const
Get the coordinates of a point in the tree.
Definition: KDTree_fwd.hpp:113
mm::Range
An extension of std::vector<T> to support additional useful operations.
Definition: Range_fwd.hpp:30