\( \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.8.1 - dD Spatial Searching
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Groups Pages
List of all members
CGAL::Kd_tree_node< Traits, Splitter, UseExtendedNode > Class Template Reference
Advanced Classes

#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 Kd_tree_leaf_node or a Kd_tree_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. If extended nodes are used, it also contains the upper limit of the lower child's tight rectangle and the lower limit of the upper child's tight rectangle along the node's cutting dimension.

Template Parameters
Traitsmust be a model of the concept SearchTraits, for example Search_traits_2<Simple_cartesian<double> >, or Cartesian_d<double>.
Splittermust be a model of the concept Splitter.

Types

typedef Traits::Point_d Point_d
 Point class.
 

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 FuzzyQueryItem >
boost::optional< Point_d > search_any_point (OutputIterator it, FuzzyQueryItem q) const
 Reports any point from the subtree of the node, that is 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.