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 
62 template < typename Kernel,
63 typename Point_range,
64 typename PointOutputIterator,
65 typename DistanceOutputIterator = Null_output_iterator>
66 void choose_n_farthest_points(Kernel const &k,
67  Point_range const &input_pts,
68  std::size_t final_size,
69  std::size_t starting_point,
70  PointOutputIterator output_it,
71  DistanceOutputIterator dist_it = {}) {
72  std::size_t nb_points = boost::size(input_pts);
73  if (final_size > nb_points)
74  final_size = nb_points;
75 
76  // Tests to the limit
77  if (final_size < 1)
78  return;
79 
80  if (starting_point == random_starting_point) {
81  // Choose randomly the first landmark
82  std::random_device rd;
83  std::mt19937 gen(rd());
84  std::uniform_int_distribution<std::size_t> dis(0, nb_points - 1);
85  starting_point = dis(gen);
86  }
87 
88  typename Kernel::Squared_distance_d sqdist = k.squared_distance_d_object();
89 
90  std::size_t current_number_of_landmarks = 0; // counter for landmarks
91  const double infty = std::numeric_limits<double>::infinity(); // infinity (see next entry)
92  std::vector< double > dist_to_L(nb_points, infty); // vector of current distances to L from input_pts
93 
94  std::size_t curr_max_w = starting_point;
95 
96  for (current_number_of_landmarks = 0; current_number_of_landmarks != final_size; current_number_of_landmarks++) {
97  // curr_max_w at this point is the next landmark
98  *output_it++ = input_pts[curr_max_w];
99  *dist_it++ = dist_to_L[curr_max_w];
100  std::size_t i = 0;
101  for (auto&& p : input_pts) {
102  double curr_dist = sqdist(p, *(std::begin(input_pts) + curr_max_w));
103  if (curr_dist < dist_to_L[i])
104  dist_to_L[i] = curr_dist;
105  ++i;
106  }
107  // choose the next curr_max_w
108  double curr_max_dist = 0; // used for defining the furhest point from L
109  for (i = 0; i < dist_to_L.size(); i++)
110  if (dist_to_L[i] > curr_max_dist) {
111  curr_max_dist = dist_to_L[i];
112  curr_max_w = i;
113  }
114  }
115 }
116 
117 } // namespace subsampling
118 
119 } // namespace Gudhi
120 
121 #endif // CHOOSE_N_FARTHEST_POINTS_H_
Gudhi::subsampling::choose_n_farthest_points
void choose_n_farthest_points(Kernel const &k, 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:66
Gudhi::Null_output_iterator
Definition: Null_output_iterator.h:19
Gudhi::subsampling::random_starting_point
Definition: choose_n_farthest_points.h:34
GUDHI  Version 3.1.0  - C++ library for Topological Data Analysis (TDA) and Higher Dimensional Geometry Understanding.  - Copyright : MIT Generated on Tue Jan 21 2020 09:26:33 for GUDHI by Doxygen 1.8.16