Searching...
No Matches
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_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.

## ◆ 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.

## ◆ 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: