CGAL 6.1 - 2D Segment Delaunay Graphs

Loading...
Searching...
No Matches
List of all members | Related Functions
CGAL::Segment_Delaunay_graph_hierarchy_2< Gt, St, STag, DS > Class Template Reference
Reference Manual

`#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> > CGAL::Segment_Delaunay_graph_face_base_2 Definition: Segment_Delaunay_graph_face_base_2.h:22 CGAL::Segment_Delaunay_graph_hierarchy_vertex_base_2 The class Segment_Delaunay_graph_hierarchy_vertex_base_2 provides a model for the SegmentDelaunayGrap... Definition: Segment_Delaunay_graph_hierarchy_vertex_base_2.h:25 CGAL::Segment_Delaunay_graph_vertex_base_2 Definition: Segment_Delaunay_graph_vertex_base_2.h:24 CGAL::Triangulation_data_structure_2

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.