Reference documentation for deal.II version 9.1.1
\(\newcommand{\dealcoloneq}{\mathrel{\vcenter{:}}=}\)
kdtree.cc
1 // ---------------------------------------------------------------------
2 //
3 // Copyright (C) 2017 - 2019 by the deal.II authors
4 //
5 // This file is part of the deal.II library.
6 //
7 // The deal.II library is free software; you can use it, redistribute
8 // it, and/or modify it under the terms of the GNU Lesser General
9 // Public License as published by the Free Software Foundation; either
10 // version 2.1 of the License, or (at your option) any later version.
11 // The full text of the license can be found in the file LICENSE.md at
12 // the top level directory of deal.II.
13 //
14 // ---------------------------------------------------------------------
15 
16 #include <deal.II/numerics/kdtree.h>
17 
18 #ifdef DEAL_II_WITH_NANOFLANN
19 
20 # include <deal.II/base/std_cxx14/memory.h>
21 
22 DEAL_II_NAMESPACE_OPEN
23 
24 
25 template <int dim>
26 KDTree<dim>::KDTree(const unsigned int max_leaf_size,
27  const std::vector<Point<dim>> &pts)
28  : max_leaf_size(max_leaf_size)
29 {
30  if (pts.size() > 0)
31  set_points(pts);
32 }
33 
34 
35 
36 template <int dim>
37 std::vector<std::pair<unsigned int, double>>
39  const double radius,
40  bool sorted) const
41 {
42  Assert(adaptor, ExcNotInitialized());
43  Assert(kdtree, ExcInternalError());
44 
45  Assert(radius > 0, ExcMessage("Radius is expected to be positive."));
46 
47  nanoflann::SearchParams params;
48  params.sorted = sorted;
49 
50  std::vector<std::pair<unsigned int, double>> matches;
51 # if NANOFLANN_VERSION < 0x130
52  kdtree->radiusSearch(center.begin_raw(), radius, matches, params);
53 # else
54  // nanoflann 1.3 performs distance comparisons with squared distances, so
55  // square the radius before we query and square root after:
56  kdtree->radiusSearch(center.begin_raw(), radius * radius, matches, params);
57  for (std::pair<unsigned int, double> &match : matches)
58  match.second = std::sqrt(match.second);
59 # endif
60 
61  return matches;
62 }
63 
64 
65 
66 template <int dim>
67 std::vector<std::pair<unsigned int, double>>
69  const unsigned int n_points) const
70 {
71  Assert(adaptor, ExcNotInitialized());
72  Assert(kdtree, ExcInternalError());
73 
74  // get the information out of nanoflann
75  std::vector<unsigned int> indices(n_points);
76  std::vector<double> distances(n_points);
77 
78  kdtree->knnSearch(target.begin_raw(),
79  n_points,
80  indices.data(),
81  distances.data());
82 
83  // convert it to the format we want to return
84  std::vector<std::pair<unsigned int, double>> matches(n_points);
85  for (unsigned int i = 0; i < n_points; ++i)
86 # if NANOFLANN_VERSION < 0x130
87  matches[i] = std::make_pair(indices[i], distances[i]);
88 # else
89  // nanoflann 1.3 performs distance comparisons with squared distances, so
90  // take a square root:
91  matches[i] = std::make_pair(indices[i], std::sqrt(distances[i]));
92 # endif
93 
94  return matches;
95 }
96 
97 
98 
99 template <int dim>
100 void
101 KDTree<dim>::set_points(const std::vector<Point<dim>> &pts)
102 {
103  Assert(pts.size() > 0, ExcMessage("Expecting a non zero set of points."));
104  adaptor = std_cxx14::make_unique<PointCloudAdaptor>(pts);
105  kdtree = std_cxx14::make_unique<NanoFlannKDTree>(
106  dim, *adaptor, nanoflann::KDTreeSingleIndexAdaptorParams(max_leaf_size));
107  kdtree->buildIndex();
108 }
109 
110 
111 template class KDTree<1>;
112 template class KDTree<2>;
113 template class KDTree<3>;
114 
115 DEAL_II_NAMESPACE_CLOSE
116 
117 #endif
std::vector< std::pair< unsigned int, double > > get_points_within_ball(const Point< dim > &target, const double radius, const bool sorted=false) const
Definition: kdtree.cc:38
Definition: kdtree.h:65
static ::ExceptionBase & ExcNotInitialized()
std::vector< std::pair< unsigned int, double > > get_closest_points(const Point< dim > &target, const unsigned int n_points) const
Definition: kdtree.cc:68
static ::ExceptionBase & ExcMessage(std::string arg1)
#define Assert(cond, exc)
Definition: exceptions.h:1407
void set_points(const std::vector< Point< dim >> &pts)
Definition: kdtree.cc:101
KDTree(const unsigned int max_leaf_size=10, const std::vector< Point< dim >> &pts={})
Definition: kdtree.cc:26
Number * begin_raw()
Definition: tensor.h:1161
static ::ExceptionBase & ExcInternalError()