From 511c3c3d8d059d13616adfc62993a6dd8d65b26f Mon Sep 17 00:00:00 2001 From: cjamin Date: Thu, 30 Jun 2016 13:31:43 +0000 Subject: Doc git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/branches/subsampling_and_spatialsearching@1364 636b058d-ea47-450e-bf9e-a15bfbe3eedb Former-commit-id: 64b1417a243d5e36a37e29ee65182f92809f5e35 --- .../include/gudhi/Spatial_tree_data_structure.h | 50 ++++++++++++++++++---- 1 file changed, 41 insertions(+), 9 deletions(-) (limited to 'src') diff --git a/src/Spatial_searching/include/gudhi/Spatial_tree_data_structure.h b/src/Spatial_searching/include/gudhi/Spatial_tree_data_structure.h index 5153720b..740c7861 100644 --- a/src/Spatial_searching/include/gudhi/Spatial_tree_data_structure.h +++ b/src/Spatial_searching/include/gudhi/Spatial_tree_data_structure.h @@ -44,11 +44,16 @@ namespace spatial_searching { * \ingroup spatial_searching * * \details - * The class Spatial_tree_data_structure represents a tree-based data structure, based on . - * CGAL dD spatial searching data structures. - * It provides a simplified API to perform (approximate) nearest neighbor searches. Contrary to CGAL default behavior, the tree + * The class Spatial_tree_data_structure is a tree-based data structure, based on + * CGAL dD spatial searching data structures. + * It provides a simplified API to perform (approximate) nearest 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 k-nearest neighbor query, where `k` is fixed and the k nearest points are + * computed right away, + * and the incremental nearest neighbor query, where no number of neighbors is provided during the call, and the + * neighbors will be computed incrementally when the iterator on the range is incremented. + * * \tparam K requires a CGAL::Epick_d class, which * can be static if you know the ambiant dimension at compile-time, or dynamic if you don't. @@ -62,6 +67,7 @@ class Spatial_tree_data_structure public: typedef typename Point_container_::value_type Point; typedef K Kernel; + /// Number type used for distances. typedef typename Kernel::FT FT; typedef CGAL::Search_traits< @@ -75,16 +81,22 @@ public: typedef CGAL::Orthogonal_k_neighbor_search K_neighbor_search; typedef typename K_neighbor_search::Tree Tree; typedef typename K_neighbor_search::Distance Distance; - typedef typename K_neighbor_search::iterator KNS_iterator; + /// The range returned by a k-nearest neighbor search. + /// Its value type is `std::pair` 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; typedef CGAL::Orthogonal_incremental_neighbor_search< STraits, Distance, CGAL::Sliding_midpoint, Tree> Incremental_neighbor_search; - typedef typename Incremental_neighbor_search::iterator INS_iterator; + /// The range returned by an incremental nearest neighbor search. + /// Its value type is `std::pair` 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; /// Constructor + /// @param[in] points Const reference to the point container. This container + /// is not copied, so it should not be destroyed or modified afterwards. Spatial_tree_data_structure(Point_container_ const& points) : m_points(points), m_tree(boost::counting_iterator(0), @@ -97,21 +109,29 @@ public: } /// Constructor + /// @param[in] points Const reference to the point container. This container + /// is not copied, so it should not be destroyed or modified afterwards. + /// @param[in] Only_these_points specifies the indices of the points that + /// should be actually inserted into the tree. The other points are ignored. template Spatial_tree_data_structure( Point_container_ const& points, Point_indices_range const& only_these_points) : m_points(points), - m_tree( - only_these_points.begin(), only_these_points.end(), - typename Tree::Splitter(), - STraits((Point*)&(points[0]))) + m_tree( + only_these_points.begin(), only_these_points.end(), + typename Tree::Splitter(), + STraits((Point*)&(points[0]))) { // Build the tree now (we don't want to wait for the first query) m_tree.build(); } /// Constructor + /// @param[in] points Const reference to the point container. This container + /// is not copied, so it should not be destroyed or modified afterwards. + /// @param[in] begin_idx, past_the_end_idx Define the subset of the points that + /// should be actually inserted into the tree. The other points are ignored. Spatial_tree_data_structure( Point_container_ const& points, std::size_t begin_idx, std::size_t past_the_end_idx) @@ -143,6 +163,12 @@ public: m_tree.insert(point_idx); } + /// Search for the k-nearest neighbors from a query point. + /// @param[in] p The query point. + /// @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_ANN(const Point &sp, unsigned int k, @@ -165,6 +191,12 @@ public: return search; } + /// 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. + /// 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_ANN(const Point &sp, FT eps = FT(0)) const { // Initialize the search structure, and search all N points -- cgit v1.2.3