\( \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.4 - dD Spatial Searching
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Groups Pages
List of all members
CGAL::Kd_tree< Traits, Splitter, UseExtendedNode > Class Template Reference
Search Classes

#include <CGAL/Kd_tree.h>

Definition

The class Kd_tree defines a k-d tree.

Parameters

Expects for the first template argument a model of the concept SearchTraits, for example Search_traits_2<Simple_cartesian<double> >.

Expects for the second template argument a model for the concept Splitter. It defaults to Sliding_midpoint<Traits>.

Expects for the third template argument Tag_true, if the tree shall be built with extended nodes, and Tag_false otherwise.

See Also
CGAL::Kd_tree_node<Traits>
CGAL::Search_traits_2<Kernel>
CGAL::Search_traits_3<Kernel>
CGAL::Search_traits<FT_,Point,CartesianIterator,ConstructCartesianIterator>
Examples:
Spatial_searching/circular_query.cpp, Spatial_searching/fuzzy_range_query.cpp, Spatial_searching/iso_rectangle_2_query.cpp, and Spatial_searching/searching_with_circular_query.cpp.

Types

typedef Traits::Point_d Point_d
 Point class. More...
 
typedef Traits::FT FT
 Number type. More...
 
typedef unspecified_type Splitter
 Splitter type. More...
 
typedef unspecified_type iterator
 Bidirectional const iterator with value type Point_d that allows to enumerate all points in the tree. More...
 
typedef unspecified_type Node_handle
 A handle with value type Kd_tree_node<Traits,Splitter>. More...
 
typedef unspecified_type Node_const_handle
 A const handle with value type Kd_tree_node<Traits,Splitter>. More...
 
typedef unspecified_type Point_d_iterator
 Random access const iterator with value type const Point_d*. More...
 
typedef unspecified_type size_type
 A type that counts the number of elements in a k-d tree. More...
 

Creation

 Kd_tree (Splitter s=Splitter(), Traits t=Traits())
 Constructs an empty k-d tree. More...
 
template<class InputIterator >
 Kd_tree (InputIterator first, InputIterator beyond, Splitter s=Splitter(), Traits t=Traits())
 Constructs a k-d tree on the elements from the sequence [first, beyond) using the splitting rule implemented by s. More...
 

Operations

void insert (Point_d p)
 Inserts the point p in the k-d tree. More...
 
template<class InputIterator >
void insert (InputIterator first, InputIterator beyond)
 Inserts the elements from the sequence [first, beyond) in the k-d tree. More...
 
template<class OutputIterator , class FuzzyQueryItem >
OutputIterator search (OutputIterator it, FuzzyQueryItem q) const
 Reports the points that are approximately contained by q. More...
 
iterator begin () const
 Returns a const iterator to the first point in the tree. More...
 
iterator end () const
 Returns the appropriate past-the-end const iterator. More...
 
void clear ()
 Removes all points from the k-d tree. More...
 
size_type size () const
 Returns the number of points that are stored in the tree. More...
 
Traits traits () const
 return the instance of the traits used to construct the tree. More...
 
Node_handle root ()
 Returns a handle to the root node of the tree. More...
 
Node_const_handle root () const
 Returns a const handle to the root node of the tree. More...
 
const Kd_tree_rectangle< FT > & bounding_box () const
 Returns a const reference to the bounding box of the root node of the tree. More...
 
std::ostream & statistics (std::ostream &s) const
 Inserts statistics of the tree into the output stream s. More...
 

Member Typedef Documentation

template<typename Traits , typename Splitter , typename UseExtendedNode >
typedef Traits::FT CGAL::Kd_tree< Traits, Splitter, UseExtendedNode >::FT

Number type.

template<typename Traits , typename Splitter , typename UseExtendedNode >
typedef unspecified_type CGAL::Kd_tree< Traits, Splitter, UseExtendedNode >::iterator

Bidirectional const iterator with value type Point_d that allows to enumerate all points in the tree.

template<typename Traits , typename Splitter , typename UseExtendedNode >
typedef unspecified_type CGAL::Kd_tree< Traits, Splitter, UseExtendedNode >::Node_const_handle

A const handle with value type Kd_tree_node<Traits,Splitter>.

template<typename Traits , typename Splitter , typename UseExtendedNode >
typedef unspecified_type CGAL::Kd_tree< Traits, Splitter, UseExtendedNode >::Node_handle

A handle with value type Kd_tree_node<Traits,Splitter>.

template<typename Traits , typename Splitter , typename UseExtendedNode >
typedef Traits::Point_d CGAL::Kd_tree< Traits, Splitter, UseExtendedNode >::Point_d

Point class.

template<typename Traits , typename Splitter , typename UseExtendedNode >
typedef unspecified_type CGAL::Kd_tree< Traits, Splitter, UseExtendedNode >::Point_d_iterator

Random access const iterator with value type const Point_d*.

template<typename Traits , typename Splitter , typename UseExtendedNode >
typedef unspecified_type CGAL::Kd_tree< Traits, Splitter, UseExtendedNode >::size_type

A type that counts the number of elements in a k-d tree.

template<typename Traits , typename Splitter , typename UseExtendedNode >
typedef unspecified_type CGAL::Kd_tree< Traits, Splitter, UseExtendedNode >::Splitter

Splitter type.

Constructor & Destructor Documentation

template<typename Traits , typename Splitter , typename UseExtendedNode >
CGAL::Kd_tree< Traits, Splitter, UseExtendedNode >::Kd_tree ( Splitter  s = Splitter(),
Traits  t = Traits() 
)

Constructs an empty k-d tree.

template<typename Traits , typename Splitter , typename UseExtendedNode >
template<class InputIterator >
CGAL::Kd_tree< Traits, Splitter, UseExtendedNode >::Kd_tree ( InputIterator  first,
InputIterator  beyond,
Splitter  s = Splitter(),
Traits  t = Traits() 
)

Constructs a k-d tree on the elements from the sequence [first, beyond) using the splitting rule implemented by s.

The value type of the InputIterator must be Point_d.

Member Function Documentation

template<typename Traits , typename Splitter , typename UseExtendedNode >
iterator CGAL::Kd_tree< Traits, Splitter, UseExtendedNode >::begin ( ) const

Returns a const iterator to the first point in the tree.

template<typename Traits , typename Splitter , typename UseExtendedNode >
const Kd_tree_rectangle<FT>& CGAL::Kd_tree< Traits, Splitter, UseExtendedNode >::bounding_box ( ) const

Returns a const reference to the bounding box of the root node of the tree.

template<typename Traits , typename Splitter , typename UseExtendedNode >
void CGAL::Kd_tree< Traits, Splitter, UseExtendedNode >::clear ( )

Removes all points from the k-d tree.

template<typename Traits , typename Splitter , typename UseExtendedNode >
iterator CGAL::Kd_tree< Traits, Splitter, UseExtendedNode >::end ( ) const

Returns the appropriate past-the-end const iterator.

template<typename Traits , typename Splitter , typename UseExtendedNode >
void CGAL::Kd_tree< Traits, Splitter, UseExtendedNode >::insert ( Point_d  p)

Inserts the point p in the k-d tree.

Examples:
Spatial_searching/circular_query.cpp.
template<typename Traits , typename Splitter , typename UseExtendedNode >
template<class InputIterator >
void CGAL::Kd_tree< Traits, Splitter, UseExtendedNode >::insert ( InputIterator  first,
InputIterator  beyond 
)

Inserts the elements from the sequence [first, beyond) in the k-d tree.

The value type of the InputIterator must be Point_d.

template<typename Traits , typename Splitter , typename UseExtendedNode >
Node_handle CGAL::Kd_tree< Traits, Splitter, UseExtendedNode >::root ( )

Returns a handle to the root node of the tree.

template<typename Traits , typename Splitter , typename UseExtendedNode >
Node_const_handle CGAL::Kd_tree< Traits, Splitter, UseExtendedNode >::root ( ) const

Returns a const handle to the root node of the tree.

template<typename Traits , typename Splitter , typename UseExtendedNode >
template<class OutputIterator , class FuzzyQueryItem >
OutputIterator CGAL::Kd_tree< Traits, Splitter, UseExtendedNode >::search ( OutputIterator  it,
FuzzyQueryItem  q 
) const

Reports the points that are approximately contained by q.

The types FuzzyQueryItem::Point_d and Point_d must be equivalent. To use this function Traits must be a model of the concept RangeSearchTraits.

template<typename Traits , typename Splitter , typename UseExtendedNode >
size_type CGAL::Kd_tree< Traits, Splitter, UseExtendedNode >::size ( ) const

Returns the number of points that are stored in the tree.

template<typename Traits , typename Splitter , typename UseExtendedNode >
std::ostream& CGAL::Kd_tree< Traits, Splitter, UseExtendedNode >::statistics ( std::ostream &  s) const

Inserts statistics of the tree into the output stream s.

template<typename Traits , typename Splitter , typename UseExtendedNode >
Traits CGAL::Kd_tree< Traits, Splitter, UseExtendedNode >::traits ( ) const

return the instance of the traits used to construct the tree.