CGAL 5.5.1 - 2D Segment Delaunay Graphs
2D Segment Delaunay Graphs Reference
Menelaos Karavelas
An algorithm for computing the dual of a Voronoi diagram of a set of segments under the Euclidean metric. It is a generalization of the standard Voronoi diagram for points. The algorithms provided are dynamic.
Introduced in: CGAL 3.1
Depends on: 2D Triangulation Data Structure
BibTeX: cgal:k-sdg2-22b
Windows Demo: 2D Segment Voronoi Diagram
Common Demo Dlls: dlls

CGAL provides the class CGAL::Segment_Delaunay_graph_2<Gt,St,DS> for computing the 2D Delaunay graph of segments and points. The two template parameters must be models of the SegmentDelaunayGraphTraits_2 and SegmentDelaunayGraphDataStructure_2 concepts. The first concept is related to the geometric objects and predicates associated with segment Delaunay graphs, whereas the second concept refers to the data structure used to represent the segment Delaunay graph, which is dual to the 2D Voronoi diagram of segments and points. The classes CGAL::Segment_Delaunay_graph_traits_2<K,MTag>, CGAL::Segment_Delaunay_graph_traits_without_intersections_2<K,MTag> CGAL::Segment_Delaunay_graph_filtered_traits_2<K,MTag> CGAL::Segment_Delaunay_graph_filtered_traits_without_intersections_2<K,MTag> are models of the SegmentDelaunayGraphTraits_2 concept, whereas the class CGAL::Triangulation_data_structure_2<Vb,Fb> is a model of the SegmentDelaunayGraphDataStructure_2 concept.

## Concepts

• SegmentDelaunayGraphSite_2
• SegmentDelaunayGraphStorageSite_2
• SegmentDelaunayGraphStorageTraits_2
• SegmentDelaunayGraphDataStructure_2
• SegmentDelaunayGraphVertexBase_2
• SegmentDelaunayGraphFaceBase_2
• SegmentDelaunayGraphTraits_2
• SegmentDelaunayGraphHierarchyVertexBase_2

## Classes

• CGAL::Segment_Delaunay_graph_2<Gt,St,DS>
• CGAL::Segment_Delaunay_graph_site_2<K>
• CGAL::Segment_Delaunay_graph_storage_site_2<Gt>
• CGAL::Segment_Delaunay_graph_storage_site_with_info_2<St,I,B>
• CGAL::Segment_Delaunay_graph_storage_traits_2<Gt>
• CGAL::Segment_Delaunay_graph_storage_traits_with_info_2<Gt,I,C,M>
• CGAL::Segment_Delaunay_graph_vertex_base_2<St,Vb>
• CGAL::Segment_Delaunay_graph_face_base_2<Gt,Fb>
• CGAL::Segment_Delaunay_graph_traits_2<K,MTag>
• CGAL::Segment_Delaunay_graph_traits_without_intersections_2<K,MTag>
• CGAL::Segment_Delaunay_graph_filtered_traits_2<CK,CM,EK,EM,FK,FM>
• CGAL::Segment_Delaunay_graph_filtered_traits_without_intersections_2<CK,CM,EK,EM,FK,FM>
• CGAL::Segment_Delaunay_graph_hierarchy_2<Gt,St,STag,DS>
• CGAL::Segment_Delaunay_graph_hierarchy_vertex_base_2<Vbb>

Concepts

## Classes

class  CGAL::Segment_Delaunay_graph_2< Gt, St, DS >
The class Segment_Delaunay_graph_2 represents the segment Delaunay graph (which is the dual graph of the 2D segment Voronoi diagram). More...

class  CGAL::Segment_Delaunay_graph_face_base_2< Gt, Fb >

struct  CGAL::Segment_Delaunay_graph_filtered_traits_2< CK, CM, EK, EM, FK, FM >
The class Segment_Delaunay_graph_filtered_traits_2 provides a model for the SegmentDelaunayGraphTraits_2 concept. More...

struct  CGAL::Segment_Delaunay_graph_filtered_traits_without_intersections_2< CK, CM, EK, EM, FK, FM >
The class Segment_Delaunay_graph_filtered_traits_without_intersections_2 provides a model for the SegmentDelaunayGraphTraits_2 concept. More...

class  CGAL::Segment_Delaunay_graph_hierarchy_2< Gt, St, STag, DS >
We provide an alternative to the class Segment_Delaunay_graph_2<Gt,St,DS> for the incremental construction of the segment Delaunay graph. More...

class  CGAL::Segment_Delaunay_graph_hierarchy_vertex_base_2< Vbb >
The class Segment_Delaunay_graph_hierarchy_vertex_base_2 provides a model for the SegmentDelaunayGraphHierarchyVertexBase_2 concept, which is the vertex base required by the Segment_Delaunay_graph_hierarchy_2<Gt,St,STag,DS> class. More...

class  CGAL::Segment_Delaunay_graph_site_2< K >
The class Segment_Delaunay_graph_site_2 is a model for the concept SegmentDelaunayGraphSite_2. More...

class  CGAL::Segment_Delaunay_graph_storage_site_2< St >
The class Segment_Delaunay_graph_storage_site_2 is a model for the concept SegmentDelaunayGraphStorageSite_2. More...

class  CGAL::Segment_Delaunay_graph_storage_site_with_info_2< STraits, Info_, Base >
The class Segment_Delaunay_graph_storage_site_with_info_2 is a model for the concept SegmentDelaunayGraphStorageSite_2. More...

class  CGAL::Segment_Delaunay_graph_storage_traits_2< Gt >
The class Segment_Delaunay_graph_storage_traits_2 provides a model for the SegmentDelaunayGraphStorageTraits_2 concept. More...

class  CGAL::Segment_Delaunay_graph_storage_traits_with_info_2< Gt, Info, Converter, Merger >
The class Segment_Delaunay_graph_storage_traits_with_info_2 provides a model for the SegmentDelaunayGraphStorageTraits_2 concept. More...

struct  CGAL::Segment_Delaunay_graph_traits_2< K, MTag >
The class Segment_Delaunay_graph_traits_2 provides a model for the SegmentDelaunayGraphTraits_2 concept. More...

struct  CGAL::Segment_Delaunay_graph_traits_without_intersections_2< K, MTag >
The class Segment_Delaunay_graph_traits_without_intersections_2 provides a model for the SegmentDelaunayGraphTraits_2 concept. More...

class  CGAL::Segment_Delaunay_graph_vertex_base_2< St, Vb >