git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/branches/Nerve_GIC@2838 636b058d-ea47-450e-bf9e-a15bfbe3eedb

Former-commit-id: aa674c458f110c5c7cc3f5c987b921fcc96e3e7e

6 files changed, 89 insertions, 49 deletions

diff --git a/src/Spatial_searching/doc/Intro_spatial_searching.h b/src/Spatial_searching/doc/Intro_spatial_searching.h
index 23705378..1ee5e92e 100644
--- a/src/Spatial_searching/doc/Intro_spatial_searching.h
+++ b/src/Spatial_searching/doc/Intro_spatial_searching.h
@@ -46,7 +46,7 @@ namespace spatial_searching {
  * 
  * \section spatial_searching_examples Example
  * 
- * This example generates 500 random points, then performs queries for nearest and farthest points using different methods.
+ * This example generates 500 random points, then performs all-near-neighbors searches, and queries for nearest and furthest neighbors using different methods.
  * 
  * \include Spatial_searching/example_spatial_searching.cpp
  * 
diff --git a/src/Spatial_searching/example/CMakeLists.txt b/src/Spatial_searching/example/CMakeLists.txt
index f4b9f3cb..4cf3d863 100644
--- a/src/Spatial_searching/example/CMakeLists.txt
+++ b/src/Spatial_searching/example/CMakeLists.txt
@@ -6,4 +6,5 @@ if(NOT CGAL_WITH_EIGEN3_VERSION VERSION_LESS 4.8.1)
   target_link_libraries(Spatial_searching_example_spatial_searching ${CGAL_LIBRARY})
   add_test(NAME Spatial_searching_example_spatial_searching
       COMMAND $<TARGET_FILE:Spatial_searching_example_spatial_searching>)
+  install(TARGETS Spatial_searching_example_spatial_searching DESTINATION bin)
 endif(NOT CGAL_WITH_EIGEN3_VERSION VERSION_LESS 4.8.1)
diff --git a/src/Spatial_searching/example/example_spatial_searching.cpp b/src/Spatial_searching/example/example_spatial_searching.cpp
index 14b324ae..034ad24a 100644
--- a/src/Spatial_searching/example/example_spatial_searching.cpp
+++ b/src/Spatial_searching/example/example_spatial_searching.cpp
@@ -24,29 +24,37 @@ int main(void) {
 
   // 10-nearest neighbor query
   std::cout << "10 nearest neighbors from points[20]:\n";
-  auto knn_range = points_ds.query_k_nearest_neighbors(points[20], 10, true);
+  auto knn_range = points_ds.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 inn_range = points_ds.query_incremental_nearest_neighbors(points[45]);
+  auto inn_range = points_ds.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)
     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 kfn_range = points_ds.query_k_farthest_neighbors(points[20], 10, true);
+  // 10-furthest neighbor query
+  std::cout << "10 furthest neighbors from points[20]:\n";
+  auto kfn_range = points_ds.k_furthest_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 ifn_range = points_ds.query_incremental_farthest_neighbors(points[45]);
+  // Incremental furthest neighbor query
+  std::cout << "Incremental furthest neighbors:\n";
+  auto ifn_range = points_ds.incremental_furthest_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)
     std::cout << ifs_iterator->first << " (sq. dist. = " << ifs_iterator->second << ")\n";
 
+  // All-near-neighbors search
+  std::cout << "All-near-neighbors search:\n";
+  std::vector<std::size_t> rs_result;
+  points_ds.all_near_neighbors(points[45], 0.5, std::back_inserter(rs_result));
+  K k;
+  for (auto const& p_idx : rs_result)
+    std::cout << p_idx << " (sq. dist. = " << k.squared_distance_d_object()(points[p_idx], points[45]) << ")\n";
+
   return 0;
 }
diff --git a/src/Spatial_searching/include/gudhi/Kd_tree_search.h b/src/Spatial_searching/include/gudhi/Kd_tree_search.h
index 6728d56e..ef428002 100644
--- a/src/Spatial_searching/include/gudhi/Kd_tree_search.h
+++ b/src/Spatial_searching/include/gudhi/Kd_tree_search.h
@@ -27,6 +27,7 @@
 #include <CGAL/Orthogonal_incremental_neighbor_search.h>
 #include <CGAL/Search_traits.h>
 #include <CGAL/Search_traits_adapter.h>
+#include <CGAL/Fuzzy_sphere.h>
 #include <CGAL/property_map.h>
 
 #include <boost/property_map/property_map.hpp>
@@ -41,19 +42,19 @@ 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 and farthest neighbor search.
+  * \brief Spatial tree data structure to perform (approximate) nearest and furthest neighbor search.
   *
   * \ingroup spatial_searching
   *
   * \details
   * The class Kd_tree_search is a tree-based data structure, based on
   * <a target="_blank" href="http://doc.cgal.org/latest/Spatial_searching/index.html">CGAL dD spatial searching data structures</a>.
-  * It provides a simplified API to perform (approximate) nearest and farthest neighbor searches. Contrary to CGAL default behavior, the tree
+  * It provides a simplified API to perform (approximate) nearest and furthest 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 <i>k-nearest or k-farthest neighbor query</i>, where <i>k</i> is fixed and the <i>k</i> nearest 
-  * or farthest points are computed right away,
-  * and the <i>incremental nearest or farthest neighbor query</i>, where no number of neighbors is provided during the call, as the
+  * There are two types of queries: the <i>k-nearest or k-furthest neighbor query</i>, where <i>k</i> is fixed and the <i>k</i> nearest 
+  * or furthest points are computed right away,
+  * and the <i>incremental nearest or furthest neighbor query</i>, 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 Search_traits must be a model of the <a target="_blank"
@@ -87,11 +88,15 @@ class Kd_tree_search {
     std::ptrdiff_t,
     Point_property_map,
     Traits_base>                                            STraits;
+  typedef CGAL::Distance_adapter<
+    std::ptrdiff_t,
+    Point_property_map,
+    CGAL::Euclidean_distance<Traits_base> >                 Orthogonal_distance;
 
   typedef CGAL::Orthogonal_k_neighbor_search<STraits>       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 or k-farthest neighbor search.
+  /// \brief The range returned by a k-nearest or k-furthest neighbor search.
   /// Its value type is `std::pair<std::size_t, FT>` 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;
@@ -99,11 +104,12 @@ class Kd_tree_search {
   typedef CGAL::Orthogonal_incremental_neighbor_search<
     STraits, Distance, CGAL::Sliding_midpoint<STraits>, Tree>
                                                    Incremental_neighbor_search;
-  /// \brief The range returned by an incremental nearest or farthest neighbor search.
+  /// \brief The range returned by an incremental nearest or furthest neighbor search.
   /// Its value type is `std::pair<std::size_t, FT>` 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;
 
+  typedef CGAL::Fuzzy_sphere<STraits>                       Fuzzy_sphere;
   /// \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.
@@ -164,9 +170,9 @@ class Kd_tree_search {
   /// @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,
+  /// @return A range (whose `value_type` is `std::size_t`) containing the k-nearest neighbors.
+  KNS_range k_nearest_neighbors(
+    Point const& p,
     unsigned int k,
     bool sorted = true,
     FT eps = FT(0)) const {
@@ -179,8 +185,7 @@ class Kd_tree_search {
       k,
       eps,
       true,
-      CGAL::Distance_adapter<std::ptrdiff_t, Point_property_map, CGAL::Euclidean_distance<Traits_base> >(
-        std::begin(m_points)), sorted);
+      Orthogonal_distance(std::begin(m_points)), sorted);
 
     return search;
   }
@@ -188,10 +193,11 @@ class Kd_tree_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.
+  /// @return A range (whose `value_type` is `std::size_t`) 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 {
+  INS_range incremental_nearest_neighbors(Point const& 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
@@ -200,20 +206,19 @@ class Kd_tree_search {
       p,
       eps,
       true,
-      CGAL::Distance_adapter<std::ptrdiff_t, Point_property_map, CGAL::Euclidean_distance<Traits_base> >(
-        std::begin(m_points)) );
+      Orthogonal_distance(std::begin(m_points)) );
 
     return search;
   }
 
-  /// \brief Search for the k-farthest points from a query point.
+  /// \brief Search for the k-furthest 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] k Number of furthest points to search.
+  /// @param[in] sorted Indicates if the computed sequence of k-furthest 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,
+  /// @return A range (whose `value_type` is `std::size_t`) containing the k-furthest neighbors.
+  KNS_range k_furthest_neighbors(
+    Point const& p,
     unsigned int k,
     bool sorted = true,
     FT eps = FT(0)) const {
@@ -226,19 +231,19 @@ class Kd_tree_search {
       k,
       eps,
       false,
-      CGAL::Distance_adapter<std::ptrdiff_t, Point_property_map, CGAL::Euclidean_distance<Traits_base> >(
-        std::begin(m_points)), sorted);
+      Orthogonal_distance(std::begin(m_points)), sorted);
 
     return search;
   }
 
-  /// \brief Search incrementally for the farthest neighbors from a query point.
+  /// \brief Search incrementally for the furthest 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.
+  /// @return A range (whose `value_type` is `std::size_t`)
+  /// 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 {
+  INS_range incremental_furthest_neighbors(Point const& 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
@@ -247,12 +252,30 @@ class Kd_tree_search {
       p,
       eps,
       false,
-      CGAL::Distance_adapter<std::ptrdiff_t, Point_property_map, CGAL::Euclidean_distance<Traits_base> >(
-        std::begin(m_points)) );
+      Orthogonal_distance(std::begin(m_points)) );
 
     return search;
   }
 
+  /// \brief Search for all the neighbors in a ball.
+  /// @param[in] p The query point.
+  /// @param[in] radius The search radius
+  /// @param[out] it The points that lie inside the sphere of center `p` and radius `radius`.
+  ///                Note: `it` is used this way: `*it++ = each_point`.
+  /// @param[in] eps Approximation factor.
+  template <typename OutputIterator>
+  void all_near_neighbors(Point const& p,
+                   FT radius,
+                   OutputIterator it,
+                   FT eps = FT(0)) const {
+    m_tree.search(it, Fuzzy_sphere(p, radius, eps, m_tree.traits()));
+  }
+
+  int tree_depth() const
+  {
+    return m_tree.root()->depth();
+  }
+
  private:
   Point_range const& m_points;
   Tree m_tree;
diff --git a/src/Spatial_searching/test/CMakeLists.txt b/src/Spatial_searching/test/CMakeLists.txt
index 2502ea5e..b9da7b4e 100644
--- a/src/Spatial_searching/test/CMakeLists.txt
+++ b/src/Spatial_searching/test/CMakeLists.txt
@@ -6,7 +6,7 @@ if (NOT CGAL_WITH_EIGEN3_VERSION VERSION_LESS 4.8.1)
 
   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})
+    ${CGAL_LIBRARY} ${Boost_UNIT_TEST_FRAMEWORK_LIBRARY})
 
   gudhi_add_coverage_test(Spatial_searching_test_Kd_tree_search)
 endif ()
diff --git a/src/Spatial_searching/test/test_Kd_tree_search.cpp b/src/Spatial_searching/test/test_Kd_tree_search.cpp
index 0ef22023..8a8334c3 100644
--- a/src/Spatial_searching/test/test_Kd_tree_search.cpp
+++ b/src/Spatial_searching/test/test_Kd_tree_search.cpp
@@ -48,12 +48,12 @@ BOOST_AUTO_TEST_CASE(test_Kd_tree_search) {
 
   Points_ds points_ds(points);
 
-  // Test query_k_nearest_neighbors
+  // Test k_nearest_neighbors
   std::size_t closest_pt_index =
-      points_ds.query_k_nearest_neighbors(points[10], 1, false).begin()->first;
+      points_ds.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);
+  auto kns_range = points_ds.k_nearest_neighbors(points[20], 10, true);
 
   std::vector<std::size_t> knn_result;
   FT last_dist = -1.;
@@ -63,12 +63,12 @@ BOOST_AUTO_TEST_CASE(test_Kd_tree_search) {
     last_dist = nghb.second;
   }
 
-  // Test query_incremental_nearest_neighbors 
+  // Test incremental_nearest_neighbors 
   closest_pt_index =
-      points_ds.query_incremental_nearest_neighbors(points[10]).begin()->first;
+      points_ds.incremental_nearest_neighbors(points[10]).begin()->first;
   BOOST_CHECK(closest_pt_index == 10);
 
-  auto inn_range = points_ds.query_incremental_nearest_neighbors(points[20]);
+  auto inn_range = points_ds.incremental_nearest_neighbors(points[20]);
 
   std::vector<std::size_t> inn_result;
   last_dist = -1.;
@@ -83,8 +83,8 @@ BOOST_AUTO_TEST_CASE(test_Kd_tree_search) {
   // Same result for KNN and INN?
   BOOST_CHECK(knn_result == inn_result);
 
-  // Test query_k_farthest_neighbors
-  auto kfn_range = points_ds.query_k_farthest_neighbors(points[20], 10, true);
+  // Test k_furthest_neighbors
+  auto kfn_range = points_ds.k_furthest_neighbors(points[20], 10, true);
 
   std::vector<std::size_t> kfn_result;
   last_dist = kfn_range.begin()->second;
@@ -94,8 +94,8 @@ BOOST_AUTO_TEST_CASE(test_Kd_tree_search) {
     last_dist = nghb.second;
   }
 
-  // Test query_k_farthest_neighbors
-  auto ifn_range = points_ds.query_incremental_farthest_neighbors(points[20]);
+  // Test k_furthest_neighbors
+  auto ifn_range = points_ds.incremental_furthest_neighbors(points[20]);
 
   std::vector<std::size_t> ifn_result;
   last_dist = ifn_range.begin()->second;
@@ -109,4 +109,12 @@ BOOST_AUTO_TEST_CASE(test_Kd_tree_search) {
 
   // Same result for KFN and IFN?
   BOOST_CHECK(kfn_result == ifn_result);
+
+  // Test all_near_neighbors
+  Point rs_q(rd.get_double(-1., 1), rd.get_double(-1., 1), rd.get_double(-1., 1), rd.get_double(-1., 1));
+  std::vector<std::size_t> rs_result;
+  points_ds.all_near_neighbors(rs_q, 0.5, std::back_inserter(rs_result));
+  K k;
+  for (auto const& p_idx : rs_result)
+    BOOST_CHECK(k.squared_distance_d_object()(points[p_idx], rs_q) <= 0.5);
 }