diff options
Diffstat (limited to 'src')
| -rw-r--r-- | src/CMakeLists.txt | 8 | ||||
| -rw-r--r-- | src/Spatial_searching/doc/Intro_spatial_searching.h | 2 | ||||
| -rw-r--r-- | src/Spatial_searching/example/example_spatial_searching.cpp | 8 | ||||
| -rw-r--r-- | src/Spatial_searching/include/gudhi/Kd_tree_search.h | 61 | ||||
| -rw-r--r-- | src/Spatial_searching/test/test_Kd_tree_search.cpp | 8 | ||||
| -rw-r--r-- | src/cmake/modules/GUDHI_modules.cmake | 23 | ||||
| -rw-r--r-- | src/cmake/modules/GUDHI_user_version_target.cmake | 4 | ||||
| -rw-r--r-- | src/common/doc/main_page.h | 3 |
8 files changed, 86 insertions, 31 deletions
diff --git a/src/CMakeLists.txt b/src/CMakeLists.txt index 8abfcf44..795005b1 100644 --- a/src/CMakeLists.txt +++ b/src/CMakeLists.txt @@ -7,10 +7,8 @@ enable_testing() list(APPEND CMAKE_MODULE_PATH "${CMAKE_SOURCE_DIR}/cmake/modules/") -# To be done first - Modules list can be found in CMAKE_MODULE_PATH/GUDHI_modules.cmake -include(GUDHI_modules) - # Add your new module in the list, order is not important +include(GUDHI_modules) add_gudhi_module(common) add_gudhi_module(Alpha_complex) @@ -27,6 +25,8 @@ add_gudhi_module(Subsampling) add_gudhi_module(Tangential_complex) add_gudhi_module(Witness_complex) +message("++ GUDHI_MODULES list is:\"${GUDHI_MODULES}\"") + # For "make doxygen" - Requires GUDHI_USER_VERSION_DIR to be set set(GUDHI_USER_VERSION_DIR ${CMAKE_SOURCE_DIR}) include(GUDHI_doxygen_target) @@ -71,7 +71,7 @@ endforeach() add_subdirectory(GudhUI) -if (NOT WITHOUT_GUDHI_PYTHON) +if (WITH_GUDHI_PYTHON) # specific for cython module add_subdirectory(${GUDHI_CYTHON_PATH}) endif() diff --git a/src/Spatial_searching/doc/Intro_spatial_searching.h b/src/Spatial_searching/doc/Intro_spatial_searching.h index 23705378..9a3c1b65 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 radius search, and queries for nearest and farthest points using different methods. * * \include Spatial_searching/example_spatial_searching.cpp * diff --git a/src/Spatial_searching/example/example_spatial_searching.cpp b/src/Spatial_searching/example/example_spatial_searching.cpp index 14b324ae..9e6a8f32 100644 --- a/src/Spatial_searching/example/example_spatial_searching.cpp +++ b/src/Spatial_searching/example/example_spatial_searching.cpp @@ -48,5 +48,13 @@ int main(void) { for (auto ifs_iterator = ifn_range.begin(); ifs_iterator->first != 0; ++ifs_iterator) std::cout << ifs_iterator->first << " (sq. dist. = " << ifs_iterator->second << ")\n"; + // Radius search + std::cout << "Radius search:\n"; + std::vector<std::size_t> rs_result; + points_ds.radius_search(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..f13a98f7 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> @@ -87,6 +88,10 @@ 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; @@ -104,6 +109,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<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 query_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 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 +206,7 @@ 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; } @@ -211,9 +216,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 +231,7 @@ 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; } @@ -235,10 +239,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 +252,32 @@ 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 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; diff --git a/src/Spatial_searching/test/test_Kd_tree_search.cpp b/src/Spatial_searching/test/test_Kd_tree_search.cpp index 0ef22023..f79114bc 100644 --- a/src/Spatial_searching/test/test_Kd_tree_search.cpp +++ b/src/Spatial_searching/test/test_Kd_tree_search.cpp @@ -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 radius search + 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.radius_search(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); } diff --git a/src/cmake/modules/GUDHI_modules.cmake b/src/cmake/modules/GUDHI_modules.cmake index 20fc8d17..f95d0c34 100644 --- a/src/cmake/modules/GUDHI_modules.cmake +++ b/src/cmake/modules/GUDHI_modules.cmake @@ -1,11 +1,26 @@ # A function to add a new module in GUDHI set(GUDHI_MODULES "") +set(GUDHI_MODULES_FULL_LIST "") function(add_gudhi_module file_path) + option("WITH_MODULE_GUDHI_${file_path}" "Activate/desactivate ${file_path} compilation and installation" ON) + if (WITH_MODULE_GUDHI_${file_path}) set(GUDHI_MODULES ${GUDHI_MODULES} ${file_path} PARENT_SCOPE) + endif() + # Required by user_version + set(GUDHI_MODULES_FULL_LIST ${GUDHI_MODULES_FULL_LIST} ${file_path} PARENT_SCOPE) + # Include module headers is independant - You may ask for no Alpha complex module but Python interface i.e. + if(IS_DIRECTORY ${CMAKE_SOURCE_DIR}/src/${file_path}/include/) + include_directories(src/${file_path}/include/) + endif() + endfunction(add_gudhi_module) -# message("++ GUDHI_MODULES list is:\"${GUDHI_MODULES}\"") +option(WITH_GUDHI_BENCHMARK "Activate/desactivate benchmark compilation" OFF) +option(WITH_GUDHI_EXAMPLE "Activate/desactivate examples compilation and installation" OFF) +option(WITH_GUDHI_PYTHON "Activate/desactivate python module compilation and installation" ON) +option(WITH_GUDHI_TEST "Activate/desactivate examples compilation and installation" ON) +option(WITH_GUDHI_UTILITIES "Activate/desactivate utilities compilation and installation" ON) if (WITH_GUDHI_BENCHMARK) set(GUDHI_SUB_DIRECTORIES "${GUDHI_SUB_DIRECTORIES};benchmark") @@ -13,10 +28,10 @@ endif() if (WITH_GUDHI_EXAMPLE) set(GUDHI_SUB_DIRECTORIES "${GUDHI_SUB_DIRECTORIES};example") endif() -if (NOT WITHOUT_GUDHI_TEST) - set(GUDHI_SUB_DIRECTORIES "${GUDHI_SUB_DIRECTORIES};test") +if (WITH_GUDHI_TEST) + set(GUDHI_SUB_DIRECTORIES "${GUDHI_SUB_DIRECTORIES};test") endif() -if (NOT WITHOUT_GUDHI_UTILITIES) +if (WITH_GUDHI_UTILITIES) set(GUDHI_SUB_DIRECTORIES "${GUDHI_SUB_DIRECTORIES};utilities") endif() diff --git a/src/cmake/modules/GUDHI_user_version_target.cmake b/src/cmake/modules/GUDHI_user_version_target.cmake index 8642d3bf..cff64ad2 100644 --- a/src/cmake/modules/GUDHI_user_version_target.cmake +++ b/src/cmake/modules/GUDHI_user_version_target.cmake @@ -50,7 +50,7 @@ if (NOT CMAKE_VERSION VERSION_LESS 2.8.11) set(GUDHI_DIRECTORIES "doc;example;concept;utilities") set(GUDHI_INCLUDE_DIRECTORIES "include/gudhi;include/gudhi_patches") - foreach(GUDHI_MODULE ${GUDHI_MODULES}) + foreach(GUDHI_MODULE ${GUDHI_MODULES_FULL_LIST}) foreach(GUDHI_DIRECTORY ${GUDHI_DIRECTORIES}) # Find files file(GLOB GUDHI_FILES ${CMAKE_SOURCE_DIR}/src/${GUDHI_MODULE}/${GUDHI_DIRECTORY}/*) @@ -85,6 +85,6 @@ if (NOT CMAKE_VERSION VERSION_LESS 2.8.11) endforeach() endforeach(GUDHI_INCLUDE_DIRECTORY ${GUDHI_INCLUDE_DIRECTORIES}) - endforeach(GUDHI_MODULE ${GUDHI_MODULES}) + endforeach(GUDHI_MODULE ${GUDHI_MODULES_FULL_LIST}) endif() diff --git a/src/common/doc/main_page.h b/src/common/doc/main_page.h index 12012ecb..bd4615f5 100644 --- a/src/common/doc/main_page.h +++ b/src/common/doc/main_page.h @@ -152,7 +152,6 @@ </table> \section Toolbox Toolbox - \subsection BottleneckDistanceToolbox Bottleneck distance \image html "perturb_pd.png" "Bottleneck distance is the length of the longest edge" <table border="0"> @@ -468,4 +467,4 @@ make doxygen * @example Witness_complex/example_witness_complex_persistence.cpp * @example Witness_complex/example_witness_complex_sphere.cpp */ -
\ No newline at end of file + |