CGAL 6.1 - dD Range and Segment Trees

Loading...
Searching...
No Matches
List of all members
CGAL::Segment_tree_d< Data, Window, Traits > Class Template Reference
Reference Manual » Search Structures

`#include <CGAL/Segment_tree_d.h>`

## Definition

template<typename Data, typename Window, typename Traits>
class CGAL::Segment_tree_d< Data, Window, Traits >

A \( d\)-dimensional segment tree stores \( d\)-dimensional intervals and can be used to find all intervals that enclose, partially overlap, or contain a query interval, which may be a point.

Implementation

A \( d\)-dimensional segment tree is constructed in \(O(n\log n^d)\) time. An inverse range query is performed in time \(O(k+{\log}^d n )\), where \( k\) is the number of reported intervals. The tree uses \(O(n\log n^d)\) storage.

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

## Creation
Segment_tree_d< Data, Window, Traits > | s (Tree_base< Data, Window > sublayer_tree)
| A segment tree is defined, such that the subtree of each vertex is of the same type prototype `sublayer_tree` is.

## Operations
bool | make_tree (In_it first, In_it last)
| The tree is constructed according to the data items in the sequence between the element pointed by iterator `first` and iterator `last`.
OutputIterator | window_query (Window win, OutputIterator result)
| `win` \( =[a_1,b_1),\ldots, [a_d,b_d)\), \( a_i,b_i\in T_i\), \( 1\le i\le d\).
OutputIterator | enclosing_query (Window win, OutputIterator result)
| All elements that enclose the associated \( d\)-dimensional interval of `win` are placed in the associated sequence container of `OutputIterator` and returns an output iterator that points to the last location the function wrote to.
bool | is_valid ()
| The tree structure is checked.
bool | is_inside (Window win, Data object)
| returns `true`, if the interval of `object` is contained in the interval of `win`, `false` otherwise.
bool | is_anchor ()
| returns false.

## Member Function Documentation

## ◆ is_valid()

template<typename Data , typename Window , typename Traits >

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

The tree structure is checked.

For each vertex either the sublayer tree is a tree anchor, or it stores a (possibly empty) list of data items. In the first case, the sublayer tree of the vertex is checked on being valid. In the second case, each data item is checked whether it contains the associated interval of the vertex and does not contain the associated interval of the parent vertex or not. `true` is returned if the tree structure is valid, `false` otherwise.

## ◆ make_tree()

template<typename Data , typename Window , typename Traits >

bool CGAL::Segment_tree_d< Data, Window, Traits >::make_tree | ( | In_it | first,
|  | In_it | last
| ) |  |

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

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.

## ◆ s()

template<typename Data , typename Window , typename Traits >

Segment_tree_d< Data, Window, Traits > CGAL::Segment_tree_d< Data, Window, Traits >::s | ( | Tree_base< Data, Window > | sublayer_tree | ) |

A segment tree is defined, 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 segment 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 described, for example, in 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 segment tree instantiate `Tree_anchor<Data, Window> sublayer_tree` with the same template parameters `Data` and `Window` `Segment_tree_d` is defined. In order to construct a two-dimensional segment tree, create `Segment_tree_d` with a one-dimensional `Segment_tree_d` with the corresponding `Traits` of the first dimension.

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

## ◆ window_query()

template<typename Data , typename Window , typename Traits >

OutputIterator CGAL::Segment_tree_d< Data, Window, Traits >::window_query | ( | Window | win,
|  | OutputIterator | result
| ) |  |

`win` \( =[a_1,b_1),\ldots, [a_d,b_d)\), \( a_i,b_i\in T_i\), \( 1\le i\le d\).

All elements that intersect the associated \( d\)-dimensional interval of `win` are placed in the associated sequence container of `OutputIterator` and returns an output iterator that points to the last location the function wrote to. In order to perform an inverse range query, a range query of \( \epsilon\) width has to be performed.