Navigation: Up, Table of Contents, Bibliography, Index, Title Page

CGAL::Segment_Voronoi_diagram_2<Gt,DS>

Definition

The class Segment_Voronoi_diagram_2<Gt,DS> represents the segment Voronoi diagram by its dual. Currently it supports only insertions of sites. It is templated by two template arguments Gt, which must be a model of SegmentVoronoiDiagramTraits_2 and DS, which must be a model of SegmentVoronoiDiagramDataStructure_2. The second template argument defaults to CGAL::Triangulation_data_structure_2< CGAL::Segment_Voronoi_diagram_vertex_base_2<Gt>, CGAL::Triangulation_face_base_2<Gt> >.

#include <CGAL/Segment_Voronoi_diagram_2.h>

Is Model for the Concept

DefaultConstructible
CopyConstructible
Assignable

Types

typedef Gt Geom_traits; A type for the geometric traits.
typedef DS Data_structure; A type for the underlying data structure.
typedef typename DS::size_type
size_type; Size type (an unsigned integral type)
typedef typename Gt::Point_2
Point_2; A type for the point defined in the geometric traits.
typedef typename Gt::Site_2
Site_2; A type for the segment Voronoi diagram site, defined in the geometric traits.
typedef std::set<Point_2>
Point_container; A type for the container of points.
typedef typename Point_container::iterator
Point_handle; A handle for points in the point container.

The vertices and faces of the dual of the segment Voronoi diagram are accessed through handles, iterators and circulators. The iterators and circulators are all bidirectional and non-mutable. The circulators and iterators are assignable to the corresponding handle types, and they are also convertible to the corresponding handles. The edges of the dual of the segment Voronoi diagram can also be visited through iterators and circulators, the edge circulators and iterators are also bidirectional and non-mutable. In the following, we call infinite any face or edge incident to the infinite vertex and the infinite vertex itself. Any other feature (face, edge or vertex) of the dual of the segment Voronoi diagram is said to be finite. Some iterators (the All iterators ) allow to visit finite or infinite features while the others (the Finite iterators) visit only finite features. Circulators visit both infinite and finite features.

typedef typename DS::Edge
Edge; The edge type. The Edge(f,i) is the edge common to faces f and f.neighbor(i). It is also the edge joining the vertices vertex(cw(i)) and vertex(ccw(i)) of f.
Precondition: i must be 0, 1 or 2.
typedef typename DS::Vertex_handle
Vertex_handle; A type for a handle to a vertex.
typedef typename DS::Face_handle
Face_handle; A type for a handle to a face.
typedef typename DS::Vertex_circulator
Vertex_circulator; A type for a circulator over vertices incident to a given vertex.
typedef typename DS::Face_circulator
Face_circulator; A type for a circulator over faces incident to a given vertex.
typedef typename DS::Edge_circulator
Edge_circulator; A type for a circulator over edges incident to a given vertex.
typedef typename DS::Vertex_iterator
All_vertices_iterator;
A type for an iterator over all vertices.
typedef typename DS::Face_iterator
All_faces_iterator; A type for an iterator over all faces.
typedef typename DS::Edge_iterator
All_edges_iterator; A type for an iterator over all edges.
Segment_Voronoi_diagram_2<Gt,DS>::Finite_vertices_iterator;
A type for an iterator over finite vertices.

Segment_Voronoi_diagram_2<Gt,DS>::Finite_faces_iterator;
A type for an iterator over finite faces.

Segment_Voronoi_diagram_2<Gt,DS>::Finite_edges_iterator;
A type for an iterator over finite edges.

In addition to iterators and circulators for vertices and faces, iterators for sites are provided. In particular there are iterators for the set of input sites and the set of output sites. The set of input sites is the set of sites inserted by the user using the insert methods of this class. If a site is inserted multiple times, every instance of this site will be reported. The set of output sites is the set of sites in the segment Voronoi diagram. The value type of these iterators is Site_2.

Segment_Voronoi_diagram_2<Gt,DS>::Input_sites_iterator
A type for a bidirectional iterator over all input sites.

Segment_Voronoi_diagram_2<Gt,DS>::Output_sites_iterator
A type for a bidirectional iterator over all output sites (the sites in the diagram).

Creation

In addition to the default and copy constructors the following constructors are defined:

Segment_Voronoi_diagram_2<Gt,DS> svd ( Gt gt=Gt());
Creates the dual of the segment Voronoi diagram using gt as geometric traits.


template< class Input_iterator >
Segment_Voronoi_diagram_2<Gt,DS> svd ( Input_iterator first,
Input_iterator beyond,
Gt gt=Gt());
Creates the dual of the segment Voronoi diagram using gt as geometric traits and inserts all sites in the range [first, beyond).
Precondition: Input_iterator must be a model of InputIterator. The value type of Input_iterator must be either Point_2 or Site_2.

Access Functions

Geom_traits svd.geom_traits () Returns a reference to the segment Voronoi diagram traits object.
int svd.dimension () Returns the dimension of the segment Voronoi diagram. The dimension is -1 if the diagram contains no sites, 0 if the diagram contains one site, 1 if it contains two sites and 2 if it contains three or more sites.
size_type svd.number_of_vertices ()
Returns the number of finite vertices of the dual of the segment Voronoi diagram.
size_type svd.number_of_faces ()
Returns the number of faces (both finite and infinite) of the dual of the segment Voronoi diagram.
size_type svd.number_of_input_sites ()
Return the number of input sites.
size_type svd.number_of_output_sites ()
Return the number of output sites. This is equal to the number of vertices in the dual of the segment Voronoi diagram.
Face_handle svd.infinite_face ()
Returns a face incident to the infinite_vertex.
Vertex_handle svd.infinite_vertex ()
Returns the infinite_vertex.
Vertex_handle svd.finite_vertex ()
Returns a vertex distinct from the infinite_vertex.
Precondition: The number of sites in the segment Voronoi diagram must be at least one.
Data_structure svd.data_structure ()
Returns a reference to the segment Voronoi diagram data structure object.
Point_container svd.point_container ()
Returns a reference to the point container object.

Traversal of the dual of the segment Voronoi diagram

A segment Voronoi diagram can be seen as a container of faces and vertices. Therefore the Segment_Voronoi_diagram_2<Gt,DS> class provides several iterators and circulators that allow to traverse it (completely or partially).

Face, Edge and Vertex Iterators

The following iterators allow respectively to visit finite faces, finite edges and finite vertices of the dual of the segment Voronoi diagram. These iterators are non-mutable, bidirectional and their value types are respectively Face, Edge and Vertex. They are all invalidated by any change in the segment Voronoi diagram.

Finite_vertices_iterator
svd.finite_vertices_begin ()
Starts at an arbitrary finite vertex.
Finite_vertices_iterator
svd.finite_vertices_end ()
Past-the-end iterator.

Finite_edges_iterator
svd.finite_edges_begin ()
Starts at an arbitrary finite edge.
Finite_edges_iterator
svd.finite_edges_end ()
Past-the-end iterator.

Finite_faces_iterator
svd.finite_faces_begin ()
Starts at an arbitrary finite face.
Finite_faces_iterator
svd.finite_faces_end ()
Past-the-end iterator.

The following iterators allow respectively to visit all (both finite and infinite) faces, edges and vertices of the dual of the segment Voronoi diagram. These iterators are non-mutable, bidirectional and their value types are respectively Face, Edge and Vertex. They are all invalidated by any change in the segment Voronoi diagram.

All_vertices_iterator
svd.all_vertices_begin ()
Starts at an arbitrary vertex.
All_vertices_iterator
svd.all_vertices_end ()
Past-the-end iterator.

All_edges_iterator svd.all_edges_begin ()
Starts at an arbitrary edge.
All_edges_iterator svd.all_edges_end ()
Past-the-end iterator.

All_faces_iterator svd.all_faces_begin ()
Starts at an arbitrary face.
All_faces_iterator svd.all_faces_end ()
Past-the-end iterator.

Site iterators

The following iterators allow respectively to visit all sites. These iterators are non-mutable, bidirectional and their value type is Site_2. They are all invalidated by any change in the segment Voronoi diagram.

Input_sites_iterator
svd.input_sites_begin ()
Starts at an arbitrary input site.
Input_sites_iterator
svd.input_sites_end ()
Past-the-end iterator.
Output_sites_iterator
svd.output_sites_begin ()
Starts at an arbitrary output site.
Output_sites_iterator
svd.output_sites_end ()
Past-the-end iterator.

Face, Edge and Vertex Circulators

The Segment_Voronoi_diagram_2<Gt,DS> class also provides circulators that allow to visit respectively all faces or edges incident to a given vertex or all vertices adjacent to a given vertex. These circulators are non-mutable and bidirectional. The operator operator++ moves the circulator counterclockwise around the vertex while the operator-- moves clockwise. A face circulator is invalidated by any modification of the face pointed to. An edge circulator is invalidated by any modification in one of the two faces incident to the edge pointed to. A vertex circulator is invalidated by any modification in any of the faces adjacent to the vertex pointed to.

Face_circulator svd.incident_faces ( Vertex_handle v)
Starts at an arbitrary face incident to v.
Face_circulator svd.incident_faces ( Vertex_handle v, Face_handle f)
Starts at face f.
Precondition: Face f is incident to vertex v.
Edge_circulator svd.incident_edges ( Vertex_handle v)
Starts at an arbitrary edge incident to v.
Edge_circulator svd.incident_edges ( Vertex_handle v, Face_handle f)
Starts at the first edge of f incident to v, in counterclockwise order around v.
Precondition: Face f is incident to vertex v.
Vertex_circulator svd.incident_vertices ( Vertex_handle v)
Starts at an arbitrary vertex incident to v.
Vertex_circulator svd.incident_vertices ( Vertex_handle v, Face_handle f)
Starts at the first vertex of f adjacent to v in counterclockwise order around v.
Precondition: Face f is incident to vertex v.

Traversal of the Convex Hull

Applied on the infinite_vertex the above methods allow to visit the vertices on the convex hull and the infinite edges and faces. Note that a counterclockwise traversal of the vertices adjacent to the infinite_vertex is a clockwise traversal of the convex hull.

Vertex_circulator svd.incident_vertices ( svd.infinite_vertex())
Vertex_circulator
svd.incident_vertices ( svd.infinite_vertex(),
Face_handle f)
Face_circulator svd.incident_faces ( svd.infinite_vertex())
Face_circulator
svd.incident_faces ( svd.infinite_vertex(),
Face_handle f)
Edge_circulator svd.incident_edges ( svd.infinite_vertex())
Edge_circulator
svd.incident_edges ( svd.infinite_vertex(),
Face_handle f)

Predicates

The class Segment_Voronoi_diagram_2<Gt,DS> provides methods to test the finite or infinite character of any feature.

bool svd.is_infinite ( Vertex_handle v)
true, iff v is the infinite_vertex.
bool svd.is_infinite ( Face_handle f)
true, iff face f is infinite.
bool svd.is_infinite ( Face_handle f, int i)
true, iff edge (f,i) is infinite.
bool svd.is_infinite ( Edge e)
true, iff edge e is infinite.
bool svd.is_infinite ( Edge_circulator ec)
true, iff edge *ec is infinite.

Insertion

template< class Input_iterator >
size_type
svd.insert ( Input_iterator first,
Input_iterator beyond)
Inserts the sites in the range [first,beyond). The number of additional sites inserted in the diagram is returned. Input_iterator must be a model of InputIterator and its value type must be either Point_2 or Site_2.

template< class Input_iterator >
size_type
svd.insert ( Input_iterator first,
Input_iterator beyond,
Tag_false)
Same as the previous method. Input_iterator must be a model of InputIterator and its value type must be either Point_2 or Site_2.

template< class Input_iterator >
size_type
svd.insert ( Input_iterator first,
Input_iterator beyond,
Tag_true)
Inserts the sites in the range [first,beyond) after performing a random shuffle on them. The number of additional sites inserted in the diagram is returned. Input_iterator must be a model of InputIterator and its value type must be either Point_2 or Site_2.
Vertex_handle svd.insert ( Point_2 p)
Inserts the point p in the segment Voronoi diagram. If p has already been inserted, then the vertex handle of its already inserted copy is returned. If p has not been inserted yet, the vertex handle of p is returned.
Vertex_handle svd.insert ( Point_2 p, Vertex_handle vnear)
Inserts p in the segment Voronoi diagram using the site associated with vnear as an estimate for the nearest neighbor of p. The vertex handle returned has the same semantics as the vertex handle returned by the method Vertex_handle insert(Point_2 p).
Vertex_handle svd.insert ( Point_2 p1, Point_2 p2)
Inserts the closed segment with endpoints p1 and p2 in the segment Voronoi diagram. If the segment has already been inserted in the diagram then the vertex handle of its already inserted copy is returned. If the segment does not intersect any segment in the existing diagram, the vertex handle corresponding to its corresponding open segment is returned. Finally, if the segment intersects other segments in the existing Voronoi diagram, the vertex handle to one of its open subsegments is returned.
Vertex_handle
svd.insert ( Point_2 p1,
Point_2 p2,
Vertex_handle vnear)
Inserts the segment whose endpoints are p1 and p2 in the segment Voronoi diagram using the site associated with vnear as an estimate for the nearest neighbor of p1. The vertex handle returned has the same semantics as the vertex handle returned by the method Vertex_handle insert(Point_2 p1, Point_2 p2).
Vertex_handle svd.insert ( Site_2 s)
Inserts the site s in the segment Voronoi diagram. The vertex handle returned has the same semantics as the vertex handle returned by the methods Vertex_handle insert(Point_2 p) and Vertex_handle insert(Point_2 p1, Point_2 p2), depending on whether s represents a point or a segment respectively.
Precondition: s.is_input() must be true.
Vertex_handle svd.insert ( Site_2 s, Vertex_handle vnear)
Inserts s in the segment Voronoi diagram 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. The vertex handle returned has the same semantics as the vertex handle returned by the method Vertex_handle insert(Site_2 s).
Precondition: s.is_input() must be true.

Nearest neighbor location

Vertex_handle svd.nearest_neighbor ( Point_2 p)
Finds the nearest neighbor of the point p. In other words it finds the site whose segment Voronoi diagram cell contains p. Ties are broken arbitrarily and one of the nearest neighbors of p is returned. If there are no sites in the segment Voronoi diagram Vertex_handle() is returned.
Vertex_handle svd.nearest_neighbor ( Point_2 p, Vertex_handle vnear)
Finds the nearest neighbor of the point p using the site associated with vnear as an estimate for the nearest neighbor of p. Ties are broken arbitrarily and one of the nearest neighbors of p is returned. If there are no sites in the segment Voronoi diagram Vertex_handle() is returned.

I/O

template < class Stream >
Stream& svd.draw_dual ( Stream& str)
Draws the segment Voronoi diagram to the stream str. The following operators must be defined:
Stream& operator<<(Stream&, Gt::Segment_2)
Stream& operator<<(Stream&, Gt::Ray_2)
Stream& operator<<(Stream&, Gt::Line_2)
template < class Stream >
Stream& svd.draw_skeleton ( Stream& str)
Draws the segment Voronoi diagram to the stream str, except the edges of the diagram corresponding to a segment and its endpoints. The following operators must be defined:
Stream& operator<<(Stream&, Gt::Segment_2)
Stream& operator<<(Stream&, Gt::Ray_2)
Stream& operator<<(Stream&, Gt::Line_2)
template< class Stream >
Stream& svd.draw_dual_edge ( Edge e, Stream& str)
Draws the edge e of the segment Voronoi diagram to the stream str. The following operators must be defined:
Stream& operator<<(Stream&, Gt::Segment_2)
Stream& operator<<(Stream&, Gt::Ray_2)
Stream& operator<<(Stream&, Gt::Line_2)
Precondition: e must be a finite edge.
template< class Stream >
Stream& svd.draw_dual_edge ( Edge_circulator ec, Stream& str)
Draws the edge *ec of the segment Voronoi diagram to the stream str. The following operators must be defined:
Stream& operator<<(Stream&, Gt::Segment_2)
Stream& operator<<(Stream&, Gt::Ray_2)
Stream& operator<<(Stream&, Gt::Line_2)
Precondition: *ec must be a finite edge.
template< class Stream >
Stream&
svd.draw_dual_edge ( All_edges_iterator eit,
Stream& str)
Draws the edge *eit of the segment Voronoi diagram to the stream str. The following operators must be defined:
Stream& operator<<(Stream&, Gt::Segment_2)
Stream& operator<<(Stream&, Gt::Ray_2)
Stream& operator<<(Stream&, Gt::Line_2)
Precondition: *eit must be a finite edge.
template< class Stream >
Stream&
svd.draw_dual_edge ( Finite_edges_iterator eit,
Stream& str)
Draws the edge *eit of the segment Voronoi diagram to the stream str. The following operators must be defined:
Stream& operator<<(Stream&, Gt::Segment_2)
Stream& operator<<(Stream&, Gt::Ray_2)
Stream& operator<<(Stream&, Gt::Line_2)

Validity check

bool svd.is_valid ( bool verbose = false, int level = 1)
Checks the validity of the segment Voronoi diagram. If verbose is true a short message is sent to std::cerr. If level is 0, only the data structure is validated. If level is 1, then both the data structure and the segment Voronoi diagram are validated. Negative values of level always return true, and values greater than 1 are equivalent to level being 1.

Miscellaneous

void svd.clear () Clears all contents of the segment Voronoi diagram.
void svd.swap ( other) The segment Voronoi diagrams other and svd are swapped. svd.swap(other) should be preferred to svd = other or to svd(other) if other is deleted afterwards.

See Also

SegmentVoronoiDiagramTraits_2
SegmentVoronoiDiagramDataStructure_2
SegmentVoronoiDiagramVertexBase_2
TriangulationFaceBase_2
CGAL::Segment_Voronoi_diagram_hierarchy_2<Gt,STag,DS>
CGAL::Segment_Voronoi_diagram_traits_2<K,MTag>
CGAL::Segment_Voronoi_diagram_traits_without_intersections_2<K,MTag>
CGAL::Segment_Voronoi_diagram_filtered_traits_2<CK,CM,EK,EM,FK,FM>
CGAL::Segment_Voronoi_diagram_filtered_traits_without_intersections_2<CK,CM,EK,EM,FK,FM>
CGAL::Triangulation_data_structure_2<Vb,Fb>
CGAL::Segment_Voronoi_diagram_vertex_base_2<Gt,SSTag>
CGAL::Triangulation_face_base_2<Gt>

Next: SegmentVoronoiDiagramSite_2
Navigation: Table of Contents, Bibliography, Index, Title Page
The CGAL Project . Tue, December 21, 2004 .