CGAL::Kd_tree_node< Traits, Splitter, UseExtendedNode > Class Template Reference

#include <CGAL/Kd_tree_node.h>

Definition

template<typename Traits, typename Splitter, typename UseExtendedNode>
class CGAL::Kd_tree_node< Traits, Splitter, UseExtendedNode >

The class Kd_tree_node implements a node class for a k-d tree.

A node is either a Kd_tree_leaf_node or a Kd_tree_internal_node. A leaf node contains one or more points. An internal node contains a pointer to its lower child, a pointer to its upper child, and a pointer to its separator. If extended nodes are used, it also contains the upper limit of the lower child's tight rectangle and the lower limit of the upper child's tight rectangle along the node's cutting dimension.

Template Parameters

Traits	must be a model of the concept SearchTraits, for example Search_traits_2<Simple_cartesian<double> >, or Cartesian_d<double>.
Splitter	must be a model of the concept Splitter.

Types
typedef Traits::Point_d	Point_d
	Point class.

Operations
template<class OutputIterator , class FuzzyQueryItem >
OutputIterator	search (OutputIterator it, FuzzyQueryItem q) const
	Reports the points from the subtree of the node, that are approximately contained by q.
template<class FuzzyQueryItem >
boost::optional< Point_d >	search_any_point (OutputIterator it, FuzzyQueryItem q) const
	Reports any point from the subtree of the node, that is approximately contained by q.
template<class OutputIterator >
OutputIterator	tree_items (OutputIterator it) const
	Reports all the points contained by the subtree of the node.
bool	is_leaf () const
	Indicates whether a node is a leaf node.