CGAL 4.7 - 2D Periodic Triangulations: 2D Periodic Triangulations Reference

\( \newcommand{\E}{\mathrm{E}} \) \( \newcommand{\A}{\mathrm{A}} \) \( \newcommand{\R}{\mathrm{R}} \) \( \newcommand{\N}{\mathrm{N}} \) \( \newcommand{\Q}{\mathrm{Q}} \) \( \newcommand{\Z}{\mathrm{Z}} \) \( \def\ccSum #1#2#3{ \sum_{#1}^{#2}{#3} } \def\ccProd #1#2#3{ \sum_{#1}^{#2}{#3} }\)

CGAL 4.7 - 2D Periodic Triangulations

All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Groups Pages
Modules
2D Periodic Triangulations Reference

##

Nico Kruithof
This package allows to build and handle triangulations of point sets in the two dimensional flat torus. Triangulations are built incrementally and can be modified by insertion or removal of vertices. They offer point location facilities. The package provides Delaunay triangulations and offers nearest neighbor queries and primitives to build the dual Voronoi diagrams.

Introduced in: CGAL 4.3
Depends on: 2D Triangulation
BibTeX: cgal:k-pt2-13-15b
License: GPL
Windows Demo: Periodic Delaunay Triangulation
Common Demo Dlls: dlls

The main classes of the 2D Periodic Triangulation package are `Periodic_2_triangulation_2` and `Periodic_2_Delaunay_triangulation_2`. They contain functionality to access triangulations and to run queries on them. `Periodic_2_Delaunay_triangulation_2` can construct and modify Delaunay triangulations. It takes the geometric traits as well as the triangulation data structure as template parameters.

The geometric traits class must be a model of the concept `Periodic_2DelaunayTriangulationTraits_2`. It contains all predicates and constructions that are needed by the functions in the triangulation classes.

The package uses `Triangulation_data_structure_2` to represent the triangulation. The faces and vertices need to be Models of the concepts `Periodic_2TriangulationFaceBase_2` and `TriangulationVertexBase_2`, respectively. A triangulation is stored as a collection of vertices and faces that are linked together through incidence and adjacency relations. Each face gives access to its three incident vertices and to its three adjacent cells. Each vertex gives access to one of its incident faces.

The three vertices of a cell are indexed with 0, 1, and 2 in positive orientation, the positive orientation being defined by the orientation of the underlying space \( \mathbb T_c^3\). The neighbors of a face are also indexed with 0, 1, 2 in such a way that the neighbor indexed by \( i\) is opposite to the vertex with the same index. See Figure 39.2.

In order to be able to specify the triangle that contain vertices both inside and outside the original domain we store additional offset information for each vertex of a face. These offsets are Models of the concept `Periodic_2Offset_2`.

## Concepts

- `Periodic_2DelaunayTriangulationTraits_2`
- `TriangulationDataStructure_2`
- `Periodic_2TriangulationFaceBase_2`
- `Periodic_2TriangulationVertexBase_2`
- `Periodic_2Offset_2`

## Classes

### Main Classes

- `CGAL::Periodic_2_triangulation_2<PT,TDS>`
- `CGAL::Periodic_2_Delaunay_triangulation_2<PT,TDS>`
- `CGAL::Periodic_2_triangulation_hierarchy_2<PTr>`
- `CGAL::Periodic_2_triangulation_face_base_2<>`
- `CGAL::Periodic_2_triangulation_vertex_base_2<>`
- `CGAL::Periodic_2_offset_2`

### Traits Classes

- `CGAL::Periodic_2_triangulation_traits_2<Traits,Periodic_2Offset_2>`

## Enums

- `CGAL::Periodic_2_triangulation_2::Iterator_type`
- `CGAL::Periodic_2_triangulation_2::Locate_type`

## Modules

| Concepts
| Main Classes
| Traits Classes
| Vertex and Face Classes
| Enums