\( \newcommand{\E}{\mathrm{E}} \) \( \newcommand{\A}{\mathrm{A}} \) \( \newcommand{\R}{\mathrm{R}} \) \( \newcommand{\N}{\mathrm{N}} \) \( \newcommand{\Q}{\mathrm{Q}} \) \( \newcommand{\Z}{\mathrm{Z}} \) \( \def\ccSum #1#2#3{ \sum_{#1}^{#2}{#3} } \def\ccProd #1#2#3{ \sum_{#1}^{#2}{#3} }\)
CGAL 4.14 - dD Spatial Searching
CGAL::K_neighbor_search< Traits, GeneralDistance, Splitter, SpatialTree > Class Template Reference

#include <CGAL/K_neighbor_search.h>

Definition

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
Traitsmust be an implementation of the concept SearchTraits, for example Simple_cartesian<double>.
Splittermust 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.
SpatialTreemust be an implementation of the concept SpatialTree. The default type is Kd_tree<Traits, Splitter, Tag_false>. The 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, FTPoint_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. More...
 

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.