diff options
Diffstat (limited to 'src/Subsampling')
-rw-r--r-- | src/Subsampling/doc/Intro_subsampling.h | 70 | ||||
-rw-r--r-- | src/Subsampling/example/CMakeLists.txt | 21 | ||||
-rw-r--r-- | src/Subsampling/example/example_choose_n_farthest_points.cpp | 27 | ||||
-rw-r--r-- | src/Subsampling/example/example_custom_kernel.cpp | 69 | ||||
-rw-r--r-- | src/Subsampling/example/example_pick_n_random_points.cpp | 27 | ||||
-rw-r--r-- | src/Subsampling/example/example_sparsify_point_set.cpp | 27 | ||||
-rw-r--r-- | src/Subsampling/include/gudhi/choose_n_farthest_points.h | 156 | ||||
-rw-r--r-- | src/Subsampling/include/gudhi/pick_n_random_points.h | 84 | ||||
-rw-r--r-- | src/Subsampling/include/gudhi/sparsify_point_set.h | 115 | ||||
-rw-r--r-- | src/Subsampling/test/CMakeLists.txt | 38 | ||||
-rw-r--r-- | src/Subsampling/test/test_choose_n_farthest_points.cpp | 56 | ||||
-rw-r--r-- | src/Subsampling/test/test_pick_n_random_points.cpp | 69 | ||||
-rw-r--r-- | src/Subsampling/test/test_sparsify_point_set.cpp | 55 |
13 files changed, 814 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..c84616dd --- /dev/null +++ b/src/Subsampling/doc/Intro_subsampling.h @@ -0,0 +1,70 @@ +/* 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): Clement Jamin + * + * 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 <http://www.gnu.org/licenses/>. + */ + +#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 + * \copyright GNU General Public License v3. + * \verbatim Contact: gudhi-users@lists.gforge.inria.fr \endverbatim + */ +/** @} */ // 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..0fd3335c --- /dev/null +++ b/src/Subsampling/example/CMakeLists.txt @@ -0,0 +1,21 @@ +cmake_minimum_required(VERSION 2.6) +project(Subsampling_examples) + +if(CGAL_FOUND) + if (NOT CGAL_VERSION VERSION_LESS 4.8.1) + 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}) + + add_test(Subsampling_example_pick_n_random_points + ${CMAKE_CURRENT_BINARY_DIR}/Subsampling_example_pick_n_random_points) + add_test(Subsampling_example_choose_n_farthest_points + ${CMAKE_CURRENT_BINARY_DIR}/Subsampling_example_choose_n_farthest_points) + add_test(Subsampling_example_sparsify_point_set + ${CMAKE_CURRENT_BINARY_DIR}/Subsampling_example_sparsify_point_set) + endif() + endif () +endif() 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..533aba74 --- /dev/null +++ b/src/Subsampling/example/example_choose_n_farthest_points.cpp @@ -0,0 +1,27 @@ +#include <gudhi/choose_n_farthest_points.h> + +#include <CGAL/Epick_d.h> +#include <CGAL/Random.h> + +#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, 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..05797ebe --- /dev/null +++ b/src/Subsampling/example/example_custom_kernel.cpp @@ -0,0 +1,69 @@ +#include <gudhi/choose_n_farthest_points.h> + +#include <CGAL/Epick_d.h> +#include <CGAL/Random.h> + +#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, 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..1e38e405 --- /dev/null +++ b/src/Subsampling/example/example_pick_n_random_points.cpp @@ -0,0 +1,27 @@ +#include <gudhi/pick_n_random_points.h> + +#include <CGAL/Epick_d.h> +#include <CGAL/Random.h> + +#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..b35a18d9 --- /dev/null +++ b/src/Subsampling/example/example_sparsify_point_set.cpp @@ -0,0 +1,27 @@ +#include <gudhi/sparsify_point_set.h> + +#include <CGAL/Epick_d.h> +#include <CGAL/Random.h> + +#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..ea387bf9 --- /dev/null +++ b/src/Subsampling/include/gudhi/choose_n_farthest_points.h @@ -0,0 +1,156 @@ +/* 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 <http://www.gnu.org/licenses/>. + */ + +#ifndef CHOOSE_N_FARTHEST_POINTS_H_ +#define CHOOSE_N_FARTHEST_POINTS_H_ + +#include <boost/range.hpp> + +#include <gudhi/Kd_tree_search.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<> + +namespace Gudhi { + +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`. + * \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> + * 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. + * \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_range, +typename OutputIterator> +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) { + 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; + + 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]; + 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; + } + } +} + +/** + * \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. + * \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> + * 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. + * \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_range, +typename OutputIterator> +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)); + int starting_point = dis(gen); + choose_n_farthest_points(k, input_pts, final_size, starting_point, output_it); +} + +} // 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..e89b2b2d --- /dev/null +++ b/src/Subsampling/include/gudhi/pick_n_random_points.h @@ -0,0 +1,84 @@ +/* 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 <http://www.gnu.org/licenses/>. + */ + +#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_SUBS_PROFILING + Gudhi::Clock t; +#endif + + std::size_t nbP = boost::size(points); + assert(nbP >= final_size); + 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_SUBS_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..7ff11b4c --- /dev/null +++ b/src/Subsampling/include/gudhi/sparsify_point_set.h @@ -0,0 +1,115 @@ +/* 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): Clement Jamin + * + * 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 <http://www.gnu.org/licenses/>. + */ + +#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; + + typename Kernel::Squared_distance_d sqdist = k.squared_distance_d_object(); + +#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.query_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..3a2fb649 --- /dev/null +++ b/src/Subsampling/test/CMakeLists.txt @@ -0,0 +1,38 @@ +cmake_minimum_required(VERSION 2.6) +project(Subsampling_tests) + +if (GCOVR_PATH) + # for gcovr to make coverage reports - Corbera Jenkins plugin + set(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} -fprofile-arcs -ftest-coverage") +endif() +if (GPROF_PATH) + # for gprof to make coverage reports - Jenkins + set(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} -pg") +endif() + +if(CGAL_FOUND) + if (NOT CGAL_VERSION VERSION_LESS 4.8.1) + if (EIGEN3_FOUND) + 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}) + + add_test(Subsampling_test_pick_n_random_points ${CMAKE_CURRENT_BINARY_DIR}/Subsampling_test_pick_n_random_points + # XML format for Jenkins xUnit plugin + --log_format=XML --log_sink=${CMAKE_SOURCE_DIR}/Subsampling_test_pick_n_random_points_UT.xml --log_level=test_suite --report_level=no) + + add_test(Subsampling_test_choose_n_farthest_points ${CMAKE_CURRENT_BINARY_DIR}/Subsampling_test_choose_n_farthest_points + # XML format for Jenkins xUnit plugin + --log_format=XML --log_sink=${CMAKE_SOURCE_DIR}/Subsampling_test_choose_n_farthest_points_UT.xml --log_level=test_suite --report_level=no) + + add_test(Subsampling_test_sparsify_point_set ${CMAKE_CURRENT_BINARY_DIR}/Subsampling_test_sparsify_point_set + # XML format for Jenkins xUnit plugin + --log_format=XML --log_sink=${CMAKE_SOURCE_DIR}/Subsampling_test_sparsify_point_set_UT.xml --log_level=test_suite --report_level=no) + endif() + endif () +endif() 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..d064899a --- /dev/null +++ b/src/Subsampling/test/test_choose_n_farthest_points.cpp @@ -0,0 +1,56 @@ +/* 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 <http://www.gnu.org/licenses/>. + */ + +// #ifdef _DEBUG +// # define TBB_USE_THREADING_TOOL +// #endif + +#define BOOST_TEST_DYN_LINK +#define BOOST_TEST_MODULE "witness_complex_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; + +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<FT>({i, j, k, l}))); + + landmarks.clear(); + K k; + Gudhi::subsampling::choose_n_farthest_points(k, points, 100, std::back_inserter(landmarks)); + + BOOST_CHECK(landmarks.size() == 100); +} 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..6c8dbea2 --- /dev/null +++ b/src/Subsampling/test/test_pick_n_random_points.cpp @@ -0,0 +1,69 @@ +/* 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 <http://www.gnu.org/licenses/>. + */ + +// #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..f993d6d6 --- /dev/null +++ b/src/Subsampling/test/test_sparsify_point_set.cpp @@ -0,0 +1,55 @@ +/* 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): Clement Jamin + * + * 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 <http://www.gnu.org/licenses/>. + */ + +#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()); +} |