Apollonius_graph_2<Gt,Agds>

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

CGAL::Apollonius_graph_2<Gt,Agds>

Definition

The class Apollonius_graph_2<Gt,Agds> represents the Apollonius graph. It supports insertions and deletions of sites. It is templated by two template arguments Gt, which must be a model of ApolloniusGraphTraits_2, and Agds, which must be a model of ApolloniusGraphDataStructure_2. The second template argument defaults to CGAL::Triangulation_data_structure_2< CGAL::Apollonius_graph_vertex_base_2<Gt,true>, CGAL::Triangulation_face_base_2<Gt> >.

#include <CGAL/Apollonius_graph_2.h>

Types

typedef Agds Data_structure; A type for the underlying data structure.

typedef Gt Geom_traits; A type for the geometric traits.

typedef Gt::Point_2
Point_2; A type for the point defined in the geometric traits.

typedef Gt::Site_2 Site_2; A type for the Apollonius site, defined in the geometric traits.

The vertices and faces of the Apollonius graph are accessed through handles, iterators and circulators. The iterators and circulators are all bidirectional and non-mutable. The circulators and iterators are assignable to the corresponding handle types, and they are also convertible to the corresponding handles. The edges of the Apollonius graph can also be visited through iterators and circulators, the edge circulators and iterators are also bidirectional and non-mutable. In the following, we call infinite any face or edge incident to the infinite vertex and the infinite vertex itself. Any other feature (face, edge or vertex) of the Apollonius graph is said to be finite. Some iterators (the All iterators ) allow to visit finite or infinite features while the others (the Finite iterators) visit only finite features. Circulators visit both infinite and finite features.

typedef Data_structure::Edge
Edge; the edge type. The Edge(f,i) is the edge common to faces f and f.neighbor(i). It is also the edge joining the vertices vertex(cw(i)) and vertex(ccw(i)) of f.
Precondition: i must be 0, 1 or 2.

typedef Data_structure::Vertex_handle
Vertex_handle; A type for a handle to a vertex.

typedef Data_structure::Face_handle
Face_handle; A type for a handle to a face.

typedef Data_structure::Vertex_circulator
Vertex_circulator; A type for a circulator over vertices incident to a given vertex.

typedef Data_structure::Face_circulator
Face_circulator; A type for a circulator over faces incident to a given vertex.

typedef Data_structure::Edge_circulator
Edge_circulator; A type for a circulator over edges incident to a given vertex.

typedef Data_structure::All_vertices_iterator
All_vertices_iterator;
A type for an iterator over all vertices.

typedef Data_structure::Finite_vertices_iterator
Finite_vertices_iterator;
A type for an iterator over finite vertices.

typedef Data_structure::All_faces_iterator
All_faces_iterator; A type for an iterator over all faces.

typedef Data_structure::Finite_faces_iterator
Finite_faces_iterator;
A type for an iterator over finite faces.

typedef Data_structure::All_edges_iterator
All_edges_iterator; A type for an iterator over all edges.

typedef Data_structure::Finite_edges_iterator
Finite_edges_iterator;
A type for an iterator over finite edges.

typedef Data_structure::size_type
size_type; An unsigned integral type.

In addition to iterators and circulators for vertices and faces, iterators for sites are provided. In particular there are iterators for the entire set of sites, the hidden sites and the visible sites of the Apollonius graph.

Apollonius_graph_2<Gt,Agds>::Sites_iterator
A type for an iterator over all sites.

Apollonius_graph_2<Gt,Agds>::Visible_sites_iterator
A type for an iterator over all visible sites.

Apollonius_graph_2<Gt,Agds>::Hidden_sites_iterator
A type for an iterator over all hidden sites.

Creation

Apollonius_graph_2<Gt,Agds> ag ( Gt gt=Gt());

Creates an Apollonius graph using gt as geometric traits.

template< class Input_iterator >

Apollonius_graph_2<Gt,Agds> ag ( Input_iterator first,
Input_iterator beyond,
Gt gt=Gt());

Creates an Apollonius graph using gt as geometric traits and inserts all sites in the range [first, beyond).
Precondition: Input_iterator must be a model of InputIterator. The value type of Input_iterator must be Site_2.

Apollonius_graph_2<Gt,Agds> ag ( other);

Copy constructor. All faces and vertices are duplicated. After the construction, ag and other refer to two different Apollonius graphs : if other is modified, ag is not.

Apollonius_graph_2<Gt,Agds>
ag = other Assignment. If ag and other are the same object nothing is done. Otherwise, all the vertices and faces are duplicated. After the assignment, ag and other refer to different Apollonius graphs : if other is modified, ag is not.

Access Functions

Geom_traits	ag.geom_traits ()	Returns a reference to the Apollonius graph traits object.
int	ag.dimension ()	Returns the dimension of the Apollonius graph.
size_type	ag.number_of_vertices ()
		Returns the number of finite vertices.
size_type	ag.number_of_visible_sites ()
		Returns the number of visible sites.
size_type	ag.number_of_hidden_sites ()
		Returns the number of hidden sites.
size_type	ag.number_of_faces ()
		Returns the number of faces (both finite and infinite) of the Apollonius graph.
Face_handle	ag.infinite_face ()
		Returns a face incident to the infinite_vertex.
Vertex_handle	ag.infinite_vertex ()
		Returns the infinite_vertex.
Vertex_handle	ag.finite_vertex ()
		Returns a vertex distinct from the infinite_vertex. Precondition: The number of (visible) vertices in the Apollonius graph must be at least one.

Traversal of the Apollonius graph

An Apollonius graph can be seen as a container of faces and vertices. Therefore the Apollonius graph provides several iterators and circulators that allow to traverse it (completely or partially).

Face, Edge and Vertex Iterators

The following iterators allow respectively to visit finite faces, finite edges and finite vertices of the Apollonius graph. These iterators are non-mutable, bidirectional and their value types are respectively Face, Edge and Vertex. They are all invalidated by any change in the Apollonius graph.

Finite_vertices_iterator
ag.finite_vertices_begin ()
Starts at an arbitrary finite vertex.

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

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

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

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

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

The following iterators allow respectively to visit all (both finite and infinite) faces, edges and vertices of the Apollonius graph. These iterators are non-mutable, bidirectional and their value types are respectively Face, Edge and Vertex. They are all invalidated by any change in the Apollonius graph.

All_vertices_iterator
ag.all_vertices_begin ()
Starts at an arbitrary vertex.

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

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

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

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

All_faces_iterator ag.all_faces_end ()
Past-the-end iterator.

Site iterators

The following iterators allow respectively to visit all sites, the visible sites and the hidden sites. These iterators are non-mutable, bidirectional and their value type is Site_2. They are all invalidated by any change in the Apollonius graph.

Sites_iterator ag.sites_begin () Starts at an arbitrary site.

Sites_iterator ag.sites_end () Past-the-end iterator.

Visible_sites_iterator
ag.visible_sites_begin ()
Starts at an arbitrary visible site.

Visible_sites_iterator
ag.visible_sites_end ()
Past-the-end iterator.

Hidden_sites_iterator
ag.hidden_sites_begin ()
Starts at an arbitrary hidden site.

Hidden_sites_iterator
ag.hidden_sites_end ()
Past-the-end iterator.

Face, Edge and Vertex Circulators

The Apollonius graph also provides 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++ moves the circulator counterclockwise around the vertex while the operator-- moves clockwise. A face circulator is invalidated by any modification of the face pointed to. An edge circulator is invalidated by any modification in one of the two faces incident to the edge pointed to. A vertex circulator is invalidated by any modification in any of the faces adjacent to the vertex pointed to.

Face_circulator ag.incident_faces ( Vertex_handle v)
Starts at an arbitrary face incident to v.

Face_circulator ag.incident_faces ( Vertex_handle v, Face_handle f)
Starts at face f.
Precondition: Face f is incident to vertex v.

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

Edge_circulator ag.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 is incident to vertex v.

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

Vertex_circulator ag.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 is incident to vertex v.

Traversal of the Convex Hull

Applied on the infinite_vertex the above functions allow to visit the vertices on the convex hull and the infinite edges and faces. Note that a counterclockwise traversal of the vertices adjacent to the infinite_vertex is a clockwise traversal of the convex hull.

Vertex_circulator ag.incident_vertices ( ag.infinite_vertex())

Vertex_circulator
ag.incident_vertices ( ag.infinite_vertex(),
Face_handle f)

Face_circulator ag.incident_faces ( ag.infinite_vertex())

Face_circulator
ag.incident_faces ( ag.infinite_vertex(),
Face_handle f)

Edge_circulator ag.incident_edges ( ag.infinite_vertex())

Edge_circulator
ag.incident_edges ( ag.infinite_vertex(),
Face_handle f)

Predicates

The class Apollonius_graph_2<Gt,Agds> provides methods to test the finite or infinite character of any feature.

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

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

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

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

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

Insertion

template< class Input_iterator >

unsigned int
ag.insert ( Input_iterator first,
Input_iterator beyond)

Inserts the sites in the range [first,beyond). The number of sites in the range [first, beyond) is returned.
Precondition: Input_iterator must be a model of InputIterator and its value type must be Site_2.

Vertex_handle ag.insert ( Site_2 s)
Inserts the site s in the Apollonius graph. If s is visible then the vertex handle of s is returned, otherwise Vertex_handle(NULL) is returned.

Vertex_handle ag.insert ( Site_2 s, Vertex_handle vnear)
Inserts s in the Apollonius graph using the site associated with vnear as an estimate for the nearest neighbor of the center of s. If s is visible then the vertex handle of s is returned, otherwise Vertex_handle(NULL) is returned.

Removal

void	ag.remove ( Vertex_handle v)
		Removes the site associated to the vertex handle v from the Apollonius graph. Precondition: v must correspond to a valid finite vertex of the Apollonius graph.

Nearest neighbor location

Vertex_handle	ag.nearest_neighbor ( Point_2 p)
		Finds the nearest neighbor of the point p. In other words it finds the site whose Apollonius cell contains p. Ties are broken arbitrarily and one of the nearest neighbors of p is returned. If there are no visible sites in the Apollonius diagram Vertex_handle(NULL) is returned.
Vertex_handle	ag.nearest_neighbor ( Point_2 p, Vertex_handle vnear)
		Finds the nearest neighbor of the point p using the site associated with vnear as an estimate for the nearest neighbor of p. Ties are broken arbitrarily and one of the nearest neighbors of p is returned. If there are no visible sites in the Apollonius diagram Vertex_handle(NULL) is returned.

Access to the dual

The Apollonius_graph_2 class provides access to the duals of the faces of the graph. The dual of a face of the Apollonius graph is a site. If the originating face is infinite, its dual is a site with center at infinity (or equivalently with infinite weight), which means that it can be represented geometrically as a line. If the originating face is finite, its dual is a site with finite center and weight. In the following three methods the returned object is assignable to either Site_2 or Gt::Line_2, depending on whether the corresponding face of the Apollonius graph is finite or infinite, respectively.

Gt::Object_2 ag.dual ( Face_handle f)
Returns the dual corresponding to the face handle f. The returned object can be assignable to one of the following: Site_2, Gt::Line_2.

Gt::Object_2 ag.dual ( All_faces_iterator it)
Returns the dual of the face to which it points to. The returned object can be assignable to one of the following: Site_2, Gt::Line_2.

Gt::Object_2 ag.dual ( Finite_faces_iterator it)
Returns the dual of the face to which it points to. The returned object can be assignable to one of the following: Site_2, Gt::Line_2.

I/O

template< class Stream >
Stream&	ag.draw_primal ( Stream& str)
		Draws the Apollonius graph to the stream str. Precondition: The following operators must be defined: Stream& operator<<(Stream&, Gt::Segment_2), Stream& operator<<(Stream&, Gt::Ray_2).
template < class Stream >
Stream&	ag.draw_dual ( Stream& str)
		Draws the dual of the Apollonius graph, i.e., the Apollonius diagram, to the stream str. Precondition: The following operators must be defined: Stream& operator<<(Stream&, Gt::Segment_2), Stream& operator<<(Stream&, Gt::Ray_2), Stream& operator<<(Stream&, Gt::Line_2).
template< class Stream >
Stream&	ag.draw_primal_edge ( Edge e, Stream& str)
		Draws the edge e of the Apollonius graph to the stream str. Precondition: The following operators must be defined: Stream& operator<<(Stream&, Gt::Segment_2), Stream& operator<<(Stream&, Gt::Ray_2).
template< class Stream >
Stream&	ag.draw_dual_edge ( Edge e, Stream& str)
		Draws the dual of the edge e to the stream str. The dual of e is an edge of the Apollonius diagram. Precondition: The following operators must be defined: Stream& operator<<(Stream&, Gt::Segment_2), Stream& operator<<(Stream&, Gt::Ray_2), Stream& operator<<(Stream&, Gt::Line_2).

Validity check

bool	ag.is_valid ( bool verbose = false, int level = 1)
		Checks the validity of the Apollonius graph. If verbose is true a short message is sent to std::cerr. If level is 0, only the data structure is validated. If level is 1, then both the data structure and the Apollonius graph are validated. Negative values of level always return true, and values greater then 1 are equivalent to level being 1.

Miscellaneous

void	ag.clear ()	Clears all contents of the Apollonius graph.
void	ag.swap ( other)	The Apollonius graphs other and ag are swapped. ag.swap(other) should be preferred to ag = other or to ag(other) if other is deleted afterwards.

typedef Agds	Data_structure;	A type for the underlying data structure.
typedef Gt	Geom_traits;	A type for the geometric traits.
typedef Gt::Point_2
	Point_2;	A type for the point defined in the geometric traits.
typedef Gt::Site_2	Site_2;	A type for the Apollonius site, defined in the geometric traits.

typedef Data_structure::Edge
	Edge;	the edge type. The Edge(f,i) is the edge common to faces f and f.neighbor(i). It is also the edge joining the vertices vertex(cw(i)) and vertex(ccw(i)) of f. Precondition: i must be 0, 1 or 2.
typedef Data_structure::Vertex_handle
	Vertex_handle;	A type for a handle to a vertex.
typedef Data_structure::Face_handle
	Face_handle;	A type for a handle to a face.
typedef Data_structure::Vertex_circulator
	Vertex_circulator;	A type for a circulator over vertices incident to a given vertex.
typedef Data_structure::Face_circulator
	Face_circulator;	A type for a circulator over faces incident to a given vertex.
typedef Data_structure::Edge_circulator
	Edge_circulator;	A type for a circulator over edges incident to a given vertex.
typedef Data_structure::All_vertices_iterator
	All_vertices_iterator;
		A type for an iterator over all vertices.
typedef Data_structure::Finite_vertices_iterator
	Finite_vertices_iterator;
		A type for an iterator over finite vertices.
typedef Data_structure::All_faces_iterator
	All_faces_iterator;	A type for an iterator over all faces.
typedef Data_structure::Finite_faces_iterator
	Finite_faces_iterator;
		A type for an iterator over finite faces.
typedef Data_structure::All_edges_iterator
	All_edges_iterator;	A type for an iterator over all edges.
typedef Data_structure::Finite_edges_iterator
	Finite_edges_iterator;
		A type for an iterator over finite edges.
typedef Data_structure::size_type
	size_type;	An unsigned integral type.

Apollonius_graph_2<Gt,Agds>::Sites_iterator
	A type for an iterator over all sites.
Apollonius_graph_2<Gt,Agds>::Visible_sites_iterator
	A type for an iterator over all visible sites.
Apollonius_graph_2<Gt,Agds>::Hidden_sites_iterator
	A type for an iterator over all hidden sites.

Apollonius_graph_2<Gt,Agds>
	ag = other	Assignment. If ag and other are the same object nothing is done. Otherwise, all the vertices and faces are duplicated. After the assignment, ag and other refer to different Apollonius graphs : if other is modified, ag is not.

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

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

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

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

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

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

Sites_iterator	ag.sites_begin ()	Starts at an arbitrary site.
Sites_iterator	ag.sites_end ()	Past-the-end iterator.

Visible_sites_iterator
	ag.visible_sites_begin ()
		Starts at an arbitrary visible site.
Visible_sites_iterator
	ag.visible_sites_end ()
		Past-the-end iterator.

Hidden_sites_iterator
	ag.hidden_sites_begin ()
		Starts at an arbitrary hidden site.
Hidden_sites_iterator
	ag.hidden_sites_end ()
		Past-the-end iterator.

Face_circulator	ag.incident_faces ( Vertex_handle v)
		Starts at an arbitrary face incident to v.
Face_circulator	ag.incident_faces ( Vertex_handle v, Face_handle f)
		Starts at face f. Precondition: Face f is incident to vertex v.
Edge_circulator	ag.incident_edges ( Vertex_handle v)
		Starts at an arbitrary edge incident to v.
Edge_circulator	ag.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 is incident to vertex v.
Vertex_circulator	ag.incident_vertices ( Vertex_handle v)
		Starts at an arbitrary vertex incident to v.
Vertex_circulator	ag.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 is incident to vertex v.

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

Gt::Object_2	ag.dual ( Face_handle f)
		Returns the dual corresponding to the face handle f. The returned object can be assignable to one of the following: Site_2, Gt::Line_2.
Gt::Object_2	ag.dual ( All_faces_iterator it)
		Returns the dual of the face to which it points to. The returned object can be assignable to one of the following: Site_2, Gt::Line_2.
Gt::Object_2	ag.dual ( Finite_faces_iterator it)
		Returns the dual of the face to which it points to. The returned object can be assignable to one of the following: Site_2, Gt::Line_2.