choose_n_farthest_points.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): Siargey Kachanovich
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 CHOOSE_N_FARTHEST_POINTS_H_
24 #define CHOOSE_N_FARTHEST_POINTS_H_
25 
26 #include <boost/range.hpp>
27 
28 #include <gudhi/Null_output_iterator.h>
29 
30 #include <iterator>
31 #include <vector>
32 #include <random>
33 #include <limits> // for numeric_limits<>
34 
35 namespace Gudhi {
36 
37 namespace subsampling {
38 
42 enum : std::size_t {
46  random_starting_point = std::size_t(-1)
47 };
48 
74 template < typename Kernel,
75 typename Point_range,
76 typename PointOutputIterator,
77 typename DistanceOutputIterator = Null_output_iterator>
78 void choose_n_farthest_points(Kernel const &k,
79  Point_range const &input_pts,
80  std::size_t final_size,
81  std::size_t starting_point,
82  PointOutputIterator output_it,
83  DistanceOutputIterator dist_it = {}) {
84  std::size_t nb_points = boost::size(input_pts);
85  if (final_size > nb_points)
86  final_size = nb_points;
87 
88  // Tests to the limit
89  if (final_size < 1)
90  return;
91 
92  if (starting_point == random_starting_point) {
93  // Choose randomly the first landmark
94  std::random_device rd;
95  std::mt19937 gen(rd());
96  std::uniform_int_distribution<std::size_t> dis(0, nb_points - 1);
97  starting_point = dis(gen);
98  }
99 
100  typename Kernel::Squared_distance_d sqdist = k.squared_distance_d_object();
101 
102  std::size_t current_number_of_landmarks = 0; // counter for landmarks
103  const double infty = std::numeric_limits<double>::infinity(); // infinity (see next entry)
104  std::vector< double > dist_to_L(nb_points, infty); // vector of current distances to L from input_pts
105 
106  std::size_t curr_max_w = starting_point;
107 
108  for (current_number_of_landmarks = 0; current_number_of_landmarks != final_size; current_number_of_landmarks++) {
109  // curr_max_w at this point is the next landmark
110  *output_it++ = input_pts[curr_max_w];
111  *dist_it++ = dist_to_L[curr_max_w];
112  std::size_t i = 0;
113  for (auto&& p : input_pts) {
114  double curr_dist = sqdist(p, *(std::begin(input_pts) + curr_max_w));
115  if (curr_dist < dist_to_L[i])
116  dist_to_L[i] = curr_dist;
117  ++i;
118  }
119  // choose the next curr_max_w
120  double curr_max_dist = 0; // used for defining the furhest point from L
121  for (i = 0; i < dist_to_L.size(); i++)
122  if (dist_to_L[i] > curr_max_dist) {
123  curr_max_dist = dist_to_L[i];
124  curr_max_w = i;
125  }
126  }
127 }
128 
129 } // namespace subsampling
130 
131 } // namespace Gudhi
132 
133 #endif // CHOOSE_N_FARTHEST_POINTS_H_
Definition: Null_output_iterator.h:31
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:78
Definition: SimplicialComplexForAlpha.h:26
Definition: choose_n_farthest_points.h:46
GUDHI  Version 2.2.0  - C++ library for Topological Data Analysis (TDA) and Higher Dimensional Geometry Understanding.  - Copyright : GPL v3 Generated on Tue Jul 17 2018 12:56:28 for GUDHI by Doxygen 1.8.13