Let choose_n_farthest_points output distances (optional).

Drop unused CGAL includes.


git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/trunk@2105 636b058d-ea47-450e-bf9e-a15bfbe3eedb

Former-commit-id: c5a34492a451c8455c42eb8db1c6c7ca5f1bc7b2

2 files changed, 55 insertions, 45 deletions

diff --git a/src/Subsampling/include/gudhi/choose_n_farthest_points.h b/src/Subsampling/include/gudhi/choose_n_farthest_points.h
index 5e908090..a77d0cd7 100644
--- a/src/Subsampling/include/gudhi/choose_n_farthest_points.h
+++ b/src/Subsampling/include/gudhi/choose_n_farthest_points.h
@@ -25,16 +25,10 @@
 
 #include <boost/range.hpp>
 
-#include <gudhi/Kd_tree_search.h>
-
+#include <gudhi/Null_output_iterator.h>
 #include <gudhi/Clock.h>
 
-#include <CGAL/Search_traits.h>
-#include <CGAL/Search_traits_adapter.h>
-#include <CGAL/Fuzzy_sphere.h>
-
 #include <iterator>
-#include <algorithm>  // for sort
 #include <vector>
 #include <random>
 #include <limits>  // for numeric_limits<>
@@ -47,7 +41,7 @@ namespace subsampling {
  *  \ingroup subsampling
  *  \brief Subsample by a greedy strategy of iteratively adding the farthest point from the
  *  current chosen point set to the subsampling. 
- *  The iteration starts with the landmark `starting point`.
+ *  The iteration starts with the landmark `starting point` or, if `starting point==-1`, with a random landmark.
  *  \tparam Kernel must provide a type Kernel::Squared_distance_d which is a model of the 
  *          concept <a target="_blank"
  *   href="http://doc.cgal.org/latest/Kernel_d/classKernel__d_1_1Squared__distance__d.html">Kernel_d::Squared_distance_d</a>
@@ -55,24 +49,30 @@ namespace subsampling {
  *  It must also contain a public member 'squared_distance_d_object' of this type.
  *  \tparam Point_range Range whose value type is Kernel::Point_d.  It must provide random-access 
  *         via `operator[]` and the points should be stored contiguously in memory.
- *  \tparam OutputIterator Output iterator whose value type is Kernel::Point_d.
- *  \details It chooses `final_size` points from a random access range `input_pts` and
- *  outputs it in the output iterator `output_it`.
+ *  \tparam PointOutputIterator Output iterator whose value type is Kernel::Point_d.
+ *  \tparam DistanceOutputIterator Output iterator for distances.
+ *  \details It chooses `final_size` points from a random access range
+ *  `input_pts` and outputs them in the output iterator `output_it`. It also
+ *  outputs the distance from each of those points to the set of previous
+ *  points in `dist_it`.
  * @param[in] k A kernel object.
  * @param[in] input_pts Const reference to the input points.
  * @param[in] final_size The size of the subsample to compute.
  * @param[in] starting_point The seed in the farthest point algorithm.
- * @param[out] output_it The output iterator.
+ * @param[out] output_it The output iterator for points.
+ * @param[out] dist_it The optional output iterator for distances.
  *  
  */
 template < typename Kernel,
 typename Point_range,
-typename OutputIterator>
+typename PointOutputIterator,
+typename DistanceOutputIterator=Null_output_iterator>
 void choose_n_farthest_points(Kernel const &k,
                               Point_range const &input_pts,
                               std::size_t final_size,
                               std::size_t starting_point,
-                              OutputIterator output_it) {
+                              PointOutputIterator output_it,
+                              DistanceOutputIterator dist_it={}) {
   std::size_t nb_points = boost::size(input_pts);
   if (final_size > nb_points)
     final_size = nb_points;
@@ -81,6 +81,14 @@ void choose_n_farthest_points(Kernel const &k,
   if (final_size < 1)
     return;
 
+  if (starting_point == std::size_t(-1)) {
+    // Choose randomly the first landmark
+    std::random_device rd;
+    std::mt19937 gen(rd());
+    std::uniform_int_distribution<std::size_t> dis(0, (input_pts.size() - 1));
+    starting_point = dis(gen);
+  }
+
   typename Kernel::Squared_distance_d sqdist = k.squared_distance_d_object();
 
   std::size_t current_number_of_landmarks = 0;  // counter for landmarks
@@ -92,6 +100,7 @@ void choose_n_farthest_points(Kernel const &k,
   for (current_number_of_landmarks = 0; current_number_of_landmarks != final_size; current_number_of_landmarks++) {
     // curr_max_w at this point is the next landmark
     *output_it++ = input_pts[curr_max_w];
+    *dist_it++ = dist_to_L[curr_max_w];
     std::size_t i = 0;
     for (auto& p : input_pts) {
       double curr_dist = sqdist(p, *(std::begin(input_pts) + curr_max_w));
@@ -121,7 +130,7 @@ void choose_n_farthest_points(Kernel const &k,
  *  It must also contain a public member 'squared_distance_d_object' of this type.
  *  \tparam Point_range Range whose value type is Kernel::Point_d.  It must provide random-access 
  *         via `operator[]` and the points should be stored contiguously in memory.
- *  \tparam OutputIterator Output iterator whose value type is Kernel::Point_d.
+ *  \tparam PointOutputIterator Output iterator whose value type is Kernel::Point_d.
  *  \details It chooses `final_size` points from a random access range `input_pts` and
  *  outputs it in the output iterator `output_it`.
  * @param[in] k A kernel object.
@@ -132,22 +141,12 @@ void choose_n_farthest_points(Kernel const &k,
  */
 template < typename Kernel,
 typename Point_range,
-typename OutputIterator>
+typename PointOutputIterator>
 void choose_n_farthest_points(Kernel const& k,
                               Point_range const &input_pts,
-                              unsigned final_size,
-                              OutputIterator output_it) {
-  // Tests to the limit
-  if ((final_size < 1) || (input_pts.size() == 0))
-    return;
-
-  // Choose randomly the first landmark
-  std::random_device rd;
-  std::mt19937 gen(rd());
-  std::uniform_int_distribution<> dis(0, (input_pts.size() - 1));
-  std::size_t starting_point = dis(gen);
-
-  choose_n_farthest_points(k, input_pts, final_size, starting_point, output_it);
+                              std::size_t final_size,
+                              PointOutputIterator output_it) {
+  choose_n_farthest_points(k, input_pts, final_size, -1, output_it);
 }
 
 }  // namespace subsampling
diff --git a/src/Subsampling/test/test_choose_n_farthest_points.cpp b/src/Subsampling/test/test_choose_n_farthest_points.cpp
index 0bc0dff4..6bc5f7b0 100644
--- a/src/Subsampling/test/test_choose_n_farthest_points.cpp
+++ b/src/Subsampling/test/test_choose_n_farthest_points.cpp
@@ -70,34 +70,45 @@ BOOST_AUTO_TEST_CASE_TEMPLATE(test_choose_farthest_point_limits, Kernel, list_of
   typedef typename Kernel::FT FT;
   typedef typename Kernel::Point_d Point_d;
   std::vector< Point_d > points, landmarks;
+  std::vector< FT > distances;
   landmarks.clear();
   Kernel k;
   // Choose -1 farthest points in an empty point cloud
-  Gudhi::subsampling::choose_n_farthest_points(k, points, -1, std::back_inserter(landmarks));
+  Gudhi::subsampling::choose_n_farthest_points(k, points, -1, -1, std::back_inserter(landmarks), std::back_inserter(distances));
   BOOST_CHECK(landmarks.size() == 0);
-  landmarks.clear();
+  landmarks.clear(); distances.clear();
   // Choose 0 farthest points in an empty point cloud
-  Gudhi::subsampling::choose_n_farthest_points(k, points, 0, std::back_inserter(landmarks));
+  Gudhi::subsampling::choose_n_farthest_points(k, points, 0, -1, std::back_inserter(landmarks), std::back_inserter(distances));
   BOOST_CHECK(landmarks.size() == 0);
-  landmarks.clear();
+  landmarks.clear(); distances.clear();
   // Choose 1 farthest points in an empty point cloud
-  Gudhi::subsampling::choose_n_farthest_points(k, points, 1, std::back_inserter(landmarks));
+  Gudhi::subsampling::choose_n_farthest_points(k, points, 1, -1, std::back_inserter(landmarks), std::back_inserter(distances));
   BOOST_CHECK(landmarks.size() == 0);
-  landmarks.clear();
+  landmarks.clear(); distances.clear();
 
   std::vector<FT> point({0.0, 0.0, 0.0, 0.0});
   points.push_back(Point_d(point.begin(), point.end()));
-  // Choose -1 farthest points in an empty point cloud
-  Gudhi::subsampling::choose_n_farthest_points(k, points, -1, std::back_inserter(landmarks));
-  BOOST_CHECK(landmarks.size() == 1);
-  landmarks.clear();
+  // Choose -1 farthest points in a one point cloud
+  Gudhi::subsampling::choose_n_farthest_points(k, points, -1, -1, std::back_inserter(landmarks), std::back_inserter(distances));
+  BOOST_CHECK(landmarks.size() == 1 && distances.size() == 1);
+  BOOST_CHECK(distances[0] == std::numeric_limits<FT>::infinity());
+  landmarks.clear(); distances.clear();
   // Choose 0 farthest points in a one point cloud
-  Gudhi::subsampling::choose_n_farthest_points(k, points, 0, std::back_inserter(landmarks));
-  BOOST_CHECK(landmarks.size() == 0);
-  landmarks.clear();
+  Gudhi::subsampling::choose_n_farthest_points(k, points, 0, -1, std::back_inserter(landmarks), std::back_inserter(distances));
+  BOOST_CHECK(landmarks.size() == 0 && distances.size() == 0);
+  landmarks.clear(); distances.clear();
   // Choose 1 farthest points in a one point cloud
-  Gudhi::subsampling::choose_n_farthest_points(k, points, 1, std::back_inserter(landmarks));
-  BOOST_CHECK(landmarks.size() == 1);
-  landmarks.clear();
+  Gudhi::subsampling::choose_n_farthest_points(k, points, 1, -1, std::back_inserter(landmarks), std::back_inserter(distances));
+  BOOST_CHECK(landmarks.size() == 1 && distances.size() == 1);
+  BOOST_CHECK(distances[0] == std::numeric_limits<FT>::infinity());
+  landmarks.clear(); distances.clear();
 
+  std::vector<FT> point2({1.0, 0.0, 0.0, 0.0});
+  points.push_back(Point_d(point2.begin(), point2.end()));
+  // Choose all farthest points in a one point cloud
+  Gudhi::subsampling::choose_n_farthest_points(k, points, -1, -1, std::back_inserter(landmarks), std::back_inserter(distances));
+  BOOST_CHECK(landmarks.size() == 2 && distances.size() == 2);
+  BOOST_CHECK(distances[0] == std::numeric_limits<FT>::infinity());
+  BOOST_CHECK(distances[1] == 1);
+  landmarks.clear(); distances.clear();
 }