CGAL 4.4 - dD Spatial Searching
|
#include <CGAL/Kd_tree_node.h>
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. More... | |
typedef Traits::Point_d | Point_d |
Point type. More... | |
typedef Splitter::Separator | Separator |
Separator type. More... | |
typedef Kd_tree< Traits, Splitter, UseExtendedNode > ::Point_d_iterator | Point_d_iterator |
const iterator over points. More... | |
typedef Kd_tree< Traits, Splitter, UseExtendedNode > ::Node_handle | Node_handle |
Node handle. More... | |
typedef Kd_tree< Traits, Splitter, UseExtendedNode > ::Node_const_handle | Node_const_handle |
const node handle. More... | |
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. More... | |
template<class OutputIterator > | |
OutputIterator | tree_items (OutputIterator it) const |
Reports all the points contained by the subtree of the node. More... | |
bool | is_leaf () const |
Indicates whether a node is a leaf node. More... | |
unsigned int | size () const |
Returns the number of items stored in a leaf node. More... | |
Point_d_iterator | begin () const |
Returns a const iterator to the first item in a leaf node. More... | |
Point_d_iterator | end () const |
Returns the appropriate past-the-end const iterator. More... | |
Node_handle | lower () |
Returns a handle to the lower child of an internal node. More... | |
Node_handle | upper () |
Returns a handle to the upper child of an internal node. More... | |
Node_const_handle | lower () const |
Returns a const handle to the lower child of an internal node. More... | |
Node_const_handle | upper () const |
Returns a const handle to the upper child of an internal node. More... | |
Separator & | separator () |
Returns a reference to the separator. More... | |
FT | low_value () const |
Returns the lower limit of an extended node's rectangle along the node's cutting dimension. More... | |
FT | high_value () const |
Returns the upper limit of an extended node's rectangle along the node's cutting dimension. More... | |
typedef Traits::FT CGAL::Kd_tree_node< Traits, Splitter, UseExtendedNode >::FT |
Number type.
typedef Kd_tree<Traits,Splitter,UseExtendedNode>::Node_const_handle CGAL::Kd_tree_node< Traits, Splitter, UseExtendedNode >::Node_const_handle |
const node handle.
typedef Kd_tree<Traits,Splitter,UseExtendedNode>::Node_handle CGAL::Kd_tree_node< Traits, Splitter, UseExtendedNode >::Node_handle |
Node handle.
typedef Traits::Point_d CGAL::Kd_tree_node< Traits, Splitter, UseExtendedNode >::Point_d |
Point type.
typedef Kd_tree<Traits,Splitter,UseExtendedNode>::Point_d_iterator CGAL::Kd_tree_node< Traits, Splitter, UseExtendedNode >::Point_d_iterator |
const iterator over points.
typedef Splitter::Separator CGAL::Kd_tree_node< Traits, Splitter, UseExtendedNode >::Separator |
Separator type.
enum CGAL::Kd_tree_node::Node_type |
Point_d_iterator CGAL::Kd_tree_node< Traits, Splitter, UseExtendedNode >::begin | ( | ) | const |
Returns a const iterator to the first item in a leaf node.
Point_d_iterator CGAL::Kd_tree_node< Traits, Splitter, UseExtendedNode >::end | ( | ) | const |
Returns the appropriate past-the-end const iterator.
FT CGAL::Kd_tree_node< Traits, Splitter, UseExtendedNode >::high_value | ( | ) | const |
Returns the upper limit of an extended node's rectangle along the node's cutting dimension.
bool CGAL::Kd_tree_node< Traits, Splitter, UseExtendedNode >::is_leaf | ( | ) | const |
Indicates whether a node is a leaf node.
FT CGAL::Kd_tree_node< Traits, Splitter, UseExtendedNode >::low_value | ( | ) | const |
Returns the lower limit of an extended node's rectangle along the node's cutting dimension.
Node_handle CGAL::Kd_tree_node< Traits, Splitter, UseExtendedNode >::lower | ( | ) |
Returns a handle to the lower child of an internal node.
Node_const_handle CGAL::Kd_tree_node< Traits, Splitter, UseExtendedNode >::lower | ( | ) | const |
Returns a const handle to the lower child of an internal node.
OutputIterator CGAL::Kd_tree_node< Traits, Splitter, UseExtendedNode >::search | ( | OutputIterator | it, |
FuzzyQueryItem | q | ||
) | const |
Reports the points from the subtree of the node, that are approximately contained by q.
Separator& CGAL::Kd_tree_node< Traits, Splitter, UseExtendedNode >::separator | ( | ) |
Returns a reference to the separator.
unsigned int CGAL::Kd_tree_node< Traits, Splitter, UseExtendedNode >::size | ( | ) | const |
Returns the number of items stored in a leaf node.
OutputIterator CGAL::Kd_tree_node< Traits, Splitter, UseExtendedNode >::tree_items | ( | OutputIterator | it | ) | const |
Reports all the points contained by the subtree of the node.
Node_handle CGAL::Kd_tree_node< Traits, Splitter, UseExtendedNode >::upper | ( | ) |
Returns a handle to the upper child of an internal node.
Node_const_handle CGAL::Kd_tree_node< Traits, Splitter, UseExtendedNode >::upper | ( | ) | const |
Returns a const handle to the upper child of an internal node.