From d48e75a5095c48da3bfaf87df5135c209dab58eb Mon Sep 17 00:00:00 2001 From: cjamin Date: Fri, 13 May 2016 16:36:46 +0000 Subject: Add sparsify_point_set git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/branches/subsampling_and_spatialsearching@1176 636b058d-ea47-450e-bf9e-a15bfbe3eedb Former-commit-id: 21e3b8d9ef41a750436fff3b8b077399cfd3e48b --- src/Subsampling/include/gudhi/sparsify_point_set.h | 99 ++++++++++++++++++++++ 1 file changed, 99 insertions(+) create mode 100644 src/Subsampling/include/gudhi/sparsify_point_set.h (limited to 'src/Subsampling') 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..89770886 --- /dev/null +++ b/src/Subsampling/include/gudhi/sparsify_point_set.h @@ -0,0 +1,99 @@ +/* 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 Sophia-Antipolis (France) +* +* 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 . +*/ + +#ifndef GUDHI_SPARSIFY_POINT_SET_H +#define GUDHI_SPARSIFY_POINT_SET_H + +#include +#ifdef GUDHI_TC_PROFILING +#include +#endif + +#include +#include + +namespace Gudhi { + + template + bool + sparsify_point_set( + const Kernel &k, Point_container const& input_pts, + typename Kernel::FT min_squared_dist, + OutputIterator output_it) + { + typedef typename Gudhi::Spatial_tree_data_structure< + Kernel, Point_container> Points_ds; + + typename Kernel::Squared_distance_d sqdist = k.squared_distance_d_object(); + +#ifdef GUDHI_TC_PROFILING + Gudhi::Clock t; +#endif + + Points_ds points_ds(input_pts); + + std::vector 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_container::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_ANN(*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) + //if (neighbor.second < 0.2*((*it_pt)[0] + 1.)*0.5 + 0.00005) + //if (neighbor.second < ((*it_pt)[0] < 0 ? 0.2 : 0.00001)) + { + // 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_TC_PROFILING + t.end(); + std::cerr << "Point set sparsified in " << t.num_seconds() + << " seconds." << std::endl; +#endif + } + + +} //namespace Gudhi + +#endif // GUDHI_POINT_CLOUD_H -- cgit v1.2.3