\( \newcommand{\E}{\mathrm{E}} \) \( \newcommand{\A}{\mathrm{A}} \) \( \newcommand{\R}{\mathrm{R}} \) \( \newcommand{\N}{\mathrm{N}} \) \( \newcommand{\Q}{\mathrm{Q}} \) \( \newcommand{\Z}{\mathrm{Z}} \) \( \def\ccSum #1#2#3{ \sum_{#1}^{#2}{#3} } \def\ccProd #1#2#3{ \sum_{#1}^{#2}{#3} }\)
CGAL 4.5 - dD Spatial Searching
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Groups Pages
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.
 
Separatorseparator ()
 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