CGAL 5.1.2 - dD Range and Segment Trees
|
#include <CGAL/Range_tree_k.h>
An object of the class Range_tree_k
is a \( k\)-dimensional range tree that can store k-dimensional keys of type Key
.
The class allows to perform window queries on the keys. The class Range_tree_k
is parameterized with a range tree traits class Traits
that defines, among other things, the type of the Key
.
CGAL provides traits class implementations that allow to use the range tree with point classes from the CGAL kernel as keys. These classes are CGAL::Range_segment_tree_traits_set_2<R>
, CGAL::Range_segment_tree_traits_set_3<R>
, CGAL::Range_tree_traits_map_2<R>
and CGAL::Range_tree_traits_map_3<R>
. The concept RangeSegmentTreeTraits_d defines the requirements that range tree traits classes must fulfill. This allows the advanced user to develop further range tree traits classes.
Example
The following example program uses the predefined Range_tree_2
data structure together with the predefined traits class Range_tree_map_traits_2
which has two template arguments specifying the type of the point data in each dimension (CGAL::Cartesian<double>
) and the value type of the 2-dimensional point data (char
). Therefore the Range_tree_2
is defined on 2-dimensional point data (CGAL::Point_2<Cartesian<double> >
) each of which is associated with a character. Then, a few data items are created and put into a list. After that the tree is constructed according to that list, a window query is performed, and the query elements are given out.
Types | |
typedef Traits::Key | Key |
typedef Traits::Interval | Interval |
Creation | |
Range_tree_k () | |
Introduces an empty range tree R . | |
template<class ForwardIterator > | |
Range_tree_k (ForwardIterator first, ForwardIterator last) | |
Introduces a range tree R and initializes it with the data in the range [first, last) . More... | |
Operations | |
template<class ForwardIterator > | |
void | make_tree (ForwardIterator first, ForwardIterator last) |
Introduces a range tree R and initializes it with the data in the range [first, last) . More... | |
template<class OutputIterator > | |
OutputIterator | window_query (Interval window, OutputIterator out) |
writes all data that are in the interval window to the container where out points to, and returns an output iterator that points to the last location the function wrote to. More... | |
CGAL::Range_tree_k< Traits >::Range_tree_k | ( | ForwardIterator | first, |
ForwardIterator | last | ||
) |
Introduces a range tree R
and initializes it with the data in the range [first, last)
.
value_type(first) == Traits::Key
. void CGAL::Range_tree_k< Traits >::make_tree | ( | ForwardIterator | first, |
ForwardIterator | last | ||
) |
Introduces a range tree R
and initializes it with the data in the range [first, last)
.
This function can only be applied once on an empty range tree.
value_type(first) == Traits::Key
. OutputIterator CGAL::Range_tree_k< Traits >::window_query | ( | Interval | window, |
OutputIterator | out | ||
) |
writes all data that are in the interval window
to the container where out
points to, and returns an output iterator that points to the last location the function wrote to.
value_type(out) == Traits::Key
.