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> >.

Excepts 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());
	Constructs an empty k-d tree.

template <class InputIterator>
Kd_tree<Traits, Splitter, UseExtendedNode> tree ( InputIterator first, InputIterator beyond, Splitter s=Splitter());
	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.

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 ()	Removes all points from the k-d tree.

unsigned int	tree.size ()	Returns the number of points that are stored in the tree.

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

Kd_tree_rectangle<Traits>	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.