#include <CGAL/Kd_tree.h>

Definition

The class Kd_tree defines a k-d tree.

Template Parameters

Traits	must be a model of the concept `SearchTraits`, for example `Search_traits_2<Simple_cartesian<double> >`.
Splitter	must be a model for the concept `Splitter`. It defaults to `Sliding_midpoint<Traits>`.
UseExtendedNode	must be `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 unspecified_type	D
	Dimension tag.

typedef Traits::Point_d	Point_d
	Point class.

typedef Traits::FT	FT
	Number type.

typedef unspecified_type	Splitter
	Splitter type.

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

typedef unspecified_type	Node_handle
	A handle with value type `Kd_tree_node<Traits,Splitter>`.

typedef unspecified_type	Node_const_handle
	A const handle with value type `Kd_tree_node<Traits,Splitter>`.

typedef unspecified_type	Point_d_iterator
	Random access const iterator with value type `const Point_d*`.

typedef unspecified_type	size_type
	A type that counts the number of elements in a `k-d` tree.

Creation
	Kd_tree (Splitter s=Splitter(), Traits t=Traits())
	Constructs an empty `k-d` tree.

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.

template<class InputIterator >
void	insert (InputIterator first, InputIterator beyond)
	Inserts the elements from the sequence `[first, beyond)` in the `k-d` tree. More...

void	reserve (size_t size)

size_t	capacity ()

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.

void	clear ()
	Removes all points from the `k-d` tree.

size_type	size () const
	Returns the number of points that are stored in the tree.

Traits	traits () const
	return the instance of the traits used to construct the tree.

Node_handle	root ()
	Returns a handle to the root node of the tree.

Node_const_handle	root () const
	Returns a const handle to the root node of the tree.

const Kd_tree_rectangle< FT, D > &	bounding_box () const
	Returns a const reference to the bounding box of the root node of the tree.

std::ostream &	statistics (std::ostream &s) const
	Inserts statistics of the tree into the output stream `s`.

Constructor & Destructor Documentation

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.

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.

Note: Starting with CGAL 4.6, the order of the points in the iterator range [begin() , end()) is not the order of insertion of the points into the tree. This was not guaranteed before but might have beeen observed and exploited.

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 >

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.