Spatial tree data structure to perform (approximate) nearest and furthest neighbor search. More...
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 knearest or kfurthest 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 knearest 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 kfurthest 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...  
Spatial tree data structure to perform (approximate) nearest and furthest neighbor search.
The class Kd_tree_search is a treebased 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 knearest or kfurthest 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.
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 compiletime, 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 . 

inline 
Constructor.
[in]  points  Const reference to the point range. This range is not copied, so it should not be destroyed or modified afterwards. 

inline 
Constructor.
[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. 

inline 
Constructor.
[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. 

inline 
Search for all the neighbors in a ball.
[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. 

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.
[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 . 

inline 
Search incrementally for the furthest neighbors from a query point.
[in]  p  The query point. 
[in]  eps  Approximation factor. 
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.

inline 
Search incrementally for the nearest neighbors from a query point.
[in]  p  The query point. 
[in]  eps  Approximation factor. 
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.

inline 
Search for the kfurthest points from a query point.
[in]  p  The query point. 
[in]  k  Number of furthest points to search. 
[in]  sorted  Indicates if the computed sequence of kfurthest neighbors needs to be sorted. 
[in]  eps  Approximation factor. 
value_type
is std::size_t
) containing the kfurthest neighbors.

inline 
Search for the knearest neighbors from a query point.
[in]  p  The query point. 
[in]  k  Number of nearest points to search. 
[in]  sorted  Indicates if the computed sequence of knearest neighbors needs to be sorted. 
[in]  eps  Approximation factor. 
value_type
is std::size_t
) containing the knearest neighbors.