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 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>::Point_d_iterator
	Random access iterator with value type Point_d*.

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)
		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 ()	Returns an iterator to the first point in the tree.

iterator	tree.end ()	Returns the corresponding past-the-end iterator.

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

unsigned int	tree.size ()	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.

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

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