From 58bcd511da7d3c00b7a1f8ca130ba437ae6665c8 Mon Sep 17 00:00:00 2001 From: cjamin Date: Tue, 28 Jun 2016 16:23:35 +0000 Subject: Add example git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/branches/subsampling_and_spatialsearching@1351 636b058d-ea47-450e-bf9e-a15bfbe3eedb Former-commit-id: 2b99baa9a43854119a46ec8ce11b93f00ef74835 --- .../example/example_spatial_searching.cpp | 37 ++++++++++++++++++++++ 1 file changed, 37 insertions(+) create mode 100644 src/Spatial_searching/example/example_spatial_searching.cpp (limited to 'src/Spatial_searching/example/example_spatial_searching.cpp') diff --git a/src/Spatial_searching/example/example_spatial_searching.cpp b/src/Spatial_searching/example/example_spatial_searching.cpp new file mode 100644 index 00000000..ba387b71 --- /dev/null +++ b/src/Spatial_searching/example/example_spatial_searching.cpp @@ -0,0 +1,37 @@ +#include + +#include +#include + +#include +#include + +namespace gss = Gudhi::spatial_searching; + +int main (void) +{ + typedef CGAL::Epick_d > K; + typedef typename K::FT FT; + typedef typename K::Point_d Point; + typedef std::vector Points; + + typedef gss::Spatial_tree_data_structure Points_ds; + typedef typename Points_ds::KNS_range KNS_range; + typedef typename Points_ds::KNS_iterator KNS_iterator; + typedef typename Points_ds::INS_range INS_range; + typedef typename Points_ds::INS_iterator INS_iterator; + + CGAL::Random rd; + + Points points; + for (int i = 0; i < 500; ++i) + points.push_back(Point(std::array({ rd.get_double(-1.,1),rd.get_double(-1.,1),rd.get_double(-1.,1),rd.get_double(-1.,1) }))); + + Points_ds points_ds(points); + + auto kns_range = points_ds.query_ANN(points[20], 10, true); + for (auto const& nghb : kns_range) + std::cout << nghb.first << " (sq. dist. = " << nghb.second << ")\n"; + + return 0; +} -- cgit v1.2.3 From dfc61b827ae2aa7f99e2ae8401f19f6f0d219af3 Mon Sep 17 00:00:00 2001 From: cjamin Date: Thu, 30 Jun 2016 13:31:23 +0000 Subject: Improved example git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/branches/subsampling_and_spatialsearching@1363 636b058d-ea47-450e-bf9e-a15bfbe3eedb Former-commit-id: 0b6e59f5c3c7c93eaed74c93f8b0284143574cd3 --- src/Spatial_searching/example/example_spatial_searching.cpp | 13 +++++++++---- 1 file changed, 9 insertions(+), 4 deletions(-) (limited to 'src/Spatial_searching/example/example_spatial_searching.cpp') diff --git a/src/Spatial_searching/example/example_spatial_searching.cpp b/src/Spatial_searching/example/example_spatial_searching.cpp index ba387b71..1a807b90 100644 --- a/src/Spatial_searching/example/example_spatial_searching.cpp +++ b/src/Spatial_searching/example/example_spatial_searching.cpp @@ -16,10 +16,6 @@ int main (void) typedef std::vector Points; typedef gss::Spatial_tree_data_structure Points_ds; - typedef typename Points_ds::KNS_range KNS_range; - typedef typename Points_ds::KNS_iterator KNS_iterator; - typedef typename Points_ds::INS_range INS_range; - typedef typename Points_ds::INS_iterator INS_iterator; CGAL::Random rd; @@ -29,9 +25,18 @@ int main (void) Points_ds points_ds(points); + // 20-nearest neighbor query + std::cout << "20 nearest neighbors:\n"; auto kns_range = points_ds.query_ANN(points[20], 10, true); for (auto const& nghb : kns_range) std::cout << nghb.first << " (sq. dist. = " << nghb.second << ")\n"; + // Incremental nearest neighbor query + std::cout << "Incremental nearest neighbors:\n"; + auto ins_range = points_ds.query_incremental_ANN(points[45]); + // Get all the neighbors that are closer than 0.5 + for (auto ins_iterator = ins_range.begin(); ins_iterator->second < 0.5*0.5 ; ++ins_iterator) + std::cout << ins_iterator->first << " (sq. dist. = " << ins_iterator->second << ")\n"; + return 0; } -- cgit v1.2.3 From 5bc90cf2f92f07a45a7104bd771d52bd0985fb9a Mon Sep 17 00:00:00 2001 From: skachano Date: Fri, 5 Aug 2016 14:22:57 +0000 Subject: Added farthest/nearest neighbor division in the functions git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/branches/subsampling_and_spatialsearching@1424 636b058d-ea47-450e-bf9e-a15bfbe3eedb Former-commit-id: b42ad020d144ea4c0b4d726764fc0d4234f5b0b3 --- .../example/example_spatial_searching.cpp | 17 ++++++- .../include/gudhi/Spatial_tree_data_structure.h | 56 +++++++++++++++++++++- .../test/test_Spatial_tree_data_structure.cpp | 13 ++++- 3 files changed, 80 insertions(+), 6 deletions(-) (limited to 'src/Spatial_searching/example/example_spatial_searching.cpp') diff --git a/src/Spatial_searching/example/example_spatial_searching.cpp b/src/Spatial_searching/example/example_spatial_searching.cpp index 1a807b90..0b1e25f5 100644 --- a/src/Spatial_searching/example/example_spatial_searching.cpp +++ b/src/Spatial_searching/example/example_spatial_searching.cpp @@ -27,16 +27,29 @@ int main (void) // 20-nearest neighbor query std::cout << "20 nearest neighbors:\n"; - auto kns_range = points_ds.query_ANN(points[20], 10, true); + auto kns_range = points_ds.query_k_nearest_neighbors(points[20], 10, true); for (auto const& nghb : kns_range) std::cout << nghb.first << " (sq. dist. = " << nghb.second << ")\n"; // Incremental nearest neighbor query std::cout << "Incremental nearest neighbors:\n"; - auto ins_range = points_ds.query_incremental_ANN(points[45]); + auto ins_range = points_ds.query_incremental_nearest_neighbors(points[45]); // Get all the neighbors that are closer than 0.5 for (auto ins_iterator = ins_range.begin(); ins_iterator->second < 0.5*0.5 ; ++ins_iterator) std::cout << ins_iterator->first << " (sq. dist. = " << ins_iterator->second << ")\n"; + // 20-farthest neighbor query + std::cout << "20 farthest neighbors:\n"; + auto kfs_range = points_ds.query_k_farthest_neighbors(points[20], 10, true); + for (auto const& nghb : kfs_range) + std::cout << nghb.first << " (sq. dist. = " << nghb.second << ")\n"; + + // Incremental farthest neighbor query + std::cout << "Incremental farthest neighbors:\n"; + auto ifs_range = points_ds.query_incremental_farthest_neighbors(points[45]); + // Get all the neighbors that are farthest than 2.3 + for (auto ifs_iterator = ifs_range.begin(); ifs_iterator->second > 2.3*2.3 ; ++ifs_iterator) + std::cout << ifs_iterator->first << " (sq. dist. = " << ifs_iterator->second << ")\n"; + return 0; } diff --git a/src/Spatial_searching/include/gudhi/Spatial_tree_data_structure.h b/src/Spatial_searching/include/gudhi/Spatial_tree_data_structure.h index 5a29b153..99f67fed 100644 --- a/src/Spatial_searching/include/gudhi/Spatial_tree_data_structure.h +++ b/src/Spatial_searching/include/gudhi/Spatial_tree_data_structure.h @@ -171,7 +171,7 @@ public: /// @param[in] sorted Indicates if the computed sequence of k-nearest neighbors needs to be sorted. /// @param[in] eps Approximation factor. /// @return A range containing the k-nearest neighbors. - KNS_range query_ANN(const + KNS_range query_k_nearest_neighbors(const Point &p, unsigned int k, bool sorted = true, @@ -199,7 +199,7 @@ public: /// @return A range containing the neighbors sorted by their distance to p. /// All the neighbors are not computed by this function, but they will be /// computed incrementally when the iterator on the range is incremented. - INS_range query_incremental_ANN(const Point &p, FT eps = FT(0)) const + INS_range query_incremental_nearest_neighbors(const Point &p, FT eps = FT(0)) const { // Initialize the search structure, and search all N points // Note that we need to pass the Distance explicitly since it needs to @@ -215,6 +215,58 @@ public: return search; } + /// \brief Search for the k-farthest points from a query point. + /// @param[in] p The query point. + /// @param[in] k Number of farthest points to search. + /// @param[in] sorted Indicates if the computed sequence of k-farthest neighbors needs to be sorted. + /// @param[in] eps Approximation factor. + /// @return A range containing the k-farthest neighbors. + KNS_range query_k_farthest_neighbors(const + Point &p, + unsigned int k, + bool sorted = true, + FT eps = FT(0)) const + { + // Initialize the search structure, and search all N points + // Note that we need to pass the Distance explicitly since it needs to + // know the property map + K_neighbor_search search( + m_tree, + p, + k, + eps, + false, + CGAL::Distance_adapter >( + (Point*)&(m_points[0])), + sorted); + + return search; + } + + /// \brief Search incrementally for the farthest neighbors from a query point. + /// @param[in] p The query point. + /// @param[in] eps Approximation factor. + /// @return A range containing the neighbors sorted by their distance to p. + /// All the neighbors are not computed by this function, but they will be + /// computed incrementally when the iterator on the range is incremented. + INS_range query_incremental_farthest_neighbors(const Point &p, FT eps = FT(0)) const + { + // Initialize the search structure, and search all N points + // Note that we need to pass the Distance explicitly since it needs to + // know the property map + Incremental_neighbor_search search( + m_tree, + p, + eps, + false, + CGAL::Distance_adapter >( + (Point*)&(m_points[0])) ); + + return search; + } + + + protected: Point_container_ const& m_points; Tree m_tree; diff --git a/src/Spatial_searching/test/test_Spatial_tree_data_structure.cpp b/src/Spatial_searching/test/test_Spatial_tree_data_structure.cpp index 916710ef..0ca35bc6 100644 --- a/src/Spatial_searching/test/test_Spatial_tree_data_structure.cpp +++ b/src/Spatial_searching/test/test_Spatial_tree_data_structure.cpp @@ -51,10 +51,10 @@ BOOST_AUTO_TEST_CASE(test_Spatial_tree_data_structure) Points_ds points_ds(points); std::size_t closest_pt_index = - points_ds.query_ANN(points[10], 1, false).begin()->first; + points_ds.query_k_nearest_neighbors(points[10], 1, false).begin()->first; BOOST_CHECK(closest_pt_index == 10); - auto kns_range = points_ds.query_ANN(points[20], 10, true); + auto kns_range = points_ds.query_k_nearest_neighbors(points[20], 10, true); FT last_dist = -1.; for (auto const& nghb : kns_range) @@ -62,4 +62,13 @@ BOOST_AUTO_TEST_CASE(test_Spatial_tree_data_structure) BOOST_CHECK(nghb.second > last_dist); last_dist = nghb.second; } + + auto kfs_range = points_ds.query_k_farthest_neighbors(points[20], 10, true); + + last_dist = kfs_range.begin()->second; + for (auto const& nghb : kfs_range) + { + BOOST_CHECK(nghb.second <= last_dist); + last_dist = nghb.second; + } } -- cgit v1.2.3 From a935df397bba093848cfe5905aca1a158294825c Mon Sep 17 00:00:00 2001 From: cjamin Date: Thu, 1 Sep 2016 14:50:04 +0000 Subject: Fix sentence git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/branches/subsampling_and_spatialsearching@1469 636b058d-ea47-450e-bf9e-a15bfbe3eedb Former-commit-id: d66e96bd7638ec76b9136b84695691af4c6a5691 --- src/Spatial_searching/example/example_spatial_searching.cpp | 8 ++++---- 1 file changed, 4 insertions(+), 4 deletions(-) (limited to 'src/Spatial_searching/example/example_spatial_searching.cpp') diff --git a/src/Spatial_searching/example/example_spatial_searching.cpp b/src/Spatial_searching/example/example_spatial_searching.cpp index 0b1e25f5..4afeccee 100644 --- a/src/Spatial_searching/example/example_spatial_searching.cpp +++ b/src/Spatial_searching/example/example_spatial_searching.cpp @@ -25,8 +25,8 @@ int main (void) Points_ds points_ds(points); - // 20-nearest neighbor query - std::cout << "20 nearest neighbors:\n"; + // 10-nearest neighbor query + std::cout << "10 nearest neighbors from points[20]:\n"; auto kns_range = points_ds.query_k_nearest_neighbors(points[20], 10, true); for (auto const& nghb : kns_range) std::cout << nghb.first << " (sq. dist. = " << nghb.second << ")\n"; @@ -38,8 +38,8 @@ int main (void) for (auto ins_iterator = ins_range.begin(); ins_iterator->second < 0.5*0.5 ; ++ins_iterator) std::cout << ins_iterator->first << " (sq. dist. = " << ins_iterator->second << ")\n"; - // 20-farthest neighbor query - std::cout << "20 farthest neighbors:\n"; + // 10-farthest neighbor query + std::cout << "10 farthest neighbors from points[20]:\n"; auto kfs_range = points_ds.query_k_farthest_neighbors(points[20], 10, true); for (auto const& nghb : kfs_range) std::cout << nghb.first << " (sq. dist. = " << nghb.second << ")\n"; -- cgit v1.2.3 From 4ba3903fab4f46e075296c391594551a93afeb6f Mon Sep 17 00:00:00 2001 From: cjamin Date: Wed, 14 Sep 2016 13:53:45 +0000 Subject: Fix construction of points git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/branches/subsampling_and_spatialsearching@1496 636b058d-ea47-450e-bf9e-a15bfbe3eedb Former-commit-id: 19a074947a803f359af2be2026d9c4135743fb49 --- src/Spatial_searching/example/example_spatial_searching.cpp | 3 +-- src/Spatial_searching/test/test_Spatial_tree_data_structure.cpp | 2 +- 2 files changed, 2 insertions(+), 3 deletions(-) (limited to 'src/Spatial_searching/example/example_spatial_searching.cpp') diff --git a/src/Spatial_searching/example/example_spatial_searching.cpp b/src/Spatial_searching/example/example_spatial_searching.cpp index 4afeccee..ba2ea25f 100644 --- a/src/Spatial_searching/example/example_spatial_searching.cpp +++ b/src/Spatial_searching/example/example_spatial_searching.cpp @@ -3,7 +3,6 @@ #include #include -#include #include namespace gss = Gudhi::spatial_searching; @@ -21,7 +20,7 @@ int main (void) Points points; for (int i = 0; i < 500; ++i) - points.push_back(Point(std::array({ rd.get_double(-1.,1),rd.get_double(-1.,1),rd.get_double(-1.,1),rd.get_double(-1.,1) }))); + points.push_back(Point(rd.get_double(-1.,1), rd.get_double(-1.,1), rd.get_double(-1.,1), rd.get_double(-1.,1))); Points_ds points_ds(points); diff --git a/src/Spatial_searching/test/test_Spatial_tree_data_structure.cpp b/src/Spatial_searching/test/test_Spatial_tree_data_structure.cpp index 207b047f..af321919 100644 --- a/src/Spatial_searching/test/test_Spatial_tree_data_structure.cpp +++ b/src/Spatial_searching/test/test_Spatial_tree_data_structure.cpp @@ -46,7 +46,7 @@ BOOST_AUTO_TEST_CASE(test_Spatial_tree_data_structure) Points points; for (int i = 0 ; i < 500 ; ++i) - points.push_back(Point(std::array({rd.get_double(-1.,1),rd.get_double(-1.,1),rd.get_double(-1.,1),rd.get_double(-1.,1)}))); + points.push_back(Point(rd.get_double(-1.,1), rd.get_double(-1.,1), rd.get_double(-1.,1), rd.get_double(-1.,1))); Points_ds points_ds(points); -- cgit v1.2.3 From 3d2205afe247f23cbe69b98845569708b4263f02 Mon Sep 17 00:00:00 2001 From: cjamin Date: Thu, 22 Sep 2016 13:35:38 +0000 Subject: Spatial_tree_data_structure => Kd_tree_search git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/branches/subsampling_and_spatialsearching@1538 636b058d-ea47-450e-bf9e-a15bfbe3eedb Former-commit-id: 095b038d0e4c1c6d78e9aa9efe73447b65dab2b1 --- .../example/example_spatial_searching.cpp | 4 +- .../include/gudhi/Kd_tree_search.h | 276 +++++++++++++++++++++ .../include/gudhi/Spatial_tree_data_structure.h | 276 --------------------- src/Spatial_searching/test/CMakeLists.txt | 4 +- src/Spatial_searching/test/test_Kd_tree_search.cpp | 118 +++++++++ .../test/test_Spatial_tree_data_structure.cpp | 118 --------- .../include/gudhi/choose_n_farthest_points.h | 2 +- src/Subsampling/include/gudhi/sparsify_point_set.h | 4 +- 8 files changed, 401 insertions(+), 401 deletions(-) create mode 100644 src/Spatial_searching/include/gudhi/Kd_tree_search.h delete mode 100644 src/Spatial_searching/include/gudhi/Spatial_tree_data_structure.h create mode 100644 src/Spatial_searching/test/test_Kd_tree_search.cpp delete mode 100644 src/Spatial_searching/test/test_Spatial_tree_data_structure.cpp (limited to 'src/Spatial_searching/example/example_spatial_searching.cpp') diff --git a/src/Spatial_searching/example/example_spatial_searching.cpp b/src/Spatial_searching/example/example_spatial_searching.cpp index ba2ea25f..7b48d055 100644 --- a/src/Spatial_searching/example/example_spatial_searching.cpp +++ b/src/Spatial_searching/example/example_spatial_searching.cpp @@ -1,4 +1,4 @@ -#include +#include #include #include @@ -14,7 +14,7 @@ int main (void) typedef typename K::Point_d Point; typedef std::vector Points; - typedef gss::Spatial_tree_data_structure Points_ds; + typedef gss::Kd_tree_search Points_ds; CGAL::Random rd; diff --git a/src/Spatial_searching/include/gudhi/Kd_tree_search.h b/src/Spatial_searching/include/gudhi/Kd_tree_search.h new file mode 100644 index 00000000..af85915a --- /dev/null +++ b/src/Spatial_searching/include/gudhi/Kd_tree_search.h @@ -0,0 +1,276 @@ +/* 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 . + */ + +#ifndef GUDHI_SPATIAL_TREE_DS_H_ +#define GUDHI_SPATIAL_TREE_DS_H_ + +#include +#include +#include +#include +#include + +#include +#include + +#include +#include + +namespace Gudhi { +namespace spatial_searching { + + + /** + * \class Kd_tree_search Kd_tree_search.h gudhi/Kd_tree_search.h + * \brief Spatial tree data structure to perform (approximate) nearest neighbor search. + * + * \ingroup spatial_searching + * + * \details + * The class Kd_tree_search is a tree-based data structure, based on + * CGAL dD spatial searching data structures. + * It provides a simplified API to perform (approximate) nearest neighbor searches. Contrary to CGAL default behavior, the tree + * does not store the points themselves, but stores indices. + * + * There are two types of queries: the k-nearest neighbor query, where k is fixed and the k nearest points are + * computed right away, + * and the incremental nearest neighbor query, where no number of neighbors is provided during the call, as the + * neighbors will be computed incrementally when the iterator on the range is incremented. + * + * \tparam K must be a model of the SearchTraits + * concept, such as the CGAL::Epick_d class, which + * can be static if you know the ambiant dimension at compile-time, or dynamic if you don't. + * \tparam Point_range is the type of the range that provides the points. + * It must be a range whose iterator type is a `RandomAccessIterator`. + */ +template +class Kd_tree_search +{ + typedef boost::iterator_property_map< + typename Point_range::const_iterator, + CGAL::Identity_property_map > Point_property_map; + +public: + /// The kernel. + typedef K Kernel; + /// Number type used for distances. + typedef typename Kernel::FT FT; + /// The point type. + typedef typename Point_range::value_type Point; + + typedef CGAL::Search_traits< + FT, Point, + typename Kernel::Cartesian_const_iterator_d, + typename Kernel::Construct_cartesian_const_iterator_d> Traits_base; + + typedef CGAL::Search_traits_adapter< + std::ptrdiff_t, + Point_property_map, + Traits_base> STraits; + + typedef CGAL::Orthogonal_k_neighbor_search K_neighbor_search; + typedef typename K_neighbor_search::Tree Tree; + typedef typename K_neighbor_search::Distance Distance; + /// \brief The range returned by a k-nearest neighbor search. + /// Its value type is `std::pair` where `first` is the index + /// of a point P and `second` is the squared distance between P and the query point. + typedef K_neighbor_search KNS_range; + + typedef CGAL::Orthogonal_incremental_neighbor_search< + STraits, Distance, CGAL::Sliding_midpoint, Tree> + Incremental_neighbor_search; + /// \brief The range returned by an incremental nearest neighbor search. + /// Its value type is `std::pair` where `first` is the index + /// of a point P and `second` is the squared distance between P and the query point. + typedef Incremental_neighbor_search INS_range; + + /// \brief Constructor + /// @param[in] points Const reference to the point range. This range + /// is not copied, so it should not be destroyed or modified afterwards. + Kd_tree_search(Point_range const& points) + : m_points(points), + m_tree(boost::counting_iterator(0), + boost::counting_iterator(points.size()), + typename Tree::Splitter(), + STraits(std::begin(points)) ) + { + // Build the tree now (we don't want to wait for the first query) + m_tree.build(); + } + + /// \brief Constructor + /// @param[in] points Const reference to the point range. This range + /// is not copied, so it should not be destroyed or modified afterwards. + /// @param[in] only_these_points Specifies the indices of the points that + /// should be actually inserted into the tree. The other points are ignored. + template + Kd_tree_search( + Point_range const& points, + Point_indices_range const& only_these_points) + : m_points(points), + m_tree( + only_these_points.begin(), only_these_points.end(), + typename Tree::Splitter(), + STraits(std::begin(points))) + { + // Build the tree now (we don't want to wait for the first query) + m_tree.build(); + } + + /// \brief Constructor + /// @param[in] points Const reference to the point range. This range + /// is not copied, so it should not be destroyed or modified afterwards. + /// @param[in] begin_idx, past_the_end_idx Define the subset of the points that + /// should be actually inserted into the tree. The other points are ignored. + Kd_tree_search( + Point_range const& points, + std::size_t begin_idx, std::size_t past_the_end_idx) + : m_points(points), + m_tree( + boost::counting_iterator(begin_idx), + boost::counting_iterator(past_the_end_idx), + typename Tree::Splitter(), + STraits(std::begin(point)) ) + { + // Build the tree now (we don't want to wait for the first query) + m_tree.build(); + } + + // Be careful, this function invalidates the tree, + // which will be recomputed at the next query + void insert(std::ptrdiff_t point_idx) + { + m_tree.insert(point_idx); + } + + /// \brief Search for the k-nearest neighbors from a query point. + /// @param[in] p The query point. + /// @param[in] k Number of nearest points to search. + /// @param[in] sorted Indicates if the computed sequence of k-nearest neighbors needs to be sorted. + /// @param[in] eps Approximation factor. + /// @return A range containing the k-nearest neighbors. + KNS_range query_k_nearest_neighbors(const + Point &p, + unsigned int k, + bool sorted = true, + FT eps = FT(0)) const + { + // Initialize the search structure, and search all N points + // Note that we need to pass the Distance explicitly since it needs to + // know the property map + K_neighbor_search search( + m_tree, + p, + k, + eps, + true, + CGAL::Distance_adapter >( + std::begin(m_points)), + sorted); + + return search; + } + + /// \brief Search incrementally for the nearest neighbors from a query point. + /// @param[in] p The query point. + /// @param[in] eps Approximation factor. + /// @return A range containing the neighbors sorted by their distance to p. + /// All the neighbors are not computed by this function, but they will be + /// computed incrementally when the iterator on the range is incremented. + INS_range query_incremental_nearest_neighbors(const Point &p, FT eps = FT(0)) const + { + // Initialize the search structure, and search all N points + // Note that we need to pass the Distance explicitly since it needs to + // know the property map + Incremental_neighbor_search search( + m_tree, + p, + eps, + true, + CGAL::Distance_adapter >( + std::begin(m_points)) ); + + return search; + } + + /// \brief Search for the k-farthest points from a query point. + /// @param[in] p The query point. + /// @param[in] k Number of farthest points to search. + /// @param[in] sorted Indicates if the computed sequence of k-farthest neighbors needs to be sorted. + /// @param[in] eps Approximation factor. + /// @return A range containing the k-farthest neighbors. + KNS_range query_k_farthest_neighbors(const + Point &p, + unsigned int k, + bool sorted = true, + FT eps = FT(0)) const + { + // Initialize the search structure, and search all N points + // Note that we need to pass the Distance explicitly since it needs to + // know the property map + K_neighbor_search search( + m_tree, + p, + k, + eps, + false, + CGAL::Distance_adapter >( + std::begin(m_points)), + sorted); + + return search; + } + + /// \brief Search incrementally for the farthest neighbors from a query point. + /// @param[in] p The query point. + /// @param[in] eps Approximation factor. + /// @return A range containing the neighbors sorted by their distance to p. + /// All the neighbors are not computed by this function, but they will be + /// computed incrementally when the iterator on the range is incremented. + INS_range query_incremental_farthest_neighbors(const Point &p, FT eps = FT(0)) const + { + // Initialize the search structure, and search all N points + // Note that we need to pass the Distance explicitly since it needs to + // know the property map + Incremental_neighbor_search search( + m_tree, + p, + eps, + false, + CGAL::Distance_adapter >( + std::begin(m_points)) ); + + return search; + } + + +private: + Point_range const& m_points; + Tree m_tree; +}; + +} // namespace spatial_searching +} // namespace Gudhi + +#endif // GUDHI_SPATIAL_TREE_DS_H_ diff --git a/src/Spatial_searching/include/gudhi/Spatial_tree_data_structure.h b/src/Spatial_searching/include/gudhi/Spatial_tree_data_structure.h deleted file mode 100644 index 68702b22..00000000 --- a/src/Spatial_searching/include/gudhi/Spatial_tree_data_structure.h +++ /dev/null @@ -1,276 +0,0 @@ -/* 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 . - */ - -#ifndef GUDHI_SPATIAL_TREE_DS_H_ -#define GUDHI_SPATIAL_TREE_DS_H_ - -#include -#include -#include -#include -#include - -#include -#include - -#include -#include - -namespace Gudhi { -namespace spatial_searching { - - - /** - * \class Spatial_tree_data_structure Spatial_tree_data_structure.h gudhi/Spatial_tree_data_structure.h - * \brief Spatial tree data structure to perform (approximate) nearest neighbor search. - * - * \ingroup spatial_searching - * - * \details - * The class Spatial_tree_data_structure is a tree-based data structure, based on - * CGAL dD spatial searching data structures. - * It provides a simplified API to perform (approximate) nearest neighbor searches. Contrary to CGAL default behavior, the tree - * does not store the points themselves, but stores indices. - * - * There are two types of queries: the k-nearest neighbor query, where k is fixed and the k nearest points are - * computed right away, - * and the incremental nearest neighbor query, where no number of neighbors is provided during the call, as the - * neighbors will be computed incrementally when the iterator on the range is incremented. - * - * \tparam K must be a model of the SearchTraits - * concept, such as the CGAL::Epick_d class, which - * can be static if you know the ambiant dimension at compile-time, or dynamic if you don't. - * \tparam Point_range is the type of the range that provides the points. - * It must be a range whose iterator type is a `RandomAccessIterator`. - */ -template -class Spatial_tree_data_structure -{ - typedef boost::iterator_property_map< - typename Point_range::const_iterator, - CGAL::Identity_property_map > Point_property_map; - -public: - /// The kernel. - typedef K Kernel; - /// Number type used for distances. - typedef typename Kernel::FT FT; - /// The point type. - typedef typename Point_range::value_type Point; - - typedef CGAL::Search_traits< - FT, Point, - typename Kernel::Cartesian_const_iterator_d, - typename Kernel::Construct_cartesian_const_iterator_d> Traits_base; - - typedef CGAL::Search_traits_adapter< - std::ptrdiff_t, - Point_property_map, - Traits_base> STraits; - - typedef CGAL::Orthogonal_k_neighbor_search K_neighbor_search; - typedef typename K_neighbor_search::Tree Tree; - typedef typename K_neighbor_search::Distance Distance; - /// \brief The range returned by a k-nearest neighbor search. - /// Its value type is `std::pair` where `first` is the index - /// of a point P and `second` is the squared distance between P and the query point. - typedef K_neighbor_search KNS_range; - - typedef CGAL::Orthogonal_incremental_neighbor_search< - STraits, Distance, CGAL::Sliding_midpoint, Tree> - Incremental_neighbor_search; - /// \brief The range returned by an incremental nearest neighbor search. - /// Its value type is `std::pair` where `first` is the index - /// of a point P and `second` is the squared distance between P and the query point. - typedef Incremental_neighbor_search INS_range; - - /// \brief Constructor - /// @param[in] points Const reference to the point range. This range - /// is not copied, so it should not be destroyed or modified afterwards. - Spatial_tree_data_structure(Point_range const& points) - : m_points(points), - m_tree(boost::counting_iterator(0), - boost::counting_iterator(points.size()), - typename Tree::Splitter(), - STraits(std::begin(points)) ) - { - // Build the tree now (we don't want to wait for the first query) - m_tree.build(); - } - - /// \brief Constructor - /// @param[in] points Const reference to the point range. This range - /// is not copied, so it should not be destroyed or modified afterwards. - /// @param[in] only_these_points Specifies the indices of the points that - /// should be actually inserted into the tree. The other points are ignored. - template - Spatial_tree_data_structure( - Point_range const& points, - Point_indices_range const& only_these_points) - : m_points(points), - m_tree( - only_these_points.begin(), only_these_points.end(), - typename Tree::Splitter(), - STraits(std::begin(points))) - { - // Build the tree now (we don't want to wait for the first query) - m_tree.build(); - } - - /// \brief Constructor - /// @param[in] points Const reference to the point range. This range - /// is not copied, so it should not be destroyed or modified afterwards. - /// @param[in] begin_idx, past_the_end_idx Define the subset of the points that - /// should be actually inserted into the tree. The other points are ignored. - Spatial_tree_data_structure( - Point_range const& points, - std::size_t begin_idx, std::size_t past_the_end_idx) - : m_points(points), - m_tree( - boost::counting_iterator(begin_idx), - boost::counting_iterator(past_the_end_idx), - typename Tree::Splitter(), - STraits(std::begin(point)) ) - { - // Build the tree now (we don't want to wait for the first query) - m_tree.build(); - } - - // Be careful, this function invalidates the tree, - // which will be recomputed at the next query - void insert(std::ptrdiff_t point_idx) - { - m_tree.insert(point_idx); - } - - /// \brief Search for the k-nearest neighbors from a query point. - /// @param[in] p The query point. - /// @param[in] k Number of nearest points to search. - /// @param[in] sorted Indicates if the computed sequence of k-nearest neighbors needs to be sorted. - /// @param[in] eps Approximation factor. - /// @return A range containing the k-nearest neighbors. - KNS_range query_k_nearest_neighbors(const - Point &p, - unsigned int k, - bool sorted = true, - FT eps = FT(0)) const - { - // Initialize the search structure, and search all N points - // Note that we need to pass the Distance explicitly since it needs to - // know the property map - K_neighbor_search search( - m_tree, - p, - k, - eps, - true, - CGAL::Distance_adapter >( - std::begin(m_points)), - sorted); - - return search; - } - - /// \brief Search incrementally for the nearest neighbors from a query point. - /// @param[in] p The query point. - /// @param[in] eps Approximation factor. - /// @return A range containing the neighbors sorted by their distance to p. - /// All the neighbors are not computed by this function, but they will be - /// computed incrementally when the iterator on the range is incremented. - INS_range query_incremental_nearest_neighbors(const Point &p, FT eps = FT(0)) const - { - // Initialize the search structure, and search all N points - // Note that we need to pass the Distance explicitly since it needs to - // know the property map - Incremental_neighbor_search search( - m_tree, - p, - eps, - true, - CGAL::Distance_adapter >( - std::begin(m_points)) ); - - return search; - } - - /// \brief Search for the k-farthest points from a query point. - /// @param[in] p The query point. - /// @param[in] k Number of farthest points to search. - /// @param[in] sorted Indicates if the computed sequence of k-farthest neighbors needs to be sorted. - /// @param[in] eps Approximation factor. - /// @return A range containing the k-farthest neighbors. - KNS_range query_k_farthest_neighbors(const - Point &p, - unsigned int k, - bool sorted = true, - FT eps = FT(0)) const - { - // Initialize the search structure, and search all N points - // Note that we need to pass the Distance explicitly since it needs to - // know the property map - K_neighbor_search search( - m_tree, - p, - k, - eps, - false, - CGAL::Distance_adapter >( - std::begin(m_points)), - sorted); - - return search; - } - - /// \brief Search incrementally for the farthest neighbors from a query point. - /// @param[in] p The query point. - /// @param[in] eps Approximation factor. - /// @return A range containing the neighbors sorted by their distance to p. - /// All the neighbors are not computed by this function, but they will be - /// computed incrementally when the iterator on the range is incremented. - INS_range query_incremental_farthest_neighbors(const Point &p, FT eps = FT(0)) const - { - // Initialize the search structure, and search all N points - // Note that we need to pass the Distance explicitly since it needs to - // know the property map - Incremental_neighbor_search search( - m_tree, - p, - eps, - false, - CGAL::Distance_adapter >( - std::begin(m_points)) ); - - return search; - } - - -private: - Point_range const& m_points; - Tree m_tree; -}; - -} // namespace spatial_searching -} // namespace Gudhi - -#endif // GUDHI_SPATIAL_TREE_DS_H_ diff --git a/src/Spatial_searching/test/CMakeLists.txt b/src/Spatial_searching/test/CMakeLists.txt index 82c38ca5..ed61cc64 100644 --- a/src/Spatial_searching/test/CMakeLists.txt +++ b/src/Spatial_searching/test/CMakeLists.txt @@ -20,8 +20,8 @@ if(CGAL_FOUND) include( ${EIGEN3_USE_FILE} ) include_directories (BEFORE "../../include") - add_executable( Spatial_searching_test_Spatial_tree_data_structure test_Spatial_tree_data_structure.cpp ) - target_link_libraries(Spatial_searching_test_Spatial_tree_data_structure + add_executable( Spatial_searching_test_Kd_tree_search test_Kd_tree_search.cpp ) + target_link_libraries(Spatial_searching_test_Kd_tree_search ${CGAL_LIBRARY} ${Boost_SYSTEM_LIBRARY} ${Boost_UNIT_TEST_FRAMEWORK_LIBRARY}) else() message(WARNING "Eigen3 not found. Version 3.1.0 is required for the Spatial_searching tests.") diff --git a/src/Spatial_searching/test/test_Kd_tree_search.cpp b/src/Spatial_searching/test/test_Kd_tree_search.cpp new file mode 100644 index 00000000..6f99b288 --- /dev/null +++ b/src/Spatial_searching/test/test_Kd_tree_search.cpp @@ -0,0 +1,118 @@ +/* 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 . + */ + +#define BOOST_TEST_DYN_LINK +#define BOOST_TEST_MODULE Spatial_searching - test Kd_tree_search +#include + +#include + +#include +#include + +#include +#include + +BOOST_AUTO_TEST_CASE(test_Kd_tree_search) +{ + typedef CGAL::Epick_d > K; + typedef K::FT FT; + typedef K::Point_d Point; + typedef std::vector Points; + + typedef Gudhi::spatial_searching::Kd_tree_search< + K, Points> Points_ds; + + CGAL::Random rd; + + Points points; + for (int i = 0 ; i < 500 ; ++i) + points.push_back(Point(rd.get_double(-1.,1), rd.get_double(-1.,1), rd.get_double(-1.,1), rd.get_double(-1.,1))); + + Points_ds points_ds(points); + + // Test query_k_nearest_neighbors + std::size_t closest_pt_index = + points_ds.query_k_nearest_neighbors(points[10], 1, false).begin()->first; + BOOST_CHECK(closest_pt_index == 10); + + auto kns_range = points_ds.query_k_nearest_neighbors(points[20], 10, true); + + std::vector knn_result; + FT last_dist = -1.; + for (auto const& nghb : kns_range) + { + BOOST_CHECK(nghb.second > last_dist); + knn_result.push_back(nghb.second); + last_dist = nghb.second; + } + + // Test query_incremental_nearest_neighbors + closest_pt_index = + points_ds.query_incremental_nearest_neighbors(points[10]).begin()->first; + BOOST_CHECK(closest_pt_index == 10); + + auto ins_range = points_ds.query_incremental_nearest_neighbors(points[20]); + + std::vector inn_result; + last_dist = -1.; + auto ins_it = ins_range.begin(); + for (int i = 0 ; i < 10 ; ++ins_it, ++i) + { + auto const& nghb = *ins_it; + BOOST_CHECK(nghb.second > last_dist); + inn_result.push_back(nghb.second); + last_dist = nghb.second; + } + + // Same result for KNN and INN? + BOOST_CHECK(knn_result == inn_result); + + // Test query_k_farthest_neighbors + auto kfs_range = points_ds.query_k_farthest_neighbors(points[20], 10, true); + + std::vector kfn_result; + last_dist = kfs_range.begin()->second; + for (auto const& nghb : kfs_range) + { + BOOST_CHECK(nghb.second <= last_dist); + kfn_result.push_back(nghb.second); + last_dist = nghb.second; + } + + // Test query_k_farthest_neighbors + auto ifs_range = points_ds.query_incremental_farthest_neighbors(points[20]); + + std::vector ifn_result; + last_dist = ifs_range.begin()->second; + auto ifs_it = ifs_range.begin(); + for (int i = 0; i < 10; ++ifs_it, ++i) + { + auto const& nghb = *ifs_it; + BOOST_CHECK(nghb.second <= last_dist); + ifn_result.push_back(nghb.second); + last_dist = nghb.second; + } + + // Same result for KFN and IFN? + BOOST_CHECK(kfn_result == ifn_result); +} diff --git a/src/Spatial_searching/test/test_Spatial_tree_data_structure.cpp b/src/Spatial_searching/test/test_Spatial_tree_data_structure.cpp deleted file mode 100644 index af321919..00000000 --- a/src/Spatial_searching/test/test_Spatial_tree_data_structure.cpp +++ /dev/null @@ -1,118 +0,0 @@ -/* 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 . - */ - -#define BOOST_TEST_DYN_LINK -#define BOOST_TEST_MODULE Spatial_searching - test Spatial_tree_data_structure -#include - -#include - -#include -#include - -#include -#include - -BOOST_AUTO_TEST_CASE(test_Spatial_tree_data_structure) -{ - typedef CGAL::Epick_d > K; - typedef K::FT FT; - typedef K::Point_d Point; - typedef std::vector Points; - - typedef Gudhi::spatial_searching::Spatial_tree_data_structure< - K, Points> Points_ds; - - CGAL::Random rd; - - Points points; - for (int i = 0 ; i < 500 ; ++i) - points.push_back(Point(rd.get_double(-1.,1), rd.get_double(-1.,1), rd.get_double(-1.,1), rd.get_double(-1.,1))); - - Points_ds points_ds(points); - - // Test query_k_nearest_neighbors - std::size_t closest_pt_index = - points_ds.query_k_nearest_neighbors(points[10], 1, false).begin()->first; - BOOST_CHECK(closest_pt_index == 10); - - auto kns_range = points_ds.query_k_nearest_neighbors(points[20], 10, true); - - std::vector knn_result; - FT last_dist = -1.; - for (auto const& nghb : kns_range) - { - BOOST_CHECK(nghb.second > last_dist); - knn_result.push_back(nghb.second); - last_dist = nghb.second; - } - - // Test query_incremental_nearest_neighbors - closest_pt_index = - points_ds.query_incremental_nearest_neighbors(points[10]).begin()->first; - BOOST_CHECK(closest_pt_index == 10); - - auto ins_range = points_ds.query_incremental_nearest_neighbors(points[20]); - - std::vector inn_result; - last_dist = -1.; - auto ins_it = ins_range.begin(); - for (int i = 0 ; i < 10 ; ++ins_it, ++i) - { - auto const& nghb = *ins_it; - BOOST_CHECK(nghb.second > last_dist); - inn_result.push_back(nghb.second); - last_dist = nghb.second; - } - - // Same result for KNN and INN? - BOOST_CHECK(knn_result == inn_result); - - // Test query_k_farthest_neighbors - auto kfs_range = points_ds.query_k_farthest_neighbors(points[20], 10, true); - - std::vector kfn_result; - last_dist = kfs_range.begin()->second; - for (auto const& nghb : kfs_range) - { - BOOST_CHECK(nghb.second <= last_dist); - kfn_result.push_back(nghb.second); - last_dist = nghb.second; - } - - // Test query_k_farthest_neighbors - auto ifs_range = points_ds.query_incremental_farthest_neighbors(points[20]); - - std::vector ifn_result; - last_dist = ifs_range.begin()->second; - auto ifs_it = ifs_range.begin(); - for (int i = 0; i < 10; ++ifs_it, ++i) - { - auto const& nghb = *ifs_it; - BOOST_CHECK(nghb.second <= last_dist); - ifn_result.push_back(nghb.second); - last_dist = nghb.second; - } - - // Same result for KFN and IFN? - BOOST_CHECK(kfn_result == ifn_result); -} diff --git a/src/Subsampling/include/gudhi/choose_n_farthest_points.h b/src/Subsampling/include/gudhi/choose_n_farthest_points.h index b999213e..8bfb38a4 100644 --- a/src/Subsampling/include/gudhi/choose_n_farthest_points.h +++ b/src/Subsampling/include/gudhi/choose_n_farthest_points.h @@ -25,7 +25,7 @@ #include -#include +#include #include diff --git a/src/Subsampling/include/gudhi/sparsify_point_set.h b/src/Subsampling/include/gudhi/sparsify_point_set.h index ca31098b..607555b4 100644 --- a/src/Subsampling/include/gudhi/sparsify_point_set.h +++ b/src/Subsampling/include/gudhi/sparsify_point_set.h @@ -23,7 +23,7 @@ #ifndef GUDHI_SPARSIFY_POINT_SET_H #define GUDHI_SPARSIFY_POINT_SET_H -#include +#include #ifdef GUDHI_SUBSAMPLING_PROFILING #include #endif @@ -62,7 +62,7 @@ sparsify_point_set( typename Kernel::FT min_squared_dist, OutputIterator output_it) { - typedef typename Gudhi::spatial_searching::Spatial_tree_data_structure< + typedef typename Gudhi::spatial_searching::Kd_tree_search< Kernel, Point_range> Points_ds; typename Kernel::Squared_distance_d sqdist = k.squared_distance_d_object(); -- cgit v1.2.3 From edf73bdb311f14187323a7df0a5815a60651526a Mon Sep 17 00:00:00 2001 From: cjamin Date: Wed, 28 Sep 2016 16:14:43 +0000 Subject: Unused typedef git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/branches/subsampling_and_spatialsearching@1584 636b058d-ea47-450e-bf9e-a15bfbe3eedb Former-commit-id: 1b8fa44e98da75619a411c1d6058ccebff9ac350 --- src/Spatial_searching/example/example_spatial_searching.cpp | 1 - 1 file changed, 1 deletion(-) (limited to 'src/Spatial_searching/example/example_spatial_searching.cpp') diff --git a/src/Spatial_searching/example/example_spatial_searching.cpp b/src/Spatial_searching/example/example_spatial_searching.cpp index 7b48d055..54e3eb13 100644 --- a/src/Spatial_searching/example/example_spatial_searching.cpp +++ b/src/Spatial_searching/example/example_spatial_searching.cpp @@ -10,7 +10,6 @@ namespace gss = Gudhi::spatial_searching; int main (void) { typedef CGAL::Epick_d > K; - typedef typename K::FT FT; typedef typename K::Point_d Point; typedef std::vector Points; -- cgit v1.2.3 From 9908fa4d77e579293e2c2def13cb1dc4c6773e9d Mon Sep 17 00:00:00 2001 From: cjamin Date: Tue, 4 Oct 2016 13:12:18 +0000 Subject: Modify the example to avoid misleading the user git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/branches/subsampling_and_spatialsearching@1618 636b058d-ea47-450e-bf9e-a15bfbe3eedb Former-commit-id: fa4a318f59e6d6dea46694bd71d0a6a2baf1aaff --- src/Spatial_searching/example/example_spatial_searching.cpp | 8 ++++---- 1 file changed, 4 insertions(+), 4 deletions(-) (limited to 'src/Spatial_searching/example/example_spatial_searching.cpp') diff --git a/src/Spatial_searching/example/example_spatial_searching.cpp b/src/Spatial_searching/example/example_spatial_searching.cpp index 54e3eb13..46aa48b3 100644 --- a/src/Spatial_searching/example/example_spatial_searching.cpp +++ b/src/Spatial_searching/example/example_spatial_searching.cpp @@ -32,8 +32,8 @@ int main (void) // Incremental nearest neighbor query std::cout << "Incremental nearest neighbors:\n"; auto ins_range = points_ds.query_incremental_nearest_neighbors(points[45]); - // Get all the neighbors that are closer than 0.5 - for (auto ins_iterator = ins_range.begin(); ins_iterator->second < 0.5*0.5 ; ++ins_iterator) + // Get the neighbors in distance order until we hit the first point + for (auto ins_iterator = ins_range.begin(); ins_iterator->first != 0 ; ++ins_iterator) std::cout << ins_iterator->first << " (sq. dist. = " << ins_iterator->second << ")\n"; // 10-farthest neighbor query @@ -45,8 +45,8 @@ int main (void) // Incremental farthest neighbor query std::cout << "Incremental farthest neighbors:\n"; auto ifs_range = points_ds.query_incremental_farthest_neighbors(points[45]); - // Get all the neighbors that are farthest than 2.3 - for (auto ifs_iterator = ifs_range.begin(); ifs_iterator->second > 2.3*2.3 ; ++ifs_iterator) + // Get the neighbors in distance reverse order until we hit the first point + for (auto ifs_iterator = ifs_range.begin(); ifs_iterator->first != 0 ; ++ifs_iterator) std::cout << ifs_iterator->first << " (sq. dist. = " << ifs_iterator->second << ")\n"; return 0; -- cgit v1.2.3 From db337a2536eb8a4c7dda384b42abe407ef53487f Mon Sep 17 00:00:00 2001 From: cjamin Date: Tue, 4 Oct 2016 13:27:11 +0000 Subject: kns, kfs... => knn, kfn... git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/branches/subsampling_and_spatialsearching@1620 636b058d-ea47-450e-bf9e-a15bfbe3eedb Former-commit-id: 4965c110b94a8ff1e919464a1f55ec3e62fd8bbf --- .../example/example_spatial_searching.cpp | 16 ++++++++-------- 1 file changed, 8 insertions(+), 8 deletions(-) (limited to 'src/Spatial_searching/example/example_spatial_searching.cpp') diff --git a/src/Spatial_searching/example/example_spatial_searching.cpp b/src/Spatial_searching/example/example_spatial_searching.cpp index 46aa48b3..528ec029 100644 --- a/src/Spatial_searching/example/example_spatial_searching.cpp +++ b/src/Spatial_searching/example/example_spatial_searching.cpp @@ -25,28 +25,28 @@ int main (void) // 10-nearest neighbor query std::cout << "10 nearest neighbors from points[20]:\n"; - auto kns_range = points_ds.query_k_nearest_neighbors(points[20], 10, true); - for (auto const& nghb : kns_range) + auto knn_range = points_ds.query_k_nearest_neighbors(points[20], 10, true); + for (auto const& nghb : knn_range) std::cout << nghb.first << " (sq. dist. = " << nghb.second << ")\n"; // Incremental nearest neighbor query std::cout << "Incremental nearest neighbors:\n"; - auto ins_range = points_ds.query_incremental_nearest_neighbors(points[45]); + auto inn_range = points_ds.query_incremental_nearest_neighbors(points[45]); // Get the neighbors in distance order until we hit the first point - for (auto ins_iterator = ins_range.begin(); ins_iterator->first != 0 ; ++ins_iterator) + for (auto ins_iterator = inn_range.begin(); ins_iterator->first != 0 ; ++ins_iterator) std::cout << ins_iterator->first << " (sq. dist. = " << ins_iterator->second << ")\n"; // 10-farthest neighbor query std::cout << "10 farthest neighbors from points[20]:\n"; - auto kfs_range = points_ds.query_k_farthest_neighbors(points[20], 10, true); - for (auto const& nghb : kfs_range) + auto kfn_range = points_ds.query_k_farthest_neighbors(points[20], 10, true); + for (auto const& nghb : kfn_range) std::cout << nghb.first << " (sq. dist. = " << nghb.second << ")\n"; // Incremental farthest neighbor query std::cout << "Incremental farthest neighbors:\n"; - auto ifs_range = points_ds.query_incremental_farthest_neighbors(points[45]); + auto ifn_range = points_ds.query_incremental_farthest_neighbors(points[45]); // Get the neighbors in distance reverse order until we hit the first point - for (auto ifs_iterator = ifs_range.begin(); ifs_iterator->first != 0 ; ++ifs_iterator) + for (auto ifs_iterator = ifn_range.begin(); ifs_iterator->first != 0 ; ++ifs_iterator) std::cout << ifs_iterator->first << " (sq. dist. = " << ifs_iterator->second << ")\n"; return 0; -- cgit v1.2.3 From f7eb2c8060b7a429f360846ce4fcd51490564ce0 Mon Sep 17 00:00:00 2001 From: vrouvrea Date: Thu, 6 Oct 2016 17:06:40 +0000 Subject: Fix cpplint git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/branches/subsampling_and_spatialsearching@1662 636b058d-ea47-450e-bf9e-a15bfbe3eedb Former-commit-id: 876f5fe1a6a5ecf281837dc86613dff85db65f27 --- .../example/example_spatial_searching.cpp | 17 +++++----- src/Spatial_searching/test/test_Kd_tree_search.cpp | 37 ++++++++++------------ 2 files changed, 24 insertions(+), 30 deletions(-) (limited to 'src/Spatial_searching/example/example_spatial_searching.cpp') diff --git a/src/Spatial_searching/example/example_spatial_searching.cpp b/src/Spatial_searching/example/example_spatial_searching.cpp index 528ec029..14b324ae 100644 --- a/src/Spatial_searching/example/example_spatial_searching.cpp +++ b/src/Spatial_searching/example/example_spatial_searching.cpp @@ -7,11 +7,10 @@ namespace gss = Gudhi::spatial_searching; -int main (void) -{ - typedef CGAL::Epick_d > K; - typedef typename K::Point_d Point; - typedef std::vector Points; +int main(void) { + typedef CGAL::Epick_d > K; + typedef typename K::Point_d Point; + typedef std::vector Points; typedef gss::Kd_tree_search Points_ds; @@ -19,7 +18,7 @@ int main (void) Points points; for (int i = 0; i < 500; ++i) - points.push_back(Point(rd.get_double(-1.,1), rd.get_double(-1.,1), rd.get_double(-1.,1), rd.get_double(-1.,1))); + points.push_back(Point(rd.get_double(-1., 1), rd.get_double(-1., 1), rd.get_double(-1., 1), rd.get_double(-1., 1))); Points_ds points_ds(points); @@ -33,7 +32,7 @@ int main (void) std::cout << "Incremental nearest neighbors:\n"; auto inn_range = points_ds.query_incremental_nearest_neighbors(points[45]); // Get the neighbors in distance order until we hit the first point - for (auto ins_iterator = inn_range.begin(); ins_iterator->first != 0 ; ++ins_iterator) + for (auto ins_iterator = inn_range.begin(); ins_iterator->first != 0; ++ins_iterator) std::cout << ins_iterator->first << " (sq. dist. = " << ins_iterator->second << ")\n"; // 10-farthest neighbor query @@ -46,8 +45,8 @@ int main (void) std::cout << "Incremental farthest neighbors:\n"; auto ifn_range = points_ds.query_incremental_farthest_neighbors(points[45]); // Get the neighbors in distance reverse order until we hit the first point - for (auto ifs_iterator = ifn_range.begin(); ifs_iterator->first != 0 ; ++ifs_iterator) + for (auto ifs_iterator = ifn_range.begin(); ifs_iterator->first != 0; ++ifs_iterator) std::cout << ifs_iterator->first << " (sq. dist. = " << ifs_iterator->second << ")\n"; - + return 0; } diff --git a/src/Spatial_searching/test/test_Kd_tree_search.cpp b/src/Spatial_searching/test/test_Kd_tree_search.cpp index 16b72c68..0ef22023 100644 --- a/src/Spatial_searching/test/test_Kd_tree_search.cpp +++ b/src/Spatial_searching/test/test_Kd_tree_search.cpp @@ -4,7 +4,7 @@ * * Author(s): Clement Jamin * - * Copyright (C) 2016 INRIA Sophia-Antipolis (France) + * 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 @@ -31,35 +31,33 @@ #include -BOOST_AUTO_TEST_CASE(test_Kd_tree_search) -{ - typedef CGAL::Epick_d > K; - typedef K::FT FT; - typedef K::Point_d Point; - typedef std::vector Points; +BOOST_AUTO_TEST_CASE(test_Kd_tree_search) { + typedef CGAL::Epick_d > K; + typedef K::FT FT; + typedef K::Point_d Point; + typedef std::vector Points; typedef Gudhi::spatial_searching::Kd_tree_search< - K, Points> Points_ds; - + K, Points> Points_ds; + CGAL::Random rd; Points points; - for (int i = 0 ; i < 500 ; ++i) - points.push_back(Point(rd.get_double(-1.,1), rd.get_double(-1.,1), rd.get_double(-1.,1), rd.get_double(-1.,1))); + for (int i = 0; i < 500; ++i) + points.push_back(Point(rd.get_double(-1., 1), rd.get_double(-1., 1), rd.get_double(-1., 1), rd.get_double(-1., 1))); Points_ds points_ds(points); // Test query_k_nearest_neighbors std::size_t closest_pt_index = - points_ds.query_k_nearest_neighbors(points[10], 1, false).begin()->first; + points_ds.query_k_nearest_neighbors(points[10], 1, false).begin()->first; BOOST_CHECK(closest_pt_index == 10); auto kns_range = points_ds.query_k_nearest_neighbors(points[20], 10, true); std::vector knn_result; FT last_dist = -1.; - for (auto const& nghb : kns_range) - { + for (auto const& nghb : kns_range) { BOOST_CHECK(nghb.second > last_dist); knn_result.push_back(nghb.second); last_dist = nghb.second; @@ -67,7 +65,7 @@ BOOST_AUTO_TEST_CASE(test_Kd_tree_search) // Test query_incremental_nearest_neighbors closest_pt_index = - points_ds.query_incremental_nearest_neighbors(points[10]).begin()->first; + points_ds.query_incremental_nearest_neighbors(points[10]).begin()->first; BOOST_CHECK(closest_pt_index == 10); auto inn_range = points_ds.query_incremental_nearest_neighbors(points[20]); @@ -75,8 +73,7 @@ BOOST_AUTO_TEST_CASE(test_Kd_tree_search) std::vector inn_result; last_dist = -1.; auto inn_it = inn_range.begin(); - for (int i = 0 ; i < 10 ; ++inn_it, ++i) - { + for (int i = 0; i < 10; ++inn_it, ++i) { auto const& nghb = *inn_it; BOOST_CHECK(nghb.second > last_dist); inn_result.push_back(nghb.second); @@ -91,8 +88,7 @@ BOOST_AUTO_TEST_CASE(test_Kd_tree_search) std::vector kfn_result; last_dist = kfn_range.begin()->second; - for (auto const& nghb : kfn_range) - { + for (auto const& nghb : kfn_range) { BOOST_CHECK(nghb.second <= last_dist); kfn_result.push_back(nghb.second); last_dist = nghb.second; @@ -104,8 +100,7 @@ BOOST_AUTO_TEST_CASE(test_Kd_tree_search) std::vector ifn_result; last_dist = ifn_range.begin()->second; auto ifn_it = ifn_range.begin(); - for (int i = 0; i < 10; ++ifn_it, ++i) - { + for (int i = 0; i < 10; ++ifn_it, ++i) { auto const& nghb = *ifn_it; BOOST_CHECK(nghb.second <= last_dist); ifn_result.push_back(nghb.second); -- cgit v1.2.3