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.

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

Public Types

Public Member Functions

Detailed Description

Constructor & Destructor Documentation

◆ Kd_tree_search() [1/3]

◆ Kd_tree_search() [2/3]

◆ Kd_tree_search() [3/3]

Member Function Documentation

◆ all_near_neighbors()

◆ all_near_neighbors2()

◆ incremental_furthest_neighbors()

◆ incremental_nearest_neighbors()

◆ k_furthest_neighbors()

◆ k_nearest_neighbors()