The class Segment_Delaunay_graph_2<Gt,DS> represents the segment Delaunay graph (which is the dual graph of the 2D segment Voronoi diagram). Currently it supports only insertions of sites. It is templated by two template arguments Gt, which must be a model of SegmentDelaunayGraphTraits_2 and DS, which must be a model of SegmentDelaunayGraphDataStructure_2. The second template argument defaults to CGAL::Triangulation_data_structure_2< CGAL::Segment_Delaunay_graph_vertex_base_2<Gt>, CGAL::Triangulation_face_base_2<Gt> >.
#include <CGAL/Segment_Delaunay_graph_2.h>
|
| A type for the geometric traits. |
|
| A type for the underlying data structure. |
|
| This type has been added so that the Segment_Delaunay_graph_2<Gt,DS> class is a model of the DelaunayGraph_2 concept. |
|
| Size type (an unsigned integral type) |
|
| A type for the point defined in the geometric traits. |
|
| A type for the segment Delaunay graph site, defined in the geometric traits. |
| |
A type for the container of points.
|
| ||
| A handle for points in the point container. |
The vertices and faces of the segment Delaunay graph 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 segment Delaunay graph 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 segment Delaunay graph 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.
| |
A type for an iterator over finite vertices.
| |
| |
A type for an iterator over finite faces.
| |
| |
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 Delaunay graph. The value type of these iterators is Site_2.
| |
A type for a bidirectional iterator over all input sites.
| |
| |
A type for a bidirectional iterator over all output sites (the sites
in the Delaunay graph).
|
In addition to the default and copy constructors the following constructors are defined:
| |||
Creates the
segment Delaunay graph using gt as geometric traits.
| |||
| |||
| |||
Creates the segment Delaunay graph using gt as geometric traits
and inserts all sites in the range [first, beyond).
|
|
| Returns a reference to the segment Delaunay graph traits object. | ||
|
| Returns the dimension of the segment Delaunay graph. The dimension is if the graph contains no sites, if the graph contains one site, if it contains two sites and if it contains three or more sites. | ||
|
| Returns the number of finite vertices of the segment Delaunay graph. | ||
|
| Returns the number of faces (both finite and infinite) of the segment Delaunay graph. | ||
|
| Return the number of input sites. | ||
|
| Return the number of output sites. This is equal to the number of vertices in the segment Delaunay graph. | ||
|
| Returns a face incident to the infinite_vertex. | ||
|
| Returns the infinite_vertex. | ||
|
|
Returns a vertex distinct from the infinite_vertex.
| ||
|
| Returns a reference to the segment Delaunay graph data structure object. | ||
|
| Same as data_structure(). It has been added for compliance to the DelaunayGraph_2 concept. | ||
|
| Returns a reference to the point container object. |
A segment Delaunay graph can be seen as a container of faces and vertices. Therefore the Segment_Delaunay_graph_2<Gt,DS> class provides several iterators and circulators that allow to traverse it (completely or partially).
The following iterators allow respectively to visit finite faces, finite edges and finite vertices of the segment Delaunay graph. 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 Delaunay graph.
|
| Starts at an arbitrary finite vertex. |
|
| Past-the-end iterator. |
|
| Starts at an arbitrary finite edge. |
|
| Past-the-end iterator. |
|
| Starts at an arbitrary finite face. |
|
| Past-the-end iterator. |
The following iterators allow respectively to visit all (both finite and infinite) faces, edges and vertices of the segment Delaunay graph. 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 Delaunay graph.
|
| Starts at an arbitrary vertex. |
|
| Past-the-end iterator. |
|
| Starts at an arbitrary edge. |
|
| Past-the-end iterator. |
|
| Starts at an arbitrary face. |
|
| Past-the-end iterator. |
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 Delaunay graph.
|
| Starts at an arbitrary input site. |
|
| Past-the-end iterator. |
|
| Starts at an arbitrary output site. |
|
| Past-the-end iterator. |
The Segment_Delaunay_graph_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.
|
| |||
Starts at an arbitrary face incident to v. | ||||
|
| |||
Starts at face f.
| ||||
|
| |||
Starts at an arbitrary edge incident to v. | ||||
|
| |||
Starts at the first edge of f incident to
v, in counterclockwise order around v.
| ||||
|
| |||
Starts at an arbitrary vertex incident to v. | ||||
|
| |||
Starts at the first vertex of f adjacent to v
in counterclockwise order around v.
|
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.
|
| |
|
| |
|
| |
|
| |
|
| |
|
|
|
| |
true, iff v is the infinite_vertex. | ||
|
| true, iff face f is infinite. |
|
| |
true, iff edge (f,i) is infinite. | ||
|
| true, iff edge e is infinite. |
|
| |
true, iff edge *ec is infinite. |
| ||||
|
| |||
Inserts the sites in the range [first,beyond). The number of additional sites inserted in the Delaunay graph is returned. Input_iterator must be a model of InputIterator and its value type must be either Point_2 or Site_2. | ||||
| ||||
|
| |||
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. | ||||
| ||||
|
| |||
Inserts the sites in the range [first,beyond) after performing a random shuffle on them. The number of additional sites inserted in the Delaunay graph is returned. Input_iterator must be a model of InputIterator and its value type must be either Point_2 or Site_2. | ||||
|
| Inserts the point p in the segment Delaunay graph. 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. | ||
|
| |||
Inserts p in the segment Delaunay graph 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). | ||||
|
| |||
Inserts the closed segment with endpoints p1 and p2 in the segment Delaunay graph. If the segment has already been inserted in the Delaunay graph 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 Delaunay graph, the vertex handle to one of its open subsegments is returned. | ||||
|
| |||
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. 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). | ||||
|
|
Inserts the site s in the
segment Delaunay graph. 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.
| ||
|
| |||
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. The vertex handle returned has the same
semantics as the vertex handle returned by the method
Vertex_handle insert(Site_2 s).
|
|
| 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 Delaunay graph Vertex_handle() is returned. |
|
| |
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 Delaunay graph Vertex_handle() is returned. |
| ||||
|
|
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) | ||
| ||||
|
|
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) | ||
| ||||
|
| |||
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)
| ||||
| ||||
|
| |||
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)
| ||||
| ||||
|
| |||
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)
| ||||
| ||||
|
| |||
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) | ||||
|
| |||
Writes the current state of the segment Delaunay graph 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 data structure. | ||||
|
| |||
Reads the state of the segment Delaunay graph from an input stream. | ||||
|
| Writes the current state of the segment Delaunay graph to an output stream. | ||
|
| Reads the state of the segment Delaunay graph from an input stream. |
|
| |
Checks the validity of the segment Delaunay graph. 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 Delaunay graph are validated. Negative values of level always return true, and values greater than 1 are equivalent to level being 1. |
|
| Clears all contents of the segment Delaunay graph. |
|
| The segment Delaunay graphs other and sdg are swapped. sdg.swap(other) should be preferred to sdg = other or to sdg(other) if other is deleted afterwards. |