CGAL::Kd_tree_node<Traits, Splitter, UseExtendedNode>

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.