sparsify_point_set.h
1/* This file is part of the Gudhi Library - https://gudhi.inria.fr/ - which is released under MIT.
2 * See file LICENSE or go to https://gudhi.inria.fr/licensing/ for full license details.
3 * Author(s): Clement Jamin
4 *
5 * Copyright (C) 2016 Inria
6 *
7 * Modification(s):
8 * - YYYY/MM Author: Description of the modification
9 */
10
11#ifndef SPARSIFY_POINT_SET_H_
12#define SPARSIFY_POINT_SET_H_
13
14#include <boost/version.hpp>
15#if BOOST_VERSION < 106600
16# include <boost/function_output_iterator.hpp>
17#else
18# include <boost/iterator/function_output_iterator.hpp>
19#endif
20
21#include <gudhi/Kd_tree_search.h>
22#ifdef GUDHI_SUBSAMPLING_PROFILING
23#include <gudhi/Clock.h>
24#endif
25
26#include <cstddef>
27#include <vector>
28
29namespace Gudhi {
30
31namespace subsampling {
32
53template <typename Kernel, typename Point_range, typename OutputIterator>
54void
56 const Kernel &k, Point_range const& input_pts,
57 typename Kernel::FT min_squared_dist,
58 OutputIterator output_it) {
60 Kernel, Point_range> Points_ds;
61
62#ifdef GUDHI_SUBSAMPLING_PROFILING
63 Gudhi::Clock t;
64#endif
65
66 Points_ds points_ds(input_pts);
67
68 std::vector<bool> dropped_points(input_pts.size(), false);
69
70 // Parse the input points, and add them if they are not too close to
71 // the other points
72 std::size_t pt_idx = 0;
73 for (auto const& pt : input_pts) {
74 if (dropped_points[pt_idx++])
75 continue;
76
77 *output_it++ = pt;
78
79 // If another point Q is closer that min_squared_dist, mark Q to be dropped
80 auto drop = [&dropped_points] (std::ptrdiff_t neighbor_point_idx) { dropped_points[neighbor_point_idx] = true; };
81 points_ds.all_near_neighbors2(pt, min_squared_dist, min_squared_dist, boost::make_function_output_iterator(std::ref(drop)));
82 }
83
84#ifdef GUDHI_SUBSAMPLING_PROFILING
85 t.end();
86 std::cerr << "Point set sparsified in " << t.num_seconds()
87 << " seconds." << std::endl;
88#endif
89}
90
91} // namespace subsampling
92} // namespace Gudhi
93
94#endif // SPARSIFY_POINT_SET_H_
Spatial tree data structure to perform (approximate) nearest and furthest neighbor search.
Definition: Kd_tree_search.h:70
void sparsify_point_set(const Kernel &k, Point_range const &input_pts, typename Kernel::FT min_squared_dist, OutputIterator output_it)
Outputs a subset of the input points so that the squared distance between any two points is greater t...
Definition: sparsify_point_set.h:55
GUDHIdev  Version 3.5.0  - C++ library for Topological Data Analysis (TDA) and Higher Dimensional Geometry Understanding.  - Copyright : MIT Generated on Tue Aug 16 2022 14:01:50 for GUDHIdev by Doxygen 1.9.4