CGAL 6.1.1 - dD Spatial Searching

Loading...
Searching...
No Matches
List of all members
CGAL::K_neighbor_search< Traits, GeneralDistance, Splitter, SpatialTree > Class Template Reference
Reference Manual » Search Classes

`#include <CGAL/K_neighbor_search.h>`

## Definition

template<typename Traits, typename GeneralDistance, typename Splitter, typename SpatialTree>
class CGAL::K_neighbor_search< Traits, GeneralDistance, Splitter, SpatialTree >

The class `K_neighbor_search` implements approximate `k`-nearest and `k`-furthest neighbor searching using standard search on a tree using a general distance class.

The tree may be built with extended or unextended nodes.

Template Parameters

  Traits | must be an implementation of the concept `SearchTraits`, for example `Simple_cartesian<double>`.
  GeneralDistance | must be a model of the concept `GeneralDistance`. If `Traits` is `Search_traits_adapter<Key,PointPropertyMap,BaseTraits>` the default type is `Distance_adapter<Key,PointPropertyMap,Euclidean_distance<BaseTraits> >`, and `Euclidean_distance<Traits>` otherwise.
  Splitter | must be a model of the concept `Splitter`. The default type is `Sliding_midpoint<Traits>`.
  SpatialTree | must be an implementation of the concept `SpatialTree`. The default type is `Kd_tree<Traits, Splitter, Tag_false, Tag_false>`. The third template argument `Tag_false` makes that the tree is built with unextended nodes.

See also
  `CGAL::Orthogonal_k_neighbor_search<Traits, OrthogonalDistance, Splitter, SpatialTree>`

Examples
  Spatial_searching/general_neighbor_searching.cpp.

## Types
typedef Traits::Point_d | Point_d
| Point type.
typedef Traits::FT | FT
| Number type.
typedef GeneralDistance | Distance
| Distance type.
typedef std::pair< Point_d, FT > | Point_with_transformed_distance
| Pair of point and transformed distance.
typedef unspecified_type | iterator
| Bidirectional const iterator with value type `Point_with_distance` for enumerating approximate neighbors.
typedef GeneralDistance::Query_item | Query_item
| Query item type.
typedef SpatialTree | Tree
| The tree type.

## Creation
| K_neighbor_search (const Tree &tree, Query_item q, unsigned int k=1, FT eps=FT(0.0), bool search_nearest=true, GeneralDistance d=GeneralDistance(), bool sorted=true)
| Constructor for searching approximately `k` neighbors of the query item `q` in the points stored in `tree` using distance class `d` and approximation factor `eps`.

## Operations
iterator | begin () const
| Returns a const iterator to the approximate nearest or furthest neighbor.
iterator | end () const
| Returns the appropriate past-the-end const iterator.
std::ostream & | statistics (std::ostream &s)
| Inserts statistics of the search process into the output stream `s`.

## Constructor & Destructor Documentation

## ◆ K_neighbor_search()

template<typename Traits , typename GeneralDistance , typename Splitter , typename SpatialTree >

CGAL::K_neighbor_search< Traits, GeneralDistance, Splitter, SpatialTree >::K_neighbor_search | ( | const Tree & | tree,
|  | Query_item | q,
|  | unsigned int | k = `1`,
|  | FT | eps = `FT(0.0)`,
|  | bool | search_nearest = `true`,
|  | GeneralDistance | d = `GeneralDistance()`,
|  | bool | sorted = `true`
| ) |  |

Constructor for searching approximately `k` neighbors of the query item `q` in the points stored in `tree` using distance class `d` and approximation factor `eps`.

`sorted` indicates if the computed sequence of `k`-nearest neighbors needs to be sorted.