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/version.hpp>
15 #if BOOST_VERSION < 106600
16 # include <boost/function_output_iterator.hpp>
17 #else
18 # include <boost/iterator/function_output_iterator.hpp>
19 #endif
20 
21 #include <gudhi/Kd_tree_search.h>
22 #ifdef GUDHI_SUBSAMPLING_PROFILING
23 #include <gudhi/Clock.h>
24 #endif
25 
26 #include <cstddef>
27 #include <vector>
28 
29 namespace Gudhi {
30 
31 namespace subsampling {
32 
53 template <typename Kernel, typename Point_range, typename OutputIterator>
54 void
56  const Kernel &k, Point_range const& input_pts,
57  typename Kernel::FT min_squared_dist,
58  OutputIterator output_it) {
60  Kernel, Point_range> Points_ds;
61 
62 #ifdef GUDHI_SUBSAMPLING_PROFILING
63  Gudhi::Clock t;
64 #endif
65 
66  Points_ds points_ds(input_pts);
67 
68  std::vector<bool> dropped_points(input_pts.size(), false);
69 
70  // Parse the input points, and add them if they are not too close to
71  // the other points
72  std::size_t pt_idx = 0;
73  for (auto const& pt : input_pts) {
74  if (dropped_points[pt_idx++])
75  continue;
76 
77  *output_it++ = pt;
78 
79  // If another point Q is closer that min_squared_dist, mark Q to be dropped
80  auto drop = [&dropped_points] (std::ptrdiff_t neighbor_point_idx) { dropped_points[neighbor_point_idx] = true; };
81  points_ds.all_near_neighbors2(pt, min_squared_dist, min_squared_dist, boost::make_function_output_iterator(std::ref(drop)));
82  }
83 
84 #ifdef GUDHI_SUBSAMPLING_PROFILING
85  t.end();
86  std::cerr << "Point set sparsified in " << t.num_seconds()
87  << " seconds." << std::endl;
88 #endif
89 }
90 
91 } // namespace subsampling
92 } // namespace Gudhi
93 
94 #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:55
GUDHIdev  Version 3.5.0  - C++ library for Topological Data Analysis (TDA) and Higher Dimensional Geometry Understanding.  - Copyright : MIT Generated on Wed Apr 6 2022 19:26:28 for GUDHIdev by Doxygen 1.9.1