Kd_tree<Traits, Splitter, UseExtendedNode>

Navigation: Up Table of Contents Package Overview Bibliography Index Title Acknowledging CGAL

CGAL::Kd_tree<Traits, Splitter, UseExtendedNode>

The class Kd_tree<Traits, Splitter, UseExtendedNode> defines a k-d tree.

Expects for the first template argument a model of the concept SearchTraits, for example CGAL::Search_traits_2<CGAL::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 CGAL::Tag_true, if the tree shall be built with extended nodes, and CGAL::Tag_false otherwise.

Kd_tree<Traits, Splitter, UseExtendedNode>::Splitter
	Splitter type.

Kd_tree<Traits, Splitter, UseExtendedNode>::iterator
	Bidirectional const iterator with value type Point_d that allows to enumerate all points in the tree.

Kd_tree<Traits, Splitter, UseExtendedNode>::Node_handle
	A handle with value type Kd_tree_node<Traits,Splitter>.

Kd_tree<Traits, Splitter, UseExtendedNode>::Node_const_handle
	A const handle with value type Kd_tree_node<Traits,Splitter>.

Kd_tree<Traits, Splitter, UseExtendedNode>::Point_d_iterator
	Random access const iterator with value type const Point_d*.

Kd_tree<Traits, Splitter, UseExtendedNode>::size_type
	A type that counts the number of elements in a k-d tree.

Kd_tree<Traits, Splitter, UseExtendedNode> tree ( Splitter s=Splitter(), Traits t=Traits());
	Constructs an empty k-d tree.

template <class InputIterator>
Kd_tree<Traits, Splitter, UseExtendedNode> 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.

void	tree.insert ( Point_d p)	Inserts the point p in the k-d tree.

template <class InputIterator>
void	tree.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 <class OutputIterator, class FuzzyQueryItem>
OutputIterator	tree.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.

iterator	tree.begin () const	Returns a const iterator to the first point in the tree.

iterator	tree.end () const	Returns the appropriate past-the-end const iterator.

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

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

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

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

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

Kd_tree_rectangle<FT>	tree.bounding_box () const	returns a const reference to the bounding box of the root node of the tree.

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