Navigation: Up, Table of Contents, Bibliography, Index, Title Page

## CGAL::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 exteneded 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.

| advanced |

Next: Kd_tree_rectangle<Traits>

Navigation: Table of Contents, Bibliography, Index, Title Page

The CGAL Project . Tue, December 21, 2004 .