sparsify_point_set.h
1 /* This file is part of the Gudhi Library - https://gudhi.inria.fr/ - which is released under MIT.
2  * See file LICENSE or go to https://gudhi.inria.fr/licensing/ for full license details.
3  * Author(s): Clement Jamin
4  *
5  * Copyright (C) 2016 Inria
6  *
7  * Modification(s):
8  * - YYYY/MM Author: Description of the modification
9  */
10 
11 #ifndef SPARSIFY_POINT_SET_H_
12 #define SPARSIFY_POINT_SET_H_
13 
14 # include <boost/iterator/function_output_iterator.hpp>
15 
16 #include <gudhi/Kd_tree_search.h>
17 #ifdef GUDHI_SUBSAMPLING_PROFILING
18 #include <gudhi/Clock.h>
19 #endif
20 
21 #include <cstddef>
22 #include <vector>
23 
24 namespace Gudhi {
25 
26 namespace subsampling {
27 
48 template <typename Kernel, typename Point_range, typename OutputIterator>
49 void
51  const Kernel &k, Point_range const& input_pts,
52  typename Kernel::FT min_squared_dist,
53  OutputIterator output_it) {
55  Kernel, Point_range> Points_ds;
56 
57 #ifdef GUDHI_SUBSAMPLING_PROFILING
58  Gudhi::Clock t;
59 #endif
60 
61  Points_ds points_ds(input_pts);
62 
63  std::vector<bool> dropped_points(input_pts.size(), false);
64 
65  // Parse the input points, and add them if they are not too close to
66  // the other points
67  std::size_t pt_idx = 0;
68  for (auto const& pt : input_pts) {
69  if (dropped_points[pt_idx++])
70  continue;
71 
72  *output_it++ = pt;
73 
74  // If another point Q is closer that min_squared_dist, mark Q to be dropped
75  auto drop = [&dropped_points] (std::ptrdiff_t neighbor_point_idx) { dropped_points[neighbor_point_idx] = true; };
76  points_ds.all_near_neighbors2(pt, min_squared_dist, min_squared_dist, boost::make_function_output_iterator(std::ref(drop)));
77  }
78 
79 #ifdef GUDHI_SUBSAMPLING_PROFILING
80  t.end();
81  std::cerr << "Point set sparsified in " << t.num_seconds()
82  << " seconds." << std::endl;
83 #endif
84 }
85 
86 } // namespace subsampling
87 } // namespace Gudhi
88 
89 #endif // SPARSIFY_POINT_SET_H_
Spatial tree data structure to perform (approximate) nearest and furthest neighbor search.
Definition: Kd_tree_search.h:70
void sparsify_point_set(const Kernel &k, Point_range const &input_pts, typename Kernel::FT min_squared_dist, OutputIterator output_it)
Outputs a subset of the input points so that the squared distance between any two points is greater t...
Definition: sparsify_point_set.h:50