CGAL::Segment_Delaunay_graph_hierarchy_2< Gt, St, STag, DS > Class Template Reference

#include <CGAL/Segment_Delaunay_graph_hierarchy_2.h>

Inherits from

CGAL::Segment_Delaunay_graph_2< Gt, St, DS >.

Definition

template<typename Gt, typename St, typename STag, typename DS>
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.

The Segment_Delaunay_graph_hierarchy_2 class maintains a hierarchy of Delaunay graphs. There are two possibilities as to how this hierarchy is constructed.

In the first case the bottom-most level of the hierarchy contains the full segment Delaunay graph. The upper levels of the hierarchy contain only points that are either point sites or endpoints of segment sites in the bottom-most Delaunay graph. A point that is in level \( i\) (either as an individdual point or as the endpoint of a segment), is inserted in level \( i+1\) with probability \( 1/\alpha\) where \( \alpha>1\) is some constant. In the second case the upper levels of the hierarchy contains not only points but also segments. A site that is in level \( i\), is in level \( i+1\) with probability \( 1/\beta\) where \( \beta > 1\) is some constant.

The difference between the Segment_Delaunay_graph_2<Gt,St,DS> class and the Segment_Delaunay_graph_hierarchy_2 class (both versions of it) is on how the nearest neighbor location is done. Given a point \( p\) the location is done as follows: at the top most level we find the nearest neighbor of \( p\) as in the Segment_Delaunay_graph_2<Gt,St,DS> class. At every subsequent level \( i\) we use the nearest neighbor found at level \( i+1\) to find the nearest neighbor at level \( i\). This is a variant of the corresponding hierarchy for points found in [3]. The details are described in [4].

The class has four template parameters. The first and fourth have essentially the same semantics as in the Segment_Delaunay_graph_2<Gt,St,DS> class.

Template Parameters

Gt	must be a model of the SegmentDelaunayGraphTraits_2 concept.
St	must be a model of SegmentDelaunayGraphStorageTraits_2. By default, the storage traits is instantiated by Segment_Delaunay_graph_storage_traits_2<Gt>.
STag	The third template parameter controls whether or not segments are added in the upper levels of the hierarchy. It's possible values are Tag_true and Tag_false. If it is set to Tag_true, segments are also inserted in the upper levels of the hierarchy. The value Tag_false indicates that only points are to be inserted in the upper levels of the hierarchy. The default value for the third template parameter is Tag_false.
DS	must be a model of the SegmentDelaunayGraphDataStructure_2 concept. However, the vertex base class that is to be used in the segment Delaunay graph data structure must be a model of the SegmentDelaunayGraphHierarchyVertexBase_2 concept. The fourth template parameter defaults to: CGAL::Triangulation_data_structure_2< CGAL::Segment_Delaunay_graph_hierarchy_vertex_base_2< CGAL::Segment_Delaunay_graph_vertex_base_2<St>, CGAL::Segment_Delaunay_graph_face_base_2<Gt> >

The Segment_Delaunay_graph_hierarchy_2 class derives publicly from the Segment_Delaunay_graph_2<Gt,St,DS> class. The interface is the same with its base class. In the sequel only additional types and methods defined are documented.

Is model of

DefaultConstructible

CopyConstructible

Assignable

See also

CGAL::Segment_Delaunay_graph_2<Gt,St,DS>

CGAL::Triangulation_data_structure_2<Vb,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_vertex_base_2<Vbb>

Examples

Segment_Delaunay_graph_2/sdg-filtered-traits.cpp, and Segment_Delaunay_graph_2/sdg-info-set.cpp.

Related Functions
(Note that these are not member functions.)
std::ostream &	operator<< (std::ostream &os, const Segment_Delaunay_graph_hierarchy_2< Gt, St, STag, DS > &svdh)
	Writes the current state of the segment Delaunay graph hierarchy to an output stream.
std::istream &	operator>> (std::istream &is, const Segment_Delaunay_graph_hierarchy_2< Gt, St, STag, DS > &svdh)
	Reads the state of the segment Delaunay graph hierarchy from an input stream.

Types
Segment_Delaunay_graph_hierarchy_2 introduces the following types in addition to those introduced by its base class Segment_Delaunay_graph_2<Gt,St,DS>.
typedef STag	Segments_in_hierarchy_tag
	A type for the STag template parameter.
typedef CGAL::Segment_Delaunay_graph_2< Gt, St, DS >	Base
	A type for the base class.

Creation
In addition to the default and copy constructors, the following constructors are defined:
	Segment_Delaunay_graph_hierarchy_2 (Gt gt=Gt())
	Creates a hierarchy of segment Delaunay graphs using gt as geometric traits.
template<class Input_iterator >
	Segment_Delaunay_graph_hierarchy_2 (Input_iterator first, Input_iterator beyond, Gt gt=Gt())
	Creates a segment Delaunay graph hierarchy using gt as geometric traits and inserts all sites in the range [first, beyond).

Additional Inherited Members
Public Types inherited from CGAL::Segment_Delaunay_graph_2< Gt, St, DS >
typedef Gt	Geom_traits
	Type for the geometric traits.
typedef St	Storage_traits
	Type for the storage traits.
typedef DS	Data_structure
	Type for the underlying data structure.
typedef Data_structure	Triangulation_data_structure
	This type has been added so that the Segment_Delaunay_graph_2 class is a model of the DelaunayGraph_2 concept.
typedef DS::size_type	size_type
	Size type (an unsigned integral type)
typedef Gt::Point_2	Point_2
	Type for the point defined in the geometric traits.
typedef Gt::Site_2	Site_2
	Type for the segment Delaunay graph site, defined in the geometric traits.
typedef Storage_traits::Storage_site_2	Storage_site_2
	Type for the segment Delaunay storage site, defined in the storage traits.
typedef Storage_traits::Point_container	Point_container
	Type for the container of points.
typedef Storage_traits::Point_handle	Point_handle
	Handle type for points in the point container.
typedef DS::Edge	Edge
	The edge type.
typedef DS::Vertex	Vertex
	Type for a vertex.
typedef DS::Face	Face
	Type for a face.
typedef DS::Vertex_handle	Vertex_handle
	Type for a handle to a vertex.
typedef DS::Face_handle	Face_handle
	Type for a handle to a face.
typedef DS::Vertex_circulator	Vertex_circulator
	Type for a circulator over vertices incident to a given vertex.
typedef DS::Face_circulator	Face_circulator
	Type for a circulator over faces incident to a given vertex.
typedef DS::Edge_circulator	Edge_circulator
	Type for a circulator over edges incident to a given vertex.
typedef DS::Vertex_iterator	All_vertices_iterator
	Type for an iterator over all vertices.
typedef DS::Face_iterator	All_faces_iterator
	Type for an iterator over all faces.
typedef DS::Edge_iterator	All_edges_iterator
	Type for an iterator over all edges.
typedef unspecified_type	Finite_vertices_iterator
	Type for an iterator over finite vertices.
typedef unspecified_type	Finite_faces_iterator
	Type for an iterator over finite faces.
typedef unspecified_type	Finite_edges_iterator
	Type for an iterator over finite edges.
typedef unspecified_type	Input_sites_iterator
	Type for a bidirectional iterator over all input sites.
typedef unspecified_type	Output_sites_iterator
	Type for a bidirectional iterator over all output sites (the sites in the Delaunay graph).
Public Member Functions inherited from CGAL::Segment_Delaunay_graph_2< Gt, St, DS >
Input_sites_iterator	input_sites_begin () const
	Starts at an arbitrary input site.
Input_sites_iterator	input_sites_end () const
	Past-the-end iterator.
Output_sites_iterator	output_sites_begin () const
	Starts at an arbitrary output site.
Output_sites_iterator	output_sites_end () const
	Past-the-end iterator.
	Segment_Delaunay_graph_2 (Gt gt=Gt(), St st=St())
	Creates the segment Delaunay graph using gt as geometric traits and st as storage traits.
template<class Input_iterator >
	Segment_Delaunay_graph_2 (Input_iterator first, Input_iterator beyond, Gt gt=Gt(), St gt=St())
	Creates the segment Delaunay graph using gt as geometric traits, st as storage traits, and inserts all sites in the range [first, beyond).
const Geom_traits &	geom_traits () const
	Returns a reference to the segment Delaunay graph geometric traits object.
const Storage_traits &	storage_traits () const
	Returns a reference to the segment Delaunay graph storage traits object.
const Point_container &	point_container () const
	Returns a reference to the point container object.
const Data_structure &	data_structure () const
	Returns a reference to the segment Delaunay graph data structure object.
const Data_structure &	tds () const
	Same as data_structure().
int	dimension () const
	Returns the dimension of the segment Delaunay graph.
size_type	number_of_vertices () const
	Returns the number of finite vertices of the segment Delaunay graph.
size_type	number_of_faces () const
	Returns the number of faces (both finite and infinite) of the segment Delaunay graph.
size_type	number_of_input_sites () const
	Return the number of input sites.
size_type	number_of_output_sites () const
	Return the number of output sites.
Face_handle	infinite_face () const
	Returns a face incident to the infinite_vertex.
Vertex_handle	infinite_vertex () const
	Returns the infinite_vertex.
Vertex_handle	finite_vertex () const
	Returns a vertex distinct from the infinite_vertex.
Finite_vertices_iterator	finite_vertices_begin () const
	Starts at an arbitrary finite vertex.
Finite_vertices_iterator	finite_vertices_end () const
	Past-the-end iterator.
Finite_edges_iterator	finite_edges_begin () const
	Starts at an arbitrary finite edge.
Finite_edges_iterator	finite_edges_end () const
	Past-the-end iterator.
Finite_faces_iterator	finite_faces_begin () const
	Starts at an arbitrary finite face.
Finite_faces_iterator	finite_faces_end () const
	Past-the-end iterator.
All_vertices_iterator	all_vertices_begin () const
	Starts at an arbitrary vertex.
All_vertices_iterator	all_vertices_end () const
	Past-the-end iterator.
All_edges_iterator	all_edges_begin () const
	Starts at an arbitrary edge.
All_edges_iterator	all_edges_end () const
	Past-the-end iterator.
All_faces_iterator	all_faces_begin () const
	Starts at an arbitrary face.
All_faces_iterator	all_faces_end () const
	Past-the-end iterator.
Face_circulator	incident_faces (Vertex_handle v) const
	Starts at an arbitrary face incident to v.
Face_circulator	incident_faces (Vertex_handle v, Face_handle f) const
	Starts at face f.
Edge_circulator	incident_edges (Vertex_handle v) const
	Starts at an arbitrary edge incident to v.
Edge_circulator	incident_edges (Vertex_handle v, Face_handle f) const
	Starts at the first edge of f incident to v, in counterclockwise order around v.
Vertex_circulator	incident_vertices (Vertex_handle v) const
	Starts at an arbitrary vertex incident to v.
Vertex_circulator	incident_vertices (Vertex_handle v, Face_handle f) const
	Starts at the first vertex of f adjacent to v in counterclockwise order around v.
bool	is_infinite (Vertex_handle v) const
	true, iff v is the infinite_vertex.
bool	is_infinite (Face_handle f) const
	true, iff face f is infinite.
bool	is_infinite (Face_handle f, int i) const
	true, iff edge (f,i) is infinite.
bool	is_infinite (Edge e) const
	true, iff edge e is infinite.
bool	is_infinite (Edge_circulator ec) const
	true, iff edge *ec is infinite.
template<class Input_iterator >
size_type	insert (Input_iterator first, Input_iterator beyond)
	Iteratively inserts the sites in the range [first,beyond).
template<class Input_iterator >
size_type	insert (Input_iterator first, Input_iterator beyond, CGAL::Tag_false)
	Iteratively inserts the sites in the range [first,beyond).
template<class Input_iterator >
size_type	insert (Input_iterator first, Input_iterator beyond, CGAL::Tag_true)
	Decomposes the range [first,beyond) into a range of input points and a range of input segments that are respectively passed to insert_segments() and insert_points().
template<class PointIterator >
std::size_t	insert_points (PointIterator first, PointIterator beyond)
	Inserts the points in the range [first,beyond) as sites.
template<class SegmentIterator >
std::size_t	insert_segments (SegmentIterator first, SegmentIterator beyond)
	Inserts the segments in the range [first,beyond) as sites.
template<class PointIterator , class IndicesIterator >
std::size_t	insert_segments (PointIterator points_first, PointIterator points_beyond, IndicesIterator indices_first, IndicesIterator indices_beyond)
	Same as above except that each segment is given as a pair of indices of the points in the range [points_first, points_beyond).
Vertex_handle	insert (const Point_2 &p)
	Inserts the point p in the segment Delaunay graph.
Vertex_handle	insert (const Point_2 &p, Vertex_handle vnear)
	Inserts p in the segment Delaunay graph using the site associated with vnear as an estimate for the nearest neighbor of p.
Vertex_handle	insert (const Point_2 &p1, const Point_2 &p2)
	Inserts the closed segment with endpoints p1 and p2 in the segment Delaunay graph.
Vertex_handle	insert (const Point_2 &p1, const Point_2 &p2, Vertex_handle vnear)
	Inserts the segment whose endpoints are p1 and p2 in the segment Delaunay graph using the site associated with vnear as an estimate for the nearest neighbor of p1.
Vertex_handle	insert (const Site_2 &s)
	Inserts the site s in the segment Delaunay graph.
Vertex_handle	insert (const Site_2 &s, Vertex_handle vnear)
	Inserts s in the segment Delaunay graph using the site associated with vnear as an estimate for the nearest neighbor of s, if s is a point, or the first endpoint of s, if s is a segment.
Vertex_handle	nearest_neighbor (const Point_2 &p) const
	Finds the nearest neighbor of the point p.
Vertex_handle	nearest_neighbor (const Point_2 &p, Vertex_handle vnear) const
	Finds the nearest neighbor of the point p using the site associated with vnear as an estimate for the nearest neighbor of p.
template<class Stream >
Stream &	draw_dual (Stream &str) const
	Draws the segment Voronoi diagram to the stream str.
template<class Stream >
Stream &	draw_skeleton (Stream &str) const
	Draws the segment Voronoi diagram to the stream str, except the edges of the diagram corresponding to a segment and its endpoints.
template<class Stream >
Stream &	draw_dual_edge (Edge e, Stream &str) const
	Draws the edge e of the segment Voronoi diagram to the stream str.
template<class Stream >
Stream &	draw_dual_edge (Edge_circulator ec, Stream &str) const
	Draws the edge *ec of the segment Voronoi diagram to the stream str.
template<class Stream >
Stream &	draw_dual_edge (All_edges_iterator eit, Stream &str) const
	Draws the edge *eit of the segment Voronoi diagram to the stream str.
template<class Stream >
Stream &	draw_dual_edge (Finite_edges_iterator eit, Stream &str) const
	Draws the edge *eit of the segment Voronoi diagram to the stream str.
void	file_output (std::ostream &os)
	Writes the current state of the segment Delaunay graph to an output stream.
void	file_input (std::istream &is)
	Reads the state of the segment Delaunay graph from an input stream.
std::ostream &	operator<< (std::ostream &os, const Segment_Delaunay_graph_2< Gt, St, DS > &sdg)
	Writes the current state of the segment Delaunay graph to an output stream.
std::istream &	operator>> (std::istream &is, Segment_Delaunay_graph_2< Gt, St, DS > &sdg)
	Reads the state of the segment Delaunay graph from an input stream.
bool	is_valid (bool verbose=false, int level=1) const
	Checks the validity of the segment Delaunay graph.
void	clear ()
	Clears all contents of the segment Delaunay graph.
void	swap (Segment_Delaunay_graph_2< Gt, St, DS > &other)
	The segment Delaunay graphs other and *this are swapped.

Constructor & Destructor Documentation

Segment_Delaunay_graph_hierarchy_2()

template<typename Gt , typename St , typename STag , typename DS >

template<class Input_iterator >

CGAL::Segment_Delaunay_graph_hierarchy_2< Gt, St, STag, DS >::Segment_Delaunay_graph_hierarchy_2	(	Input_iterator	first,
		Input_iterator	beyond,
		Gt	gt = Gt()
	)

Creates a segment Delaunay graph hierarchy using gt as geometric traits and inserts all sites in the range [first, beyond).

Input_iterator must be a model of InputIterator. The value type of Input_iterator must be either Point_2 or Site_2.

Friends And Related Function Documentation

operator<<()

template<typename Gt , typename St , typename STag , typename DS >

std::ostream & operator<< ( std::ostream &  os, const Segment_Delaunay_graph_hierarchy_2< Gt, St, STag, DS > &  svdh  )

related

Writes the current state of the segment Delaunay graph hierarchy to an output stream.

In particular, all sites in the diagram are written to the stream (represented through appropriate input sites), as well as the underlying combinatorial hierarchical data structure.