Gudhi::spatial_searching::Kd_tree_search< Search_traits, Point_range > Class Template Reference

Spatial tree data structure to perform (approximate) nearest and furthest neighbor search. More...

#include <gudhi/Kd_tree_search.h>

Public Types

typedef Search_traits Traits
 The Traits.
 
typedef Traits::FT FT
 Number type used for distances.
 
typedef Point_range::value_type Point
 The point type.
 
typedef K_neighbor_search KNS_range
 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 Incremental_neighbor_search INS_range
 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.
 

Public Member Functions

 Kd_tree_search (Point_range const &points)
 Constructor. More...
 
template<typename Point_indices_range >
 Kd_tree_search (Point_range const &points, Point_indices_range const &only_these_points)
 Constructor. More...
 
 Kd_tree_search (Point_range const &points, std::size_t begin_idx, std::size_t past_the_end_idx)
 Constructor. More...
 
KNS_range k_nearest_neighbors (Point const &p, unsigned int k, bool sorted=true, FT eps=FT(0)) const
 Search for the k-nearest neighbors from a query point. More...
 
INS_range incremental_nearest_neighbors (Point const &p, FT eps=FT(0)) const
 Search incrementally for the nearest neighbors from a query point. More...
 
KNS_range k_furthest_neighbors (Point const &p, unsigned int k, bool sorted=true, FT eps=FT(0)) const
 Search for the k-furthest points from a query point. More...
 
INS_range incremental_furthest_neighbors (Point const &p, FT eps=FT(0)) const
 Search incrementally for the furthest neighbors from a query point. More...
 
template<typename OutputIterator >
void all_near_neighbors (Point const &p, FT const &radius, OutputIterator it, FT eps=FT(0)) const
 Search for all the neighbors in a ball. More...
 
template<typename OutputIterator >
void all_near_neighbors2 (Point const &p, FT const &sq_radius_min, FT const &sq_radius_max, OutputIterator it) const
 Search for all the neighbors in a ball. This is similar to all_near_neighbors but takes directly the square of the minimum distance below which points must be considered neighbors and square of the maximum distance above which they cannot be. More...
 

Detailed Description

template<typename Search_traits, typename Point_range>
class Gudhi::spatial_searching::Kd_tree_search< Search_traits, Point_range >

Spatial tree data structure to perform (approximate) nearest and furthest neighbor search.

The class Kd_tree_search is a tree-based data structure, based on CGAL dD spatial searching data structures. 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 k-nearest or k-furthest neighbor query, where k is fixed and the k nearest or furthest points are computed right away, and the incremental nearest or furthest neighbor query, 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.

Template Parameters
Search_traitsmust be a model of the SearchTraits concept, such as the CGAL::Epick_d class, which can be static if you know the ambiant dimension at compile-time, or dynamic if you don't.
Point_rangeis the type of the range that provides the points. It must be a range whose iterator type is a RandomAccessIterator.

Constructor & Destructor Documentation

◆ Kd_tree_search() [1/3]

template<typename Search_traits , typename Point_range >
Gudhi::spatial_searching::Kd_tree_search< Search_traits, Point_range >::Kd_tree_search ( Point_range const &  points)
inline

Constructor.

Parameters
[in]pointsConst reference to the point range. This range is not copied, so it should not be destroyed or modified afterwards.

◆ Kd_tree_search() [2/3]

template<typename Search_traits , typename Point_range >
template<typename Point_indices_range >
Gudhi::spatial_searching::Kd_tree_search< Search_traits, Point_range >::Kd_tree_search ( Point_range const &  points,
Point_indices_range const &  only_these_points 
)
inline

Constructor.

Parameters
[in]pointsConst reference to the point range. This range is not copied, so it should not be destroyed or modified afterwards.
[in]only_these_pointsSpecifies the indices of the points that should be actually inserted into the tree. The other points are ignored.

◆ Kd_tree_search() [3/3]

template<typename Search_traits , typename Point_range >
Gudhi::spatial_searching::Kd_tree_search< Search_traits, Point_range >::Kd_tree_search ( Point_range const &  points,
std::size_t  begin_idx,
std::size_t  past_the_end_idx 
)
inline

Constructor.

Parameters
[in]pointsConst reference to the point range. This range is not copied, so it should not be destroyed or modified afterwards.
[in]begin_idx,past_the_end_idxDefine the subset of the points that should be actually inserted into the tree. The other points are ignored.

Member Function Documentation

◆ all_near_neighbors()

template<typename Search_traits , typename Point_range >
template<typename OutputIterator >
void Gudhi::spatial_searching::Kd_tree_search< Search_traits, Point_range >::all_near_neighbors ( Point const &  p,
FT const &  radius,
OutputIterator  it,
FT  eps = FT(0) 
) const
inline

Search for all the neighbors in a ball.

Parameters
[in]pThe query point.
[in]radiusThe search radius
[out]itThe points that lie inside the sphere of center p and radius radius. Note: it is used this way: *it++ = each_point.
[in]epsApproximation factor.

◆ all_near_neighbors2()

template<typename Search_traits , typename Point_range >
template<typename OutputIterator >
void Gudhi::spatial_searching::Kd_tree_search< Search_traits, Point_range >::all_near_neighbors2 ( Point const &  p,
FT const &  sq_radius_min,
FT const &  sq_radius_max,
OutputIterator  it 
) const
inline

Search for all the neighbors in a ball. This is similar to all_near_neighbors but takes directly the square of the minimum distance below which points must be considered neighbors and square of the maximum distance above which they cannot be.

Parameters
[in]pThe query point.
[in]sq_radius_minThe square of the minimum search radius
[in]sq_radius_maxThe square of the maximum search radius
[out]itThe points that lie inside the sphere of center p and squared radius sq_radius. Note: it is used this way: *it++ = each_point.

◆ incremental_furthest_neighbors()

template<typename Search_traits , typename Point_range >
INS_range Gudhi::spatial_searching::Kd_tree_search< Search_traits, Point_range >::incremental_furthest_neighbors ( Point const &  p,
FT  eps = FT(0) 
) const
inline

Search incrementally for the furthest neighbors from a query point.

Parameters
[in]pThe query point.
[in]epsApproximation factor.
Returns
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.

◆ incremental_nearest_neighbors()

template<typename Search_traits , typename Point_range >
INS_range Gudhi::spatial_searching::Kd_tree_search< Search_traits, Point_range >::incremental_nearest_neighbors ( Point const &  p,
FT  eps = FT(0) 
) const
inline

Search incrementally for the nearest neighbors from a query point.

Parameters
[in]pThe query point.
[in]epsApproximation factor.
Returns
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.

◆ k_furthest_neighbors()

template<typename Search_traits , typename Point_range >
KNS_range Gudhi::spatial_searching::Kd_tree_search< Search_traits, Point_range >::k_furthest_neighbors ( Point const &  p,
unsigned int  k,
bool  sorted = true,
FT  eps = FT(0) 
) const
inline

Search for the k-furthest points from a query point.

Parameters
[in]pThe query point.
[in]kNumber of furthest points to search.
[in]sortedIndicates if the computed sequence of k-furthest neighbors needs to be sorted.
[in]epsApproximation factor.
Returns
A range (whose value_type is std::size_t) containing the k-furthest neighbors.

◆ k_nearest_neighbors()

template<typename Search_traits , typename Point_range >
KNS_range Gudhi::spatial_searching::Kd_tree_search< Search_traits, Point_range >::k_nearest_neighbors ( Point const &  p,
unsigned int  k,
bool  sorted = true,
FT  eps = FT(0) 
) const
inline

Search for the k-nearest neighbors from a query point.

Parameters
[in]pThe query point.
[in]kNumber of nearest points to search.
[in]sortedIndicates if the computed sequence of k-nearest neighbors needs to be sorted.
[in]epsApproximation factor.
Returns
A range (whose value_type is std::size_t) containing the k-nearest neighbors.

The documentation for this class was generated from the following file: