CGAL 6.1.1 - 2D Segment Delaunay Graphs

Loading...
Searching...
No Matches
List of all members
CGAL::Segment_Delaunay_graph_2< Gt, St, DS > Class Template Reference
Reference Manual

`#include <CGAL/Segment_Delaunay_graph_2.h>`

Inherited by CGAL::Segment_Delaunay_graph_hierarchy_2< Gt, St, STag, DS >.

## Definition

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

Currently it only supports the insertions of sites.

Template Parameters

  Gt | must be a model of `SegmentDelaunayGraphTraits_2`.
  St | must be a model of `SegmentDelaunayGraphStorageTraits_2`. By default, the storage traits is instantiated by `Segment_Delaunay_graph_storage_traits_2<Gt>`.
  DS | must be a model of `SegmentDelaunayGraphDataStructure_2` whose vertex and face are models of the concepts `SegmentDelaunayGraphVertexBase_2` and `TriangulationFaceBase_2`, respectively. It defaults to: CGAL::Triangulation_data_structure_2< CGAL::Segment_Delaunay_graph_vertex_base_2<St>, CGAL::Segment_Delaunay_graph_face_base_2<Gt> > CGAL::Segment_Delaunay_graph_face_base_2 Definition: Segment_Delaunay_graph_face_base_2.h:22 CGAL::Segment_Delaunay_graph_vertex_base_2 Definition: Segment_Delaunay_graph_vertex_base_2.h:24 CGAL::Triangulation_data_structure_2

Storage

To avoid redundancy in the storage of points, input points are stored in a container, and the various types of sites (input points and segments, points of intersection, subsegments with one or two points of intersection as endpoints) only store handles to the points in the container. See Section Strongly Intersecting Sites and their Representation for more information.

Traversal of the Segment Delaunay Graph

A segment Delaunay graph can be seen as a container of faces and vertices. Therefore the `Segment_Delaunay_graph_2` class provides several iterators and circulators that allow to traverse it (completely or partially).

Is model of
  `DelaunayGraph_2`

See also
  `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>`

Examples
  Segment_Delaunay_graph_2/sdg-count-sites.cpp, Segment_Delaunay_graph_2/sdg-fast-sp-polygon.cpp, Segment_Delaunay_graph_2/sdg-fast-sp.cpp, Segment_Delaunay_graph_2/sdg-red-blue-info.cpp, and Segment_Delaunay_graph_2/sdg-voronoi-edges.cpp.

## Types
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.

## Iterators and Handles
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.
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.

## 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 Delaunay graph.
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).
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.

## Creation
In addition to the default and copy constructors the following constructors are defined:
| 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`).

## Access Functions
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 Face, Edge and Vertex Iterators
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.
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.

## Infinite Face, Edge, and Vertex Iterators
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.
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, Edge and Vertex Circulators
The `Segment_Delaunay_graph_2` 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. 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.
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`.

## Predicates
The class `Segment_Delaunay_graph_2` provides methods to test the finite or infinite character of any feature.
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.

## Insertion
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.

## Nearest neighbor location
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`.

## I/O
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.

## Validity check
bool | is_valid (bool verbose=false, int level=1) const
| Checks the validity of the segment Delaunay graph.

## Miscellaneous
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.

## Member Typedef Documentation

## ◆ Edge

template<typename Gt , typename St , typename DS >

typedef DS::Edge CGAL::Segment_Delaunay_graph_2< Gt, St, DS >::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`.

## Constructor & Destructor Documentation

## ◆ Segment_Delaunay_graph_2()

template<typename Gt , typename St , typename DS >
template<class Input_iterator >

CGAL::Segment_Delaunay_graph_2< Gt, St, DS >::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`).

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

## Member Function Documentation

## ◆ dimension()

template<typename Gt , typename St , typename DS >

int CGAL::Segment_Delaunay_graph_2< Gt, St, DS >::dimension | ( |  | ) | const

Returns the dimension of the segment Delaunay graph.

The dimension is \( -1\) if the graph contains no sites, \( 0\) if the graph contains one site, \( 1\) if it contains two sites and \( 2\) if it contains three or more sites.

## ◆ draw_dual()

template<typename Gt , typename St , typename DS >
template<class Stream >

Stream & CGAL::Segment_Delaunay_graph_2< Gt, St, DS >::draw_dual | ( | Stream & | str | ) | const

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)`

## ◆ draw_dual_edge() [1/4]

template<typename Gt , typename St , typename DS >
template<class Stream >

Stream & CGAL::Segment_Delaunay_graph_2< Gt, St, DS >::draw_dual_edge | ( | All_edges_iterator | eit,
|  | Stream & | str
| ) |  | const

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.

## ◆ draw_dual_edge() [2/4]

template<typename Gt , typename St , typename DS >
template<class Stream >

Stream & CGAL::Segment_Delaunay_graph_2< Gt, St, DS >::draw_dual_edge | ( | Edge | e,
|  | Stream & | str
| ) |  | const

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.

## ◆ draw_dual_edge() [3/4]

template<typename Gt , typename St , typename DS >
template<class Stream >

Stream & CGAL::Segment_Delaunay_graph_2< Gt, St, DS >::draw_dual_edge | ( | Edge_circulator | ec,
|  | Stream & | str
| ) |  | const

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.

## ◆ draw_dual_edge() [4/4]

template<typename Gt , typename St , typename DS >
template<class Stream >

Stream & CGAL::Segment_Delaunay_graph_2< Gt, St, DS >::draw_dual_edge | ( | Finite_edges_iterator | eit,
|  | Stream & | str
| ) |  | const

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)`

## ◆ draw_skeleton()

template<typename Gt , typename St , typename DS >
template<class Stream >

Stream & CGAL::Segment_Delaunay_graph_2< Gt, St, DS >::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.

The following operators must be defined:

`Stream& operator<<(Stream&, Gt::Segment_2)`

`Stream& operator<<(Stream&, Gt::Ray_2)`

`Stream& operator<<(Stream&, Gt::Line_2)`

## ◆ file_output()

template<typename Gt , typename St , typename DS >

void CGAL::Segment_Delaunay_graph_2< Gt, St, DS >::file_output | ( | std::ostream & | os | ) |

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.

## ◆ finite_vertex()

template<typename Gt , typename St , typename DS >

Vertex_handle CGAL::Segment_Delaunay_graph_2< Gt, St, DS >::finite_vertex | ( |  | ) | const

Returns a vertex distinct from the `infinite_vertex`.

Precondition
  The number of sites in the segment Delaunay graph must be at least one.

## ◆ incident_edges()

template<typename Gt , typename St , typename DS >

Edge_circulator CGAL::Segment_Delaunay_graph_2< Gt, St, DS >::incident_edges | ( | Vertex_handle | v,
|  | Face_handle | f
| ) |  | const

Starts at the first edge of `f` incident to `v`, in counterclockwise order around `v`.

Precondition
  Face `f` is incident to vertex `v`.

## ◆ incident_faces()

template<typename Gt , typename St , typename DS >

Face_circulator CGAL::Segment_Delaunay_graph_2< Gt, St, DS >::incident_faces | ( | Vertex_handle | v,
|  | Face_handle | f
| ) |  | const

Starts at face `f`.

Precondition
  Face `f` is incident to vertex `v`.

## ◆ incident_vertices()

template<typename Gt , typename St , typename DS >

Vertex_circulator CGAL::Segment_Delaunay_graph_2< Gt, St, DS >::incident_vertices | ( | Vertex_handle | v,
|  | Face_handle | f
| ) |  | const

Starts at the first vertex of `f` adjacent to `v` in counterclockwise order around `v`.

Precondition
  Face `f` is incident to vertex `v`.

## ◆ insert() [1/9]

template<typename Gt , typename St , typename DS >

Vertex_handle CGAL::Segment_Delaunay_graph_2< Gt, St, DS >::insert | ( | const Point_2 & | p | ) |

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.

## ◆ insert() [2/9]

template<typename Gt , typename St , typename DS >

Vertex_handle CGAL::Segment_Delaunay_graph_2< Gt, St, DS >::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`.

The vertex handle returned has the same semantics as the vertex handle returned by the method `Vertex_handle insert(Point_2 p)`.

## ◆ insert() [3/9]

template<typename Gt , typename St , typename DS >

Vertex_handle CGAL::Segment_Delaunay_graph_2< Gt, St, DS >::insert | ( | const Point_2 & | p1,
|  | const Point_2 & | p2
| ) |  |

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.

## ◆ insert() [4/9]

template<typename Gt , typename St , typename DS >

Vertex_handle CGAL::Segment_Delaunay_graph_2< Gt, St, DS >::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`.

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)`.

## ◆ insert() [5/9]

template<typename Gt , typename St , typename DS >

Vertex_handle CGAL::Segment_Delaunay_graph_2< Gt, St, DS >::insert | ( | const Site_2 & | s | ) |

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.

Precondition
  `s.is_input()` must be `true`.

## ◆ insert() [6/9]

template<typename Gt , typename St , typename DS >

Vertex_handle CGAL::Segment_Delaunay_graph_2< Gt, St, DS >::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.

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`.

## ◆ insert() [7/9]

template<typename Gt , typename St , typename DS >
template<class Input_iterator >

size_type CGAL::Segment_Delaunay_graph_2< Gt, St, DS >::insert | ( | Input_iterator | first,
|  | Input_iterator | beyond
| ) |  |

Iteratively inserts the sites in the range [`first`,`beyond`).

Template Parameters

  Input_iterator | must be a model of `InputIterator` and its value type must be either `Point_2` or `Site_2`.

Returns
  the number of sites inserted in the Delaunay graph

## ◆ insert() [8/9]

template<typename Gt , typename St , typename DS >
template<class Input_iterator >

size_type CGAL::Segment_Delaunay_graph_2< Gt, St, DS >::insert | ( | Input_iterator | first,
|  | Input_iterator | beyond,
|  | CGAL::Tag_false |
| ) |  |

Iteratively inserts the sites in the range [`first`,`beyond`).

Template Parameters

  Input_iterator | must be a model of `InputIterator` and its value type must be either `Point_2` or `Site_2`.

Returns
  the number of sites inserted in the Delaunay graph

## ◆ insert() [9/9]

template<typename Gt , typename St , typename DS >
template<class Input_iterator >

size_type CGAL::Segment_Delaunay_graph_2< Gt, St, DS >::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()`.

Non-input sites are first random_shuffled and then inserted one by one.

Template Parameters

  Input_iterator | must be a model of `InputIterator` and its value type must be either `Point_2`, `Segment_2` or `Site_2`.

Returns
  the number of sites inserted in the Delaunay graph

## ◆ insert_points()

template<typename Gt , typename St , typename DS >
template<class PointIterator >

std::size_t CGAL::Segment_Delaunay_graph_2< Gt, St, DS >::insert_points | ( | PointIterator | first,
|  | PointIterator | beyond
| ) |  |

Inserts the points in the range [first,beyond) as sites.

Note that this function is not guaranteed to insert the points following the order of `PointInputIterator`, as `spatial_sort()` is used to improve efficiency.

Template Parameters

  PointIterator | must be an input iterator `Point_2` or `Site_2` as value_type.

Returns
  the number of points inserted in the Delaunay graph

## ◆ insert_segments() [1/2]

template<typename Gt , typename St , typename DS >
template<class PointIterator , class IndicesIterator >

std::size_t CGAL::Segment_Delaunay_graph_2< Gt, St, DS >::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).

The indices must start from 0 to `std::distance(points_first, points_beyond)`

Template Parameters

  PointIterator | is an input iterator with `Point_2` as value type.
  IndicesIterator | is an input iterator with `std::pair<std::size_t, std::size_t>` as value type.

Returns
  the number of segments inserted in the Delaunay graph

## ◆ insert_segments() [2/2]

template<typename Gt , typename St , typename DS >
template<class SegmentIterator >

std::size_t CGAL::Segment_Delaunay_graph_2< Gt, St, DS >::insert_segments | ( | SegmentIterator | first,
|  | SegmentIterator | beyond
| ) |  |

Inserts the segments in the range [first,beyond) as sites.

Note that this function is not guaranteed to insert the segments following the order of `SegmentIterator`, as `spatial_sort()` is used to improve efficiency.

Template Parameters

  SegmentIterator | must be an input iterator with `Site_2`, `Segment_2` or `std::pair<Point_2,Point_2>` as value type.

Returns
  the number of segments inserted in the Delaunay graph

## ◆ is_valid()

template<typename Gt , typename St , typename DS >

bool CGAL::Segment_Delaunay_graph_2< Gt, St, DS >::is_valid | ( | bool | verbose = `false`,
|  | int | level = `1`
| ) |  | const

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.

## ◆ nearest_neighbor() [1/2]

template<typename Gt , typename St , typename DS >

Vertex_handle CGAL::Segment_Delaunay_graph_2< Gt, St, DS >::nearest_neighbor | ( | const Point_2 & | p | ) | const

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.

## ◆ nearest_neighbor() [2/2]

template<typename Gt , typename St , typename DS >

Vertex_handle CGAL::Segment_Delaunay_graph_2< Gt, St, DS >::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`.

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.

## ◆ number_of_output_sites()

template<typename Gt , typename St , typename DS >

size_type CGAL::Segment_Delaunay_graph_2< Gt, St, DS >::number_of_output_sites | ( |  | ) | const

Return the number of output sites.

This is equal to the number of vertices in the segment Delaunay graph.

## ◆ swap()

template<typename Gt , typename St , typename DS >

void CGAL::Segment_Delaunay_graph_2< Gt, St, DS >::swap | ( | Segment_Delaunay_graph_2< Gt, St, DS > & | other | ) |

The segment Delaunay graphs `other` and `*this` are swapped.

For a segment Delaunay graph `sdg`, the operation `sdg`.`swap(other)` should be preferred to `sdg``= other` or to `sdg``(other)` if `other` is deleted afterwards.

## ◆ tds()

template<typename Gt , typename St , typename DS >

const Data_structure & CGAL::Segment_Delaunay_graph_2< Gt, St, DS >::tds | ( |  | ) | const

Same as `data_structure()`.

It has been added for compliance to the `DelaunayGraph_2` concept.