diff options
Diffstat (limited to 'src/Spatial_searching')
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); } |