CGAL 5.5 - 2D Apollonius Graphs (Delaunay Graphs of Disks)
CGAL::Apollonius_graph_hierarchy_2< Gt, Agds > Class Template Reference

#include <CGAL/Apollonius_graph_hierarchy_2.h>

Inherits from

CGAL::Apollonius_graph_2< Gt, Agds >.

Definition

We provide an alternative to the class Apollonius_graph_2<Gt,Agds> for the dynamic construction of the Apollonius graph.

The Apollonius_graph_hierarchy_2 class maintains a hierarchy of Apollonius graphs. The bottom-most level of the hierarchy contains the full Apollonius diagram. A site that is in level \( i\), is in level \( i+1\) with probability \( 1/\alpha\) where \( \alpha > 1\) is some constant. The difference between the Apollonius_graph_2<Gt,Agds> class and the Apollonius_graph_hierarchy_2 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 Apollonius_graph_2<Gt,Agds> 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 [2].

The class has two template parameters which have essentially the same meaning as in the Apollonius_graph_2<Gt,Agds> class.

Template Parameters
Gtis the geometric traits class and must be a model of ApolloniusGraphTraits_2.
Agdsis the Apollonius graph data structure and must be a model of ApolloniusGraphDataStructure_2 whose vertex and face must be models of ApolloniusGraphHierarchyVertexBase_2 and TriangulationFaceBase_2, respectively. It defaults to:

Heritage

The Apollonius_graph_hierarchy_2 class derives publicly from the Apollonius_graph_2<Gt,Agds> class. The interface is the same with its base class. In the sequel only the methods overridden are documented.

Apollonius_graph_hierarchy_2 does not introduce other types than those introduced by its base class Apollonius_graph_2<Gt,Agds>.

See also
CGAL::Apollonius_graph_2<Gt,Agds>
CGAL::Apollonius_graph_traits_2<K,Method_tag>
CGAL::Apollonius_graph_filtered_traits_2<CK,CM,EK,EM,FK,FM>
Examples:
Apollonius_graph_2/ag2_hierarchy.cpp.

Creation

 Apollonius_graph_hierarchy_2 (Gt gt=Gt())
 Creates an hierarchy of Apollonius graphs using gt as geometric traits.
 
template<class Input_iterator >
 Apollonius_graph_hierarchy_2 (Input_iterator first, Input_iterator beyond, Gt gt=Gt())
 Creates an Apollonius graph hierarchy using gt as geometric traits and inserts all sites in the range [first, beyond).
 
 Apollonius_graph_hierarchy_2 (const Apollonius_graph_hierarchy_2< Gt, Agds > &other)
 Copy constructor. More...
 
Apollonius_graph_hierarchy_2< Gt, Agds > operator= (Apollonius_graph_hierarchy_2< Gt, Agds > other)
 Assignment. More...
 

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 (const Site_2 &s)
 Inserts the site s in the Apollonius graph hierarchy. More...
 
Vertex_handle insert (const Site_2 &s, Vertex_handle vnear)
 Inserts s in the Apollonius graph hierarchy 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 hierarchy. More...
 

Nearest Neighbor Location

Vertex_handle nearest_neighbor (const Point_2 &p) const
 Finds the nearest neighbor of the point p. More...
 
Vertex_handle nearest_neighbor (const Point_2 &p, Vertex_handle vnear) const
 Finds the nearest neighbor of the point p. More...
 

I/O

void file_output (std::ostream &os) const
 Writes the current state of the Apollonius graph hierarchy to an output stream. More...
 
void file_input (std::istream &is)
 Reads the state of the Apollonius graph hierarchy from an input stream.
 
std::ostream & operator<< (std::ostream &os, Apollonius_graph_hierarchy_2< Gt, Agds > agh) const
 Writes the current state of the Apollonius graph hierarchy to an output stream.
 
std::istream & operator>> (std::istream &is, Apollonius_graph_hierarchy_2< Gt, Agds > agh)
 Reads the state of the Apollonius graph hierarchy from an input stream.
 

Validity Check

bool is_valid (bool verbose=false, int level=1) const
 Checks the validity of the Apollonius graph hierarchy. More...
 

Miscellaneous

void clear ()
 Clears all contents of the Apollonius graph hierarchy.
 
void swap (Apollonius_graph_hierarchy_2< Gt, Agds > &other)
 The Apollonius graph hierarchies other and agh are swapped. More...
 

Additional Inherited Members

- Public Types inherited from CGAL::Apollonius_graph_2< Gt, Agds >
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.
 
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.
 
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.
 
- Public Member Functions inherited from CGAL::Apollonius_graph_2< Gt, Agds >
Sites_iterator sites_begin () const
 Starts at an arbitrary site.
 
Sites_iterator sites_end () const
 Past-the-end iterator.
 
Visible_sites_iterator visible_sites_begin () const
 Starts at an arbitrary visible site.
 
Visible_sites_iterator visible_sites_end () const
 Past-the-end iterator.
 
Hidden_sites_iterator hidden_sites_begin () const
 Starts at an arbitrary hidden site.
 
Hidden_sites_iterator hidden_sites_end () const
 Past-the-end iterator.
 
 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...
 
const Geom_traitsgeom_traits () const
 Returns a reference to the Apollonius graph traits object.
 
const Data_structuredata_structure () const
 Returns a reference to the underlying data structure.
 
const Data_structuretds () const
 Same as data_structure(). More...
 
int dimension () const
 Returns the dimension of the Apollonius graph.
 
size_type number_of_vertices () const
 Returns the number of finite vertices.
 
size_type number_of_visible_sites () const
 Returns the number of visible sites.
 
size_type number_of_hidden_sites () const
 Returns the number of hidden sites.
 
size_type number_of_faces () const
 Returns the number of faces (both finite and infinite) of the Apollonius graph.
 
Face_handle infinite_face () const
 Returns a face incident to the infinite_vertex.
 
Vertex_handle infinite_vertex () const
 Returns the infinite_vertex.
 
Vertex_handle finite_vertex () const
 Returns a vertex distinct from the infinite_vertex. More...
 
Finite_vertices_iterator finite_vertices_begin () const
 Starts at an arbitrary finite vertex.
 
Finite_vertices_iterator finite_vertices_end () const
 Past-the-end iterator.
 
Finite_edges_iterator finite_edges_begin () const
 Starts at an arbitrary finite edge.
 
Finite_edges_iterator finite_edges_end () const
 Past-the-end iterator.
 
Finite_faces_iterator finite_faces_begin () const
 Starts at an arbitrary finite face.
 
Finite_faces_iterator finite_faces_end () const
 Past-the-end iterator.
 
All_vertices_iterator all_vertices_begin () const
 Starts at an arbitrary vertex.
 
All_vertices_iterator all_vertices_end () const
 Past-the-end iterator.
 
All_edges_iterator all_edges_begin () const
 Starts at an arbitrary edge.
 
All_edges_iterator all_edges_end () const
 Past-the-end iterator.
 
All_faces_iterator all_faces_begin () const
 Starts at an arbitrary face.
 
All_faces_iterator all_faces_end () const
 Past-the-end iterator.
 
Face_circulator incident_faces (Vertex_handle v) const
 Starts at an arbitrary face incident to v.
 
Face_circulator incident_faces (Vertex_handle v, Face_handle f) const
 Starts at face f. More...
 
Edge_circulator incident_edges (Vertex_handle v) const
 Starts at an arbitrary edge incident to v.
 
Edge_circulator incident_edges (Vertex_handle v, Face_handle f) const
 Starts at the first edge of f incident to v, in counterclockwise order around v. More...
 
Vertex_circulator incident_vertices (Vertex_handle v) const
 Starts at an arbitrary vertex incident to v.
 
Vertex_circulator incident_vertices (Vertex_handle v, Face_handle f) const
 Starts at the first vertex of f adjacent to v in counterclockwise order around v. More...
 
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 (const Edge &e) const
 true, iff edge e is infinite.
 
bool is_infinite (Edge_circulator ec) const
 true, iff edge *ec is infinite.
 
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 (const Site_2 &s)
 Inserts the site s in the Apollonius graph. More...
 
Vertex_handle insert (const 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...
 
void remove (Vertex_handle v)
 Removes the site associated to the vertex handle v from the Apollonius graph. More...
 
Vertex_handle nearest_neighbor (const Point_2 &p) const
 Finds the nearest neighbor of the point p. More...
 
Vertex_handle nearest_neighbor (const Point_2 &p, Vertex_handle vnear) const
 Finds the nearest neighbor of the point p using the site associated with vnear as an estimate for the nearest neighbor of p. More...
 
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...
 
template<class Stream >
Stream & draw_primal (Stream &str) const
 Draws the Apollonius graph to the stream str. More...
 
template<class Stream >
Stream & draw_dual (Stream &str) const
 Draws the dual of the Apollonius graph, i.e., the Apollonius diagram, to the stream str. More...
 
template<class Stream >
Stream & draw_primal_edge (const Edge &e, Stream &str) const
 Draws the edge e of the Apollonius graph to the stream str. More...
 
template<class Stream >
Stream & draw_dual_edge (const Edge &e, Stream &str) const
 Draws the dual of the edge e to the stream str. More...
 
void file_output (std::ostream &os) const
 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, const Apollonius_graph_2< Gt, Agds > &ag) const
 Writes the current state of the Apollonius graph to an output stream.
 
std::istream & operator>> (std::istream &is, const Apollonius_graph_2< Gt, Agds > &ag)
 Reads the state of the Apollonius graph from an input stream.
 
bool is_valid (bool verbose=false, int level=1) const
 Checks the validity of the Apollonius graph. More...
 
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...
 

Constructor & Destructor Documentation

◆ Apollonius_graph_hierarchy_2()

template<typename Gt , typename Agds >
CGAL::Apollonius_graph_hierarchy_2< Gt, Agds >::Apollonius_graph_hierarchy_2 ( const Apollonius_graph_hierarchy_2< Gt, Agds > &  other)

Copy constructor.

All faces, vertices, and inter-level pointers are duplicated. After the construction, agh and other refer to two different Apollonius graph hierarchies: if other is modified, agh is not.

Member Function Documentation

◆ file_output()

template<typename Gt , typename Agds >
void CGAL::Apollonius_graph_hierarchy_2< Gt, Agds >::file_output ( std::ostream &  os) const

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

In particular, all visible and hidden sites are written as well as the underlying combinatorial hierarchical data structure.

◆ insert() [1/3]

template<typename Gt , typename Agds >
template<class Input_iterator >
unsigned int CGAL::Apollonius_graph_hierarchy_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.

Precondition
Input_iterator must be a model of InputIterator and its value type must be Site_2.

◆ insert() [2/3]

template<typename Gt , typename Agds >
Vertex_handle CGAL::Apollonius_graph_hierarchy_2< Gt, Agds >::insert ( const Site_2 s)

Inserts the site s in the Apollonius graph hierarchy.

If s is visible then the vertex handle of s is returned, otherwise Vertex_handle(nullptr) is returned.

◆ insert() [3/3]

template<typename Gt , typename Agds >
Vertex_handle CGAL::Apollonius_graph_hierarchy_2< Gt, Agds >::insert ( const Site_2 s,
Vertex_handle  vnear 
)

Inserts s in the Apollonius graph hierarchy 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. A call to this method is equivalent to agh.insert(s); and it has been added for the sake of conformity with the interface of the Apollonius_graph_2<Gt,Agds> class.

◆ is_valid()

template<typename Gt , typename Agds >
bool CGAL::Apollonius_graph_hierarchy_2< Gt, Agds >::is_valid ( bool  verbose = false,
int  level = 1 
) const

Checks the validity of the Apollonius graph hierarchy.

If verbose is true a short message is sent to std::cerr. If level is 0, the data structure at all levels is validated, as well as the inter-level pointers. If level is 1, then the data structure at all levels is validated, the inter-level pointers are validated and all levels of the Apollonius graph hierarchy are also validated. Negative values of level always return true, and values greater than 1 are equivalent to level being 1.

◆ nearest_neighbor() [1/2]

template<typename Gt , typename Agds >
Vertex_handle CGAL::Apollonius_graph_hierarchy_2< Gt, Agds >::nearest_neighbor ( const Point_2 p) const

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.

◆ nearest_neighbor() [2/2]

template<typename Gt , typename Agds >
Vertex_handle CGAL::Apollonius_graph_hierarchy_2< Gt, Agds >::nearest_neighbor ( const Point_2 p,
Vertex_handle  vnear 
) const

Finds the nearest neighbor of the point p.

If there are no visible sites in the Apollonius diagram Vertex_handle(nullptr) is returned. A call to this method is equivalent to agh.nearest_neighbor(p); and it has been added for the sake of conformity with the interface of the Apollonius_graph_2<Gt,Agds> class.

◆ operator=()

template<typename Gt , typename Agds >
Apollonius_graph_hierarchy_2<Gt,Agds> CGAL::Apollonius_graph_hierarchy_2< Gt, Agds >::operator= ( Apollonius_graph_hierarchy_2< Gt, Agds >  other)

Assignment.

All faces, vertices and inter-level pointers are duplicated. After the construction, agh and other refer to two different Apollonius graph hierarchies: if other is modified, agh is not.

◆ remove()

template<typename Gt , typename Agds >
void CGAL::Apollonius_graph_hierarchy_2< Gt, Agds >::remove ( Vertex_handle  v)

Removes the site associated to the vertex handle v from the Apollonius graph hierarchy.

Precondition
v must correspond to a valid finite vertex of the Apollonius graph hierarchy.

◆ swap()

template<typename Gt , typename Agds >
void CGAL::Apollonius_graph_hierarchy_2< Gt, Agds >::swap ( Apollonius_graph_hierarchy_2< Gt, Agds > &  other)

The Apollonius graph hierarchies other and agh are swapped.

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