CGAL::Kd_tree<Traits, Splitter, UseExtendedNode>

Definition

#include <CGAL/Kd_tree.h>

Parameters

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.

Types

Traits::Point_d	Point_d;	Point class.
Traits::FT	FT;	Number type.

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.

advanced

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

advanced

Creation

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.

Operations

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.

advanced

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.

advanced

See Also