CGAL 6.1 - 2D Periodic Hyperbolic Triangulations

Loading...
Searching...
No Matches
List of all members
CGAL::Periodic_4_hyperbolic_triangulation_2< GT, TDS > Class Template Reference
Reference Manual » Main Classes

`#include <CGAL/Periodic_4_hyperbolic_triangulation_2.h>`

Inherited by CGAL::Periodic_4_hyperbolic_Delaunay_triangulation_2< GT, TDS >.

## Definition

template<class GT, class TDS>
class CGAL::Periodic_4_hyperbolic_triangulation_2< GT, TDS >

The class `Periodic_4_hyperbolic_triangulation_2` offers base functionalities needed by `Periodic_4_hyperbolic_Delaunay_triangulation_2`.

Note that this class does not support modification of the triangulation (insertion or removal).

The class expects two template parameters.

Template Parameters

  GT | Geometric traits parameter. Must be a model of the concept `Periodic_4HyperbolicTriangulationTraits_2`. This parameter has no default value.
  TDS | Triangulation data structure parameter. Must be a model of the concept `TriangulationDataStructure_2` with some additional functionality in the vertices and faces, following the concepts `Periodic_4HyperbolicTriangulationVertexBase_2` and `Periodic_4HyperbolicTriangulationFaceBase_2`, respectively. The default value for this parameter is CGAL::Triangulation_data_structure_2< CGAL::Periodic_4_hyperbolic_triangulation_vertex_base_2<GT>, CGAL::Periodic_4_hyperbolic_triangulation_face_base_2<GT> > CGAL::Periodic_4_hyperbolic_triangulation_face_base_2 The class Periodic_4_hyperbolic_triangulation_face_base_2 is the default model for the concept Period... Definition: Periodic_4_hyperbolic_triangulation_face_base_2.h:32 CGAL::Periodic_4_hyperbolic_triangulation_vertex_base_2 The class Periodic_4_hyperbolic_triangulation_vertex_base_2 is the default model for the concept Peri... Definition: Periodic_4_hyperbolic_triangulation_vertex_base_2.h:31 CGAL::Triangulation_data_structure_2

## Enums
The following enumeration type indicates where a point is located in the triangulation.
enum | Locate_type { VERTEX = 0 , EDGE , FACE }

## Types
typedef GT | Geometric_traits
typedef TDS | Triangulation_data_structure
The following types represent geometric objects.
typedef Triangulation_data_structure::Vertex::Point | Point
| Represents a point in the hyperbolic plane.
typedef Geometric_traits::Hyperbolic_segment_2 | Hyperbolic_segment
| Represents a hyperbolic segment in the hyperbolic plane.
typedef Geometric_traits::Hyperbolic_triangle_2 | Hyperbolic_triangle
| Represents a triangle contained in the Poincaré disk.
The following type represents hyperbolic translations specific for the Bolza surface.
typedef Geometric_traits::Hyperbolic_translation | Hyperbolic_translation
The following types represent images of points, segments, and triangles under the action of hyperbolic translations.
typedef std::pair< Point, Hyperbolic_translation > | Periodic_point
| Represents a periodic point, i.e., a pair of a point in the original octagon and a hyperbolic translation.
typedef std::array< std::pair< Point, Hyperbolic_translation >, 2 > | Periodic_segment
| Represents a periodic segment, defined by two periodic points.
typedef std::array< std::pair< Point, Hyperbolic_translation >, 3 > | Periodic_triangle
| Represents a periodic triangle, defined by three periodic points.
The following types give access to the elements of the triangulation.
typedef Triangulation_data_structure::Edge | Edge
typedef Triangulation_data_structure::Face | Face
typedef Triangulation_data_structure::Vertex_handle | Vertex_handle
typedef Triangulation_data_structure::Face_handle | Face_handle
The following iterator and circulator types are defined to give access over the vertices, edges, and faces of the triangulation.
typedef Triangulation_data_structure::Face_iterator | Face_iterator
typedef Triangulation_data_structure::Edge_iterator | Edge_iterator
typedef Triangulation_data_structure::Vertex_iterator | Vertex_iterator
typedef Triangulation_data_structure::Face_circulator | Face_circulator
typedef Triangulation_data_structure::Edge_circulator | Edge_circulator
typedef Triangulation_data_structure::Vertex_circulator | Vertex_circulator

## Creation
| Periodic_4_hyperbolic_triangulation_2 (const Geometric_traits &gt=Geometric_traits())
| Default constructor, with an optional parameter for the geometric traits object.
| Periodic_4_hyperbolic_triangulation_2 (const Periodic_4_hyperbolic_triangulation_2 &tr)
| Copy constructor.

## Assignment
Periodic_4_hyperbolic_triangulation_2 & | operator= (Periodic_4_hyperbolic_triangulation_2 tr)
| The triangulation `tr` is duplicated, and modifying the copy after the duplication does not modify the original.
void | swap (Periodic_4_hyperbolic_triangulation_2 &tr)
| The triangulation is swapped with `tr`.
void | clear ()
| Deletes all faces and vertices of the triangulation.

## Access functions
const Geometric_traits & | geom_traits () const
| Returns a const reference to the geometric traits object.
const Triangulation_data_structure & | tds () const
| Returns a const reference to the triangulation data structure.
Triangulation_data_structure & | tds ()
| Returns a reference to the triangulation data structure.
size_type | number_of_vertices () const
| Returns the number of vertices in the triangulation.
size_type | number_of_edges () const
| Returns the number of edges in the triangulation.
size_type | number_of_faces () const
| Returns the number of faces in the triangulation.

## Geometric access functions
The functions below return periodic points, segments, and triangles.
Periodic_point | periodic_point (const Face_handle f, int i) const
| Returns the periodic point given by the `i`-th vertex of face `f`, that is the point in the original domain and the translation of the vertex in `f`.
Periodic_segment | periodic_segment (const Point &p1, const Point &p2, const Hyperbolic_translation &tr1, const Hyperbolic_translation &tr2) const
| Returns the periodic segment formed by the two point-translation pairs `(p1, tr1)` and `(p2, tr2)`.
Periodic_segment | periodic_segment (const Point &p1, const Point &p2) const
| Returns the periodic segment formed by the two point-translation pairs `(p1, Id)` and `(p2, Id)`, where `Id` is the identity translation.
Periodic_segment | periodic_segment (const Face_handle c, int i, int j) const
| Returns the periodic segment formed by the endpoints of edge `(f,i,j)`.
Periodic_segment | periodic_segment (const Edge &e) const
| Returns the periodic segment formed by the endpoints of edge `e`.
Periodic_segment | periodic_segment (const Edge &e, const Hyperbolic_translation &tr) const
| Returns the periodic segment formed by the endpoints of edge `e` translated by `tr`.
Periodic_triangle | periodic_triangle (const Face &f) const
| Returns the periodic triangle formed by the pairs of points and translations corresponding to each vertex of `f`.
Periodic_triangle | periodic_triangle (const Face &f, const Hyperbolic_translation &tr) const
| Returns the periodic triangle formed by the pairs of points and translations corresponding to each vertex of `f`, translated by `tr`.
The functions below return non-periodic points, segments and triangles.
Point | construct_point (const Periodic_point &pp) const
| Converts the periodic point `pp` into a point in the hyperbolic plane by applying `pp.second` to `pp.first`.
Hyperbolic_segment | construct_hyperbolic_segment (const Face_handle &fh, int idx) const
| Constructs the hyperbolic segment formed by the endpoints of edge `(fh, idx)`.
Hyperbolic_segment | construct_hyperbolic_segment (const Point &p1, const Point &p2) const
| Returns the hyperbolic segment with endpoints `p1` and `p2`.
Hyperbolic_segment | construct_hyperbolic_segment (const pair< Face_handle, int > &e) const
| Returns the hyperbolic segment formed by the endpoints of `e`.
Hyperbolic_segment | construct_hyperbolic_segment (const Periodic_segment &ps) const
| Returns the hyperbolic segment formed by the endpoints of `ps`.
Triangle | construct_triangle (const Face_handle &fh) const
| Returns the triangle formed by the vertices of `fh`.
Triangle | construct_triangle (const Periodic_triangle &pt) const
| Returns the triangle formed by the vertices of `pt`.

## Point location
Face_handle | hyperbolic_periodic_locate (const Point &p, Hyperbolic_translation &lo, const Face_handle start=Face_handle()) const
| Returns the face `rf` for which the periodic triangle `(rf, lo)` contains the query point `p`.
Face_handle | hyperbolic_periodic_locate (const Point &p, Locate_type &lt, int &li, Hyperbolic_translation &lo, const Face_handle start=Face_handle()) const
| Same as above.
Face_handle | hyperbolic_locate (const Point &p, Face_handle start=Face_handle()) const
| Returns the canonical representative of the face that contains the query point `p`.
Face_handle | hyperbolic_locate (const Point &p, Locate_type &lt, int &li, Face_handle start=Face_handle()) const
| Same as above.

## Predicate functions
Orientation | orientation (const Point &p1, const Point &p2, const Point &p3) const
| Returns the `Orientation` of the points `p1, p2, p3`.
Orientation | orientation (const Point &p1, const Point &p2, const Point &p3, const Hyperbolic_translation &tr1, const Hyperbolic_translation &tr2, const Hyperbolic_translation &tr3) const
| Returns the `Orientation` of the three periodic points `(p1, tr1), (p2, tr2)` and `(p3, tr3)`.
Oriented_side | side_of_oriented_circle (const Point &p1, const Point &p2, const Point &p3, const Point &q) const
| Returns the `Oriented_side` on which `q` is located with respect to the circle defined by the points `p1,p2,p3`.
Oriented_side | side_of_oriented_circle (const Point &p1, const Point &p2, const Point &p3, const Point &q, const Hyperbolic_translation &tr1, const Hyperbolic_translation &tr2, const Hyperbolic_translation &tr3, const Hyperbolic_translation &trq) const
| Returns the `Oriented_side` on which the periodic point `(q, trq)` is located with respect to the circle defined by the periodic points `(p1, tr1), (p2, tr2)` and `(p3, tr3)`.

## Queries
bool | is_vertex (Vertex_handle v) const
| Tests whether `v` is a vertex of the triangulation.
bool | is_edge (Vertex_handle u, Vertex_handle v, Face_handle &fh, int &i) const
| Tests whether `(u, v)` is an edge of the triangulation.
bool | is_face (Vertex_handle u, Vertex_handle v, Vertex_handle w, Face_handle &fh) const
| Tests whether there exists a face in the triangulation with vertices `u, v` and `w`.
bool | has_vertex (const Face_handle f, const Vertex_handle v, const int i) const
| Tests whether face `f` has `v` as a vertex.

## Vertex, Edge, and Face iterators
Vertex_iterator | vertices_begin () const
| Starts at an arbitrary vertex.
Vertex_iterator | vertices_end () const
| Past-the-end iterator.
Edge_iterator | edges_begin () const
| Starts at an arbitrary edge.
Edge_iterator | edges_end () const
| Past-the-end iterator.
Face_iterator | faces_begin () const
| Starts at an arbitrary face.
Face_iterator | faces_end () const
| Past-the-end iterator.

## Vertex, Edge and Face circulators
Vertex_circulator | adjacent_vertices (Vertex_handle v) const
| Starts at an arbitrary vertex incident to `v`.
Vertex_circulator | adjacent_vertices (Vertex_handle v, Face_handle f) const
| Starts at the first vertex of `f` adjacent to `v` in counterclockwise order around `v`.
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`.
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`.

## Traversal of the Vertices, Edges and Faces incident to a vertex
template<class OutputIterator >
OutputIterator | incident_faces (Vertex_handle v, OutputIterator faces) const
| Copies the faces incident to `v` into the output iterator `faces`.
template<class OutputIterator >
OutputIterator | incident_edges (Vertex_handle v, OutputIterator edges) const
| Copies the edges incident to `v` into the output iterator `edges`.
template<class OutputIterator >
OutputIterator | adjacent_vertices (Vertex_handle v, OutputIterator vertices) const
| Copies the vertices incident to `v` into the output iterator `vertices`.
size_type | degree (Vertex_handle v) const
| Returns the degree of `v`, i.e., the number of edges incident to `v`.

## Traversal between adjacent faces
int | mirror_index (Face_handle f, int i) const
| Returns the index of `f` in its `i`-th neighbor.
Vertex_handle | mirror_vertex (Face_handle f, int i) const
| Returns the vertex of the `i`-th neighbor of `f` that is opposite to `f`.
Edge | mirror_edge (Edge e) const
| Returns the same edge seen from the other adjacent face.
Hyperbolic_translation | neighbor_translation (const Face_handle fh, int i) const
| Returns the hyperbolic translation for which the `i`-th neighbor of `fh` is adjacent to (the canonical representative of) `fh` in the hyperbolic plane.

## Validity checking
bool | is_valid (bool verbose=false) const
| Checks the combinatorial validity of the triangulation, and also the validity of its geometric embedding.
bool | is_valid (Face_handle f, bool verbose=false) const
| Checks the combinatorial validity of face `f`.

## Member Typedef Documentation

## ◆ Point

template<class GT , class TDS >

typedef Triangulation_data_structure::Vertex::Point CGAL::Periodic_4_hyperbolic_triangulation_2< GT, TDS >::Point

Represents a point in the hyperbolic plane.

Note that for Delaunay triangulations of the Bolza surface, all points must lie inside the original hyperbolic octagon.

## Member Enumeration Documentation

## ◆ Locate_type

template<class GT , class TDS >

enum CGAL::Periodic_4_hyperbolic_triangulation_2::Locate_type

Enumerator
VERTEX | the located point coincides with a vertex of the triangulation
EDGE | the point is in the relative interior of an edge
FACE | the point is in the interior of a facet

## Member Function Documentation

## ◆ construct_hyperbolic_segment()

template<class GT , class TDS >

Hyperbolic_segment CGAL::Periodic_4_hyperbolic_triangulation_2< GT, TDS >::construct_hyperbolic_segment | ( | const Face_handle & | fh,
|  | int | idx
| ) |  | const

Constructs the hyperbolic segment formed by the endpoints of edge `(fh, idx)`.

Precondition
  \( 0 \leq idx \leq 2 \)

## ◆ edges_begin()

template<class GT , class TDS >

Edge_iterator CGAL::Periodic_4_hyperbolic_triangulation_2< GT, TDS >::edges_begin | ( |  | ) | const

Starts at an arbitrary edge.

Iterates over all the edges in the triangulation.

## ◆ faces_begin()

template<class GT , class TDS >

Face_iterator CGAL::Periodic_4_hyperbolic_triangulation_2< GT, TDS >::faces_begin | ( |  | ) | const

Starts at an arbitrary face.

Iterates over all the faces of the triangulation.

## ◆ has_vertex()

template<class GT , class TDS >

bool CGAL::Periodic_4_hyperbolic_triangulation_2< GT, TDS >::has_vertex | ( | const Face_handle | f,
|  | const Vertex_handle | v,
|  | const int | i
| ) |  | const

Tests whether face `f` has `v` as a vertex.

If the answer is `true`, then `i` contains the index of `v` in `f`.

## ◆ hyperbolic_locate() [1/2]

template<class GT , class TDS >

Face_handle CGAL::Periodic_4_hyperbolic_triangulation_2< GT, TDS >::hyperbolic_locate | ( | const Point & | p,
|  | Face_handle | start = `Face_handle()`
| ) |  | const

Returns the canonical representative of the face that contains the query point `p`.

The parameter `start`, if provided, is used as a starting point for the location.

## ◆ hyperbolic_locate() [2/2]

template<class GT , class TDS >

Face_handle CGAL::Periodic_4_hyperbolic_triangulation_2< GT, TDS >::hyperbolic_locate | ( | const Point & | p,
|  | Locate_type & | lt,
|  | int & | li,
|  | Face_handle | start = `Face_handle()`
| ) |  | const

Same as above.

The value of the variable `lt` indicates whether `p` has been located inside the canonical representative, on one of its sides, or on one of its vertices. If `p` is located on a side or on a vertex, then `li` contains the index of the corresponding edge or vertex in the returned face. The parameter `start`, if provided, is used as a starting point for the location.

## ◆ hyperbolic_periodic_locate() [1/2]

template<class GT , class TDS >

Face_handle CGAL::Periodic_4_hyperbolic_triangulation_2< GT, TDS >::hyperbolic_periodic_locate | ( | const Point & | p,
|  | Hyperbolic_translation & | lo,
|  | const Face_handle | start = `Face_handle()`
| ) |  | const

Returns the face `rf` for which the periodic triangle `(rf, lo)` contains the query point `p`.

The parameter `start`, if provided, is used as a starting point for the location.

## ◆ hyperbolic_periodic_locate() [2/2]

template<class GT , class TDS >

Face_handle CGAL::Periodic_4_hyperbolic_triangulation_2< GT, TDS >::hyperbolic_periodic_locate | ( | const Point & | p,
|  | Locate_type & | lt,
|  | int & | li,
|  | Hyperbolic_translation & | lo,
|  | const Face_handle | start = `Face_handle()`
| ) |  | const

Same as above.

The value of the variable `lt` indicates whether `p` has been located inside the hyperbolic triangle, on one of its sides, or on one of its vertices. If `p` is located on a side or on a vertex, then `li` contains the index of the corresponding edge or vertex in the returned face. The parameter `start`, if provided, is used as a starting point for the location.

## ◆ is_edge()

template<class GT , class TDS >

bool CGAL::Periodic_4_hyperbolic_triangulation_2< GT, TDS >::is_edge | ( | Vertex_handle | u,
|  | Vertex_handle | v,
|  | Face_handle & | fh,
|  | int & | i
| ) |  | const

Tests whether `(u, v)` is an edge of the triangulation.

If the edge is found, then it is the `i`-th edge of `fh`.

## ◆ is_face()

template<class GT , class TDS >

bool CGAL::Periodic_4_hyperbolic_triangulation_2< GT, TDS >::is_face | ( | Vertex_handle | u,
|  | Vertex_handle | v,
|  | Vertex_handle | w,
|  | Face_handle & | fh
| ) |  | const

Tests whether there exists a face in the triangulation with vertices `u, v` and `w`.

If the face is found, then it is returned as `fh`.

## ◆ orientation()

template<class GT , class TDS >

Orientation CGAL::Periodic_4_hyperbolic_triangulation_2< GT, TDS >::orientation | ( | const Point & | p1,
|  | const Point & | p2,
|  | const Point & | p3
| ) |  | const

Returns the `Orientation` of the points `p1, p2, p3`.

See also
  CGAL::orientation()

## ◆ periodic_point()

template<class GT , class TDS >

Periodic_point CGAL::Periodic_4_hyperbolic_triangulation_2< GT, TDS >::periodic_point | ( | const Face_handle | f,
|  | int | i
| ) |  | const

Returns the periodic point given by the `i`-th vertex of face `f`, that is the point in the original domain and the translation of the vertex in `f`.

Precondition
  \(0 \leq i \leq 2\)

## ◆ periodic_segment() [1/3]

template<class GT , class TDS >

Periodic_segment CGAL::Periodic_4_hyperbolic_triangulation_2< GT, TDS >::periodic_segment | ( | const Edge & | e | ) | const

Returns the periodic segment formed by the endpoints of edge `e`.

Note that the translations in the resulting periodic segment are determined by `e.first`.

## ◆ periodic_segment() [2/3]

template<class GT , class TDS >

Periodic_segment CGAL::Periodic_4_hyperbolic_triangulation_2< GT, TDS >::periodic_segment | ( | const Edge & | e,
|  | const Hyperbolic_translation & | tr
| ) |  | const

Returns the periodic segment formed by the endpoints of edge `e` translated by `tr`.

Note that the translations in the resulting segment are determined by the translations in `e.first`, multiplied on the left by `tr`.

## ◆ periodic_segment() [3/3]

template<class GT , class TDS >

Periodic_segment CGAL::Periodic_4_hyperbolic_triangulation_2< GT, TDS >::periodic_segment | ( | const Face_handle | c,
|  | int | i,
|  | int | j
| ) |  | const

Returns the periodic segment formed by the endpoints of edge `(f,i,j)`.

Precondition
  \( 0 \leq i,j \leq 2, \qquad i \neq j \)

## ◆ side_of_oriented_circle()

template<class GT , class TDS >

Oriented_side CGAL::Periodic_4_hyperbolic_triangulation_2< GT, TDS >::side_of_oriented_circle | ( | const Point & | p1,
|  | const Point & | p2,
|  | const Point & | p3,
|  | const Point & | q
| ) |  | const

Returns the `Oriented_side` on which `q` is located with respect to the circle defined by the points `p1,p2,p3`.

See also
  CGAL::side_of_oriented_circle()

## ◆ vertices_begin()

template<class GT , class TDS >

Vertex_iterator CGAL::Periodic_4_hyperbolic_triangulation_2< GT, TDS >::vertices_begin | ( |  | ) | const

Starts at an arbitrary vertex.

Iterates over all the vertices in the triangulation.