\( \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.4 - 2D Segment Delaunay Graphs
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Groups Pages
CGAL::Segment_Delaunay_graph_hierarchy_2< Gt, STag, DS > Class Template Reference

#include <CGAL/Segment_Delaunay_graph_hierarchy_2.h>

Inherits from

CGAL::Segment_Delaunay_graph_2< Gt, DS >.

Definition

We provide an alternative to the class Segment_Delaunay_graph_2<Gt,DS> for the incremental construction of the segment Delaunay graph.

The Segment_Delaunay_graph_hierarchy_2 class maintains a hierarchy of Delaunay graphs. There are two possibilities as to how this hierarchy is constructed.

In the first case the bottom-most level of the hierarchy contains the full segment Delaunay graph. The upper levels of the hierarchy contain only points that are either point sites or endpoints of segment sites in the bottom-most Delaunay graph. A point that is in level \( i\) (either as an individdual point or as the endpoint of a segment), is inserted in level \( i+1\) with probability \( 1/\alpha\) where \( \alpha>1\) is some constant. In the second case the upper levels of the hierarchy contains not only points but also segments. A site that is in level \( i\), is in level \( i+1\) with probability \( 1/\beta\) where \( \beta > 1\) is some constant.

The difference between the Segment_Delaunay_graph_2<Gt,DS> class and the Segment_Delaunay_graph_hierarchy_2 class (both versions of it) is on how the nearest neighbor location is done. Given a point \( p\) the location is done as follows: at the top most level we find the nearest neighbor of \( p\) as in the Segment_Delaunay_graph_2<Gt,DS> class. At every subsequent level \( i\) we use the nearest neighbor found at level \( i+1\) to find the nearest neighbor at level \( i\). This is a variant of the corresponding hierarchy for points found in [3]. The details are described in [4].

The class has three template parameters. The first and third have essentially the same semantics as in the Segment_Delaunay_graph_2<Gt,DS> class. The first template parameter must be a model of the SegmentDelaunayGraphTraits_2 concept. The third template parameter must be a model of the SegmentDelaunayGraphDataStructure_2 concept. However, the vertex base class that is to be used in the segment Delaunay graph data structure must be a model of the SegmentDelaunayGraphHierarchyVertexBase_2 concept. The third template parameter defaults to Triangulation_data_structure_2< Segment_Delaunay_graph_hierarchy_vertex_base_2< Segment_Delaunay_graph_vertex_base_2<Gt> >, Triangulation_face_base_2<Gt> >. The second template parameter controls whether or not segments are added in the upper levels of the hierarchy. It's possible values are Tag_true and Tag_false. If it is set to Tag_true, segments are also inserted in the upper levels of the hierarchy. The value Tag_false indicates that only points are to be inserted in the upper levels of the hierarchy. The default value for the second template parameter is Tag_false.

The Segment_Delaunay_graph_hierarchy_2 class derives publicly from the Segment_Delaunay_graph_2<Gt,DS> class. The interface is the same with its base class. In the sequel only additional types and methods defined are documented.

Is Model Of:

DefaultConstructible

CopyConstructible

Assignable

See Also
SegmentDelaunayGraphDataStructure_2
SegmentDelaunayGraphTraits_2
SegmentDelaunayGraphHierarchyVertexBase_2
CGAL::Segment_Delaunay_graph_2<Gt,DS>
CGAL::Triangulation_data_structure_2<Vb,Fb>
CGAL::Segment_Delaunay_graph_traits_2<K,MTag>
CGAL::Segment_Delaunay_graph_traits_without_intersections_2<K,MTag>
CGAL::Segment_Delaunay_graph_filtered_traits_2<CK,CM,EK,EM,FK,FM>
CGAL::Segment_Delaunay_graph_filtered_traits_without_intersections_2<CK,CM,EK,EM,FK,FM>
CGAL::Segment_Delaunay_graph_hierarchy_vertex_base_2<Vbb>
Examples:
Segment_Delaunay_graph_2/sdg-filtered-traits.cpp, and Segment_Delaunay_graph_2/sdg-info-set.cpp.

Related Functions

(Note that these are not member functions.)

std::ostream & operator<< (std::ostream &os, Segment_Delaunay_graph_hierarchy_2< Gt, STag, DS > svdh)
 Writes the current state of the segment Delaunay graph hierarchy to an output stream. More...
 
std::istream & operator>> (std::istream &is, Segment_Delaunay_graph_hierarchy_2< Gt, STag, DS > svdh)
 Reads the state of the segment Delaunay graph hierarchy from an input stream. More...
 

Types

Segment_Delaunay_graph_hierarchy_2 introduces the following types in addition to those introduced by its base class Segment_Delaunay_graph_2<Gt,DS>.

typedef STag Segments_in_hierarchy_tag
 A type for the STag template parameter. More...
 
typedef
CGAL::Segment_Delaunay_graph_2
< Gt, DS > 
Base
 A type for the base class. More...
 

Creation

In addition to the default and copy constructors, the following constructors are defined:

 Segment_Delaunay_graph_hierarchy_2 (Gt gt=Gt())
 Creates a hierarchy of segment Delaunay graphs using gt as geometric traits. More...
 
template<class Input_iterator >
 Segment_Delaunay_graph_hierarchy_2 (Input_iterator first, Input_iterator beyond, Gt gt=Gt())
 Creates a segment Delaunay graph hierarchy using gt as geometric traits and inserts all sites in the range [first, beyond). More...
 

Member Typedef Documentation

template<typename Gt , typename STag , typename DS >
typedef CGAL::Segment_Delaunay_graph_2<Gt,DS> CGAL::Segment_Delaunay_graph_hierarchy_2< Gt, STag, DS >::Base

A type for the base class.

template<typename Gt , typename STag , typename DS >
typedef STag CGAL::Segment_Delaunay_graph_hierarchy_2< Gt, STag, DS >::Segments_in_hierarchy_tag

A type for the STag template parameter.

Constructor & Destructor Documentation

template<typename Gt , typename STag , typename DS >
CGAL::Segment_Delaunay_graph_hierarchy_2< Gt, STag, DS >::Segment_Delaunay_graph_hierarchy_2 ( Gt  gt = Gt())

Creates a hierarchy of segment Delaunay graphs using gt as geometric traits.

template<typename Gt , typename STag , typename DS >
template<class Input_iterator >
CGAL::Segment_Delaunay_graph_hierarchy_2< Gt, STag, DS >::Segment_Delaunay_graph_hierarchy_2 ( Input_iterator  first,
Input_iterator  beyond,
Gt  gt = Gt() 
)

Creates a segment Delaunay graph hierarchy using gt as geometric traits and inserts all sites in the range [first, beyond).

Input_iterator must be a model of InputIterator. The value type of Input_iterator must be either Point_2 or Site_2.

Friends And Related Function Documentation

template<typename Gt , typename STag , typename DS >
std::ostream & operator<< ( std::ostream &  os,
Segment_Delaunay_graph_hierarchy_2< Gt, STag, DS >  svdh 
)
related

Writes the current state of the segment Delaunay graph hierarchy to an output stream.

In particular, all sites in the diagram are written to the stream (represented through appropriate input sites), as well as the underlying combinatorial hierarchical data structure.

Examples:
Segment_Delaunay_graph_2/sdg-red-blue-info.cpp.
template<typename Gt , typename STag , typename DS >
std::istream & operator>> ( std::istream &  is,
Segment_Delaunay_graph_hierarchy_2< Gt, STag, DS >  svdh 
)
related

Reads the state of the segment Delaunay graph hierarchy from an input stream.