diff options
author | skachano <skachano@636b058d-ea47-450e-bf9e-a15bfbe3eedb> | 2016-08-05 14:22:57 +0000 |
---|---|---|
committer | skachano <skachano@636b058d-ea47-450e-bf9e-a15bfbe3eedb> | 2016-08-05 14:22:57 +0000 |
commit | 5bc90cf2f92f07a45a7104bd771d52bd0985fb9a (patch) | |
tree | 1a501a20c3370e9b54dc32c72304e812b2412e67 /src | |
parent | 6cdf1246015e1ce8c87a938f7fb2ccde787e5d4c (diff) |
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
Diffstat (limited to 'src')
3 files changed, 80 insertions, 6 deletions
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<std::ptrdiff_t,Point*,CGAL::Euclidean_distance<Traits_base> >( + (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<std::ptrdiff_t, Point*, CGAL::Euclidean_distance<Traits_base> >( + (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; + } } |