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

#include <CGAL/Kd_tree_node.h>

Definition

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

A node is either a leaf node, an internal node or an extended 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. An extended internal node is an internal node containing the lower and upper limit of an extended node's rectangle along the node's cutting dimension.

Parameters

Expects for the template argument a model of the concept SearchTraits, for example Search_traits_2<Simple_cartesian<double> >, or Cartesian_d<double>.

Types
enum	Node_type { LEAF, INTERNAL, EXTENDED_INTERNAL }
	Denotes type of node. More...
typedef Traits::FT	FT
	Number type.
typedef Traits::Point_d	Point_d
	Point type.
typedef Splitter::Separator	Separator
	Separator type.
typedef Kd_tree< Traits, Splitter, UseExtendedNode > ::Point_d_iterator	Point_d_iterator
	const iterator over points.
typedef Kd_tree< Traits, Splitter, UseExtendedNode > ::Node_handle	Node_handle
	Node handle.
typedef Kd_tree< Traits, Splitter, UseExtendedNode > ::Node_const_handle	Node_const_handle
	const node handle.

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 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.
unsigned int	size () const
	Returns the number of items stored in a leaf node.
Point_d_iterator	begin () const
	Returns a const iterator to the first item in a leaf node.
Point_d_iterator	end () const
	Returns the appropriate past-the-end const iterator.
Node_handle	lower ()
	Returns a handle to the lower child of an internal node.
Node_handle	upper ()
	Returns a handle to the upper child of an internal node.
Node_const_handle	lower () const
	Returns a const handle to the lower child of an internal node.
Node_const_handle	upper () const
	Returns a const handle to the upper child of an internal node.
Separator &	separator ()
	Returns a reference to the separator.
FT	low_value () const
	Returns the lower limit of an extended node's rectangle along the node's cutting dimension.
FT	high_value () const
	Returns the upper limit of an extended node's rectangle along the node's cutting dimension.

Member Enumeration Documentation

template<typename Traits , typename Splitter , typename UseExtendedNode >

enum CGAL::Kd_tree_node::Node_type

Denotes type of node.

Enumerator
LEAF
INTERNAL
EXTENDED_INTERNAL