Kd_tree_node<Traits, Splitter, UseExtendedNode>

advanced

Definition

The class Kd_tree_node<Traits, Splitter, UseExtendedNode> 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.

#include <CGAL/Kd_tree_node.h>

Parameters

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

Types

enum Node_type { LEAF, INTERNAL, EXTENDED_INTERNAL};
	Denotes type of node.

Traits::FT	FT;	Number type.

Traits::Point_d	Point_d;	Point type.

Splitter::Separator	Separator;	Separator type.

Kd_tree<Traits,Splitter,UseExtendedNode>::Point_d_iterator
	Point_d_iterator;	Iterator over points.

Kd_tree<Traits,Splitter,UseExtendedNode>::Node_handle
	Node_handle;	Node handle.

Creation

Operations

template <class OutputIterator, class FuzzyQueryItem>
OutputIterator	n.search ( OutputIterator it, FuzzyQueryItem q)
		Reports the points from the subtree of the node, that are approximately contained by q.

template <class OutputIterator>
OutputIterator	n.tree_points ( OutputIterator it)
		Reports all the points contained by the subtree of the node.

bool	n.is_leaf ()	Indicates whether a node is a leaf node.

int	n.size ()	Returns the number of items stored in a leaf node.

Point_d_iterator	n.begin ()	Returns the iterator to the first item in a leaf node.

Point_d_iterator	n.end ()	Returns the past-the-end iterator in a leaf node.

Node_handle	n.lower ()	Returns a handle to the lower child of an internal node.

Node_handle	n.upper ()	Returns a handle to the upper child of an internal node.

Separator&	n.separator ()	Returns a reference to the separator.

FT	n.low_val ()	Returns the lower limit of an extended node's rectangle along the node's cutting dimension.

FT	n.high_val ()	Returns the upper limit of an extended node's rectangle along the node's cutting dimension.