CGAL 4.7 - dD Range and Segment Trees: CGAL::Range_tree_d< Data, Window, Traits > Class Template Reference

\( \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.7 - dD Range and Segment Trees

All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Groups Pages
List of all members
CGAL::Range_tree_d< Data, Window, Traits > Class Template Reference
Search Structures

`#include <CGAL/Range_tree_d.h>`

## Definition

A \( d\)-dimensional range tree stores points and can be used to determine all points that lie inside a given \( d\)-dimensional interval.

Implementation

The construction of a \( d\)-dimensional range tree takes \( {O}(n\log n^{d-1})\) time. The points in the query window are reported in time \( {O}(k+{\log}^d n )\), where \( k\) is the number of reported points. The tree uses \( {O}(n\log n^{d-1})\) storage.

## Types

typedef unspecified_type | Data
| container `Data`.
typedef unspecified_type | Window
| container `Window`.

## Creation

Range_tree_d< Data, Window, Traits > | r (Tree_base< Data, Window > sublayer_tree)
| A range tree is constructed, such that the subtree of each vertex is of the same type prototype `sublayer_tree` is. More...

## Operations

template<class ForwardIterator >
bool | make_tree (ForwardIterator first, ForwardIterator last)
| The tree is constructed according to the data items in the sequence between the element pointed by iterator `first` and iterator `last`. More...
template<class OutputIterator >
OutputIterator | window_query (Window win, OutputIterator result)
| All elements that lay inside the \( d\)-dimensional interval defined through `win` are placed in the sequence container of `OutputIterator`; the output iterator that points to the last location the function wrote to is returned.
bool | is_valid ()
| The tree structure is checked. More...
bool | is_inside (Window win, Data object)
| returns `true`, if the data of `object` lies between the start and endpoint of interval `win`. More...
bool | is_anchor ()
| returns false.

## Member Function Documentation

template<typename Data , typename Window , typename Traits >

bool CGAL::Range_tree_d< Data, Window, Traits >::is_inside | ( | Window | win,
|  | Data | object
| ) |  |

protected

returns `true`, if the data of `object` lies between the start and endpoint of interval `win`.

Returns `false` otherwise.

template<typename Data , typename Window , typename Traits >

bool CGAL::Range_tree_d< Data, Window, Traits >::is_valid | ( | ) |  |

The tree structure is checked.

For each vertex the subtree is checked on being valid and it is checked whether the value of the `Key_type` of a vertex corresponds to the highest `Key_type` value of the left subtree.

template<typename Data , typename Window , typename Traits >
template<class ForwardIterator >

bool CGAL::Range_tree_d< Data, Window, Traits >::make_tree | ( | ForwardIterator | first,
|  | ForwardIterator | last
| ) |  |

The tree is constructed according to the data items in the sequence between the element pointed by iterator `first` and iterator `last`.

The data items of the iterator must have type `Data`.

Precondition
  This function can only be called once. If it is the first call the tree is build and `true` is returned. Otherwise, nothing is done but a CGAL warning is given and `false` returned.

template<typename Data , typename Window , typename Traits >

Range_tree_d<Data, Window, Traits> CGAL::Range_tree_d< Data, Window, Traits >::r | ( | Tree_base< Data, Window > | sublayer_tree) |  |

A range tree is constructed, such that the subtree of each vertex is of the same type prototype `sublayer_tree` is.

We assume that the dimension of the tree is \( d\). This means, that `sublayer_tree` is a prototype of a \( d-1\)-dimensional tree. All data items of the \( d\)-dimensional range tree have container type `Data`. The query window of the tree has container type `Window`. `Traits` provides access to the corresponding data slots of container `Data` and `Window` for the \( d\)-th dimension. The traits class `Traits` must at least provide all functions and type definitions as described in, for example, the reference page for `tree_point_traits`. The template class described there is fully generic and should fulfill the most requirements one can have. In order to generate a one-dimensional range tree instantiate `Tree_anchor<Data, Window> sublayer_tree` with the same template parameters (`Data` and `Window`) `Range_tree_d` is defined. In order to construct a two-dimensional range tree, create `Range_tree_d` with a one-dimensional `Range_tree_d` with the corresponding `Traits` class of the first dimension.

Precondition
  `Traits::Data==Data` and `Traits::Window==Window.`