summaryrefslogtreecommitdiff
path: root/src/Spatial_searching
diff options
context:
space:
mode:
Diffstat (limited to 'src/Spatial_searching')
-rw-r--r--src/Spatial_searching/doc/Intro_spatial_searching.h4
-rw-r--r--src/Spatial_searching/example/CMakeLists.txt14
-rw-r--r--src/Spatial_searching/example/example_spatial_searching.cpp34
-rw-r--r--src/Spatial_searching/include/gudhi/Kd_tree_search.h88
-rw-r--r--src/Spatial_searching/test/CMakeLists.txt15
-rw-r--r--src/Spatial_searching/test/test_Kd_tree_search.cpp56
6 files changed, 92 insertions, 119 deletions
diff --git a/src/Spatial_searching/doc/Intro_spatial_searching.h b/src/Spatial_searching/doc/Intro_spatial_searching.h
index 2406c931..23705378 100644
--- a/src/Spatial_searching/doc/Intro_spatial_searching.h
+++ b/src/Spatial_searching/doc/Intro_spatial_searching.h
@@ -39,6 +39,10 @@ namespace spatial_searching {
* <a target="_blank" href="http://doc.cgal.org/latest/Spatial_searching/index.html">CGAL dD spatial searching algorithms</a>.
* It provides a simplified API to perform (approximate) neighbor searches. Contrary to CGAL default behavior, the tree
* does not store the points themselves, but stores indices.
+ *
+ * For more details about the data structure or the algorithms, or for more advanced usages, reading
+ * <a target="_blank" href="http://doc.cgal.org/latest/Spatial_searching/index.html">CGAL documentation</a>
+ * is highly recommended.
*
* \section spatial_searching_examples Example
*
diff --git a/src/Spatial_searching/example/CMakeLists.txt b/src/Spatial_searching/example/CMakeLists.txt
index 3c3970d8..e73b201c 100644
--- a/src/Spatial_searching/example/CMakeLists.txt
+++ b/src/Spatial_searching/example/CMakeLists.txt
@@ -2,18 +2,12 @@ cmake_minimum_required(VERSION 2.6)
project(Spatial_searching_examples)
if(CGAL_FOUND)
- if (NOT CGAL_VERSION VERSION_LESS 4.8.1)
- message(STATUS "CGAL version: ${CGAL_VERSION}.")
-
+ if (NOT CGAL_VERSION VERSION_LESS 4.9.0)
if (EIGEN3_FOUND)
add_executable( Spatial_searching_example_spatial_searching example_spatial_searching.cpp )
target_link_libraries(Spatial_searching_example_spatial_searching ${CGAL_LIBRARY})
- else()
- message(WARNING "Eigen3 not found. Version 3.1.0 is required for the Tangential_complex examples.")
+ add_test(Spatial_searching_example_spatial_searching
+ ${CMAKE_CURRENT_BINARY_DIR}/Spatial_searching_example_spatial_searching)
endif()
- else()
- message(WARNING "CGAL version: ${CGAL_VERSION} is too old to compile Spatial_searching examples. Version 4.8.1 is required.")
- endif ()
-else()
- message(WARNING "CGAL not found. It is required for the Spatial_searching examples.")
+ endif()
endif()
diff --git a/src/Spatial_searching/example/example_spatial_searching.cpp b/src/Spatial_searching/example/example_spatial_searching.cpp
index 7b48d055..14b324ae 100644
--- a/src/Spatial_searching/example/example_spatial_searching.cpp
+++ b/src/Spatial_searching/example/example_spatial_searching.cpp
@@ -7,12 +7,10 @@
namespace gss = Gudhi::spatial_searching;
-int main (void)
-{
- typedef CGAL::Epick_d<CGAL::Dimension_tag<4> > K;
- typedef typename K::FT FT;
- typedef typename K::Point_d Point;
- typedef std::vector<Point> Points;
+int main(void) {
+ typedef CGAL::Epick_d<CGAL::Dimension_tag<4> > K;
+ typedef typename K::Point_d Point;
+ typedef std::vector<Point> Points;
typedef gss::Kd_tree_search<K, Points> Points_ds;
@@ -20,35 +18,35 @@ int main (void)
Points points;
for (int i = 0; i < 500; ++i)
- points.push_back(Point(rd.get_double(-1.,1), rd.get_double(-1.,1), rd.get_double(-1.,1), rd.get_double(-1.,1)));
+ points.push_back(Point(rd.get_double(-1., 1), rd.get_double(-1., 1), rd.get_double(-1., 1), rd.get_double(-1., 1)));
Points_ds points_ds(points);
// 10-nearest neighbor query
std::cout << "10 nearest neighbors from points[20]:\n";
- auto kns_range = points_ds.query_k_nearest_neighbors(points[20], 10, true);
- for (auto const& nghb : kns_range)
+ auto knn_range = points_ds.query_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 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)
+ auto inn_range = points_ds.query_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 kfs_range = points_ds.query_k_farthest_neighbors(points[20], 10, true);
- for (auto const& nghb : kfs_range)
+ auto kfn_range = points_ds.query_k_farthest_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 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)
+ auto ifn_range = points_ds.query_incremental_farthest_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";
-
+
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 ff630e9d..6728d56e 100644
--- a/src/Spatial_searching/include/gudhi/Kd_tree_search.h
+++ b/src/Spatial_searching/include/gudhi/Kd_tree_search.h
@@ -20,8 +20,8 @@
* along with this program. If not, see <http://www.gnu.org/licenses/>.
*/
-#ifndef GUDHI_SPATIAL_TREE_DS_H_
-#define GUDHI_SPATIAL_TREE_DS_H_
+#ifndef KD_TREE_SEARCH_H_
+#define KD_TREE_SEARCH_H_
#include <CGAL/Orthogonal_k_neighbor_search.h>
#include <CGAL/Orthogonal_incremental_neighbor_search.h>
@@ -41,22 +41,22 @@ 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 neighbor search.
+ * \brief Spatial tree data structure to perform (approximate) nearest and farthest 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 neighbor searches. Contrary to CGAL default behavior, the tree
+ * It provides a simplified API to perform (approximate) nearest and farthest 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 neighbor query</i>, where <i>k</i> is fixed and the <i>k</i> nearest points are
- * computed right away,
- * and the <i>incremental nearest 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-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
* neighbors will be computed incrementally when the iterator on the range is incremented.
*
- * \tparam K must be a model of the <a target="_blank"
+ * \tparam Search_traits must be a model of the <a target="_blank"
* href="http://doc.cgal.org/latest/Spatial_searching/classSearchTraits.html">SearchTraits</a>
* concept, such as the <a target="_blank"
* href="http://doc.cgal.org/latest/Kernel_d/classCGAL_1_1Epick__d.html">CGAL::Epick_d</a> class, which
@@ -64,35 +64,34 @@ namespace spatial_searching {
* \tparam Point_range is the type of the range that provides the points.
* It must be a range whose iterator type is a `RandomAccessIterator`.
*/
-template <typename K, typename Point_range>
-class Kd_tree_search
-{
+template <typename Search_traits, typename Point_range>
+class Kd_tree_search {
typedef boost::iterator_property_map<
typename Point_range::const_iterator,
CGAL::Identity_property_map<std::ptrdiff_t> > Point_property_map;
-public:
- /// The kernel.
- typedef K Kernel;
+ public:
+ /// The Traits.
+ typedef Search_traits Traits;
/// Number type used for distances.
- typedef typename Kernel::FT FT;
+ typedef typename Traits::FT FT;
/// The point type.
typedef typename Point_range::value_type Point;
typedef CGAL::Search_traits<
FT, Point,
- typename Kernel::Cartesian_const_iterator_d,
- typename Kernel::Construct_cartesian_const_iterator_d> Traits_base;
-
+ typename Traits::Cartesian_const_iterator_d,
+ typename Traits::Construct_cartesian_const_iterator_d> Traits_base;
+
typedef CGAL::Search_traits_adapter<
std::ptrdiff_t,
Point_property_map,
Traits_base> STraits;
-
+
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 neighbor search.
+ /// \brief The range returned by a k-nearest or k-farthest 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;
@@ -100,7 +99,7 @@ public:
typedef CGAL::Orthogonal_incremental_neighbor_search<
STraits, Distance, CGAL::Sliding_midpoint<STraits>, Tree>
Incremental_neighbor_search;
- /// \brief The range returned by an incremental nearest neighbor search.
+ /// \brief The range returned by an incremental nearest or farthest 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;
@@ -113,8 +112,7 @@ public:
m_tree(boost::counting_iterator<std::ptrdiff_t>(0),
boost::counting_iterator<std::ptrdiff_t>(points.size()),
typename Tree::Splitter(),
- STraits(std::begin(points)) )
- {
+ STraits(std::begin(points))) {
// Build the tree now (we don't want to wait for the first query)
m_tree.build();
}
@@ -132,8 +130,7 @@ public:
m_tree(
only_these_points.begin(), only_these_points.end(),
typename Tree::Splitter(),
- STraits(std::begin(points)))
- {
+ STraits(std::begin(points))) {
// Build the tree now (we don't want to wait for the first query)
m_tree.build();
}
@@ -151,16 +148,14 @@ public:
boost::counting_iterator<std::ptrdiff_t>(begin_idx),
boost::counting_iterator<std::ptrdiff_t>(past_the_end_idx),
typename Tree::Splitter(),
- STraits(std::begin(points)) )
- {
+ STraits(std::begin(points))) {
// Build the tree now (we don't want to wait for the first query)
m_tree.build();
}
// Be careful, this function invalidates the tree,
// which will be recomputed at the next query
- void insert(std::ptrdiff_t point_idx)
- {
+ void insert(std::ptrdiff_t point_idx) {
m_tree.insert(point_idx);
}
@@ -174,8 +169,7 @@ public:
Point &p,
unsigned int k,
bool sorted = true,
- FT eps = FT(0)) const
- {
+ 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
@@ -185,9 +179,8 @@ public:
k,
eps,
true,
- CGAL::Distance_adapter<std::ptrdiff_t,Point_property_map,CGAL::Euclidean_distance<Traits_base> >(
- std::begin(m_points)),
- sorted);
+ CGAL::Distance_adapter<std::ptrdiff_t, Point_property_map, CGAL::Euclidean_distance<Traits_base> >(
+ std::begin(m_points)), sorted);
return search;
}
@@ -195,11 +188,10 @@ public:
/// \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 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(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
@@ -224,8 +216,7 @@ public:
Point &p,
unsigned int k,
bool sorted = true,
- FT eps = FT(0)) const
- {
+ 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
@@ -235,9 +226,8 @@ public:
k,
eps,
false,
- CGAL::Distance_adapter<std::ptrdiff_t,Point_property_map,CGAL::Euclidean_distance<Traits_base> >(
- std::begin(m_points)),
- sorted);
+ CGAL::Distance_adapter<std::ptrdiff_t, Point_property_map, CGAL::Euclidean_distance<Traits_base> >(
+ std::begin(m_points)), sorted);
return search;
}
@@ -245,11 +235,10 @@ public:
/// \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 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(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
@@ -264,13 +253,12 @@ public:
return search;
}
-
-private:
+ private:
Point_range const& m_points;
Tree m_tree;
};
-} // namespace spatial_searching
-} // namespace Gudhi
+} // namespace spatial_searching
+} // namespace Gudhi
-#endif // GUDHI_SPATIAL_TREE_DS_H_
+#endif // KD_TREE_SEARCH_H_
diff --git a/src/Spatial_searching/test/CMakeLists.txt b/src/Spatial_searching/test/CMakeLists.txt
index 0f2c5ae4..7f443b79 100644
--- a/src/Spatial_searching/test/CMakeLists.txt
+++ b/src/Spatial_searching/test/CMakeLists.txt
@@ -11,20 +11,15 @@ if (GPROF_PATH)
endif()
if(CGAL_FOUND)
- if (NOT CGAL_VERSION VERSION_LESS 4.8.1)
- message(STATUS "CGAL version: ${CGAL_VERSION}.")
-
+ if (NOT CGAL_VERSION VERSION_LESS 4.9.0)
if (EIGEN3_FOUND)
-
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})
- else()
- message(WARNING "Eigen3 not found. Version 3.1.0 is required for the Spatial_searching tests.")
+
+ add_test(Spatial_searching_test_Kd_tree_search ${CMAKE_CURRENT_BINARY_DIR}/Spatial_searching_test_Kd_tree_search
+ # XML format for Jenkins xUnit plugin
+ --log_format=XML --log_sink=${CMAKE_SOURCE_DIR}/Spatial_searching_UT.xml --log_level=test_suite --report_level=no)
endif()
- else()
- message(WARNING "CGAL version: ${CGAL_VERSION} is too old to compile Subsampling tests. Version 4.8.1 is required.")
endif ()
-else()
- message(WARNING "CGAL not found. It is required for the Spatial_searching tests.")
endif()
diff --git a/src/Spatial_searching/test/test_Kd_tree_search.cpp b/src/Spatial_searching/test/test_Kd_tree_search.cpp
index 6f99b288..0ef22023 100644
--- a/src/Spatial_searching/test/test_Kd_tree_search.cpp
+++ b/src/Spatial_searching/test/test_Kd_tree_search.cpp
@@ -4,7 +4,7 @@
*
* Author(s): Clement Jamin
*
- * Copyright (C) 2016 INRIA Sophia-Antipolis (France)
+ * Copyright (C) 2016 INRIA
*
* This program is free software: you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
@@ -29,38 +29,35 @@
#include <CGAL/Epick_d.h>
#include <CGAL/Random.h>
-#include <array>
#include <vector>
-BOOST_AUTO_TEST_CASE(test_Kd_tree_search)
-{
- typedef CGAL::Epick_d<CGAL::Dimension_tag<4> > K;
- typedef K::FT FT;
- typedef K::Point_d Point;
- typedef std::vector<Point> Points;
+BOOST_AUTO_TEST_CASE(test_Kd_tree_search) {
+ typedef CGAL::Epick_d<CGAL::Dimension_tag<4> > K;
+ typedef K::FT FT;
+ typedef K::Point_d Point;
+ typedef std::vector<Point> Points;
typedef Gudhi::spatial_searching::Kd_tree_search<
- K, Points> Points_ds;
-
+ K, Points> Points_ds;
+
CGAL::Random rd;
Points points;
- for (int i = 0 ; i < 500 ; ++i)
- points.push_back(Point(rd.get_double(-1.,1), rd.get_double(-1.,1), rd.get_double(-1.,1), rd.get_double(-1.,1)));
+ for (int i = 0; i < 500; ++i)
+ points.push_back(Point(rd.get_double(-1., 1), rd.get_double(-1., 1), rd.get_double(-1., 1), rd.get_double(-1., 1)));
Points_ds points_ds(points);
// Test query_k_nearest_neighbors
std::size_t closest_pt_index =
- points_ds.query_k_nearest_neighbors(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_k_nearest_neighbors(points[20], 10, true);
std::vector<std::size_t> knn_result;
FT last_dist = -1.;
- for (auto const& nghb : kns_range)
- {
+ for (auto const& nghb : kns_range) {
BOOST_CHECK(nghb.second > last_dist);
knn_result.push_back(nghb.second);
last_dist = nghb.second;
@@ -68,17 +65,16 @@ BOOST_AUTO_TEST_CASE(test_Kd_tree_search)
// Test query_incremental_nearest_neighbors
closest_pt_index =
- points_ds.query_incremental_nearest_neighbors(points[10]).begin()->first;
+ points_ds.query_incremental_nearest_neighbors(points[10]).begin()->first;
BOOST_CHECK(closest_pt_index == 10);
- auto ins_range = points_ds.query_incremental_nearest_neighbors(points[20]);
+ auto inn_range = points_ds.query_incremental_nearest_neighbors(points[20]);
std::vector<std::size_t> inn_result;
last_dist = -1.;
- auto ins_it = ins_range.begin();
- for (int i = 0 ; i < 10 ; ++ins_it, ++i)
- {
- auto const& nghb = *ins_it;
+ auto inn_it = inn_range.begin();
+ for (int i = 0; i < 10; ++inn_it, ++i) {
+ auto const& nghb = *inn_it;
BOOST_CHECK(nghb.second > last_dist);
inn_result.push_back(nghb.second);
last_dist = nghb.second;
@@ -88,26 +84,24 @@ BOOST_AUTO_TEST_CASE(test_Kd_tree_search)
BOOST_CHECK(knn_result == inn_result);
// Test query_k_farthest_neighbors
- auto kfs_range = points_ds.query_k_farthest_neighbors(points[20], 10, true);
+ auto kfn_range = points_ds.query_k_farthest_neighbors(points[20], 10, true);
std::vector<std::size_t> kfn_result;
- last_dist = kfs_range.begin()->second;
- for (auto const& nghb : kfs_range)
- {
+ last_dist = kfn_range.begin()->second;
+ for (auto const& nghb : kfn_range) {
BOOST_CHECK(nghb.second <= last_dist);
kfn_result.push_back(nghb.second);
last_dist = nghb.second;
}
// Test query_k_farthest_neighbors
- auto ifs_range = points_ds.query_incremental_farthest_neighbors(points[20]);
+ auto ifn_range = points_ds.query_incremental_farthest_neighbors(points[20]);
std::vector<std::size_t> ifn_result;
- last_dist = ifs_range.begin()->second;
- auto ifs_it = ifs_range.begin();
- for (int i = 0; i < 10; ++ifs_it, ++i)
- {
- auto const& nghb = *ifs_it;
+ last_dist = ifn_range.begin()->second;
+ auto ifn_it = ifn_range.begin();
+ for (int i = 0; i < 10; ++ifn_it, ++i) {
+ auto const& nghb = *ifn_it;
BOOST_CHECK(nghb.second <= last_dist);
ifn_result.push_back(nghb.second);
last_dist = nghb.second;
generated by cgit v1.2.3 (git 2.39.1) at 2024-07-19 22:31:38 +0000