Range_tree_d<Data, Window, Traits>

Navigation: Up, Table of Contents, Bibliography, Index, Title Page

CGAL::Range_tree_d<Data, Window, Traits>

Types

Range_tree_d<Data, Window, Traits>::Data
	container Data.

Range_tree_d<Data, Window, Traits>::Window
	container Window.

Range_tree_d<Data, Window, Traits>::Traits
	container Traits.

Creation

#include <CGAL/Range_tree_d.h>

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.

Operations

template<class ForwardIterator>

bool

r.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<class OutputIterator>

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

Protected Operations

bool r.is_inside ( Window win, Data object)
returns true, if the data of object lies between the start and endpoint of interval win. False otherwise.

bool r.is_anchor () returns false.

Implementation

The construction of a

d-dimensional range tree takes

O(nlog

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(nlog

n^d-1) storage.

Next: Range_tree_k<Traits>

Navigation: Table of Contents, Bibliography, Index, Title Page

The CGAL Project . Tue, December 21, 2004 .

template<class OutputIterator>
OutputIterator	r.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	r.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	r.is_inside ( Window win, Data object)
		returns true, if the data of object lies between the start and endpoint of interval win. False otherwise.

bool	r.is_anchor ()	returns false.