CGAL 5.1.2 - 2D Apollonius Graphs (Delaunay Graphs of Disks)
|
#include <CGAL/Apollonius_graph_2.h>
Inherited by CGAL::Apollonius_graph_hierarchy_2< Gt, Agds >.
The class Apollonius_graph_2
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> >
.
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).
Traversal of the Convex Hull
Applied on the infinite_vertex
the incident_*
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.
DelaunayGraph_2
ApolloniusGraphTraits_2
ApolloniusGraphDataStructure_2
ApolloniusGraphVertexBase_2
TriangulationFaceBase_2
CGAL::Apollonius_graph_traits_2<K,Method_tag>
CGAL::Apollonius_graph_filtered_traits_2<CK,CM,EK,EM,FK,FM>
CGAL::Triangulation_data_structure_2<Vb,Fb>
CGAL::Apollonius_graph_vertex_base_2<Gt,StoreHidden>
CGAL::Triangulation_face_base_2<Gt>
Types | |
typedef Agds | Data_structure |
A type for the underlying data structure. | |
typedef Data_structure | Triangulation_data_structure |
Same as the Data_structure type. More... | |
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. | |
Handles And Iterators | |
The vertices and faces of the Apollonius graph are accessed through 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 | |
typedef Data_structure::Edge | Edge |
the edge type. More... | |
typedef Data_structure::Vertex | Vertex |
A type for a vertex. | |
typedef Data_structure::Face | Face |
A type for a face. | |
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::Vertex_iterator | All_vertices_iterator |
A type for an iterator over all vertices. | |
typedef Data_structure::Face_iterator | All_faces_iterator |
A type for an iterator over all faces. | |
typedef Data_structure::Edge_iterator | All_edges_iterator |
A type for an iterator over all edges. | |
typedef Data_structure::size_type | size_type |
An unsigned integral type. | |
typedef unspecified_type | Finite_vertices_iterator |
A type for an iterator over finite vertices. | |
typedef unspecified_type | Finite_faces_iterator |
A type for an iterator over finite faces. | |
typedef unspecified_type | Finite_edges_iterator |
A type for an iterator over finite edges. | |
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 | |
typedef unspecified_type | Sites_iterator |
A type for an iterator over all sites. | |
typedef unspecified_type | Visible_sites_iterator |
A type for an iterator over all visible sites. | |
typedef unspecified_type | Hidden_sites_iterator |
A type for an iterator over all hidden sites. | |
Sites_iterator | sites_begin () |
Starts at an arbitrary site. | |
Sites_iterator | sites_end () |
Past-the-end iterator. | |
Visible_sites_iterator | visible_sites_begin () |
Starts at an arbitrary visible site. | |
Visible_sites_iterator | visible_sites_end () |
Past-the-end iterator. | |
Hidden_sites_iterator | hidden_sites_begin () |
Starts at an arbitrary hidden site. | |
Hidden_sites_iterator | hidden_sites_end () |
Past-the-end iterator. | |
Creation | |
Apollonius_graph_2 (Gt gt=Gt()) | |
Creates an Apollonius graph ag using gt as geometric traits. | |
template<class Input_iterator > | |
Apollonius_graph_2 (Input_iterator first, Input_iterator beyond, Gt gt=Gt()) | |
Creates an Apollonius graph ag using gt as geometric traits and inserts all sites in the range [first , beyond ). More... | |
Apollonius_graph_2 (const Apollonius_graph_2< Gt, Agds > &other) | |
Copy constructor. More... | |
Apollonius_graph_2< Gt, Agds > | operator= (const Apollonius_graph_2< Gt, Agds > &other) |
Assignment. More... | |
Access Functions | |
Geom_traits | geom_traits () |
Returns a reference to the Apollonius graph traits object. | |
Data_structure | data_structure () |
Returns a reference to the underlying data structure. | |
Data_structure | tds () |
Same as data_structure() . More... | |
int | dimension () |
Returns the dimension of the Apollonius graph. | |
size_type | number_of_vertices () |
Returns the number of finite vertices. | |
size_type | number_of_visible_sites () |
Returns the number of visible sites. | |
size_type | number_of_hidden_sites () |
Returns the number of hidden sites. | |
size_type | number_of_faces () |
Returns the number of faces (both finite and infinite) of the Apollonius graph. | |
Face_handle | infinite_face () |
Returns a face incident to the infinite_vertex . | |
Vertex_handle | infinite_vertex () |
Returns the infinite_vertex . | |
Vertex_handle | finite_vertex () |
Returns a vertex distinct from the infinite_vertex . More... | |
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 | |
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_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 | |
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 | |
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 | |
The class | |
bool | is_infinite (Vertex_handle v) const |
true , iff v is the infinite_vertex . | |
bool | is_infinite (Face_handle f) const |
true , iff face f is infinite. | |
bool | is_infinite (Face_handle f, int i) const |
true , iff edge (f,i) is infinite. | |
bool | is_infinite (Edge e) const |
true , iff edge e is infinite. | |
bool | is_infinite (Edge_circulator ec) const |
true , iff edge *ec is infinite. | |
Insertion | |
template<class Input_iterator > | |
unsigned int | insert (Input_iterator first, Input_iterator beyond) |
Inserts the sites in the range [first ,beyond ). More... | |
Vertex_handle | insert (Site_2 s) |
Inserts the site s in the Apollonius graph. More... | |
Vertex_handle | 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 . More... | |
Removal | |
void | remove (Vertex_handle v) |
Removes the site associated to the vertex handle v from the Apollonius graph. More... | |
Nearest Neighbor Location | |
Vertex_handle | nearest_neighbor (Point_2 p) |
Finds the nearest neighbor of the point p . More... | |
Vertex_handle | 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 . More... | |
Access to the Dual | |
The 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 | |
Gt::Object_2 | dual (Face_handle f) const |
Returns the dual corresponding to the face handle f . More... | |
Gt::Object_2 | dual (All_faces_iterator it) const |
Returns the dual of the face to which it points to. More... | |
Gt::Object_2 | dual (Finite_faces_iterator it) const |
Returns the dual of the face to which it points to. More... | |
I/O | |
template<class Stream > | |
Stream & | draw_primal (Stream &str) |
Draws the Apollonius graph to the stream str . More... | |
template<class Stream > | |
Stream & | draw_dual (Stream &str) |
Draws the dual of the Apollonius graph, i.e., the Apollonius diagram, to the stream str . More... | |
template<class Stream > | |
Stream & | draw_primal_edge (Edge e, Stream &str) |
Draws the edge e of the Apollonius graph to the stream str . More... | |
template<class Stream > | |
Stream & | draw_dual_edge (Edge e, Stream &str) |
Draws the dual of the edge e to the stream str . More... | |
void | file_output (std::ostream &os) |
Writes the current state of the Apollonius graph to an output stream. More... | |
void | file_input (std::istream &is) |
Reads the state of the Apollonius graph from an input stream. | |
std::ostream & | operator<< (std::ostream &os, Apollonius_graph_2< Gt, Agds > ag) |
Writes the current state of the Apollonius graph to an output stream. | |
std::istream & | operator>> (std::istream &is, Apollonius_graph_2< Gt, Agds > ag) |
Reads the state of the Apollonius graph from an input stream. | |
Validity Check | |
bool | is_valid (bool verbose=false, int level=1) |
Checks the validity of the Apollonius graph. More... | |
Miscellaneous | |
void | clear () |
Clears all contents of the Apollonius graph. | |
void | swap (Apollonius_graph_2< Gt, Agds > other) |
The Apollonius graphs other and ag are swapped. More... | |
typedef Data_structure::Edge CGAL::Apollonius_graph_2< Gt, Agds >::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
.
i
must be 0
, 1
or 2
. typedef Data_structure CGAL::Apollonius_graph_2< Gt, Agds >::Triangulation_data_structure |
Same as the Data_structure
type.
This type has been introduced in order for the Apollonius_graph_2
class to be a model of the DelaunayGraph_2
concept.
CGAL::Apollonius_graph_2< Gt, Agds >::Apollonius_graph_2 | ( | Input_iterator | first, |
Input_iterator | beyond, | ||
Gt | gt = Gt() |
||
) |
Creates an Apollonius graph ag
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 Site_2
. CGAL::Apollonius_graph_2< Gt, Agds >::Apollonius_graph_2 | ( | const Apollonius_graph_2< Gt, Agds > & | 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.
Stream& CGAL::Apollonius_graph_2< Gt, Agds >::draw_dual | ( | Stream & | str | ) |
Draws the dual of the Apollonius graph, i.e., the Apollonius diagram, to the stream str
.
Stream& operator<<(Stream&, Gt::Segment_2)
, Stream& operator<<(Stream&, Gt::Ray_2)
, Stream& operator<<(Stream&, Gt::Line_2)
. Stream& CGAL::Apollonius_graph_2< Gt, Agds >::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.
Stream& operator<<(Stream&, Gt::Segment_2)
, Stream& operator<<(Stream&, Gt::Ray_2)
, Stream& operator<<(Stream&, Gt::Line_2)
. Stream& CGAL::Apollonius_graph_2< Gt, Agds >::draw_primal | ( | Stream & | str | ) |
Draws the Apollonius graph to the stream str
.
Stream& operator<<(Stream&, Gt::Segment_2)
, Stream& operator<<(Stream&, Gt::Ray_2)
. Stream& CGAL::Apollonius_graph_2< Gt, Agds >::draw_primal_edge | ( | Edge | e, |
Stream & | str | ||
) |
Draws the edge e
of the Apollonius graph to the stream str
.
Stream& operator<<(Stream&, Gt::Segment_2)
, Stream& operator<<(Stream&, Gt::Ray_2)
. Gt::Object_2 CGAL::Apollonius_graph_2< Gt, Agds >::dual | ( | Face_handle | f | ) | const |
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 CGAL::Apollonius_graph_2< Gt, Agds >::dual | ( | All_faces_iterator | it | ) | const |
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 CGAL::Apollonius_graph_2< Gt, Agds >::dual | ( | Finite_faces_iterator | it | ) | const |
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
.
void CGAL::Apollonius_graph_2< Gt, Agds >::file_output | ( | std::ostream & | os | ) |
Writes the current state of the Apollonius graph to an output stream.
In particular, all visible and hidden sites are written as well as the underlying combinatorial data structure.
Vertex_handle CGAL::Apollonius_graph_2< Gt, Agds >::finite_vertex | ( | ) |
Returns a vertex distinct from the infinite_vertex
.
Edge_circulator CGAL::Apollonius_graph_2< Gt, Agds >::incident_edges | ( | Vertex_handle | v, |
Face_handle | f | ||
) |
Starts at the first edge of f
incident to v
, in counterclockwise order around v
.
f
is incident to vertex v
. Face_circulator CGAL::Apollonius_graph_2< Gt, Agds >::incident_faces | ( | Vertex_handle | v, |
Face_handle | f | ||
) |
Starts at face f
.
f
is incident to vertex v
. Vertex_circulator CGAL::Apollonius_graph_2< Gt, Agds >::incident_vertices | ( | Vertex_handle | v, |
Face_handle | f | ||
) |
Starts at the first vertex of f
adjacent to v
in counterclockwise order around v
.
f
is incident to vertex v
. unsigned int CGAL::Apollonius_graph_2< Gt, Agds >::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.
Input_iterator
must be a model of InputIterator
and its value type must be Site_2
. Vertex_handle CGAL::Apollonius_graph_2< Gt, Agds >::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(nullptr)
is returned.
Vertex_handle CGAL::Apollonius_graph_2< Gt, Agds >::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(nullptr)
is returned.
bool CGAL::Apollonius_graph_2< Gt, Agds >::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.
Vertex_handle CGAL::Apollonius_graph_2< Gt, Agds >::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(nullptr)
is returned.
Vertex_handle CGAL::Apollonius_graph_2< Gt, Agds >::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(nullptr)
is returned.
Apollonius_graph_2<Gt,Agds> CGAL::Apollonius_graph_2< Gt, Agds >::operator= | ( | const Apollonius_graph_2< Gt, Agds > & | 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.
void CGAL::Apollonius_graph_2< Gt, Agds >::remove | ( | Vertex_handle | v | ) |
Removes the site associated to the vertex handle v
from the Apollonius graph.
v
must correspond to a valid finite vertex of the Apollonius graph. void CGAL::Apollonius_graph_2< Gt, Agds >::swap | ( | Apollonius_graph_2< Gt, Agds > | 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.
Data_structure CGAL::Apollonius_graph_2< Gt, Agds >::tds | ( | ) |
Same as data_structure()
.
This method has been added in compliance with the DelaunayGraph_2
concept.