DelaunayGraph

Navigation: Up, Table of Contents, Short Table of Contents, Package Overview, Bibliography, Index, Title Page

DelaunayGraph_2

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

Types

DelaunayGraph_2::size_type
	A type for sizes.
DelaunayGraph_2::Geom_traits
	A type for the geometric traits associated with the Delaunay graph.
DelaunayGraph_2::Triangulation_data_structure
	A type for the underlying triangulation data structure. It must be a model of the concept TriangulationDataStructure_2.
DelaunayGraph_2::Vertex
	A type for the vertices of the Delaunay graph.
DelaunayGraph_2::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.

DelaunayGraph_2::Vertex_handle
	Handle to the vertices of the Delaunay graph.
DelaunayGraph_2::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.

DelaunayGraph_2::All_edges_iterator
A type for an iterator over all edges of the Delaunay graph. Its value type must be Edge.

DelaunayGraph_2::Finite_edges_iterator
A type for an iterator over the finite edges of the Delaunay graph. Its value type must be Edge.

DelaunayGraph_2::All_faces_iterator
A type for an iterator over all faces of the Delaunay graph. Its value type must be Face.

DelaunayGraph_2::Finite_faces_iterator
A type for an iterator over the finite faces of the Delaunay graph. Its value type must be Face.

DelaunayGraph_2::All_vertices_iterator
A type for an iterator over all vertices of the Delaunay graph. Its value type must be Vertex.

DelaunayGraph_2::Finite_vertices_iterator
A type for an iterator over the finite vertices of the Delaunay graph. Its value type must be Vertex.

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.

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.

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.

Creation

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

DelaunayGraph_2 dg ( Geom_traits gt);
Constructor that takes an instance of the geometric traits.

template<class It>

DelaunayGraph_2 dg ( 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 dg ( 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.

Access methods

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

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.

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
dg.finite_vertices_begin ()
Starts at an arbitrary finite vertex.

Finite_vertices_iterator
dg.finite_vertices_end ()
Past-the-end iterator.

Finite_edges_iterator
dg.finite_edges_begin ()
Starts at an arbitrary finite edge.

Finite_edges_iterator
dg.finite_edges_end ()
Past-the-end iterator.

Finite_faces_iterator
dg.finite_faces_begin ()
Starts at an arbitrary finite face.

Finite_faces_iterator
dg.finite_faces_end ()
Past-the-end iterator.

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
dg.all_vertices_begin ()
Starts at an arbitrary vertex.

All_vertices_iterator
dg.all_vertices_end ()
Past-the-end iterator.

All_edges_iterator dg.all_edges_begin ()
Starts at an arbitrary edge.

All_edges_iterator dg.all_edges_end ()
Past-the-end iterator.

All_faces_iterator dg.all_faces_begin ()
Starts at an arbitrary face.

All_faces_iterator dg.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 dg.incident_faces ( Vertex_handle v)
Starts at an arbitrary face incident to v.

Face_circulator dg.incident_faces ( Vertex_handle v, Face_handle f)
Starts at face f.
Precondition: Face f must be incident to vertex v.

Edge_circulator dg.incident_edges ( Vertex_handle v)
Starts at an arbitrary edge incident to v.

Edge_circulator dg.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.

Vertex_circulator dg.incident_vertices ( Vertex_handle v)
Starts at an arbitrary vertex incident to v.

Vertex_circulator dg.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.

Predicates

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

bool dg.is_infinite ( Vertex_handle v)
true, iff v is the infinite_vertex.

bool dg.is_infinite ( Face_handle f)
true, iff face f is infinite.

bool dg.is_infinite ( Face_handle f, int i)
true, iff edge (f,i) is infinite.

bool dg.is_infinite ( Edge e)
true, iff edge e is infinite.

bool dg.is_infinite ( Edge_circulator ec)
true, iff edge *ec is infinite.

Validity check

bool	dg.is_valid ( bool verbose = false)
		Checks the validity of the Delaunay graph. If verbose is true a short message is sent to std::cerr.

Miscellaneous

void	dg.clear ()	Clears all contents of the Delaunay graph.
void	dg.swap ( 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.

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>

DelaunayGraph_2::All_edges_iterator
	A type for an iterator over all edges of the Delaunay graph. Its value type must be Edge.
DelaunayGraph_2::Finite_edges_iterator
	A type for an iterator over the finite edges of the Delaunay graph. Its value type must be Edge.
DelaunayGraph_2::All_faces_iterator
	A type for an iterator over all faces of the Delaunay graph. Its value type must be Face.
DelaunayGraph_2::Finite_faces_iterator
	A type for an iterator over the finite faces of the Delaunay graph. Its value type must be Face.
DelaunayGraph_2::All_vertices_iterator
	A type for an iterator over all vertices of the Delaunay graph. Its value type must be Vertex.
DelaunayGraph_2::Finite_vertices_iterator
	A type for an iterator over the finite vertices of the Delaunay graph. Its value type must be Vertex.
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.
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.
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.

DelaunayGraph_2 dg ( Geom_traits gt);
	Constructor that takes an instance of the geometric traits.
template<class It>
DelaunayGraph_2 dg ( 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 dg ( 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.

Finite_vertices_iterator
	dg.finite_vertices_begin ()
		Starts at an arbitrary finite vertex.
Finite_vertices_iterator
	dg.finite_vertices_end ()
		Past-the-end iterator.

Finite_edges_iterator
	dg.finite_edges_begin ()
		Starts at an arbitrary finite edge.
Finite_edges_iterator
	dg.finite_edges_end ()
		Past-the-end iterator.

Finite_faces_iterator
	dg.finite_faces_begin ()
		Starts at an arbitrary finite face.
Finite_faces_iterator
	dg.finite_faces_end ()
		Past-the-end iterator.

All_vertices_iterator
	dg.all_vertices_begin ()
		Starts at an arbitrary vertex.
All_vertices_iterator
	dg.all_vertices_end ()
		Past-the-end iterator.

All_edges_iterator	dg.all_edges_begin ()
		Starts at an arbitrary edge.
All_edges_iterator	dg.all_edges_end ()
		Past-the-end iterator.

All_faces_iterator	dg.all_faces_begin ()
		Starts at an arbitrary face.
All_faces_iterator	dg.all_faces_end ()
		Past-the-end iterator.

Face_circulator	dg.incident_faces ( Vertex_handle v)
		Starts at an arbitrary face incident to v.
Face_circulator	dg.incident_faces ( Vertex_handle v, Face_handle f)
		Starts at face f. Precondition: Face f must be incident to vertex v.

Edge_circulator	dg.incident_edges ( Vertex_handle v)
		Starts at an arbitrary edge incident to v.
Edge_circulator	dg.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.

Vertex_circulator	dg.incident_vertices ( Vertex_handle v)
		Starts at an arbitrary vertex incident to v.
Vertex_circulator	dg.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	dg.is_infinite ( Vertex_handle v)
		true, iff v is the infinite_vertex.
bool	dg.is_infinite ( Face_handle f)
		true, iff face f is infinite.
bool	dg.is_infinite ( Face_handle f, int i)
		true, iff edge (f,i) is infinite.
bool	dg.is_infinite ( Edge e)
		true, iff edge e is infinite.
bool	dg.is_infinite ( Edge_circulator ec)
		true, iff edge *ec is infinite.