choose_n_farthest_points.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): Siargey Kachanovich
4  *
5  * Copyright (C) 2016 Inria
6  *
7  * Modification(s):
8  * - YYYY/MM Author: Description of the modification
9  */
10 
11 #ifndef CHOOSE_N_FARTHEST_POINTS_H_
12 #define CHOOSE_N_FARTHEST_POINTS_H_
13 
14 #include <boost/range.hpp>
15 
16 #include <gudhi/Null_output_iterator.h>
17 
18 #include <iterator>
19 #include <vector>
20 #include <random>
21 #include <limits> // for numeric_limits<>
22 
23 namespace Gudhi {
24 
25 namespace subsampling {
26 
30 enum : std::size_t {
34  random_starting_point = std::size_t(-1)
35 };
36 
65 template < typename Distance,
66 typename Point_range,
67 typename PointOutputIterator,
68 typename DistanceOutputIterator = Null_output_iterator>
69 void choose_n_farthest_points(Distance dist,
70  Point_range const &input_pts,
71  std::size_t final_size,
72  std::size_t starting_point,
73  PointOutputIterator output_it,
74  DistanceOutputIterator dist_it = {}) {
75  std::size_t nb_points = boost::size(input_pts);
76  if (final_size > nb_points)
77  final_size = nb_points;
78 
79  // Tests to the limit
80  if (final_size < 1)
81  return;
82 
83  if (starting_point == random_starting_point) {
84  // Choose randomly the first landmark
85  std::random_device rd;
86  std::mt19937 gen(rd());
87  std::uniform_int_distribution<std::size_t> dis(0, nb_points - 1);
88  starting_point = dis(gen);
89  }
90 
91  std::size_t current_number_of_landmarks = 0; // counter for landmarks
92  static_assert(std::numeric_limits<double>::has_infinity, "the number type needs to support infinity()");
93  // FIXME: don't hard-code the type as double. For Epeck_d, we also want to handle types that do not have an infinity.
94  const double infty = std::numeric_limits<double>::infinity(); // infinity (see next entry)
95  std::vector< double > dist_to_L(nb_points, infty); // vector of current distances to L from input_pts
96 
97  std::size_t curr_max_w = starting_point;
98 
99  for (current_number_of_landmarks = 0; current_number_of_landmarks != final_size; current_number_of_landmarks++) {
100  // curr_max_w at this point is the next landmark
101  *output_it++ = input_pts[curr_max_w];
102  *dist_it++ = dist_to_L[curr_max_w];
103  std::size_t i = 0;
104  for (auto&& p : input_pts) {
105  double curr_dist = dist(p, input_pts[curr_max_w]);
106  if (curr_dist < dist_to_L[i])
107  dist_to_L[i] = curr_dist;
108  ++i;
109  }
110  // choose the next curr_max_w
111  double curr_max_dist = 0; // used for defining the furhest point from L
112  for (i = 0; i < dist_to_L.size(); i++)
113  if (dist_to_L[i] > curr_max_dist) {
114  curr_max_dist = dist_to_L[i];
115  curr_max_w = i;
116  }
117  // If all that remains are duplicates of points already taken, stop.
118  if (curr_max_dist == 0) break;
119  }
120 }
121 
122 } // namespace subsampling
123 
124 } // namespace Gudhi
125 
126 #endif // CHOOSE_N_FARTHEST_POINTS_H_
void choose_n_farthest_points(Distance dist, Point_range const &input_pts, std::size_t final_size, std::size_t starting_point, PointOutputIterator output_it, DistanceOutputIterator dist_it={})
Subsample by a greedy strategy of iteratively adding the farthest point from the current chosen point...
Definition: choose_n_farthest_points.h:69
@ random_starting_point
Definition: choose_n_farthest_points.h:34
Definition: Null_output_iterator.h:19
GUDHI  Version 3.4.1  - C++ library for Topological Data Analysis (TDA) and Higher Dimensional Geometry Understanding.  - Copyright : MIT Generated on Fri Jan 22 2021 10:27:48 for GUDHI by Doxygen 1.9.1