2D Voronoi Diagram Adaptor Reference

Menelaos Karavelas

The 2D Voronoi diagram adaptor package provides an adaptor that adapts a 2-dimensional triangulated Delaunay graph to the corresponding Voronoi diagram, represented as a doubly connected edge list (DCEL) data structure. The adaptor has the ability to automatically eliminate, in a consistent manner, degenerate features of the Voronoi diagram, that are artifacts of the requirement that Delaunay graphs should be triangulated even in degenerate configurations. Depending on the type of operations that the underlying Delaunay graph supports, the adaptor allows for the incremental or dynamic construction of Voronoi diagrams and can support point location queries.

Introduced in: CGAL 3.2
BibTeX: cgal:k-vda2-21a
License: GPL
Windows Demos: 2D Point Voronoi Diagram , 2D Disk Voronoi Diagram, 2D Segment Voronoi Diagram
Common Demo Dlls: dlls

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.

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>

Draw Voronoi Diagram

• CGAL::draw<VD>()

Modules
	Concepts
	Voronoi Diagram of Points
	Voronoi Diagram of Segments
	Voronoi Diagram of Disks
	Draw a 2D Voronoi Diagram

Classes
struct	CGAL::Identity_policy_2< DG, AT >
	The class Identity_policy_2 provides a model for the AdaptationPolicy_2 concept. More...
class	CGAL::Voronoi_diagram_2< DG, AT, AP >::Face
	The class Face is the class provided by the Voronoi_diagram_2<DG,AT,AP> class for Voronoi faces. More...
class	CGAL::Voronoi_diagram_2< DG, AT, AP >::Halfedge
	The class Halfedge is the class provided by the Voronoi_diagram_2<DG,AT,AP> class for Voronoi halfedges. More...
class	CGAL::Voronoi_diagram_2< DG, AT, AP >::Vertex
	The class Vertex is the Voronoi vertex class provided by the class Voronoi_diagram_2<DG,AT,AP> class. More...
class	CGAL::Voronoi_diagram_2< DG, AT, AP >
	The class Voronoi_diagram_2 provides an adaptor that enables us to view a triangulated Delaunay graph as their dual subdivision, the Voronoi diagram. More...