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-24a
License: GNU GPL
Windows Demo: 2D Segment Voronoi Diagram

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.

Classified Reference Pages

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>

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