sparsify_point_set.h
1 /* This file is part of the Gudhi Library. The Gudhi library
2  * (Geometric Understanding in Higher Dimensions) is a generic C++
3  * library for computational topology.
4  *
5  * Author(s): Clement Jamin
6  *
7  * Copyright (C) 2016 INRIA
8  *
9  * This program is free software: you can redistribute it and/or modify
10  * it under the terms of the GNU General Public License as published by
11  * the Free Software Foundation, either version 3 of the License, or
12  * (at your option) any later version.
13  *
14  * This program is distributed in the hope that it will be useful,
15  * but WITHOUT ANY WARRANTY; without even the implied warranty of
16  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
17  * GNU General Public License for more details.
18  *
19  * You should have received a copy of the GNU General Public License
20  * along with this program. If not, see <http://www.gnu.org/licenses/>.
21  */
22 
23 #ifndef SPARSIFY_POINT_SET_H_
24 #define SPARSIFY_POINT_SET_H_
25 
26 #include <gudhi/Kd_tree_search.h>
27 #ifdef GUDHI_SUBSAMPLING_PROFILING
28 #include <gudhi/Clock.h>
29 #endif
30 
31 #include <cstddef>
32 #include <vector>
33 
34 namespace Gudhi {
35 
36 namespace subsampling {
37 
58 template <typename Kernel, typename Point_range, typename OutputIterator>
59 void
61  const Kernel &k, Point_range const& input_pts,
62  typename Kernel::FT min_squared_dist,
63  OutputIterator output_it) {
65  Kernel, Point_range> Points_ds;
66 
67 #ifdef GUDHI_SUBSAMPLING_PROFILING
68  Gudhi::Clock t;
69 #endif
70 
71  Points_ds points_ds(input_pts);
72 
73  std::vector<bool> dropped_points(input_pts.size(), false);
74 
75  // Parse the input points, and add them if they are not too close to
76  // the other points
77  std::size_t pt_idx = 0;
78  for (typename Point_range::const_iterator it_pt = input_pts.begin();
79  it_pt != input_pts.end();
80  ++it_pt, ++pt_idx) {
81  if (dropped_points[pt_idx])
82  continue;
83 
84  *output_it++ = *it_pt;
85 
86  auto ins_range = points_ds.incremental_nearest_neighbors(*it_pt);
87 
88  // If another point Q is closer that min_squared_dist, mark Q to be dropped
89  for (auto const& neighbor : ins_range) {
90  std::size_t neighbor_point_idx = neighbor.first;
91  // If the neighbor is too close, we drop the neighbor
92  if (neighbor.second < min_squared_dist) {
93  // N.B.: If neighbor_point_idx < pt_idx,
94  // dropped_points[neighbor_point_idx] is already true but adding a
95  // test doesn't make things faster, so why bother?
96  dropped_points[neighbor_point_idx] = true;
97  } else {
98  break;
99  }
100  }
101  }
102 
103 #ifdef GUDHI_SUBSAMPLING_PROFILING
104  t.end();
105  std::cerr << "Point set sparsified in " << t.num_seconds()
106  << " seconds." << std::endl;
107 #endif
108 }
109 
110 } // namespace subsampling
111 } // namespace Gudhi
112 
113 #endif // SPARSIFY_POINT_SET_H_
Spatial tree data structure to perform (approximate) nearest and furthest neighbor search...
Definition: Kd_tree_search.h:69
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:60
Definition: SimplicialComplexForAlpha.h:26
GUDHI  Version 2.1.0  - C++ library for Topological Data Analysis (TDA) and Higher Dimensional Geometry Understanding.  - Copyright : GPL v3 Generated on Thu May 24 2018 09:46:12 for GUDHI by Doxygen 1.8.13