Loading...
Searching...
No Matches
Gudhi::spatial_searching::Kd_tree_search< Search_traits, Point_range > Class Template Reference
Spatial_searching

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.
template<typename Point_indices_range>
| Kd_tree_search (Point_range const &points, Point_indices_range const &only_these_points)
| Constructor.
| Kd_tree_search (Point_range const &points, std::size_t begin_idx, std::size_t past_the_end_idx)
| Constructor.
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.
INS_range | incremental_nearest_neighbors (Point const &p, FT eps=FT(0)) const
| Search incrementally for the nearest neighbors from a query point.
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.
INS_range | incremental_furthest_neighbors (Point const &p, FT eps=FT(0)) const
| Search incrementally for the furthest neighbors from a query point.
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.
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.

## 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_traits | must 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_range | is the type of the range that provides the points. It must be a range whose iterator type is a RandomAccessIterator.

Examples
  example_spatial_searching.cpp.

## 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] | points | Const 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] | points | Const reference to the point range. This range is not copied, so it should not be destroyed or modified afterwards.
  [in] | only_these_points | Specifies 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] | points | Const 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_idx | Define 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] | p | The query point.
  [in] | radius | The search radius
  [out] | it | The points that lie inside the sphere of center p and radius radius. Note: it is used this way: *it++ = each_point.
  [in] | eps | Approximation 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] | p | The query point.
  [in] | sq_radius_min | The square of the minimum search radius
  [in] | sq_radius_max | The square of the maximum search radius
  [out] | it | The 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] | p | The query point.
  [in] | eps | Approximation 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] | p | The query point.
  [in] | eps | Approximation 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] | p | The query point.
  [in] | k | Number of furthest points to search.
  [in] | sorted | Indicates if the computed sequence of k-furthest neighbors needs to be sorted.
  [in] | eps | Approximation 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] | p | The query point.
  [in] | k | Number of nearest points to search.
  [in] | sorted | Indicates if the computed sequence of k-nearest neighbors needs to be sorted.
  [in] | eps | Approximation 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:

- include/gudhi/Kd_tree_search.h