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

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;
+  }
 }