diff options
author | cjamin <cjamin@636b058d-ea47-450e-bf9e-a15bfbe3eedb> | 2016-06-30 13:31:43 +0000 |
---|---|---|
committer | cjamin <cjamin@636b058d-ea47-450e-bf9e-a15bfbe3eedb> | 2016-06-30 13:31:43 +0000 |
commit | 511c3c3d8d059d13616adfc62993a6dd8d65b26f (patch) | |
tree | 1ea3ffaa75f009d1e40eb240e7cac8e6d592b4ef /src/Spatial_searching/include/gudhi/Spatial_tree_data_structure.h | |
parent | dfc61b827ae2aa7f99e2ae8401f19f6f0d219af3 (diff) |
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
Diffstat (limited to 'src/Spatial_searching/include/gudhi/Spatial_tree_data_structure.h')
-rw-r--r-- | src/Spatial_searching/include/gudhi/Spatial_tree_data_structure.h | 50 |
1 files changed, 41 insertions, 9 deletions
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 . - * <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 + * The class Spatial_tree_data_structure 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 * does not store the points themselves, but stores indices. * + * There are two types of queries: the <i>k-nearest neighbor query</i>, where `k` is fixed and the k nearest points are + * computed right away, + * and the <i>incremental nearest neighbor query</i>, 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 <a target="_blank" * href="http://doc.cgal.org/latest/Kernel_d/classCGAL_1_1Epick__d.html">CGAL::Epick_d</a> 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<STraits> 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<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; typedef CGAL::Orthogonal_incremental_neighbor_search< STraits, Distance, CGAL::Sliding_midpoint<STraits>, 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<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; /// 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<std::ptrdiff_t>(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 <typename Point_indices_range> 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 |