The class Voronoi_diagram_2<DG,AT,AP> provides an adaptor that enables us
to view a triangulated Delaunay graph as their dual subdivision, the
Voronoi diagram. The class Voronoi_diagram_2<DG,AT,AP> is designed to provide an API
that is similar to that of CGAL's arrangements.
The first template parameter of the Voronoi_diagram_2<DG,AT,AP> class corresponds to the
triangulated Delaunay graph and must be a model of the
DelaunayGraph_2 concept. The second template parameter must be a
model of the AdaptationTraits_2 concept. The third template
parameter must be a model of the AdaptationPolicy_2 concept. The
third template parameter defaults to CGAL::Identity_policy_2<DG,AT>.
#include <CGAL/Voronoi_diagram_2.h>
|
| A type for the dual Delaunay graph. |
|
| A type for the adaptation traits needed by the Voronoi diagram adaptor. |
|
| A type for the adaptation policy used. |
| ||
| A type a point. | |
| ||
| A type for the sites of the Voronoi diagram. | |
| ||
| A type for sizes. | |
| ||
| ||
A type for the geometric traits of the Delaunay graph. | ||
| ||
| ||
A type for the vertex handles of the Delaunay graph. | ||
| ||
| ||
A type for the face handles of the Delaunay graph. | ||
| ||
| A type for the edges of the Delaunay graph. |
| |
A type for the halfedges of the Voronoi diagram.
| |
| |
A type for the vertices of the Voronoi diagram.
| |
| |
A type for the faces of the Voronoi diagram.
|
The vertices, edges and faces of the Voronoi diagram 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.
| |
Handle for halfedges.
| |
| |
Handle for vertices.
| |
| |
Handle for faces.
| |
| |
A type for an iterator over Voronoi
edges. Edges are considered non-oriented. Its value type is
Halfedge.
| |
| |
A type for an iterator over Voronoi
halfedges. Halfedges are oriented and come in pairs. Its value type
is Halfedge.
| |
| |
A type for an iterator over Voronoi
faces. Its value type is Face.
| |
| |
A type for an iterator over Voronoi
vertices. Its value type is Vertex.
| |
| |
A type for a
circulator over the halfedges that have a common vertex as their
target. Its value type is Halfedge.
| |
| |
A type for a circulator over
the halfedges on the boundary of a Voronoi face. Its value type of
is Halfedge.
| |
| |
A type for an iterator over
the unbounded faces of the Voronoi diagram. Its value type is
Face.
| |
| |
A type for an iterator over
the bounded faces of the Voronoi diagram. Its value type is
Face.
| |
| |
A type for an iterator over
the unbounded halfedges of the Voronoi diagram. Its value type is
Halfedge.
| |
| |
A type for an iterator over
the bounded halfedges of the Voronoi diagram. Its value type is
Halfedge.
| |
| |
A type for an iterator over the
sites of the Voronoi diagram. Its value type is Site_2.
|
| ||
| The result type of the point location queries. |
| |||
Creates a Voronoi diagram using at as adaptation traits and
ap as adaptation policy; the underlying Delaunay graph is
created using gt as geometric traits.
| |||
| |||
Creates a Voronoi diagram from the Delaunay graph dg and using
at as adaptation traits and ap as adaptation policy. The
Delaunay graph dg is fully copied if swap_dg is set to
false, or swapped with the one stored internally if
swap_dg is set to true.
| |||
| |||
| |||
Creates a Voronoi diagram using as sites the sites in the iterator
range [first, beyond), at as adaptation traits and
ap as adaptation policy; the underlying Delaunay graph is
created using gt as geometric traits. Iterator must be a
model of the InputIterator concept and its value type must be
Site_2.
|
A Voronoi diagram can be seen as a container of faces, vertices and halfedges. Therefore the Voronoi diagram provides several iterators and circulators that allow to traverse it.
The following iterators allow respectively to visit the faces (all or only the unbounded/bounded ones), edges, halfedges (all or only the unbounded/bounded ones) and vertices of the Voronoi diagram. These iterators are non-mutable, bidirectional and their value types are respectively Face, Halfedge, Halfedge and Vertex. All iterators are convertible to the corresponding handles and are invalidated by any change in the Voronoi diagram.
The following iterator provides access to the sites that define the Voronoi diagram. Its value type is Site_2. It is invalidated by any change in the Voronoi diagram.
|
| Starts at an arbitrary site. |
|
| Past-the-end iterator. |
The Voronoi diagram adaptor also provides circulators that allow to visit all halfedges whose target is a given vertex - this is the Halfedge_around_vertex_circulator, as well as all halfedges on the boundary of a Voronoi face - this is the Ccb_halfedge_circulator. These circulators are non-mutable and bidirectional. The operator operator++ moves the former circulator counterclockwise around the vertex while the operator-- moves clockwise. The latter circulator is moved by the operator operator++ to the next halfedge on the boundary in the counterclockwise sense, while operator-- moves clockwise. When the Ccb_halfedge_circulator is defined over an infinite Voronoi face f, then applying operator++ to a circulator corresponding to a halfedge whose target is not finite moves to the next infinite (or semi-infinite) halfedge of f in the counterclockwise sense. Similarly, applying operator++ to a circulator corresponding to a halfedge whose source is not finite, moves to the previous infinite (or semi-infinite) halfedge of f in the clockwise sense. The Halfedge_around_vertex_circulator circulator is invalidated by any modification in the faces adjacent to the vertex over which it is defined. The Ccb_halfedge_circulator is invalidated by any modification in the face over which it is defined.
|
| |
Inserts the site t in the Voronoi diagram. A handle to the face corresponding to the Voronoi face of t in the Voronoi diagram is returned. If t has an empty Voronoi cell, the default constructed face handle is returned. This method is supported only if Voronoi_traits::Has_inserter is set to CGAL::Tag_true. | ||
| ||
|
| |
Inserts, in the Voronoi diagram, the sites in the iterator range [first, beyond). The value type of Iterator must be Site_2. The number of sites in the iterator range is returned. This method is supported only if Voronoi_traits::Has_inserter is set to CGAL::Tag_true. |
|
| |
Performs point location for
the query point p. In other words, the face, halfedge or
vertex of the Voronoi diagram is found on which the point p
lies. This method is supported only if
Voronoi_traits::Has_nearest_site_2 is set to
CGAL::Tag_true. Precondition: The Voronoi diagram must contain at least one face. |
|
| |
Writes the current state of the Voronoi diagram to the output
stream os. The following operator must be defined: std::ostream& operator<<(std::ostream&, Delaunay_graph) | ||
|
| |
Reads the current state of the Voronoi diagram from the input
stream is. The following operator must be defined: std::istream& operator>>(std::istream&, Delaunay_graph) | ||
|
| |
Writes the current state of the Voronoi diagram to the output
stream os. The following operator must be defined: std::ostream& operator<<(std::ostream&, Delaunay_graph) | ||
|
| |
Reads the current state of the Voronoi diagram from the input
stream is. The following operator must be defined: std::istream& operator>>(std::istream&, Delaunay_graph) |
|
| Checks the validity of the dual Delaunay graph and the Voronoi diagram adaptor. |
|
| Clears all contents of the Voronoi diagram. |
|
| The Voronoi diagrams other and vd are swapped. vd.swap(other) should be preferred to vd = other or to vd(other) if other is deleted afterwards. |