CGAL 5.1.2 - 2D Voronoi Diagram Adaptor
|
#include <CGAL/Voronoi_diagram_2.h>
The class Voronoi_diagram_2
provides an adaptor that enables us to view a triangulated Delaunay graph as their dual subdivision, the Voronoi diagram.
The class Voronoi_diagram_2
is designed to provide an API that is similar to that of CGAL's arrangements.
DG | corresponds to the triangulated Delaunay graph and must be a model of the DelaunayGraph_2 concept. |
AT | must be a model of the AdaptationTraits_2 concept. |
AP | must be a model of the AdaptationPolicy_2 concept. The third template parameter defaults to CGAL::Identity_policy_2<DG,AT> . |
CGAL::Delaunay_triangulation_2<Traits,Tds>
CGAL::Regular_triangulation_2<Traits,Tds>
CGAL::Triangulation_hierarchy_2<Tr>
provided that Tr
is a model of DelaunayGraph_2
CGAL::Segment_Delaunay_graph_2<Gt,DS>
CGAL::Segment_Delaunay_graph_hierarchy_2<Gt,STag,DS>
CGAL::Apollonius_graph_2<Gt,Agds>
CGAL::Apollonius_graph_hierarchy_2<Gt,Agds>
Classes | |
class | Face |
The class Face is the class provided by the Voronoi_diagram_2<DG,AT,AP> class for Voronoi faces. More... | |
class | Halfedge |
The class Halfedge is the class provided by the Voronoi_diagram_2<DG,AT,AP> class for Voronoi halfedges. More... | |
class | Vertex |
The class Vertex is the Voronoi vertex class provided by the class Voronoi_diagram_2<DG,AT,AP> class. More... | |
Types | |
typedef DG | Delaunay_graph |
A type for the dual Delaunay graph. | |
typedef AT | Adaptation_traits |
A type for the adaptation traits needed by the Voronoi diagram adaptor. | |
typedef AP | Adaptation_policy |
A type for the adaptation policy used. | |
typedef Adaptation_traits::Point_2 | Point_2 |
A type a point. | |
typedef Adaptation_traits::Site_2 | Site_2 |
A type for the sites of the Voronoi diagram. | |
typedef Delaunay_graph::size_type | size_type |
A type for sizes. | |
typedef Delaunay_graph::Geom_traits | Delaunay_geom_traits |
A type for the geometric traits of the Delaunay graph. | |
typedef Delaunay_graph::Vertex_handle | Delaunay_vertex_handle |
A type for the vertex handles of the Delaunay graph. | |
typedef Delaunay_graph::Face_handle | Delaunay_face_handle |
A type for the face handles of the Delaunay graph. | |
typedef Delaunay_graph::Edge | Delaunay_edge |
A type for the edges of the Delaunay graph. | |
The vertices, edges and faces of the Voronoi diagram 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. | |
typedef unspecified_type | Halfedge_handle |
Handle for halfedges. | |
typedef unspecified_type | Vertex_handle |
Handle for vertices. | |
typedef unspecified_type | Face_handle |
Handle for faces. | |
typedef unspecified_type | Edge_iterator |
A type for an iterator over Voronoi edges. More... | |
typedef unspecified_type | Halfedge_iterator |
A type for an iterator over Voronoi halfedges. More... | |
typedef unspecified_type | Face_iterator |
A type for an iterator over Voronoi faces. More... | |
typedef unspecified_type | Vertex_iterator |
A type for an iterator over Voronoi vertices. More... | |
typedef unspecified_type | Halfedge_around_vertex_circulator |
A type for a circulator over the halfedges that have a common vertex as their target. More... | |
typedef unspecified_type | Ccb_halfedge_circulator |
A type for a circulator over the halfedges on the boundary of a Voronoi face. More... | |
typedef unspecified_type | Unbounded_faces_iterator |
A type for an iterator over the unbounded faces of the Voronoi diagram. More... | |
typedef unspecified_type | Bounded_faces_iterator |
A type for an iterator over the bounded faces of the Voronoi diagram. More... | |
typedef unspecified_type | Unbounded_halfedges_iterator |
A type for an iterator over the unbounded halfedges of the Voronoi diagram. More... | |
typedef unspecified_type | Bounded_halfedges_iterator |
A type for an iterator over the bounded halfedges of the Voronoi diagram. More... | |
typedef unspecified_type | Site_iterator |
A type for an iterator over the sites of the Voronoi diagram. More... | |
typedef boost::variant< Face_handle, Halfedge_handle, Vertex_handle > | Locate_result |
The result type of the point location queries. | |
Creation | |
Voronoi_diagram_2 (Adaptation_traits at=Adaptation_traits(), Adaptation_policy ap=Adaptation_policy(), Delaunay_geom_traits gt=Delaunay_geom_traits()) | |
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. | |
Voronoi_diagram_2 (Delaunay_graph dg, bool swap_dg=false, Adaptation_traits at=Adaptation_traits(), Adaptation_policy ap=Adaptation_policy()) | |
Creates a Voronoi diagram from the Delaunay graph dg and using at as adaptation traits and ap as adaptation policy. More... | |
template<class Iterator > | |
Voronoi_diagram_2 (Iterator first, Iterator beyond, Adaptation_traits at=Adaptation_traits(), Adaptation_policy ap=Adaptation_policy(), Delaunay_geom_traits gt=Delaunay_geom_traits()) | |
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. More... | |
Access Methods | |
Delaunay_graph | dual () |
Returns a const reference to the dual graph, i.e., the Delaunay graph. | |
Halfedge_handle | dual (Delaunay_edge e) |
Returns a handle to the halfedge in the Voronoi diagram that is dual to the edge e in the Delaunay graph. | |
Face_handle | dual (Delaunay_vertex_handle v) |
Returns a handle to the face in the Voronoi diagram that is dual to the vertex corresponding to the vertex handle v in the Delaunay graph. | |
Vertex_handle | dual (Delaunay_face_handle f) |
Returns a handle to the vertex in the Voronoi diagram that is dual to the face corresponding to the face handle f in the Delaunay graph. | |
Adaptation_traits | adaptation_traits () |
Returns a reference to the Voronoi traits. | |
Adaptation_policy | adaptation_policy () |
Returns a reference to the adaptation policy. | |
size_type | number_of_vertices () |
Returns the number of Voronoi vertices. | |
size_type | number_of_faces () |
Returns the number of Voronoi faces (bounded and unbounded). | |
size_type | number_of_halfedges () |
Returns the number of halfedges (bounded and unbounded) in the Voronoi diagram. More... | |
size_type | number_of_connected_components () |
Returns the number of connected components of the Voronoi skeleton. | |
Face_handle | unbounded_face () |
Returns one of the unbounded faces of the Voronoi diagram. More... | |
Face_handle | bounded_face () |
Returns one of the bounded faces of the Voronoi diagram. More... | |
Halfedge_handle | unbounded_halfedge () |
Returns one of the unbounded halfedges of the Voronoi diagram. More... | |
Halfedge_handle | bounded_halfedge () |
Returns one of the bounded halfedges of the Voronoi diagram. More... | |
Iterators | |
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_iterator | faces_begin () |
Starts at an arbitrary Voronoi face. | |
Face_iterator | faces_end () |
Past-the-end iterator. | |
Unbounded_faces_iterator | unbounded_faces_begin () |
Starts at an arbitrary unbounded Voronoi face. | |
Unbounded_faces_iterator | unbounded_faces_end () |
Past-the-end iterator. | |
Bounded_faces_iterator | bounded_faces_begin () |
Starts at an arbitrary bounded Voronoi face. | |
Bounded_faces_iterator | bounded_faces_end () |
Past-the-end iterator. | |
Edge_iterator | edges_begin () |
Starts at an arbitrary Voronoi edge. | |
Edge_iterator | edges_end () |
Past-the-end iterator. | |
Halfedge_iterator | halfedges_begin () |
Starts at an arbitrary Voronoi halfedge. | |
Halfedge_iterator | halfedges_end () |
Past-the-end iterator. | |
Unbounded_halfedges_iterator | unbounded_halfedges_begin () |
Starts at an arbitrary unbounded Voronoi edge. | |
Unbounded_halfedges_iterator | unbounded_halfedges_end () |
Past-the-end iterator. | |
Bounded_halfedges_iterator | bounded_halfedges_begin () |
Starts at an arbitrary bounded Voronoi edge. | |
Bounded_halfedges_iterator | bounded_halfedges_end () |
Past-the-end iterator. | |
Vertex_iterator | vertices_begin () |
Starts at an arbitrary Voronoi vertex. | |
Vertex_iterator | vertices_end () |
Past-the-end iterator. | |
Site_iterator | sites_begin () |
Starts at an arbitrary site. | |
Site_iterator | sites_end () |
Past-the-end iterator. | |
Circulators | |
The Voronoi diagram adaptor also provides circulators that allow to visit all halfedges whose target is a given vertex - this is the These circulators are non-mutable and bidirectional. The operator | |
Ccb_halfedge_circulator | ccb_halfedges (Face_handle f) |
Returns a circulator over the halfedges on the boundary of f . More... | |
Ccb_halfedge_circulator | ccb_halfedges (Face_handle f, Halfedge_handle h) |
Returns a circulator over the halfedges on the boundary of f . More... | |
Halfedge_around_vertex_circulator | incident_halfedges (Vertex_handle v) |
Returns a circulator over the halfedges whose target is the Voronoi vertex v . More... | |
Halfedge_around_vertex_circulator | incident_halfedges (Vertex_handle v, Halfedge_handle h) |
Returns a circulator over the halfedges whose target is the Voronoi vertex v . More... | |
Insertion | |
Face_handle | insert (Site_2 t) |
Inserts the site t in the Voronoi diagram. More... | |
template<class Iterator > | |
size_type | insert (Iterator first, Iterator beyond) |
Inserts, in the Voronoi diagram, the sites in the iterator range [first, beyond) . More... | |
Queries | |
Locate_result | locate (Point_2 p) |
Performs point location for the query point p . More... | |
I/O | |
void | file_output (std::ostream &os) |
Writes the current state of the Voronoi diagram to the output stream os . More... | |
void | file_input (std::istream &is) |
Reads the current state of the Voronoi diagram from the input stream is . More... | |
std::ostream & | operator<< (std::ostream &os, Voronoi_diagram_2< DG, AT, AP > vd) |
Writes the current state of the Voronoi diagram to the output stream os . More... | |
std::istream & | operator>> (std::istream &is, Voronoi_diagram_2< DG, AT, AP > vd) |
Reads the current state of the Voronoi diagram from the input stream is . More... | |
Validity Check | |
bool | is_valid () |
Checks the validity of the dual Delaunay graph and the Voronoi diagram adaptor. | |
Miscellaneous | |
void | clear () |
Clears all contents of the Voronoi diagram. | |
void | swap (Voronoi_diagram_2< DG, AT, AP > other) |
The Voronoi diagrams other and vd are swapped. More... | |
typedef unspecified_type CGAL::Voronoi_diagram_2< DG, AT, AP >::Bounded_faces_iterator |
A type for an iterator over the bounded faces of the Voronoi diagram.
Its value type is Face
.
typedef unspecified_type CGAL::Voronoi_diagram_2< DG, AT, AP >::Bounded_halfedges_iterator |
A type for an iterator over the bounded halfedges of the Voronoi diagram.
Its value type is Halfedge
.
typedef unspecified_type CGAL::Voronoi_diagram_2< DG, AT, AP >::Ccb_halfedge_circulator |
A type for a circulator over the halfedges on the boundary of a Voronoi face.
Its value type of is Halfedge
.
typedef unspecified_type CGAL::Voronoi_diagram_2< DG, AT, AP >::Edge_iterator |
A type for an iterator over Voronoi edges.
Edges are considered non-oriented. Its value type is Halfedge
.
typedef unspecified_type CGAL::Voronoi_diagram_2< DG, AT, AP >::Face_iterator |
A type for an iterator over Voronoi faces.
Its value type is Face
.
typedef unspecified_type CGAL::Voronoi_diagram_2< DG, AT, AP >::Halfedge_around_vertex_circulator |
A type for a circulator over the halfedges that have a common vertex as their target.
Its value type is Halfedge
.
typedef unspecified_type CGAL::Voronoi_diagram_2< DG, AT, AP >::Halfedge_iterator |
A type for an iterator over Voronoi halfedges.
Halfedges are oriented and come in pairs. Its value type is Halfedge
.
typedef unspecified_type CGAL::Voronoi_diagram_2< DG, AT, AP >::Site_iterator |
A type for an iterator over the sites of the Voronoi diagram.
Its value type is Site_2
.
typedef unspecified_type CGAL::Voronoi_diagram_2< DG, AT, AP >::Unbounded_faces_iterator |
A type for an iterator over the unbounded faces of the Voronoi diagram.
Its value type is Face
.
typedef unspecified_type CGAL::Voronoi_diagram_2< DG, AT, AP >::Unbounded_halfedges_iterator |
A type for an iterator over the unbounded halfedges of the Voronoi diagram.
Its value type is Halfedge
.
typedef unspecified_type CGAL::Voronoi_diagram_2< DG, AT, AP >::Vertex_iterator |
A type for an iterator over Voronoi vertices.
Its value type is Vertex
.
CGAL::Voronoi_diagram_2< DG, AT, AP >::Voronoi_diagram_2 | ( | Delaunay_graph | dg, |
bool | swap_dg = false , |
||
Adaptation_traits | at = Adaptation_traits() , |
||
Adaptation_policy | ap = Adaptation_policy() |
||
) |
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
.
CGAL::Voronoi_diagram_2< DG, AT, AP >::Voronoi_diagram_2 | ( | Iterator | first, |
Iterator | beyond, | ||
Adaptation_traits | at = Adaptation_traits() , |
||
Adaptation_policy | ap = Adaptation_policy() , |
||
Delaunay_geom_traits | gt = Delaunay_geom_traits() |
||
) |
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
.
Face_handle CGAL::Voronoi_diagram_2< DG, AT, AP >::bounded_face | ( | ) |
Returns one of the bounded faces of the Voronoi diagram.
If no bounded faces exist the default constructed face handle is returned.
Halfedge_handle CGAL::Voronoi_diagram_2< DG, AT, AP >::bounded_halfedge | ( | ) |
Returns one of the bounded halfedges of the Voronoi diagram.
If no bounded halfedges exist the default constructed halfedge handle is returned.
Ccb_halfedge_circulator CGAL::Voronoi_diagram_2< DG, AT, AP >::ccb_halfedges | ( | Face_handle | f | ) |
Returns a circulator over the halfedges on the boundary of f
.
The circulator is initialized to an arbitrary halfedge on the boundary of the Voronoi face f
.
Ccb_halfedge_circulator CGAL::Voronoi_diagram_2< DG, AT, AP >::ccb_halfedges | ( | Face_handle | f, |
Halfedge_handle | h | ||
) |
Returns a circulator over the halfedges on the boundary of f
.
The circulator is initialized with the halfedge h
.
h
must lie on the boundary of f
. void CGAL::Voronoi_diagram_2< DG, AT, AP >::file_input | ( | std::istream & | is | ) |
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)
void CGAL::Voronoi_diagram_2< DG, AT, AP >::file_output | ( | std::ostream & | os | ) |
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)
Halfedge_around_vertex_circulator CGAL::Voronoi_diagram_2< DG, AT, AP >::incident_halfedges | ( | Vertex_handle | v | ) |
Returns a circulator over the halfedges whose target is the Voronoi vertex v
.
The circulator is initialized to an arbitrary halfedge incident to v
.
Halfedge_around_vertex_circulator CGAL::Voronoi_diagram_2< DG, AT, AP >::incident_halfedges | ( | Vertex_handle | v, |
Halfedge_handle | h | ||
) |
Returns a circulator over the halfedges whose target is the Voronoi vertex v
.
The circulator is initialized with the halfedge h
.
v
must be the target vertex of the halfedge h
. Face_handle CGAL::Voronoi_diagram_2< DG, AT, AP >::insert | ( | Site_2 | t | ) |
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
.
size_type CGAL::Voronoi_diagram_2< DG, AT, AP >::insert | ( | Iterator | first, |
Iterator | beyond | ||
) |
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
.
Locate_result CGAL::Voronoi_diagram_2< DG, AT, AP >::locate | ( | Point_2 | p | ) |
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
.
size_type CGAL::Voronoi_diagram_2< DG, AT, AP >::number_of_halfedges | ( | ) |
Returns the number of halfedges (bounded and unbounded) in the Voronoi diagram.
This is always an even number.
std::ostream& CGAL::Voronoi_diagram_2< DG, AT, AP >::operator<< | ( | std::ostream & | os, |
Voronoi_diagram_2< DG, AT, AP > | vd | ||
) |
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)
std::istream& CGAL::Voronoi_diagram_2< DG, AT, AP >::operator>> | ( | std::istream & | is, |
Voronoi_diagram_2< DG, AT, AP > | vd | ||
) |
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)
void CGAL::Voronoi_diagram_2< DG, AT, AP >::swap | ( | Voronoi_diagram_2< DG, AT, AP > | other | ) |
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.
Face_handle CGAL::Voronoi_diagram_2< DG, AT, AP >::unbounded_face | ( | ) |
Returns one of the unbounded faces of the Voronoi diagram.
If no unbounded faces exist (this can happen if the number of sites is zero) the default constructed face handle is returned.
Halfedge_handle CGAL::Voronoi_diagram_2< DG, AT, AP >::unbounded_halfedge | ( | ) |
Returns one of the unbounded halfedges of the Voronoi diagram.
If no unbounded halfedges exist the default constructed halfedge handle is returned.