summaryrefslogtreecommitdiff
path: root/src/Subsampling
diff options
context:
space:
mode:
Diffstat (limited to 'src/Subsampling')
-rw-r--r--src/Subsampling/doc/Intro_subsampling.h56
-rw-r--r--src/Subsampling/example/CMakeLists.txt22
-rw-r--r--src/Subsampling/example/example_choose_n_farthest_points.cpp30
-rw-r--r--src/Subsampling/example/example_custom_kernel.cpp63
-rw-r--r--src/Subsampling/example/example_pick_n_random_points.cpp28
-rw-r--r--src/Subsampling/example/example_sparsify_point_set.cpp28
-rw-r--r--src/Subsampling/include/gudhi/choose_n_farthest_points.h121
-rw-r--r--src/Subsampling/include/gudhi/pick_n_random_points.h74
-rw-r--r--src/Subsampling/include/gudhi/sparsify_point_set.h101
-rw-r--r--src/Subsampling/test/CMakeLists.txt18
-rw-r--r--src/Subsampling/test/test_choose_n_farthest_points.cpp102
-rw-r--r--src/Subsampling/test/test_pick_n_random_points.cpp57
-rw-r--r--src/Subsampling/test/test_sparsify_point_set.cpp43
13 files changed, 743 insertions, 0 deletions
diff --git a/src/Subsampling/doc/Intro_subsampling.h b/src/Subsampling/doc/Intro_subsampling.h
new file mode 100644
index 00000000..1c84fb2e
--- /dev/null
+++ b/src/Subsampling/doc/Intro_subsampling.h
@@ -0,0 +1,56 @@
+/* This file is part of the Gudhi Library - https://gudhi.inria.fr/ - which is released under MIT.
+ * See file LICENSE or go to https://gudhi.inria.fr/licensing/ for full license details.
+ * Author(s): Clement Jamin
+ *
+ * Copyright (C) 2016 Inria
+ *
+ * Modification(s):
+ * - YYYY/MM Author: Description of the modification
+ */
+
+#ifndef DOC_SUBSAMPLING_INTRO_SUBSAMPLING_H_
+#define DOC_SUBSAMPLING_INTRO_SUBSAMPLING_H_
+
+// needs namespace for Doxygen to link on classes
+namespace Gudhi {
+// needs namespace for Doxygen to link on classes
+namespace subsampling {
+
+/** \defgroup subsampling Subsampling
+ *
+ * \author Clément Jamin, Siargey Kachanovich
+ *
+ * @{
+ *
+ * \section subsamplingintroduction Introduction
+ *
+ * This Gudhi component offers methods to subsample a set of points.
+ *
+ * \section sparsifyexamples Example: sparsify_point_set
+ *
+ * This example outputs a subset of the input points so that the
+ * squared distance between any two points
+ * is greater than or equal to 0.4.
+ *
+ * \include Subsampling/example_sparsify_point_set.cpp
+ *
+ * \section farthestpointexamples Example: choose_n_farthest_points
+ *
+ * This example outputs a subset of 100 points obtained by González algorithm,
+ * starting with a random point.
+ *
+ * \include Subsampling/example_choose_n_farthest_points.cpp
+ *
+ * \section randompointexamples Example: pick_n_random_points
+ *
+ * This example outputs a subset of 100 points picked randomly.
+ *
+ * \include Subsampling/example_pick_n_random_points.cpp
+ */
+/** @} */ // end defgroup subsampling
+
+} // namespace subsampling
+
+} // namespace Gudhi
+
+#endif // DOC_SUBSAMPLING_INTRO_SUBSAMPLING_H_
diff --git a/src/Subsampling/example/CMakeLists.txt b/src/Subsampling/example/CMakeLists.txt
new file mode 100644
index 00000000..28aab103
--- /dev/null
+++ b/src/Subsampling/example/CMakeLists.txt
@@ -0,0 +1,22 @@
+project(Subsampling_examples)
+
+if(NOT CGAL_WITH_EIGEN3_VERSION VERSION_LESS 4.11.0)
+ add_executable(Subsampling_example_pick_n_random_points example_pick_n_random_points.cpp)
+ add_executable(Subsampling_example_choose_n_farthest_points example_choose_n_farthest_points.cpp)
+ add_executable(Subsampling_example_custom_kernel example_custom_kernel.cpp)
+ add_executable(Subsampling_example_sparsify_point_set example_sparsify_point_set.cpp)
+ target_link_libraries(Subsampling_example_sparsify_point_set ${CGAL_LIBRARY})
+
+ add_test(NAME Subsampling_example_pick_n_random_points
+ COMMAND $<TARGET_FILE:Subsampling_example_pick_n_random_points>)
+ add_test(NAME Subsampling_example_choose_n_farthest_points
+ COMMAND $<TARGET_FILE:Subsampling_example_choose_n_farthest_points>)
+ add_test(NAME Subsampling_example_sparsify_point_set
+ COMMAND $<TARGET_FILE:Subsampling_example_sparsify_point_set>)
+
+ install(TARGETS Subsampling_example_pick_n_random_points DESTINATION bin)
+ install(TARGETS Subsampling_example_choose_n_farthest_points DESTINATION bin)
+ install(TARGETS Subsampling_example_custom_kernel DESTINATION bin)
+ install(TARGETS Subsampling_example_sparsify_point_set DESTINATION bin)
+
+endif(NOT CGAL_WITH_EIGEN3_VERSION VERSION_LESS 4.11.0)
diff --git a/src/Subsampling/example/example_choose_n_farthest_points.cpp b/src/Subsampling/example/example_choose_n_farthest_points.cpp
new file mode 100644
index 00000000..5cfeb4d8
--- /dev/null
+++ b/src/Subsampling/example/example_choose_n_farthest_points.cpp
@@ -0,0 +1,30 @@
+#include <gudhi/choose_n_farthest_points.h>
+
+#include <CGAL/Epick_d.h>
+#include <CGAL/Random.h>
+
+#include <iostream>
+#include <vector>
+#include <iterator>
+
+int main(void) {
+ typedef CGAL::Epick_d<CGAL::Dimension_tag<4> > K;
+ typedef typename K::Point_d Point_d;
+
+ CGAL::Random rd;
+
+ std::vector<Point_d> points;
+ for (int i = 0; i < 500; ++i)
+ points.push_back(Point_d(rd.get_double(-1., 1), rd.get_double(-1., 1),
+ rd.get_double(-1., 1), rd.get_double(-1., 1)));
+
+ K k;
+ std::vector<Point_d> results;
+ Gudhi::subsampling::choose_n_farthest_points(k, points, 100,
+ Gudhi::subsampling::random_starting_point,
+ std::back_inserter(results));
+ std::cout << "Before sparsification: " << points.size() << " points.\n";
+ std::cout << "After sparsification: " << results.size() << " points.\n";
+
+ return 0;
+}
diff --git a/src/Subsampling/example/example_custom_kernel.cpp b/src/Subsampling/example/example_custom_kernel.cpp
new file mode 100644
index 00000000..f1eb757b
--- /dev/null
+++ b/src/Subsampling/example/example_custom_kernel.cpp
@@ -0,0 +1,63 @@
+#include <gudhi/choose_n_farthest_points.h>
+
+#include <iostream>
+#include <vector>
+#include <iterator>
+
+
+/* The class Kernel contains a distance function defined on the set of points {0, 1, 2, 3}
+ * and computes a distance according to the matrix:
+ * 0 1 2 4
+ * 1 0 4 2
+ * 2 4 0 1
+ * 4 2 1 0
+ */
+class Kernel {
+ public:
+ typedef double FT;
+ typedef unsigned Point_d;
+
+ // Class Squared_distance_d
+ class Squared_distance_d {
+ private:
+ std::vector<std::vector<FT>> matrix_;
+
+ public:
+ Squared_distance_d() {
+ matrix_.push_back(std::vector<FT>({0, 1, 2, 4}));
+ matrix_.push_back(std::vector<FT>({1, 0, 4, 2}));
+ matrix_.push_back(std::vector<FT>({2, 4, 0, 1}));
+ matrix_.push_back(std::vector<FT>({4, 2, 1, 0}));
+ }
+
+ FT operator()(Point_d p1, Point_d p2) {
+ return matrix_[p1][p2];
+ }
+ };
+
+ // Constructor
+ Kernel() {}
+
+ // Object of type Squared_distance_d
+ Squared_distance_d squared_distance_d_object() const {
+ return Squared_distance_d();
+ }
+};
+
+int main(void) {
+ typedef Kernel K;
+ typedef typename K::Point_d Point_d;
+
+ K k;
+ std::vector<Point_d> points = {0, 1, 2, 3};
+ std::vector<Point_d> results;
+
+ Gudhi::subsampling::choose_n_farthest_points(k, points, 2,
+ Gudhi::subsampling::random_starting_point,
+ std::back_inserter(results));
+ std::cout << "Before sparsification: " << points.size() << " points.\n";
+ std::cout << "After sparsification: " << results.size() << " points.\n";
+ std::cout << "Result table: {" << results[0] << "," << results[1] << "}\n";
+
+ return 0;
+}
diff --git a/src/Subsampling/example/example_pick_n_random_points.cpp b/src/Subsampling/example/example_pick_n_random_points.cpp
new file mode 100644
index 00000000..25266403
--- /dev/null
+++ b/src/Subsampling/example/example_pick_n_random_points.cpp
@@ -0,0 +1,28 @@
+#include <gudhi/pick_n_random_points.h>
+
+#include <CGAL/Epick_d.h>
+#include <CGAL/Random.h>
+
+#include <iostream>
+#include <vector>
+#include <iterator>
+
+int main(void) {
+ typedef CGAL::Epick_d<CGAL::Dimension_tag<4> > K;
+ typedef typename K::Point_d Point_d;
+
+ CGAL::Random rd;
+
+ std::vector<Point_d> points;
+ for (int i = 0; i < 500; ++i)
+ points.push_back(Point_d(rd.get_double(-1., 1), rd.get_double(-1., 1),
+ rd.get_double(-1., 1), rd.get_double(-1., 1)));
+
+ K k;
+ std::vector<Point_d> results;
+ Gudhi::subsampling::pick_n_random_points(points, 100, std::back_inserter(results));
+ std::cout << "Before sparsification: " << points.size() << " points.\n";
+ std::cout << "After sparsification: " << results.size() << " points.\n";
+
+ return 0;
+}
diff --git a/src/Subsampling/example/example_sparsify_point_set.cpp b/src/Subsampling/example/example_sparsify_point_set.cpp
new file mode 100644
index 00000000..a8caa720
--- /dev/null
+++ b/src/Subsampling/example/example_sparsify_point_set.cpp
@@ -0,0 +1,28 @@
+#include <gudhi/sparsify_point_set.h>
+
+#include <CGAL/Epick_d.h>
+#include <CGAL/Random.h>
+
+#include <iostream>
+#include <vector>
+#include <iterator>
+
+int main(void) {
+ typedef CGAL::Epick_d<CGAL::Dimension_tag<4> > K;
+ typedef typename K::Point_d Point_d;
+
+ CGAL::Random rd;
+
+ std::vector<Point_d> points;
+ for (int i = 0; i < 500; ++i)
+ points.push_back(Point_d(rd.get_double(-1., 1), rd.get_double(-1., 1),
+ rd.get_double(-1., 1), rd.get_double(-1., 1)));
+
+ K k;
+ std::vector<Point_d> results;
+ Gudhi::subsampling::sparsify_point_set(k, points, 0.4, std::back_inserter(results));
+ std::cout << "Before sparsification: " << points.size() << " points.\n";
+ std::cout << "After sparsification: " << results.size() << " points.\n";
+
+ return 0;
+}
diff --git a/src/Subsampling/include/gudhi/choose_n_farthest_points.h b/src/Subsampling/include/gudhi/choose_n_farthest_points.h
new file mode 100644
index 00000000..66421a69
--- /dev/null
+++ b/src/Subsampling/include/gudhi/choose_n_farthest_points.h
@@ -0,0 +1,121 @@
+/* This file is part of the Gudhi Library - https://gudhi.inria.fr/ - which is released under MIT.
+ * See file LICENSE or go to https://gudhi.inria.fr/licensing/ for full license details.
+ * Author(s): Siargey Kachanovich
+ *
+ * Copyright (C) 2016 Inria
+ *
+ * Modification(s):
+ * - YYYY/MM Author: Description of the modification
+ */
+
+#ifndef CHOOSE_N_FARTHEST_POINTS_H_
+#define CHOOSE_N_FARTHEST_POINTS_H_
+
+#include <boost/range.hpp>
+
+#include <gudhi/Null_output_iterator.h>
+
+#include <iterator>
+#include <vector>
+#include <random>
+#include <limits> // for numeric_limits<>
+
+namespace Gudhi {
+
+namespace subsampling {
+
+/**
+ * \ingroup subsampling
+ */
+enum : std::size_t {
+/**
+ * Argument for `choose_n_farthest_points` to indicate that the starting point should be picked randomly.
+ */
+ random_starting_point = std::size_t(-1)
+};
+
+/**
+ * \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` or, if `starting point==random_starting_point`, 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> (despite the name, taken from CGAL, this can be any kind of metric or proximity measure).
+ * It must also contain a public member `squared_distance_d_object()` that returns an 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 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 for points.
+ * @param[out] dist_it The optional output iterator for distances.
+ *
+ */
+template < typename Kernel,
+typename Point_range,
+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,
+ PointOutputIterator output_it,
+ DistanceOutputIterator dist_it = {}) {
+ std::size_t nb_points = boost::size(input_pts);
+ if (final_size > nb_points)
+ final_size = nb_points;
+
+ // Tests to the limit
+ if (final_size < 1)
+ return;
+
+ if (starting_point == random_starting_point) {
+ // Choose randomly the first landmark
+ std::random_device rd;
+ std::mt19937 gen(rd());
+ std::uniform_int_distribution<std::size_t> dis(0, nb_points - 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
+ const double infty = std::numeric_limits<double>::infinity(); // infinity (see next entry)
+ std::vector< double > dist_to_L(nb_points, infty); // vector of current distances to L from input_pts
+
+ std::size_t curr_max_w = starting_point;
+
+ 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));
+ if (curr_dist < dist_to_L[i])
+ dist_to_L[i] = curr_dist;
+ ++i;
+ }
+ // choose the next curr_max_w
+ double curr_max_dist = 0; // used for defining the furhest point from L
+ for (i = 0; i < dist_to_L.size(); i++)
+ if (dist_to_L[i] > curr_max_dist) {
+ curr_max_dist = dist_to_L[i];
+ curr_max_w = i;
+ }
+ }
+}
+
+} // namespace subsampling
+
+} // namespace Gudhi
+
+#endif // CHOOSE_N_FARTHEST_POINTS_H_
diff --git a/src/Subsampling/include/gudhi/pick_n_random_points.h b/src/Subsampling/include/gudhi/pick_n_random_points.h
new file mode 100644
index 00000000..a67b2b84
--- /dev/null
+++ b/src/Subsampling/include/gudhi/pick_n_random_points.h
@@ -0,0 +1,74 @@
+/* This file is part of the Gudhi Library - https://gudhi.inria.fr/ - which is released under MIT.
+ * See file LICENSE or go to https://gudhi.inria.fr/licensing/ for full license details.
+ * Author(s): Siargey Kachanovich
+ *
+ * Copyright (C) 2016 Inria
+ *
+ * Modification(s):
+ * - YYYY/MM Author: Description of the modification
+ */
+
+#ifndef PICK_N_RANDOM_POINTS_H_
+#define PICK_N_RANDOM_POINTS_H_
+
+#include <gudhi/Clock.h>
+
+#include <boost/range/size.hpp>
+
+#include <cstddef>
+#include <random> // random_device, mt19937
+#include <algorithm> // shuffle
+#include <numeric> // iota
+#include <iterator>
+#include <vector>
+
+
+namespace Gudhi {
+
+namespace subsampling {
+
+/**
+ * \ingroup subsampling
+ * \brief Subsample a point set by picking random vertices.
+ *
+ * \details It chooses `final_size` distinct points from a random access range `points`
+ * and outputs them to the output iterator `output_it`.
+ * Point_container::iterator should be ValueSwappable and RandomAccessIterator.
+ */
+template <typename Point_container,
+typename OutputIterator>
+void pick_n_random_points(Point_container const &points,
+ std::size_t final_size,
+ OutputIterator output_it) {
+#ifdef GUDHI_SUBSAMPLING_PROFILING
+ Gudhi::Clock t;
+#endif
+
+ std::size_t nbP = boost::size(points);
+ if (final_size > nbP)
+ final_size = nbP;
+
+ std::vector<int> landmarks(nbP);
+ std::iota(landmarks.begin(), landmarks.end(), 0);
+
+ std::random_device rd;
+ std::mt19937 g(rd());
+
+ std::shuffle(landmarks.begin(), landmarks.end(), g);
+ landmarks.resize(final_size);
+
+ for (int l : landmarks)
+ *output_it++ = points[l];
+
+#ifdef GUDHI_SUBSAMPLING_PROFILING
+ t.end();
+ std::cerr << "Random landmark choice took " << t.num_seconds()
+ << " seconds." << std::endl;
+#endif
+}
+
+} // namespace subsampling
+
+} // namespace Gudhi
+
+#endif // PICK_N_RANDOM_POINTS_H_
diff --git a/src/Subsampling/include/gudhi/sparsify_point_set.h b/src/Subsampling/include/gudhi/sparsify_point_set.h
new file mode 100644
index 00000000..b30cec80
--- /dev/null
+++ b/src/Subsampling/include/gudhi/sparsify_point_set.h
@@ -0,0 +1,101 @@
+/* This file is part of the Gudhi Library - https://gudhi.inria.fr/ - which is released under MIT.
+ * See file LICENSE or go to https://gudhi.inria.fr/licensing/ for full license details.
+ * Author(s): Clement Jamin
+ *
+ * Copyright (C) 2016 Inria
+ *
+ * Modification(s):
+ * - YYYY/MM Author: Description of the modification
+ */
+
+#ifndef SPARSIFY_POINT_SET_H_
+#define SPARSIFY_POINT_SET_H_
+
+#include <gudhi/Kd_tree_search.h>
+#ifdef GUDHI_SUBSAMPLING_PROFILING
+#include <gudhi/Clock.h>
+#endif
+
+#include <cstddef>
+#include <vector>
+
+namespace Gudhi {
+
+namespace subsampling {
+
+/**
+ * \ingroup subsampling
+ * \brief Outputs a subset of the input points so that the
+ * squared distance between any two points
+ * is greater than or equal to `min_squared_dist`.
+ *
+ * \tparam Kernel must be a model of the <a target="_blank"
+ * href="http://doc.cgal.org/latest/Spatial_searching/classSearchTraits.html">SearchTraits</a>
+ * concept, such as the <a target="_blank"
+ * href="http://doc.cgal.org/latest/Kernel_d/classCGAL_1_1Epick__d.html">CGAL::Epick_d</a> class, which
+ * can be static if you know the ambiant dimension at compile-time, or dynamic if you don't.
+ * \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.
+ *
+ * @param[in] k A kernel object.
+ * @param[in] input_pts Const reference to the input points.
+ * @param[in] min_squared_dist Minimum squared distance separating the output points.
+ * @param[out] output_it The output iterator.
+ */
+template <typename Kernel, typename Point_range, typename OutputIterator>
+void
+sparsify_point_set(
+ const Kernel &k, Point_range const& input_pts,
+ typename Kernel::FT min_squared_dist,
+ OutputIterator output_it) {
+ typedef typename Gudhi::spatial_searching::Kd_tree_search<
+ Kernel, Point_range> Points_ds;
+
+#ifdef GUDHI_SUBSAMPLING_PROFILING
+ Gudhi::Clock t;
+#endif
+
+ Points_ds points_ds(input_pts);
+
+ std::vector<bool> dropped_points(input_pts.size(), false);
+
+ // Parse the input points, and add them if they are not too close to
+ // the other points
+ std::size_t pt_idx = 0;
+ for (typename Point_range::const_iterator it_pt = input_pts.begin();
+ it_pt != input_pts.end();
+ ++it_pt, ++pt_idx) {
+ if (dropped_points[pt_idx])
+ continue;
+
+ *output_it++ = *it_pt;
+
+ auto ins_range = points_ds.incremental_nearest_neighbors(*it_pt);
+
+ // If another point Q is closer that min_squared_dist, mark Q to be dropped
+ for (auto const& neighbor : ins_range) {
+ std::size_t neighbor_point_idx = neighbor.first;
+ // If the neighbor is too close, we drop the neighbor
+ if (neighbor.second < min_squared_dist) {
+ // N.B.: If neighbor_point_idx < pt_idx,
+ // dropped_points[neighbor_point_idx] is already true but adding a
+ // test doesn't make things faster, so why bother?
+ dropped_points[neighbor_point_idx] = true;
+ } else {
+ break;
+ }
+ }
+ }
+
+#ifdef GUDHI_SUBSAMPLING_PROFILING
+ t.end();
+ std::cerr << "Point set sparsified in " << t.num_seconds()
+ << " seconds." << std::endl;
+#endif
+}
+
+} // namespace subsampling
+} // namespace Gudhi
+
+#endif // SPARSIFY_POINT_SET_H_
diff --git a/src/Subsampling/test/CMakeLists.txt b/src/Subsampling/test/CMakeLists.txt
new file mode 100644
index 00000000..cf54788e
--- /dev/null
+++ b/src/Subsampling/test/CMakeLists.txt
@@ -0,0 +1,18 @@
+project(Subsampling_tests)
+
+if(NOT CGAL_WITH_EIGEN3_VERSION VERSION_LESS 4.11.0)
+ include(GUDHI_test_coverage)
+
+ add_executable( Subsampling_test_pick_n_random_points test_pick_n_random_points.cpp )
+ target_link_libraries(Subsampling_test_pick_n_random_points ${CGAL_LIBRARY} ${Boost_UNIT_TEST_FRAMEWORK_LIBRARY})
+
+ add_executable( Subsampling_test_choose_n_farthest_points test_choose_n_farthest_points.cpp )
+ target_link_libraries(Subsampling_test_choose_n_farthest_points ${CGAL_LIBRARY} ${Boost_UNIT_TEST_FRAMEWORK_LIBRARY})
+
+ add_executable(Subsampling_test_sparsify_point_set test_sparsify_point_set.cpp)
+ target_link_libraries(Subsampling_test_sparsify_point_set ${CGAL_LIBRARY} ${Boost_UNIT_TEST_FRAMEWORK_LIBRARY})
+
+ gudhi_add_coverage_test(Subsampling_test_pick_n_random_points)
+ gudhi_add_coverage_test(Subsampling_test_choose_n_farthest_points)
+ gudhi_add_coverage_test(Subsampling_test_sparsify_point_set)
+endif(NOT CGAL_WITH_EIGEN3_VERSION VERSION_LESS 4.11.0)
diff --git a/src/Subsampling/test/test_choose_n_farthest_points.cpp b/src/Subsampling/test/test_choose_n_farthest_points.cpp
new file mode 100644
index 00000000..5c4bd4cb
--- /dev/null
+++ b/src/Subsampling/test/test_choose_n_farthest_points.cpp
@@ -0,0 +1,102 @@
+/* This file is part of the Gudhi Library - https://gudhi.inria.fr/ - which is released under MIT.
+ * See file LICENSE or go to https://gudhi.inria.fr/licensing/ for full license details.
+ * Author(s): Siargey Kachanovich
+ *
+ * Copyright (C) 2016 Inria
+ *
+ * Modification(s):
+ * - YYYY/MM Author: Description of the modification
+ */
+
+// #ifdef _DEBUG
+// # define TBB_USE_THREADING_TOOL
+// #endif
+
+#define BOOST_TEST_DYN_LINK
+#define BOOST_TEST_MODULE Subsampling - test choose_n_farthest_points
+#include <boost/test/unit_test.hpp>
+#include <boost/mpl/list.hpp>
+
+#include <gudhi/choose_n_farthest_points.h>
+#include <vector>
+#include <iterator>
+
+#include <CGAL/Epick_d.h>
+
+typedef CGAL::Epick_d<CGAL::Dynamic_dimension_tag> K;
+typedef typename K::FT FT;
+typedef typename K::Point_d Point_d;
+
+typedef boost::mpl::list<CGAL::Epick_d<CGAL::Dynamic_dimension_tag>, CGAL::Epick_d<CGAL::Dimension_tag<4>>> list_of_tested_kernels;
+
+BOOST_AUTO_TEST_CASE_TEMPLATE(test_choose_farthest_point, Kernel, list_of_tested_kernels) {
+ typedef typename Kernel::FT FT;
+ typedef typename Kernel::Point_d Point_d;
+ std::vector< Point_d > points, landmarks;
+ // Add grid points (625 points)
+ for (FT i = 0; i < 5; i += 1.0)
+ for (FT j = 0; j < 5; j += 1.0)
+ for (FT k = 0; k < 5; k += 1.0)
+ for (FT l = 0; l < 5; l += 1.0) {
+ std::vector<FT> point({i, j, k, l});
+ points.push_back(Point_d(point.begin(), point.end()));
+ }
+
+ landmarks.clear();
+ Kernel k;
+ Gudhi::subsampling::choose_n_farthest_points(k, points, 100, Gudhi::subsampling::random_starting_point, std::back_inserter(landmarks));
+
+ BOOST_CHECK(landmarks.size() == 100);
+ for (auto landmark : landmarks)
+ {
+ // Check all landmarks are in points
+ BOOST_CHECK(std::find (points.begin(), points.end(), landmark) != points.end());
+ }
+}
+
+BOOST_AUTO_TEST_CASE_TEMPLATE(test_choose_farthest_point_limits, Kernel, list_of_tested_kernels) {
+ 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, -1, std::back_inserter(landmarks), std::back_inserter(distances));
+ BOOST_CHECK(landmarks.size() == 0);
+ landmarks.clear(); distances.clear();
+ // Choose 0 farthest points in an empty point cloud
+ 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(); distances.clear();
+ // Choose 1 farthest points in an empty point cloud
+ 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(); 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 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, -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, -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();
+}
diff --git a/src/Subsampling/test/test_pick_n_random_points.cpp b/src/Subsampling/test/test_pick_n_random_points.cpp
new file mode 100644
index 00000000..018fb8d2
--- /dev/null
+++ b/src/Subsampling/test/test_pick_n_random_points.cpp
@@ -0,0 +1,57 @@
+/* This file is part of the Gudhi Library - https://gudhi.inria.fr/ - which is released under MIT.
+ * See file LICENSE or go to https://gudhi.inria.fr/licensing/ for full license details.
+ * Author(s): Siargey Kachanovich
+ *
+ * Copyright (C) 2016 Inria
+ *
+ * Modification(s):
+ * - YYYY/MM Author: Description of the modification
+ */
+
+// #ifdef _DEBUG
+// # define TBB_USE_THREADING_TOOL
+// #endif
+
+#define BOOST_TEST_DYN_LINK
+#define BOOST_TEST_MODULE Subsampling - test pick_n_random_points
+#include <boost/test/unit_test.hpp>
+
+#include <gudhi/pick_n_random_points.h>
+#include <vector>
+#include <iterator>
+
+#include <CGAL/Epick_d.h>
+
+
+BOOST_AUTO_TEST_CASE(test_pick_n_random_points)
+{
+ typedef CGAL::Epick_d<CGAL::Dynamic_dimension_tag> K;
+ typedef typename K::FT FT;
+ typedef typename K::Point_d Point_d;
+
+ std::vector<Point_d> vect;
+ vect.push_back(Point_d(std::vector<FT>({0,0,0,0})));
+ vect.push_back(Point_d(std::vector<FT>({0,0,0,1})));
+ vect.push_back(Point_d(std::vector<FT>({0,0,1,0})));
+ vect.push_back(Point_d(std::vector<FT>({0,0,1,1})));
+ vect.push_back(Point_d(std::vector<FT>({0,1,0,0})));
+ vect.push_back(Point_d(std::vector<FT>({0,1,0,1})));
+ vect.push_back(Point_d(std::vector<FT>({0,1,1,0})));
+ vect.push_back(Point_d(std::vector<FT>({0,1,1,1})));
+ vect.push_back(Point_d(std::vector<FT>({1,0,0,0})));
+ vect.push_back(Point_d(std::vector<FT>({1,0,0,1})));
+ vect.push_back(Point_d(std::vector<FT>({1,0,1,0})));
+ vect.push_back(Point_d(std::vector<FT>({1,0,1,1})));
+ vect.push_back(Point_d(std::vector<FT>({1,1,0,0})));
+ vect.push_back(Point_d(std::vector<FT>({1,1,0,1})));
+ vect.push_back(Point_d(std::vector<FT>({1,1,1,0})));
+ vect.push_back(Point_d(std::vector<FT>({1,1,1,1})));
+
+ std::vector<Point_d> results;
+ Gudhi::subsampling::pick_n_random_points(vect, 5, std::back_inserter(results));
+ std::cout << "landmark vector contains: ";
+ for (auto l: results)
+ std::cout << l << "\n";
+
+ BOOST_CHECK(results.size() == 5);
+}
diff --git a/src/Subsampling/test/test_sparsify_point_set.cpp b/src/Subsampling/test/test_sparsify_point_set.cpp
new file mode 100644
index 00000000..587ab3ad
--- /dev/null
+++ b/src/Subsampling/test/test_sparsify_point_set.cpp
@@ -0,0 +1,43 @@
+/* This file is part of the Gudhi Library - https://gudhi.inria.fr/ - which is released under MIT.
+ * See file LICENSE or go to https://gudhi.inria.fr/licensing/ for full license details.
+ * Author(s): Clement Jamin
+ *
+ * Copyright (C) 2016 Inria
+ *
+ * Modification(s):
+ * - YYYY/MM Author: Description of the modification
+ */
+
+#define BOOST_TEST_DYN_LINK
+#define BOOST_TEST_MODULE Subsampling - test sparsify_point_set
+#include <boost/test/unit_test.hpp>
+
+#include <gudhi/sparsify_point_set.h>
+
+#include <CGAL/Epick_d.h>
+#include <CGAL/Random.h>
+
+#include <vector>
+#include <iterator>
+
+BOOST_AUTO_TEST_CASE(test_sparsify_point_set)
+{
+ typedef CGAL::Epick_d<CGAL::Dimension_tag<4> > K;
+ typedef typename K::Point_d Point_d;
+
+ CGAL::Random rd;
+
+ std::vector<Point_d> points;
+ for (int i = 0 ; i < 500 ; ++i)
+ points.push_back(Point_d(rd.get_double(-1.,1),rd.get_double(-1.,1),rd.get_double(-1.,1),rd.get_double(-1.,1)));
+
+ K k;
+ std::vector<Point_d> results;
+ Gudhi::subsampling::sparsify_point_set(k, points, 0.5, std::back_inserter(results));
+ std::cout << "Before sparsification: " << points.size() << " points.\n";
+ std::cout << "After sparsification: " << results.size() << " points.\n";
+ //for (auto p : results)
+ // std::cout << p << "\n";
+
+ BOOST_CHECK(points.size() > results.size());
+}
generated by cgit v1.2.3 (git 2.39.1) at 2024-05-17 09:17:46 +0000