From 9e8db290ff0b3f69f88fa5ed54482bfb6730ad9b Mon Sep 17 00:00:00 2001 From: skachano Date: Wed, 14 Dec 2016 14:03:59 +0000 Subject: Improved the documentation for choose_farthest_points git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/branches/subsampling_and_spatialsearching@1869 636b058d-ea47-450e-bf9e-a15bfbe3eedb Former-commit-id: 08223b7d1788c73b0fb3fc7255a6386896b63626 --- .../include/gudhi/choose_n_farthest_points.h | 31 +++++++++++++++++++--- 1 file changed, 27 insertions(+), 4 deletions(-) (limited to 'src') diff --git a/src/Subsampling/include/gudhi/choose_n_farthest_points.h b/src/Subsampling/include/gudhi/choose_n_farthest_points.h index 40c7808d..43bf6402 100644 --- a/src/Subsampling/include/gudhi/choose_n_farthest_points.h +++ b/src/Subsampling/include/gudhi/choose_n_farthest_points.h @@ -48,15 +48,27 @@ namespace 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`. + * \tparam Kernel must provide a type Kernel::Squared_distance_d which is a model of the + * concept Kernel_d::Squared_distance_d + * concept. + * \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`. + * @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. * */ template < typename Kernel, -typename Point_container, +typename Point_range, typename OutputIterator> void choose_n_farthest_points(Kernel const &k, - Point_container const &input_pts, + Point_range const &input_pts, std::size_t final_size, std::size_t starting_point, OutputIterator output_it) { @@ -96,15 +108,26 @@ void choose_n_farthest_points(Kernel const &k, * \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 a random landmark. + * \tparam Kernel must provide a type Kernel::Squared_distance_d which is a model of the + * concept Kernel_d::Squared_distance_d + * concept. + * \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`. + * @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[out] output_it The output iterator. * */ template < typename Kernel, -typename Point_container, +typename Point_range, typename OutputIterator> void choose_n_farthest_points(Kernel const& k, - Point_container const &input_pts, + Point_range const &input_pts, unsigned final_size, OutputIterator output_it) { // Choose randomly the first landmark -- cgit v1.2.3 From 04f4501b35eaa2bd33393ef2445d038251ba1355 Mon Sep 17 00:00:00 2001 From: skachano Date: Wed, 14 Dec 2016 18:08:09 +0000 Subject: Added an example with a distance matrix for the farthest point algorithm git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/branches/subsampling_and_spatialsearching@1874 636b058d-ea47-450e-bf9e-a15bfbe3eedb Former-commit-id: 340e465189dc7ec8f8706e60e2d8097b53bfd5a0 --- src/Subsampling/example/CMakeLists.txt | 1 + src/Subsampling/example/example_custom_kernel.cpp | 69 ++++++++++++++++++++++ .../include/gudhi/choose_n_farthest_points.h | 4 +- 3 files changed, 73 insertions(+), 1 deletion(-) create mode 100644 src/Subsampling/example/example_custom_kernel.cpp (limited to 'src') diff --git a/src/Subsampling/example/CMakeLists.txt b/src/Subsampling/example/CMakeLists.txt index 54349f0c..0fd3335c 100644 --- a/src/Subsampling/example/CMakeLists.txt +++ b/src/Subsampling/example/CMakeLists.txt @@ -6,6 +6,7 @@ if(CGAL_FOUND) if (EIGEN3_FOUND) 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}) diff --git a/src/Subsampling/example/example_custom_kernel.cpp b/src/Subsampling/example/example_custom_kernel.cpp new file mode 100644 index 00000000..05797ebe --- /dev/null +++ b/src/Subsampling/example/example_custom_kernel.cpp @@ -0,0 +1,69 @@ +#include + +#include +#include + +#include +#include + + +/* 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> matrix_; + + public: + + Squared_distance_d() + { + matrix_.push_back(std::vector({0,1,2,4})); + matrix_.push_back(std::vector({1,0,4,2})); + matrix_.push_back(std::vector({2,4,0,1})); + matrix_.push_back(std::vector({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 points = {0,1,2,3}; + std::vector results; + + Gudhi::subsampling::choose_n_farthest_points(k, points, 2, 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/include/gudhi/choose_n_farthest_points.h b/src/Subsampling/include/gudhi/choose_n_farthest_points.h index 43bf6402..b6b7ace3 100644 --- a/src/Subsampling/include/gudhi/choose_n_farthest_points.h +++ b/src/Subsampling/include/gudhi/choose_n_farthest_points.h @@ -52,6 +52,7 @@ namespace subsampling { * concept Kernel_d::Squared_distance_d * concept. + * 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. @@ -112,6 +113,7 @@ void choose_n_farthest_points(Kernel const &k, * concept Kernel_d::Squared_distance_d * concept. + * 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. @@ -133,7 +135,7 @@ void choose_n_farthest_points(Kernel const& k, // Choose randomly the first landmark std::random_device rd; std::mt19937 gen(rd()); - std::uniform_int_distribution<> dis(1, 6); + std::uniform_int_distribution<> dis(0, final_size); int starting_point = dis(gen); choose_n_farthest_points(k, input_pts, final_size, starting_point, output_it); } -- cgit v1.2.3 From 66d5bb10fcbaf75962004dfa34d8f2b8d5d23c0a Mon Sep 17 00:00:00 2001 From: vrouvrea Date: Thu, 15 Dec 2016 16:30:50 +0000 Subject: Modify random and limit tests cases git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/branches/subsampling_and_spatialsearching@1883 636b058d-ea47-450e-bf9e-a15bfbe3eedb Former-commit-id: 385f334f9358ae62c2ba6ec0d652ecfd52a052a7 --- .../include/gudhi/choose_n_farthest_points.h | 17 +++++++++++++---- 1 file changed, 13 insertions(+), 4 deletions(-) (limited to 'src') diff --git a/src/Subsampling/include/gudhi/choose_n_farthest_points.h b/src/Subsampling/include/gudhi/choose_n_farthest_points.h index b6b7ace3..ea387bf9 100644 --- a/src/Subsampling/include/gudhi/choose_n_farthest_points.h +++ b/src/Subsampling/include/gudhi/choose_n_farthest_points.h @@ -73,10 +73,15 @@ void choose_n_farthest_points(Kernel const &k, std::size_t final_size, std::size_t starting_point, OutputIterator output_it) { - typename Kernel::Squared_distance_d sqdist = k.squared_distance_d_object(); - std::size_t nb_points = boost::size(input_pts); - assert(nb_points >= final_size); + if (final_size > nb_points) + final_size = nb_points; + + // Tests to the limit + if (final_size < 1) + return; + + 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::infinity(); // infinity (see next entry) @@ -132,10 +137,14 @@ 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, final_size); + std::uniform_int_distribution<> dis(0, (input_pts.size() - 1)); int starting_point = dis(gen); choose_n_farthest_points(k, input_pts, final_size, starting_point, output_it); } -- cgit v1.2.3