\( \newcommand{\E}{\mathrm{E}} \) \( \newcommand{\A}{\mathrm{A}} \) \( \newcommand{\R}{\mathrm{R}} \) \( \newcommand{\N}{\mathrm{N}} \) \( \newcommand{\Q}{\mathrm{Q}} \) \( \newcommand{\Z}{\mathrm{Z}} \) \( \def\ccSum #1#2#3{ \sum_{#1}^{#2}{#3} } \def\ccProd #1#2#3{ \sum_{#1}^{#2}{#3} }\)
CGAL 4.14 - 2D Voronoi Diagram Adaptor
2D Voronoi Diagram Adaptor Reference

voronoi.png
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-19a
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

Classes

Modules

 Concepts
 
 Voronoi Diagram of Points
 
 Voronoi Diagram of Segments
 
 Voronoi Diagram of Disks
 

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