\( \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.3 - 2D Voronoi Diagram Adaptor
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Groups Pages
List of all members
DelaunayGraph_2 Concept Reference
Concepts

Definition

The concept DelaunayGraph_2 defines the requirements for the first template parameter of the Voronoi_diagram_2<DG,AT,AP> class. The DelaunayGraph_2 concept essentially defines the requirements that a class representing a Delaunay graph must obey so that the Voronoi diagram adaptor can adapt it.

Refines:

DefaultConstructible,

CopyConstructible,

Assignable

Traversal of the Delaunay graph

A model of the DelaunayGraph_2 concept must provide several iterators and circulators that allow to traverse it (completely or partially). All iterators and circulators must be convertible to the corresponding handles.

Has Models:

CGAL::Delaunay_triangulation_2<Traits,Tds>

CGAL::Regular_triangulation_2<Traits,Tds>

CGAL::Triangulation_hierarchy_2<Tr> provided that Tr is a model of DelaunayGraph_2

CGAL::Segment_Delaunay_graph_2<Gt,DS>

CGAL::Segment_Delaunay_graph_hierarchy_2<Gt,STag,DS>

CGAL::Apollonius_graph_2<Gt,Agds>

CGAL::Apollonius_graph_hierarchy_2<Gt,Agds>

See Also
AdaptationTraits_2
AdaptationPolicy_2
CGAL::Voronoi_diagram_2<DG,AT,AP>

Types

typedef unspecified_type size_type
 A type for sizes.
 
typedef unspecified_type Geom_traits
 A type for the geometric traits associated with the Delaunay graph.
 
typedef unspecified_type Triangulation_data_structure
 A type for the underlying triangulation data structure. More...
 
typedef unspecified_type Vertex
 A type for the vertices of the Delaunay graph.
 
typedef unspecified_type Face
 A type for the faces of the Delaunay graph.
 
typedef std::pair< Face_handle,
int > 		Edge
 The type of the edges of the Delaunay graph.
 
typedef unspecified_type Vertex_handle
 Handle to the vertices of the Delaunay graph.
 
typedef unspecified_type Face_handle
 Handle to the faces of the Delaunay graph.
 

The following iterators and circulators must be defined.

All iterators and circulators must be assignable and convertible to their corresponding handles.

typedef unspecified_type All_edges_iterator
 A type for an iterator over all edges of the Delaunay graph. More...
 
typedef unspecified_type Finite_edges_iterator
 A type for an iterator over the finite edges of the Delaunay graph. More...
 
typedef unspecified_type All_faces_iterator
 A type for an iterator over all faces of the Delaunay graph. More...
 
typedef unspecified_type Finite_faces_iterator
 A type for an iterator over the finite faces of the Delaunay graph. More...
 
typedef unspecified_type All_vertices_iterator
 A type for an iterator over all vertices of the Delaunay graph. More...
 
typedef unspecified_type Finite_vertices_iterator
 A type for an iterator over the finite vertices of the Delaunay graph. More...
 
typedef unspecified_type Face_circulator
 A type for a circulator over the adjacent faces of a vertex of the Delaunay graph. More...
 
typedef unspecified_type Vertex_circulator
 A type for a circulator over the adjacent vertices of a vertex of the Delaunay graph. More...
 
typedef unspecified_type Edge_circulator
 A type for a circulator over the adjacent edges of a vertex of the Delaunay graph. More...
 

Creation

In addition to the default and copy constructors, as well as the assignment operator, the following constructors are required.

 DelaunayGraph_2 (Geom_traits gt)
 Constructor that takes an instance of the geometric traits.
 
template<class It >
 DelaunayGraph_2 (It first, It beyond)
 Constructor that takes an iterator range. More...
 
template<class It >
 DelaunayGraph_2 (It first, It beyond, Geom_traits gt)
 Constructor that takes an iterator range and an instance of the geometric traits. More...
 

Access methods

Triangulation_data_structure tds ()
 Returns a reference to the underlying triangulation data structure.
 
Geom_traits geom_traits ()
 Returns a reference to the geometric traits object.
 
Vertex_handle infinite_vertex ()
 Returns a handle to the infinite vertex.
 
Vertex_handle finite_vertex ()
 Returns a handle to a finite vertex, provided there exists one.
 
Face_handle infinite_face ()
 Returns a handle to a face incident to the infinite vertex.
 
int dimension ()
 Returns the dimension of the Delaunay graph.
 
size_type number_of_vertices ()
 Returns the number of finite vertices.
 
size_type number_of_faces ()
 Returns the number of faces (both finite and infinite).
 

Finite Face, Edge and Vertex Iterators

The following iterators must allow, respectively, to visit finite faces, finite edges and finite vertices of the Delaunay graph.

These iterators must be non-mutable, bidirectional and their value types are respectively Face, Edge and Vertex.

Finite_vertices_iterator finite_vertices_begin ()
 Starts at an arbitrary finite vertex.
 
Finite_vertices_iterator finite_vertices_end ()
 Past-the-end iterator.
 
Finite_edges_iterator finite_edges_begin ()
 Starts at an arbitrary finite edge.
 
Finite_edges_iterator finite_edges_end ()
 Past-the-end iterator.
 
Finite_faces_iterator finite_faces_begin ()
 Starts at an arbitrary finite face.
 
Finite_faces_iterator finite_faces_end () const
 Past-the-end iterator.
 

All Face, Edge and Vertex Iterators

The following iterators must allow, respectively, to visit all (both finite and infinite) faces, edges and vertices of the Delaunay graph.

These iterators are non-mutable, bidirectional and their value types are respectively Face, Edge and Vertex.

All_vertices_iterator all_vertices_begin ()
 Starts at an arbitrary vertex.
 
All_vertices_iterator all_vertices_end ()
 Past-the-end iterator.
 
All_edges_iterator all_edges_begin ()
 Starts at an arbitrary edge.
 
All_edges_iterator all_edges_end ()
 Past-the-end iterator.
 
All_faces_iterator all_faces_begin ()
 Starts at an arbitrary face.
 
All_faces_iterator all_faces_end ()
 Past-the-end iterator.
 

Face, Edge and Vertex Circulators

A model of the DelaunayGraph_2 concept must also provide circulators that allow to visit, respectively, all faces or edges incident to a given vertex or all vertices adjacent to a given vertex.

These circulators are non-mutable and bidirectional. The operator operator++ must move the circulator counterclockwise around the vertex while the operator- must move the circulator clockwise.

Face_circulator incident_faces (Vertex_handle v)
 Starts at an arbitrary face incident to v.
 
Face_circulator incident_faces (Vertex_handle v, Face_handle f)
 Starts at face f. More...
 
Edge_circulator incident_edges (Vertex_handle v)
 Starts at an arbitrary edge incident to v.
 
Edge_circulator incident_edges (Vertex_handle v, Face_handle f)
 Starts at the first edge of f incident to v, in counterclockwise order around v. More...
 
Vertex_circulator incident_vertices (Vertex_handle v)
 Starts at an arbitrary vertex incident to v.
 
Vertex_circulator incident_vertices (Vertex_handle v, Face_handle f)
 Starts at the first vertex of f adjacent to v in counterclockwise order around v. More...
 

Predicates

A model of the DelaunayGraph_2 concept must provide methods to test the finite or infinite character of any feature.

bool is_infinite (Vertex_handle v)
 true, iff v is the infinite_vertex.
 
bool is_infinite (Face_handle f)
 true, iff face f is infinite.
 
bool is_infinite (Face_handle f, int i)
 true, iff edge (f,i) is infinite.
 
bool is_infinite (Edge e)
 true, iff edge e is infinite.
 
bool is_infinite (Edge_circulator ec)
 true, iff edge *ec is infinite.
 

Validity check

bool is_valid (bool verbose=false)
 Checks the validity of the Delaunay graph. More...
 

Miscellaneous

void clear ()
 Clears all contents of the Delaunay graph.
 
void swap (DelaunayGraph_2 other)
 The Delaunay graphs other and dg are swapped. More...
 

Member Typedef Documentation

typedef unspecified_type DelaunayGraph_2::All_edges_iterator

A type for an iterator over all edges of the Delaunay graph.

Its value type must be Edge.

typedef unspecified_type DelaunayGraph_2::All_faces_iterator

A type for an iterator over all faces of the Delaunay graph.

Its value type must be Face.

typedef unspecified_type DelaunayGraph_2::All_vertices_iterator

A type for an iterator over all vertices of the Delaunay graph.

Its value type must be Vertex.

typedef unspecified_type DelaunayGraph_2::Edge_circulator

A type for a circulator over the adjacent edges of a vertex of the Delaunay graph.

Its value type must be Edge.

typedef unspecified_type DelaunayGraph_2::Face_circulator

A type for a circulator over the adjacent faces of a vertex of the Delaunay graph.

Its value type must be Face.

typedef unspecified_type DelaunayGraph_2::Finite_edges_iterator

A type for an iterator over the finite edges of the Delaunay graph.

Its value type must be Edge.

typedef unspecified_type DelaunayGraph_2::Finite_faces_iterator

A type for an iterator over the finite faces of the Delaunay graph.

Its value type must be Face.

typedef unspecified_type DelaunayGraph_2::Finite_vertices_iterator

A type for an iterator over the finite vertices of the Delaunay graph.

Its value type must be Vertex.

typedef unspecified_type DelaunayGraph_2::Triangulation_data_structure

A type for the underlying triangulation data structure.

It must be a model of the concept TriangulationDataStructure_2.

typedef unspecified_type DelaunayGraph_2::Vertex_circulator

A type for a circulator over the adjacent vertices of a vertex of the Delaunay graph.

Its value type must be Vertex.

Constructor & Destructor Documentation

template<class It >
DelaunayGraph_2::DelaunayGraph_2 ( It  first,
It  beyond 
)

Constructor that takes an iterator range.

The value type of the iterator must be the type of the sites of the Delaunay graph.

template<class It >
DelaunayGraph_2::DelaunayGraph_2 ( It  first,
It  beyond,
Geom_traits  gt 
)

Constructor that takes an iterator range and an instance of the geometric traits.

The value type of the iterator must be the type of the sites of the Delaunay graph.

Member Function Documentation

Edge_circulator DelaunayGraph_2::incident_edges ( Vertex_handle  v,
Face_handle  f 
)

Starts at the first edge of f incident to v, in counterclockwise order around v.

Precondition
Face f must be incident to vertex v.
Face_circulator DelaunayGraph_2::incident_faces ( Vertex_handle  v,
Face_handle  f 
)

Starts at face f.

Precondition
Face f must be incident to vertex v.
Vertex_circulator DelaunayGraph_2::incident_vertices ( Vertex_handle  v,
Face_handle  f 
)

Starts at the first vertex of f adjacent to v in counterclockwise order around v.

Precondition
Face f must be incident to vertex v.
bool DelaunayGraph_2::is_valid ( bool  verbose = false)

Checks the validity of the Delaunay graph.

If verbose is true a short message is sent to std::cerr.

void DelaunayGraph_2::swap ( DelaunayGraph_2  other)

The Delaunay graphs other and dg are swapped.

dg.swap(other) should be preferred to dg= other or to dg(other) if other is deleted afterwards.