From b06c5d015ba1524fe63997eefe7b461e06dd9966 Mon Sep 17 00:00:00 2001 From: cjamin Date: Thu, 13 Apr 2017 09:31:33 +0000 Subject: Add radius search git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/branches/Spatial_searching-Add_radius_search@2341 636b058d-ea47-450e-bf9e-a15bfbe3eedb Former-commit-id: c30c32b27b8c3c1c8dd65e45d2bdd49738794062 --- .../include/gudhi/Kd_tree_search.h | 57 +++++++++++++++------- 1 file changed, 39 insertions(+), 18 deletions(-) (limited to 'src/Spatial_searching/include/gudhi') diff --git a/src/Spatial_searching/include/gudhi/Kd_tree_search.h b/src/Spatial_searching/include/gudhi/Kd_tree_search.h index 6728d56e..374ebed6 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 #include #include +#include #include #include @@ -104,6 +105,7 @@ class Kd_tree_search { /// 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 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 +166,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 query_k_nearest_neighbors( + Point const& p, unsigned int k, bool sorted = true, FT eps = FT(0)) const { @@ -179,8 +181,7 @@ class Kd_tree_search { k, eps, true, - CGAL::Distance_adapter >( - std::begin(m_points)), sorted); + Orthogonal_distance(std::begin(m_points)), sorted); return search; } @@ -188,10 +189,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 query_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,8 +202,7 @@ class Kd_tree_search { p, eps, true, - CGAL::Distance_adapter >( - std::begin(m_points)) ); + Orthogonal_distance(std::begin(m_points)) ); return search; } @@ -211,9 +212,9 @@ class Kd_tree_search { /// @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, + /// @return A range (whose `value_type` is `std::size_t`) containing the k-farthest neighbors. + KNS_range query_k_farthest_neighbors( + Point const& p, unsigned int k, bool sorted = true, FT eps = FT(0)) const { @@ -226,8 +227,7 @@ class Kd_tree_search { k, eps, false, - CGAL::Distance_adapter >( - std::begin(m_points)), sorted); + Orthogonal_distance(std::begin(m_points)), sorted); return search; } @@ -235,10 +235,11 @@ class Kd_tree_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. + /// @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 query_incremental_farthest_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 +248,32 @@ class Kd_tree_search { p, eps, false, - CGAL::Distance_adapter >( - 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`. + /// The `value_type` of the iterator must be `Point`. + /// @param[in] eps Approximation factor. + template + void radius_search( + 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; -- cgit v1.2.3