\( \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.5 - dD Range and Segment Trees
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Groups Pages
List of all members
CGAL::Segment_tree_d< Data, Window, Traits > Class Template Reference
Search Structures

#include <CGAL/Segment_tree_d.h>

Definition

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. More...
 

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. More...
 
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\). More...
 
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. More...
 
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

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 weather 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.

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.
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.
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.