CGAL 4.8.2  dD Range and Segment Trees

#include <CGAL/Range_tree_d.h>
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^{d1})\) 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^{d1})\) 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.  

protected 
returns true
, if the data of object
lies between the start and endpoint of interval win
.
Returns false
otherwise.
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.
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
.
true
is returned. Otherwise, nothing is done but a CGAL warning is given and false
returned. 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 \( d1\)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 onedimensional 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 twodimensional range tree, create Range_tree_d
with a onedimensional Range_tree_d
with the corresponding Traits
class of the first dimension.
Traits::Data==Data
and Traits::Window==Window.