From 7928209595af6f7559fde36fa06c031cd47e7179 Mon Sep 17 00:00:00 2001 From: skachano Date: Fri, 24 Jun 2016 13:42:39 +0000 Subject: Copied Clément's example for 2 functions MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/branches/subsampling_and_spatialsearching@1338 636b058d-ea47-450e-bf9e-a15bfbe3eedb Former-commit-id: 42f29038057980965bfead2c73cbc013448493fb --- .../include/gudhi/choose_by_farthest_point.h | 119 +++++++++++++++++++-- 1 file changed, 110 insertions(+), 9 deletions(-) (limited to 'src/Subsampling/include/gudhi') diff --git a/src/Subsampling/include/gudhi/choose_by_farthest_point.h b/src/Subsampling/include/gudhi/choose_by_farthest_point.h index 52647c16..d1db0d1a 100644 --- a/src/Subsampling/include/gudhi/choose_by_farthest_point.h +++ b/src/Subsampling/include/gudhi/choose_by_farthest_point.h @@ -25,6 +25,14 @@ #include +#include + +#include + +#include +#include +#include + #include #include // for sort #include @@ -45,10 +53,11 @@ namespace subsampling { 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) + void choose_by_farthest_point_old( 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(); @@ -60,11 +69,7 @@ namespace subsampling { const double infty = std::numeric_limits::infinity(); // infinity (see next entry) std::vector< double > dist_to_L(nb_points, infty); // vector of current distances to L from points - // Choose randomly the first landmark - std::random_device rd; - std::mt19937 gen(rd()); - std::uniform_int_distribution<> dis(1, 6); - int curr_max_w = dis(gen); + 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 @@ -86,7 +91,103 @@ 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); + } + + 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); + } + + } // namespace subsampling } // namespace Gudhi -- cgit v1.2.3