From 96b7e2ec76b94aa8d609c816f3adab63f0b6caa9 Mon Sep 17 00:00:00 2001 From: skachano Date: Fri, 24 Jun 2016 14:08:26 +0000 Subject: Removed headers in the examples git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/branches/subsampling_and_spatialsearching@1339 636b058d-ea47-450e-bf9e-a15bfbe3eedb Former-commit-id: 835003033dc15ce8fd2d8efdc7bfdf3e0be7760d --- src/Subsampling/doc/Intro_subsampling.h | 7 ++ .../example/example_choose_by_farthest_point.cpp | 23 ----- .../example/example_pick_random_points.cpp | 23 ----- .../include/gudhi/choose_by_farthest_point.h | 102 ++++----------------- .../test/test_choose_farthest_point.cpp | 65 +++---------- 5 files changed, 38 insertions(+), 182 deletions(-) (limited to 'src/Subsampling') diff --git a/src/Subsampling/doc/Intro_subsampling.h b/src/Subsampling/doc/Intro_subsampling.h index e62ebc61..5ccab3af 100644 --- a/src/Subsampling/doc/Intro_subsampling.h +++ b/src/Subsampling/doc/Intro_subsampling.h @@ -46,6 +46,13 @@ namespace subsampling { * * \include Subsampling/example_sparsify_point_set.cpp * + * \section farthestpointexamples Example: choose_by_farthest_point + * + * This example outputs a subset of 100 points obtained by González algorithm, + * starting with a random point. + * + * \include Subsampling/example_choose_by_farthest_point.cpp + * * \copyright GNU General Public License v3. * \verbatim Contact: gudhi-users@lists.gforge.inria.fr \endverbatim */ diff --git a/src/Subsampling/example/example_choose_by_farthest_point.cpp b/src/Subsampling/example/example_choose_by_farthest_point.cpp index 5b81bc9d..29ecbf9b 100644 --- a/src/Subsampling/example/example_choose_by_farthest_point.cpp +++ b/src/Subsampling/example/example_choose_by_farthest_point.cpp @@ -1,26 +1,3 @@ -/* This file is part of the Gudhi Library. The Gudhi library - * (Geometric Understanding in Higher Dimensions) is a generic C++ - * library for computational topology. - * - * Author(s): Siargey Kachanovich - * - * Copyright (C) 2016 INRIA - * - * This program is free software: you can redistribute it and/or modify - * it under the terms of the GNU General Public License as published by - * the Free Software Foundation, either version 3 of the License, or - * (at your option) any later version. - * - * This program is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - * GNU General Public License for more details. - * - * You should have received a copy of the GNU General Public License - * along with this program. If not, see . - */ - - #include #include diff --git a/src/Subsampling/example/example_pick_random_points.cpp b/src/Subsampling/example/example_pick_random_points.cpp index 49a027a4..348b1b81 100644 --- a/src/Subsampling/example/example_pick_random_points.cpp +++ b/src/Subsampling/example/example_pick_random_points.cpp @@ -1,26 +1,3 @@ -/* This file is part of the Gudhi Library. The Gudhi library - * (Geometric Understanding in Higher Dimensions) is a generic C++ - * library for computational topology. - * - * Author(s): Siargey Kachanovich - * - * Copyright (C) 2016 INRIA - * - * This program is free software: you can redistribute it and/or modify - * it under the terms of the GNU General Public License as published by - * the Free Software Foundation, either version 3 of the License, or - * (at your option) any later version. - * - * This program is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - * GNU General Public License for more details. - * - * You should have received a copy of the GNU General Public License - * along with this program. If not, see . - */ - - #include #include diff --git a/src/Subsampling/include/gudhi/choose_by_farthest_point.h b/src/Subsampling/include/gudhi/choose_by_farthest_point.h index d1db0d1a..8dea19be 100644 --- a/src/Subsampling/include/gudhi/choose_by_farthest_point.h +++ b/src/Subsampling/include/gudhi/choose_by_farthest_point.h @@ -45,6 +45,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`. * \details It chooses `final_size` points from a random access range `points` and * outputs it in the output iterator `output_it`. * @@ -53,11 +54,11 @@ namespace subsampling { template < typename Kernel, typename Point_container, typename OutputIterator> - void choose_by_farthest_point_old( Kernel& k, - Point_container const &points, - int final_size, - int starting_point, - OutputIterator output_it) + void choose_by_farthest_point( Kernel& k, + Point_container const &points, + int final_size, + int starting_point, + OutputIterator output_it) { typename Kernel::Squared_distance_d sqdist = k.squared_distance_d_object(); @@ -92,101 +93,30 @@ namespace subsampling { } } - template < typename Kernel, - typename Point_container, - typename OutputIterator> - void choose_by_farthest_point_old( Kernel& k, - Point_container const &points, - int final_size, - OutputIterator output_it) - { - // Choose randomly the first landmark - std::random_device rd; - std::mt19937 gen(rd()); - std::uniform_int_distribution<> dis(1, 6); - int starting_point = dis(gen); - choose_by_farthest_point_old(k, points, final_size, starting_point, output_it); - } - + /** + * \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 a random landmark. + * \details It chooses `final_size` points from a random access range `points` and + * outputs it in the output iterator `output_it`. + * + */ template < typename Kernel, typename Point_container, typename OutputIterator> void choose_by_farthest_point( Kernel& k, Point_container const &points, int final_size, - int starting_point, OutputIterator output_it) { - // typedef typename Kernel::Point_d Point_d; - // typedef typename Kernel::FT FT; - // typedef CGAL::Search_traits< - // FT, Point_d, - // typename Kernel::Cartesian_const_iterator_d, - // typename Kernel::Construct_cartesian_const_iterator_d> Traits_base; - - // typedef CGAL::Search_traits_adapter< std::ptrdiff_t, Point_d*, Traits_base > STraits; - // typedef CGAL::Fuzzy_sphere< STraits > Fuzzy_sphere; - - typename Kernel::Squared_distance_d sqdist = k.squared_distance_d_object(); - - int nb_points = boost::size(points); - assert(nb_points >= final_size); - - Clock t; - Gudhi::spatial_searching::Spatial_tree_data_structure< Kernel, Point_container> tree(points); - t.end(); - //std::cout << "Constructed the Kd tree: " << t.num_seconds() << " s." << std::endl; - - //CGAL::Fuzzy_sphere< CGAL::Search_trai> - - int current_number_of_landmarks = 0; // counter for landmarks - const double infty = std::numeric_limits::infinity(); // infinity (see next entry) - double curr_max_dist = infty; // used for defining the furhest point from L - std::vector< double > dist_to_L(nb_points, infty); // vector of current distances to L from points - - // Choose randomly the first landmark - int 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++ = points[curr_max_w]; - // std::cout << curr_max_w << "\n"; - //for (auto& p : points) { - auto search = tree.query_incremental_ANN(points[curr_max_w]); - auto search_it = search.begin(); - while (search_it != search.end() && search_it->second <= curr_max_dist ) { - //std::cout << search_it->second << " " << curr_max_dist << "\n"; - if (dist_to_L[search_it->first] > search_it->second) - dist_to_L[search_it->first] = search_it->second; - search_it++; - } - // choose the next curr_max_w - curr_max_dist = 0; - for (unsigned 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; - } - } - } - - template < typename Kernel, - typename Point_container, - typename OutputIterator> - void choose_by_farthest_point( Kernel& k, - Point_container const &points, - int final_size, - OutputIterator output_it) - { // Choose randomly the first landmark std::random_device rd; std::mt19937 gen(rd()); std::uniform_int_distribution<> dis(1, 6); int starting_point = dis(gen); - - choose_by_farthest_point_old(k, points, final_size, starting_point, output_it); + choose_by_farthest_point(k, points, final_size, starting_point, output_it); } - } // namespace subsampling diff --git a/src/Subsampling/test/test_choose_farthest_point.cpp b/src/Subsampling/test/test_choose_farthest_point.cpp index dff2cd4e..5f705de6 100644 --- a/src/Subsampling/test/test_choose_farthest_point.cpp +++ b/src/Subsampling/test/test_choose_farthest_point.cpp @@ -24,15 +24,14 @@ // # define TBB_USE_THREADING_TOOL // #endif -// #define BOOST_TEST_DYN_LINK -// #define BOOST_TEST_MODULE "test_choose_farthest_point" -//#include -//#include +#define BOOST_TEST_DYN_LINK +#define BOOST_TEST_MODULE "witness_complex_points" +#include +#include #include #include #include -#include #include @@ -41,52 +40,18 @@ typedef typename K::FT FT; typedef typename K::Point_d Point_d; -//BOOST_AUTO_TEST_CASE(test_choose_farthest_point) -int main() { - std::vector< Point_d > points, results, results2; - K k; - Clock t; - // Add grid points (810000 points) - for (FT i = 0; i < 30; i += 1.0) - for (FT j = 0; j < 30; j += 1.0) - for (FT k = 0; k < 30; k += 1.0) - for (FT l = 0; l < 30; l += 1.0) +BOOST_AUTO_TEST_CASE(test_choose_farthest_point) { + 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) points.push_back(Point_d(std::vector({i, j, k, l}))); - unsigned final_size = 100, numeral = 1; - std::cout << "Test New Old\n"; - while (final_size < 100001) { - std::cout << final_size << ": "; - results.clear(); - t.begin(); - Gudhi::subsampling::choose_by_farthest_point(k, points, final_size, 0, std::back_inserter(results)); - t.end(); - std::cout << t.num_seconds() << " s, "; - - // std::cout << "New algorithm result:\n"; - // for (auto p: results) - // std::cout << p << std::endl; - - results2.clear(); - t.begin(); - Gudhi::subsampling::choose_by_farthest_point_old(k, points, final_size, 0, std::back_inserter(results2)); - t.end(); - std::cout << t.num_seconds() << " s" << std::endl; - - - // std::cout << "Old algorithm result:\n"; - // for (auto p: results2) - // std::cout << p << std::endl; + landmarks.clear(); + K k; + Gudhi::subsampling::choose_by_farthest_point(k, points, 100, std::back_inserter(landmarks)); - assert(results.size() == final_size); - assert(results2.size() == final_size); - assert(results == results2); - - switch (numeral) { - case 1: numeral = 2; final_size *= 2; break; - case 2: numeral = 5; final_size = final_size/2*5; break; - case 5: numeral = 1; final_size *= 2; break; - default: assert(false); - } - } + assert(landmarks.size() == 100); } -- cgit v1.2.3