CGAL 6.1.1 - 2D Apollonius Graphs (Delaunay Graphs of Disks)

Loading...
Searching...
No Matches
List of all members
CGAL::Apollonius_graph_hierarchy_2< Gt, Agds > Class Template Reference
Reference Manual

`#include <CGAL/Apollonius_graph_hierarchy_2.h>`

## Inherits from

CGAL::Apollonius_graph_2< Gt, Agds >.

## Definition

template<typename Gt, typename Agds>
class CGAL::Apollonius_graph_hierarchy_2< Gt, Agds >

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

  Gt | is the geometric traits class and must be a model of `ApolloniusGraphTraits_2`.
  Agds | is 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: CGAL::Triangulation_data_structure_2< CGAL::Apollonius_graph_hierarchy_vertex_base_2<CGAL::Apollonius_graph_vertex_base_2<Gt,true> >, CGAL::Triangulation_face_base_2<Gt> > CGAL::Apollonius_graph_hierarchy_vertex_base_2 The class Apollonius_graph_hierarchy_vertex_base_2 provides a model for the ApolloniusGraphHierarchyV... Definition: Apollonius_graph_hierarchy_vertex_base_2.h:21 CGAL::Triangulation_data_structure_2 CGAL::Triangulation_face_base_2

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.
Apollonius_graph_hierarchy_2< Gt, Agds > | operator= (Apollonius_graph_hierarchy_2< Gt, Agds > other)
| Assignment.

## Insertion
template<class Input_iterator >
unsigned int | insert (Input_iterator first, Input_iterator beyond)
| Inserts the sites in the range [`first`,`beyond`).
Vertex_handle | insert (const Site_2 &s)
| Inserts the site `s` in the Apollonius graph hierarchy.
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`.

## Removal
void | remove (Vertex_handle v)
| Removes the site associated to the vertex handle `v` from the Apollonius graph hierarchy.

## Nearest Neighbor Location
Vertex_handle | nearest_neighbor (const Point_2 &p) const
| Finds the nearest neighbor of the point `p`.
Vertex_handle | nearest_neighbor (const Point_2 &p, Vertex_handle vnear) const
| Finds the nearest neighbor of the point `p`.

## I/O
void | file_output (std::ostream &os) const
| Writes the current state of the Apollonius graph hierarchy to an output stream.
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.

## 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.

## 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.
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.
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`).
| Apollonius_graph_2 (const Apollonius_graph_2< Gt, Agds > &other)
| Copy constructor.
Apollonius_graph_2< Gt, Agds > | operator= (const Apollonius_graph_2< Gt, Agds > &other)
| Assignment.
const Geom_traits & | geom_traits () const
| Returns a reference to the Apollonius graph traits object.
const Data_structure & | data_structure () const
| Returns a reference to the underlying data structure.
const Data_structure & | tds () const
| Same as `data_structure()`.
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`.
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`.
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`.
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`.
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`).
Vertex_handle | insert (const Site_2 &s)
| Inserts the site `s` in the Apollonius graph.
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`.
void | remove (Vertex_handle v)
| Removes the site associated to the vertex handle `v` from the Apollonius graph.
Vertex_handle | nearest_neighbor (const Point_2 &p) const
| Finds the nearest neighbor of the point `p`.
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`.
Gt::Object_2 | dual (Face_handle f) const
| Returns the dual corresponding to the face handle `f`.
Gt::Object_2 | dual (All_faces_iterator it) const
| Returns the dual of the face to which `it` points to.
Site | dual (Finite_faces_iterator it) const
| Returns the dual of the face to which `it` points to.
template<class Stream >
Stream & | draw_primal (Stream &str) const
| Draws the Apollonius graph to the stream `str`.
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`.
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`.
template<class Stream >
Stream & | draw_dual_edge (const Edge &e, Stream &str) const
| Draws the dual of the edge `e` to the stream `str`.
void | file_output (std::ostream &os) const
| Writes the current state of the Apollonius graph to an output stream.
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.
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.

## 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 >

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() [2/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.

## ◆ insert() [3/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`.

## ◆ 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.