CGAL::Kd_tree<Traits, Splitter, UseExtendedNode>

Definition

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

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

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

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.

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.

See Also

Tree. CGAL::Kd_tree_node<Traits>,
CGAL::Search_traits_2<Kernel>,
CGAL::Search_traits_3<Kernel>,
CGAL::Search_traits<FT_,Point,CartesianIterator,ConstructCartesianIterator>.