CGAL 6.1.2 - dD Spatial Searching

Loading...
Searching...
No Matches
List of all members
CGAL::Kd_tree_node< Traits, Splitter, UseExtendedNode > Class Template Reference
Reference Manual » Advanced Classes

`#include <CGAL/Kd_tree_node.h>`

## Definition

template<typename Traits, typename Splitter, typename UseExtendedNode>
class CGAL::Kd_tree_node< Traits, Splitter, UseExtendedNode >

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

  Traits | must be a model of the concept `SearchTraits`, for example `Search_traits_2<Simple_cartesian<double> >`, or `Cartesian_d<double>`.
  Splitter | must 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 >
std::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.