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 <gudhi/Kd_tree_search.h>
15 #ifdef GUDHI_SUBSAMPLING_PROFILING
16 #include <gudhi/Clock.h>
17 #endif
18 
19 #include <cstddef>
20 #include <vector>
21 
22 namespace Gudhi {
23 
24 namespace subsampling {
25 
46 template <typename Kernel, typename Point_range, typename OutputIterator>
47 void
49  const Kernel &k, Point_range const& input_pts,
50  typename Kernel::FT min_squared_dist,
51  OutputIterator output_it) {
53  Kernel, Point_range> Points_ds;
54 
55 #ifdef GUDHI_SUBSAMPLING_PROFILING
56  Gudhi::Clock t;
57 #endif
58 
59  Points_ds points_ds(input_pts);
60 
61  std::vector<bool> dropped_points(input_pts.size(), false);
62 
63  // Parse the input points, and add them if they are not too close to
64  // the other points
65  std::size_t pt_idx = 0;
66  for (typename Point_range::const_iterator it_pt = input_pts.begin();
67  it_pt != input_pts.end();
68  ++it_pt, ++pt_idx) {
69  if (dropped_points[pt_idx])
70  continue;
71 
72  *output_it++ = *it_pt;
73 
74  auto ins_range = points_ds.incremental_nearest_neighbors(*it_pt);
75 
76  // If another point Q is closer that min_squared_dist, mark Q to be dropped
77  for (auto const& neighbor : ins_range) {
78  std::size_t neighbor_point_idx = neighbor.first;
79  // If the neighbor is too close, we drop the neighbor
80  if (neighbor.second < min_squared_dist) {
81  // N.B.: If neighbor_point_idx < pt_idx,
82  // dropped_points[neighbor_point_idx] is already true but adding a
83  // test doesn't make things faster, so why bother?
84  dropped_points[neighbor_point_idx] = true;
85  } else {
86  break;
87  }
88  }
89  }
90 
91 #ifdef GUDHI_SUBSAMPLING_PROFILING
92  t.end();
93  std::cerr << "Point set sparsified in " << t.num_seconds()
94  << " seconds." << std::endl;
95 #endif
96 }
97 
98 } // namespace subsampling
99 } // namespace Gudhi
100 
101 #endif // SPARSIFY_POINT_SET_H_
Gudhi::spatial_searching::Kd_tree_search
Spatial tree data structure to perform (approximate) nearest and furthest neighbor search.
Definition: Kd_tree_search.h:70
Gudhi::subsampling::sparsify_point_set
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:48
GUDHI  Version 3.3.0  - C++ library for Topological Data Analysis (TDA) and Higher Dimensional Geometry Understanding.  - Copyright : MIT Generated on Fri Oct 30 2020 17:07:14 for GUDHI by Doxygen 1.8.18