2D Voronoi Diagram Adaptor
Reference Manual

Menelaos Karavelas

CGAL provides the class CGAL::Voronoi_diagram_2<DG,AT,AP> for adapting the various (triangulated) Delaunay graphs to Voronoi diagrams according to some adaptation policy. In particular, the class CGAL::Voronoi_diagram_2<DG,AT,AP> provides an API for the duals of (triangulated) Delaunay graphs, that makes them look like planar subdivisions. The adaptation policy is responsible for deciding which edges and faces of these duals should be eliminated. This is especially important when, for instance, we want to eliminate degenerate features in the Voronoi diagram that are the result of the fact that Delaunay graphs are always triangulated and are due to degenerate configurations in the generating data.

The three template parameters must be models of the DelaunayGraph_2, AdaptationTraits_2 and AdaptationPolicy_2 concepts, respectively. The first concept is related to the Delaunay graphs that are to be adapted, whereas the second one is responsible for manipulating/accessing in a unified way the geometry of a specific Voronoi diagram as well as for performing nearest site queries. The third template parameter corresponds to the chosen adaptation policy and provides the necessary types and functors needed for performing this adaptation.

37.6   Classified Reference Pages

Concepts

DelaunayGraph_2
AdaptationTraits_2
AdaptationPolicy_2

Classes

CGAL::Voronoi_diagram_2<DG,AT,AP>
CGAL::Voronoi_diagram_2<DG,AT,AP>::Halfedge
CGAL::Voronoi_diagram_2<DG,AT,AP>::Vertex
CGAL::Voronoi_diagram_2<DG,AT,AP>::Face
CGAL::Apollonius_graph_adaptation_traits_2<AG2>
CGAL::Delaunay_triangulation_adaptation_traits_2<DT2>
CGAL::Regular_triangulation_adaptation_traits_2<RT2>
CGAL::Segment_Delaunay_graph_adaptation_traits_2<SDG2>
CGAL::Identity_policy_2<DG,AT>
CGAL::Apollonius_graph_degeneracy_removal_policy_2<AG2>
CGAL::Apollonius_graph_caching_degeneracy_removal_policy_2<AG2>
CGAL::Delaunay_triangulation_degeneracy_removal_policy_2<DT2>
CGAL::Delaunay_triangulation_caching_degeneracy_removal_policy_2<DT2>
CGAL::Regular_triangulation_degeneracy_removal_policy_2<RT2>
CGAL::Regular_triangulation_caching_degeneracy_removal_policy_2<RT2>
CGAL::Segment_Delaunay_graph_degeneracy_removal_policy_2<SDG2>
CGAL::Segment_Delaunay_graph_caching_degeneracy_removal_policy_2<SDG2>

37.7   Alphabetical List of Reference Pages

AdaptationPolicy_2
AdaptationTraits_2
Apollonius_graph_adaptation_traits_2<AG2>
Apollonius_graph_caching_degeneracy_removal_policy_2<AG2>
Apollonius_graph_degeneracy_removal_policy_2<AG2>
DelaunayGraph_2
Delaunay_triangulation_adaptation_traits_2<DT2>
Delaunay_triangulation_caching_degeneracy_removal_policy_2<DT2>
Delaunay_triangulation_degeneracy_removal_policy_2<DT2>
Identity_policy_2<DG,AT>
Regular_triangulation_adaptation_traits_2<RT2>
Regular_triangulation_caching_degeneracy_removal_policy_2<RT2>
Regular_triangulation_degeneracy_removal_policy_2<RT2>
Segment_Delaunay_graph_adaptation_traits_2<SDG2>
Segment_Delaunay_graph_caching_degeneracy_removal_policy_2<SDG2>
Segment_Delaunay_graph_degeneracy_removal_policy_2<SDG2>
Voronoi_diagram_2<DG,AT,AP>::Face
Voronoi_diagram_2<DG,AT,AP>::Halfedge
Voronoi_diagram_2<DG,AT,AP>::Vertex
Voronoi_diagram_2<DG,AT,AP>