CGAL 6.1 - 3D Periodic Triangulations

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

`#include <CGAL/Periodic_3_Delaunay_triangulation_3.h>`

## Inherits from

CGAL::Periodic_3_triangulation_3< PT, TDS >.

## Definition

template<typename PT, typename TDS>
class CGAL::Periodic_3_Delaunay_triangulation_3< PT, TDS >

The class `Periodic_3_Delaunay_triangulation_3` represents a Delaunay triangulation in three-dimensional periodic space.

Template Parameters

  PT | must be a model of the concept `Periodic_3DelaunayTriangulationTraits_3`.
  TDS | must be a model of the concept `TriangulationDataStructure_3` whose vertex and cell are models of `Periodic_3TriangulationDSVertexBase_3` and `Periodic_3TriangulationDSCellBase_3`, respectively. It defaults to: CGAL::Triangulation_data_structure_3< CGAL::Triangulation_vertex_base_3<PT, Periodic_3_triangulation_ds_vertex_base_3<> >, CGAL::Triangulation_cell_base_3<PT,Periodic_3_triangulation_ds_cell_base_3<> > > CGAL::Triangulation_cell_base_3 CGAL::Triangulation_data_structure_3 CGAL::Triangulation_vertex_base_3

Examples
  Periodic_3_triangulation_3/colored_vertices.cpp, Periodic_3_triangulation_3/covering.cpp, Periodic_3_triangulation_3/geometric_access.cpp, Periodic_3_triangulation_3/large_point_set.cpp, Periodic_3_triangulation_3/periodic_adding_handles.cpp, and Periodic_3_triangulation_3/simple_example.cpp.

## Creation
| Periodic_3_Delaunay_triangulation_3 (const Iso_cuboid &domain=Iso_cuboid(0, 0, 0, 1, 1, 1), const Geom_traits &traits=Geom_traits())
| Creates an empty periodic Delaunay triangulation `dt`, with `domain` as original domain and possibly specifying a traits class `traits`.
| Periodic_3_Delaunay_triangulation_3 (const Periodic_3_Delaunay_triangulation_3 &dt1)
| Copy constructor.
template<class InputIterator >
| Periodic_3_Delaunay_triangulation_3 (InputIterator first, InputIterator last, const Iso_cuboid &domain=Iso_cuboid(0, 0, 0, 1, 1, 1), const Geom_traits &traits=Geom_traits())
| Equivalent to constructing an empty triangulation with the optional domain and traits class arguments and calling `insert(first,last)`.

## Insertion
The following methods insert points in the triangulation ensuring the empty sphere property of Delaunay triangulations. The inserted points need to lie in the original domain (see Section The Flat Torus of the user manual). In the degenerate case when there are co-spherical points, the Delaunay triangulation is known not to be uniquely defined. In this case, CGAL chooses a particular Delaunay triangulation using a symbolic perturbation scheme [2]. Note that insertion of a new point can cause a switch from computing in the 27-sheeted covering space to computing in the 1-sheeted covering space, which invalidates some `Vertex_handle`s and `Cell_handle`s.
Vertex_handle | insert (const Point &p, Cell_handle start=Cell_handle())
| Inserts point `p` in the triangulation and returns the corresponding vertex.
Vertex_handle | insert (const Point &p, Locate_type lt, Cell_handle loc, int li, int lj)
| Inserts point `p` in the triangulation and returns the corresponding vertex.
The following method allows the insertion of several points and returns the number of inserted points.
template<class InputIterator >
std::ptrdiff_t | insert (InputIterator first, InputIterator last, bool is_large_point_set=false)
| Inserts the points in the iterator range \( \left[\right.\)`first`, `last` \( \left.\right)\).

## Point moving
Vertex_handle | move_point (Vertex_handle v, const Point &p)
| Moves the point stored in `v` to `p`, while preserving the Delaunay property.

## Removal
The following methods remove points in the triangulation. When a vertex `v` is removed from a triangulation, all the cells incident to `v` must be removed, and the polyhedral region consisting of all the tetrahedra that are incident to `v` must be re-triangulated. The problem thus reduces to triangulating a polyhedral region, while preserving its boundary, or to compute a constrained triangulation. This is known to be sometimes impossible: the Schönhardt polyhedron cannot be triangulated [5]. However, when dealing with Delaunay triangulations, the case of such polyhedra that cannot be re-triangulated cannot happen, so CGAL proposes a vertex removal.
void | remove (Vertex_handle v)
| Removes the vertex `v` from the triangulation.
template<class InputIterator >
std::ptrdiff_t | remove (InputIterator first, InputIterator beyond)
| Removes the vertices specified by the iterator range (`first, beyond`) of value type `Vertex_handle`.

## Queries
Bounded_side | side_of_sphere (Cell_handle c, const Point &p, const Offset &off=Offset(0, 0, 0)) const
| Returns a value indicating on which side of the circumscribed sphere of `c` the point-offset pair (`p`,`off`) lies.
Vertex_handle | nearest_vertex (Point p, Cell_handle c=Cell_handle())
| Returns any nearest vertex to the point `p`, or the default constructed handle if the triangulation is empty.
Vertex_handle | nearest_vertex_in_cell (Cell_handle c, Point p, Offset off=Offset(0, 0, 0)) const
| Returns the vertex of the cell `c` that is nearest to the point-offset pair (`p`,`off`).
A point-offset pair (`p`,`off`) is said to be in conflict with a cell `c` iff `dt.side_of_sphere(c, p, off)` returns `ON_BOUNDED_SIDE`. The set of cells that are in conflict with (`p`,`off`) is star-shaped.
template<class OutputIteratorBoundaryFacets , class OutputIteratorCells , class OutputIteratorInternalFacets >
Triple< OutputIteratorBoundaryFacets, OutputIteratorCells, OutputIteratorInternalFacets > | find_conflicts (Point p, Cell_handle c, OutputIteratorBoundaryFacets bfit, OutputIteratorCells cit, OutputIteratorInternalFacets ifit)
| Computes the conflict hole induced by `p`.
template<class OutputIterator >
OutputIterator | vertices_in_conflict (Point p, Cell_handle c, OutputIterator res)
| Similar to `find_conflicts()`, but reports the vertices which are on the boundary of the conflict hole of `p`, in the output iterator `res`.
A face (cell, facet or edge) is said to be a Gabriel face iff its smallest circumscribing sphere do not enclose any vertex of the triangulation. Any Gabriel face belongs to the Delaunay triangulation, but the reciprocal is not true. The following member functions test the Gabriel property of Delaunay faces.
bool | is_Gabriel (Cell_handle c, int i)
bool | is_Gabriel (Cell_handle c, int i, int j)
bool | is_Gabriel (const Facet &f)
bool | is_Gabriel (const Edge &e)

## Voronoi diagram
CGAL offers several functions to display the Voronoi diagram of a set of points in 3D. Note that a traits class providing exact constructions should be used in order to guarantee the computation of the Voronoi diagram (as opposed to computing the triangulation only, which requires only exact predicates).
Point | canonical_dual (Cell_handle c) const
| Returns the representative of the circumcenter of the four vertices of c that lies in the original domain.
Point | dual (Cell_handle c) const
| Returns the circumcenter of the four vertices of c.
Periodic_segment | dual (Facet f) const
| Returns the dual of the facet `f`, which is a periodic segment.
Periodic_segment | dual (Cell_handle c, int i) const
| same as the previous method for the facet `(c,i)`.
template<class OutputIterator >
OutputIterator | dual (Edge e, OutputIterator pts) const
| Returns in the output iterator the points of the dual polygon of edge `e` in the same order as the `Facet_circulator` returns facets incident to the edge `e`.
template<class OutputIterator >
OutputIterator | dual (Cell_handle c, int i, int j, OutputIterator pts) const
| same as the previous method for the edge `(c,i,j)`.
template<class OutputIterator >
OutputIterator | dual (Vertex_handle v, OutputIterator pts) const
| Returns in the output iterator the points of the dual polyhedron of the vertex `v` in no particular order.
template<class Stream >
Stream & | draw_dual (Stream &os)
| Sends the set of duals to all the facets of `dt` into `os`.
Geom_traits::FT | dual_volume (Vertex_handle v) const
| Returns the volume of the Voronoi cell dual to `v`.
Point | dual_centroid (Vertex_handle v) const
| Returns the centroid of the Voronoi cell dual to `v`.

## Checking
These methods are mainly a debugging help for the users of advanced features.
bool | is_valid (bool verbose=false) const
| Checks the combinatorial validity of the triangulation and the validity of its geometric embedding (see Section Representation).
bool | is_valid (Cell_handle c, bool verbose=false) const
| Checks the combinatorial and geometric validity of the cell (see Section Representation).

## Additional Inherited Members
Public Types inherited from CGAL::Periodic_3_triangulation_3< PT, TDS >
enum | Locate_type
| The enum `Locate_type` is defined by `Periodic_3_triangulation_3` to specify which case occurs when locating a point in the triangulation. More...
enum | Iterator_type
| The enum `Iterator_type` is defined by `Periodic_3_triangulation_3` to specify the behavior of geometric iterators. More...
typedef PT | Geom_traits
typedef TDS | Triangulation_data_structure
typedef Geom_traits::Periodic_3_offset_3 | Offset
typedef Geom_traits::Iso_cuboid_3 | Iso_cuboid
| A type representing an axis-aligned cuboid.
typedef array< int, 3 > | Covering_sheets
| Integer triple to store the number of sheets in each direction of space.
typedef TDS::Vertex::Point | Point
| The point type of the triangulation.
typedef Geom_traits::Point_3 | Point_3
| The geometric basic 3D point type.
typedef Geom_traits::Segment_3 | Segment
typedef Geom_traits::Triangle_3 | Triangle
typedef Geom_traits::Tetrahedron_3 | Tetrahedron
typedef std::pair< Point, Offset > | Periodic_point
| Represents a point-offset pair.
typedef std::pair< Point_3, Offset > | Periodic_point_3
| Represents a point-offset pair.
typedef array< Periodic_point, 2 > | Periodic_segment
| A periodic segment.
typedef array< Periodic_point_3, 2 > | Periodic_segment_3
| A periodic segment.
typedef array< Periodic_point, 3 > | Periodic_triangle
| A periodic triangle.
typedef array< Periodic_point_3, 3 > | Periodic_triangle_3
| A periodic triangle.
typedef array< Periodic_point, 4 > | Periodic_tetrahedron
| A periodic tetrahedron.
typedef array< Periodic_point_3, 4 > | Periodic_tetrahedron_3
| A periodic tetrahedron.
typedef Triangulation_data_structure::Vertex | Vertex
typedef Triangulation_data_structure::Cell | Cell
typedef Triangulation_data_structure::Edge | Edge
typedef Triangulation_data_structure::Facet | Facet
typedef Triangulation_data_structure::Vertex_handle | Vertex_handle
| handle to a vertex
typedef Triangulation_data_structure::Cell_handle | Cell_handle
| handle to a cell
typedef Triangulation_data_structure::size_type | size_type
| Size type (an unsigned integral type)
typedef Triangulation_data_structure::difference_type | difference_type
| Difference type (a signed integral type)
typedef Triangulation_data_structure::Cell_iterator | Cell_iterator
| iterator over cells
typedef Triangulation_data_structure::Facet_iterator | Facet_iterator
| iterator over facets
typedef Triangulation_data_structure::Edge_iterator | Edge_iterator
| iterator over edges
typedef Triangulation_data_structure::Vertex_iterator | Vertex_iterator
| iterator over vertices
typedef unspecified_type | Unique_vertex_iterator
| iterator over the vertices whose corresponding points lie in the original domain, i.e. for each set of periodic copies the `Unique_vertex_iterator` iterates over exactly one representative.
typedef Triangulation_data_structure::Cell_circulator | Cell_circulator
| circulator over all cells incident to a given edge
typedef Triangulation_data_structure::Facet_circulator | Facet_circulator
| circulator over all facets incident to a given edge
typedef unspecified_type | Periodic_tetrahedron_iterator
| iterator over the tetrahedra corresponding to cells of the triangulation.
typedef unspecified_type | Periodic_triangle_iterator
| iterator over the triangles corresponding to facets of the triangulation.
typedef unspecified_type | Periodic_segment_iterator
| iterator over the segments corresponding to edges of the triangulation.
typedef unspecified_type | Periodic_point_iterator
| iterator over the points corresponding to vertices of the triangulation.
Public Member Functions inherited from CGAL::Periodic_3_triangulation_3< PT, TDS >
| Periodic_3_triangulation_3 (const Iso_cuboid &domain=Iso_cuboid(0, 0, 0, 1, 1, 1), const Geom_traits &traits=Geom_traits())
| Introduces an empty triangulation `t` with `domain` as original domain.
| Periodic_3_triangulation_3 (const Periodic_3_triangulation_3 &tr)
| Copy constructor.
Periodic_3_triangulation_3 & | operator= (const Periodic_3_triangulation_3 &tr)
| The triangulation `tr` is duplicated, and modifying the copy after the duplication does not modify the original.
void | swap (Periodic_3_triangulation_3 &tr)
| The triangulations `tr` and `t` are swapped.
void | clear ()
| Deletes all vertices and all cells of `t`.
const Geom_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.
Iso_cuboid | domain () const
| Returns the original domain.
Covering_sheets | number_of_sheets () const
| This is an advanced function.
Offset | neighbor_offset (Cell_handle ch, int i) const
| Get the offset between the origins of the internal offset coordinate systems of two neighboring cells with respect from ch to its i-th neighbor.
Triangulation_data_structure & | tds ()
| This is an advanced function.
void | set_domain (const Iso_cuboid dom)
| This is an advanced function.
bool | is_extensible_triangulation_in_1_sheet_h1 () const
| The current triangulation remains a triangulation in the 1-sheeted covering space even after adding points if this method returns `true`.
bool | is_extensible_triangulation_in_1_sheet_h2 () const
| The same as `is_extensible_triangulation_in_1_sheet_h1()` but with a more precise heuristic, i.e. it might answer `true` in cases in which `is_extensible_triangulation_in_1_sheet_h1()` would not.
bool | is_triangulation_in_1_sheet () const
| Returns `true` if the current triangulation would still be a triangulation in the 1-sheeted covering space, returns `false` otherwise.
void | convert_to_1_sheeted_covering () const
| Converts the current triangulation into the same periodic triangulation in the 1-sheeted covering space.
void | convert_to_27_sheeted_covering () const
| Converts the current triangulation into the same periodic triangulation in the 27-sheeted covering space.
size_type | number_of_vertices () const
| Returns the number of vertices.
size_type | number_of_cells () const
| Returns the number of cells.
size_type | number_of_stored_vertices () const
| Returns the number of vertices in the data structure.
size_type | number_of_stored_cells () const
| Returns the number of cells in the data structure.
size_type | number_of_edges () const
| Returns the number of edges.
size_type | number_of_facets () const
| Returns the number of facets.
size_type | number_of_stored_edges () const
| Returns the number of edges in the data structure.
size_type | number_of_stored_facets () const
| Returns the number of facets in the data structure.
Point | point (const Periodic_point &pp) const
| Converts the `Periodic_point` `pp` (point-offset pair) to the corresponding `Point` in \( \mathbb R^3\).
Point | point (Vertex_handle v) const
| Equivalent to the call `t.point(t.periodic_point(v));`
Point | point (Cell_handle c, int idx) const
| Equivalent to the call `t.point(t.periodic_point(c,idx));`
Periodic_point | periodic_point (const Vertex_handle v) const
| Returns the periodic point given by vertex `v`.
Periodic_point | periodic_point (const Cell_handle c, int i) const
| If `t` is represented in the 1-sheeted covering space, this function returns the periodic point given by the \( i\)-th vertex of cell `c`, that is the point in the original domain and the offset of the vertex in `c`.
Periodic_segment | periodic_segment (const Cell_handle c, int i, int j) const
| Returns the periodic segment formed by the two point-offset pairs corresponding to the two vertices of edge `(c,i,j)`.
Periodic_segment | periodic_segment (const Cell_handle c, Offset offset, int i, int j) const
| Returns the periodic segment formed by the two point-offset pairs corresponding to the two vertices of edge `(c,i,j)`.
Periodic_segment | periodic_segment (const Edge &e) const
| Same as the previous method for edge `e`.
Periodic_triangle | periodic_triangle (const Cell_handle c, int i) const
| Returns the periodic triangle formed by the three point-offset pairs corresponding to the three vertices of facet `(c,i)`.
Periodic_triangle | periodic_triangle (const Cell_handle c, Offset offset, int i) const
| Returns the periodic triangle formed by the three point-offset pairs corresponding to the three vertices of facet `(c,i)`.
Periodic_triangle | periodic_triangle (const Facet &f) const
| Same as the previous method for facet `f`.
Periodic_tetrahedron | periodic_tetrahedron (const Cell_handle c) const
| Returns the periodic tetrahedron formed by the four point-offset pairs corresponding to the four vertices of `c`.
Periodic_tetrahedron | periodic_tetrahedron (const Cell_handle c, Offset offset) const
| Returns the periodic tetrahedron formed by the four point-offset pairs corresponding to the four vertices of `c`.
Point_3 | construct_point (const PP &pp) const
| Converts the periodic point of type `PP` to a `Point_3`.
Point_3 | construct_point (const Point &p) const
| Converts the `Point` `p` to a `Point_3`.
Point_3 | construct_point (const P &p1, const Offset &o1) const
| Same as above, with offsets.
Segment | construct_segment (const PS &s) const
| Converts the periodic segment of type `PS` to a `Segment`.
Segment | construct_segment (const P &p1, const P &p2) const
| Creates a segment from two points.
Segment | construct_segment (const P &p1, const P &p2, const Offset &o1, const Offset &o2) const
| Same as above, with offsets.
Triangle | construct_triangle (const PT &t) const
| Converts the periodic triangle of type `PT` to a `Triangle`.
Triangle | construct_triangle (const P &p1, const P &p2, const P &p3) const
| Creates a triangle from three points.
Triangle | construct_triangle (const P &p1, const P &p2, const P &p3, const Offset &o1, const Offset &o2, const Offset &o3) const
| Same as above, with offsets.
Tetrahedron | construct_tetrahedron (const PT &t) const
| Converts the periodic tetrahedron of type `PT` to a `Tetrahedron`.
Tetrahedron | construct_tetrahedron (const P &p1, const P &p2, const P &p3, const P &p4) const
| Creates a tetrahedron from four points.
Tetrahedron | construct_tetrahedron (const P &p1, const P &p2, const P &p3, const P &p4, const Offset &o1, const Offset &o2, const Offset &o3, const Offset &o4) const
| Same as above, with offsets.
bool | is_vertex (const Point &p, Vertex_handle &v) const
| Tests whether `p` is a vertex of `t` by locating `p` in the triangulation.
bool | is_vertex (Vertex_handle v) const
| Tests whether `v` is a vertex of `t`.
bool | is_edge (Vertex_handle u, Vertex_handle v, Cell_handle &c, int &i, int &j) const
| Tests whether `(u,v)` is an edge of `t`.
bool | is_edge (Vertex_handle u, const Offset &offu, Vertex_handle v, const Offset &offv, Cell_handle &c, int &i, int &j) const
| Tests whether `((u,offu),(v,offu))` is an edge of `t`.
bool | is_facet (Vertex_handle u, Vertex_handle v, Vertex_handle w, Cell_handle &c, int &i, int &j, int &k) const
| Tests whether `(u,v,w)` is a facet of `t`.
bool | is_facet (Vertex_handle u, const Offset &offu, Vertex_handle v, const Offset &offv, Vertex_handle w, const Offset &offw, Cell_handle &c, int &i, int &j, int &k) const
| Tests whether `((u,offu),(v,offv),(w,offw))` is a facet of `t`.
bool | is_cell (Cell_handle c) const
| Tests whether `c` is a cell of `t`.
bool | is_cell (Vertex_handle u, Vertex_handle v, Vertex_handle w, Vertex_handle x, Cell_handle &c, int &i, int &j, int &k, int &l) const
| Tests whether `(u,v,w,x)` is a cell of `t`.
bool | is_cell (Vertex_handle u, Vertex_handle v, Vertex_handle w, Vertex_handle x, Cell_handle &c) const
| Tests whether `(u,v,w,x)` is a cell of `t` and computes this cell `c`.
bool | is_cell (Vertex_handle u, const Offset &offu, Vertex_handle v, const Offset &offv, Vertex_handle w, const Offset &offw, Vertex_handle x, const Offset &offx, Cell_handle &c, int &i, int &j, int &k, int &l) const
| Tests whether `((u,offu),(v,offv),(w,offv),(x,offx))` is a cell of `t`.
bool | is_cell (Vertex_handle u, const Offset &offu, Vertex_handle v, const Offset &offv, Vertex_handle w, const Offset &offw, Vertex_handle x, const Offset &offx, Cell_handle &c) const
| Tests whether `((u,offu),(v,offv),(w,offv),(x,offx))` is a cell of `t` and computes this cell `c`.
bool | has_vertex (const Facet &f, Vertex_handle v, int &j) const
| If `v` is a vertex of `f`, then `j` is the index of `v` in the cell `f.first`, and the method returns `true`.
bool | has_vertex (Cell_handle c, int i, Vertex_handle v, int &j) const
| Same for facet `(c,i)`.
bool | has_vertex (const Facet &f, Vertex_handle v) const
bool | has_vertex (Cell_handle c, int i, Vertex_handle v) const
| Same as the first two methods, but these two methods do not return the index of the vertex.
bool | are_equal (Cell_handle c, int i, Cell_handle n, int j) const
bool | are_equal (const Facet &f, const Facet &g) const
bool | are_equal (const Facet &f, Cell_handle n, int j) const
Cell_handle | locate (const Point &query, Cell_handle start=Cell_handle()) const
| Returns the cell that contains the query in its interior.
Cell_handle | locate (const Point &query, Offset &locate_offset, Cell_handle start=Cell_handle()) const
| Returns the cell that contains the query in its interior.
Cell_handle | locate (const Point &query, Locate_type &lt, int &li, int &lj, Cell_handle start=Cell_handle()) const
| The \( k\)-face that contains `query` in its interior is returned, by means of the cell returned together with `lt`, which is set to the locate type of the query (`VERTEX, EDGE, FACET, CELL`) and two indices `li` and `lj` that specify the \( k\)-face of the cell containing `query`.
Cell_handle | locate (const Point &query, Offset &locate_offset, Locate_type &lt, int &li, int &lj, Cell_handle start=Cell_handle()) const
| The \( k\)-face that contains `query` in its interior is returned, by means of the cell returned together with `lt`, which is set to the locate type of the query (`VERTEX, EDGE, FACET, CELL`) and two indices `li` and `lj` that specify the \( k\)-face of the cell containing `query`.
Cell_handle | inexact_locate (const Point &query, Cell_handle start=Cell_handle()) const
| Same as `locate()` but uses inexact predicates.
Bounded_side | side_of_cell (const Point &p, Cell_handle c, Locate_type &lt, int &li, int &lj) const
| Returns a value indicating on which side of the oriented boundary of `c` the point `p` lies.
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.
Facet_iterator | facets_begin () const
| Starts at an arbitrary facet.
Facet_iterator | facets_end () const
| Past-the-end iterator.
Cell_iterator | cells_begin () const
| Starts at an arbitrary cell.
Cell_iterator | cells_end () const
| Past-the-end iterator.
Unique_vertex_iterator | unique_vertices_begin () const
| Starts at an arbitrary vertex.
Unique_vertex_iterator | unique_vertices_end () const
| Past-the-end iterator.
Periodic_point_iterator | periodic_points_begin (Iterator_type it=STORED) const
| Iterates over the points of the triangulation.
Periodic_point_iterator | periodic_points_end (Iterator_type it=STORED) const
| Past-the-end iterator.
Periodic_segment_iterator | periodic_segments_begin (Iterator_type it=STORED) const
| Iterates over the segments of the triangulation.
Periodic_segment_iterator | periodic_segments_end (Iterator_type it=STORED) const
| Past-the-end iterator.
Periodic_triangle_iterator | periodic_triangles_begin (Iterator_type it=STORED) const
| Iterates over the triangles of the triangulation.
Periodic_triangle_iterator | periodic_triangles_end (Iterator_type it=STORED) const
| Past-the-end iterator.
Periodic_tetrahedron_iterator | periodic_tetrahedra_begin (Iterator_type it=STORED) const
| Iterates over the tetrahedra of the triangulation.
Periodic_tetrahedron_iterator | periodic_tetrahedra_end (Iterator_type it=STORED) const
| Past-the-end iterator.
Cell_circulator | incident_cells (Edge e) const
| Starts at an arbitrary cell incident to `e`.
Cell_circulator | incident_cells (Cell_handle c, int i, int j) const
| As above for edge `(i,j)` of `c`.
Cell_circulator | incident_cells (Edge e, Cell_handle start) const
| Starts at cell `start`.
Cell_circulator | incident_cells (Cell_handle c, int i, int j, Cell_handle start) const
| As above for edge `(i,j)` of `c`.
Facet_circulator | incident_facets (Edge e) const
| Starts at an arbitrary facet incident to `e`.
Facet_circulator | incident_facets (Cell_handle c, int i, int j) const
| As above for edge `(i,j)` of `c`.
Facet_circulator | incident_facets (Edge e, Facet start) const
| Starts at facet `start`.
Facet_circulator | incident_facets (Edge e, Cell_handle start, int f) const
| Starts at facet of index `f` in `start`.
Facet_circulator | incident_facets (Cell_handle c, int i, int j, Facet start) const
| As above for edge `(i,j)` of `c`.
Facet_circulator | incident_facets (Cell_handle c, int i, int j, Cell_handle start, int f) const
| As above for edge `(i,j)` of `c` and facet `(start,f)`.
OutputIterator | incident_cells (Vertex_handle v, OutputIterator cells) const
| Copies the `Cell_handle`s of all cells incident to `v` to the output iterator `cells`.
OutputIterator | incident_facets (Vertex_handle v, OutputIterator facets) const
| Copies the `Facet`s incident to `v` to the output iterator `facets`.
OutputIterator | incident_edges (Vertex_handle v, OutputIterator edges) const
| Copies the `Edge`s incident to `v` to the output iterator `edges`.
OutputIterator | adjacent_vertices (Vertex_handle v, OutputIterator vertices) const
| Copies the `Vertex_handle`s of all vertices adjacent to `v` to the output iterator `vertices`.
size_type | degree (Vertex_handle v) const
| Returns the degree of a vertex, that is, the number of adjacent vertices.
int | mirror_index (Cell_handle c, int i) const
| Returns the index of `c` in its \( i^{th}\) neighbor.
Vertex_handle | mirror_vertex (Cell_handle c, int i) const
| Returns the vertex of the \( i^{th}\) neighbor of `c` that is opposite to `c`.
Facet | mirror_facet (Facet f) const
| Returns the same facet viewed from the other adjacent cell.
bool | is_valid (bool verbose=false) const
| Checks the combinatorial validity of the triangulation.
bool | is_valid (Cell_handle c, bool verbose=false) const
| Checks the combinatorial validity of the cell by calling the `is_valid` method of the `Triangulation_data_structure` cell class.
Related Functions inherited from CGAL::Periodic_3_triangulation_3< PT, TDS >
istream & | operator>> (istream &is, Periodic_3_triangulation_3 &t)
| Reads a triangulation from `is` and stores it in `t`.
ostream & | operator<< (ostream &os, const Periodic_3_triangulation_3 &t)
| Writes the triangulation `t` into `os`.
bool | operator== (const Periodic_3_triangulation_3< PT, TDS1 > &t1, const Periodic_3_triangulation_3< PT, TDS2 > &t2)
| Equality operator.
bool | operator!= (const Periodic_3_triangulation_3< PT, TDS1 > &t1, const Periodic_3_triangulation_3< PT, TDS2 > &t2)
| The opposite of `operator==`.

## Constructor & Destructor Documentation

## ◆ Periodic_3_Delaunay_triangulation_3() [1/2]

template<typename PT , typename TDS >

CGAL::Periodic_3_Delaunay_triangulation_3< PT, TDS >::Periodic_3_Delaunay_triangulation_3 | ( | const Iso_cuboid & | domain = `Iso_cuboid(0, 0, 0, 1, 1, 1)`,
|  | const Geom_traits & | traits = `Geom_traits()`
| ) |  |

Creates an empty periodic Delaunay triangulation `dt`, with `domain` as original domain and possibly specifying a traits class `traits`.

Precondition
  `domain` is a cube.

## ◆ Periodic_3_Delaunay_triangulation_3() [2/2]

template<typename PT , typename TDS >
template<class InputIterator >

CGAL::Periodic_3_Delaunay_triangulation_3< PT, TDS >::Periodic_3_Delaunay_triangulation_3 | ( | InputIterator | first,
|  | InputIterator | last,
|  | const Iso_cuboid & | domain = `Iso_cuboid(0, 0, 0, 1, 1, 1)`,
|  | const Geom_traits & | traits = `Geom_traits()`
| ) |  |

Equivalent to constructing an empty triangulation with the optional domain and traits class arguments and calling `insert(first,last)`.

Precondition
  The `value_type` of `first` and `last` are `Point`s lying inside `domain` and `domain` is a cube.

## Member Function Documentation

## ◆ dual() [1/4]

template<typename PT , typename TDS >

Periodic_segment CGAL::Periodic_3_Delaunay_triangulation_3< PT, TDS >::dual | ( | Cell_handle | c,
|  | int | i
| ) |  | const

same as the previous method for the facet `(c,i)`.

Precondition
  \( i\in\{0,1,2,3\}\)

## ◆ dual() [2/4]

template<typename PT , typename TDS >
template<class OutputIterator >

OutputIterator CGAL::Periodic_3_Delaunay_triangulation_3< PT, TDS >::dual | ( | Cell_handle | c,
|  | int | i,
|  | int | j,
|  | OutputIterator | pts
| ) |  | const

same as the previous method for the edge `(c,i,j)`.

Precondition
  \( i,j\in\{0,1,2,3\}, i\neq j\)

## ◆ dual() [3/4]

template<typename PT , typename TDS >
template<class OutputIterator >

OutputIterator CGAL::Periodic_3_Delaunay_triangulation_3< PT, TDS >::dual | ( | Edge | e,
|  | OutputIterator | pts
| ) |  | const

Returns in the output iterator the points of the dual polygon of edge `e` in the same order as the `Facet_circulator` returns facets incident to the edge `e`.

The points form the dual polygon in \( \mathbb R^3\), so they do not necessarily all lie inside the original domain.

## ◆ dual() [4/4]

template<typename PT , typename TDS >
template<class OutputIterator >

OutputIterator CGAL::Periodic_3_Delaunay_triangulation_3< PT, TDS >::dual | ( | Vertex_handle | v,
|  | OutputIterator | pts
| ) |  | const

Returns in the output iterator the points of the dual polyhedron of the vertex `v` in no particular order.

The points form the dual polyhedron in \( \mathbb R^3\), so they do not necessarily lie all inside the original domain.

## ◆ find_conflicts()

template<typename PT , typename TDS >
template<class OutputIteratorBoundaryFacets , class OutputIteratorCells , class OutputIteratorInternalFacets >

Triple< OutputIteratorBoundaryFacets, OutputIteratorCells, OutputIteratorInternalFacets > CGAL::Periodic_3_Delaunay_triangulation_3< PT, TDS >::find_conflicts | ( | Point | p,
|  | Cell_handle | c,
|  | OutputIteratorBoundaryFacets | bfit,
|  | OutputIteratorCells | cit,
|  | OutputIteratorInternalFacets | ifit
| ) |  |

Computes the conflict hole induced by `p`.

The starting cell `c` must be in conflict. Then this function returns respectively in the output iterators:

- `cit`: the cells in conflict.
- `bfit`: the facets on the boundary, that is, the facets `(t, i)` where the cell `t` is in conflict, but `t->neighbor(i)` is not.
- `ifit`: the facets inside the hole, that is, delimiting two cells in conflict.

Returns the pair composed of the resulting output iterators.

Precondition
  `c` is in conflict with `p` and `p` lies in the original domain.

## ◆ insert() [1/3]

template<typename PT , typename TDS >

Vertex_handle CGAL::Periodic_3_Delaunay_triangulation_3< PT, TDS >::insert | ( | const Point & | p,
|  | Cell_handle | start = `Cell_handle()`
| ) |  |

Inserts point `p` in the triangulation and returns the corresponding vertex.

The optional argument `start` is used as a starting place for the point location.

Precondition
  `p` lies in the original domain.

Examples
  Periodic_3_triangulation_3/colored_vertices.cpp, Periodic_3_triangulation_3/covering.cpp, Periodic_3_triangulation_3/geometric_access.cpp, and Periodic_3_triangulation_3/periodic_adding_handles.cpp.

## ◆ insert() [2/3]

template<typename PT , typename TDS >

Vertex_handle CGAL::Periodic_3_Delaunay_triangulation_3< PT, TDS >::insert | ( | const Point & | p,
|  | Locate_type | lt,
|  | Cell_handle | loc,
|  | int | li,
|  | int | lj
| ) |  |

Inserts point `p` in the triangulation and returns the corresponding vertex.

Similar to the above `insert()` function, but takes as additional parameter the return values of a previous location query. See description of `Periodic_3_triangulation_3::locate()`.

Precondition
  `p` lies in the original domain.

## ◆ insert() [3/3]

template<typename PT , typename TDS >
template<class InputIterator >

std::ptrdiff_t CGAL::Periodic_3_Delaunay_triangulation_3< PT, TDS >::insert | ( | InputIterator | first,
|  | InputIterator | last,
|  | bool | is_large_point_set = `false`
| ) |  |

Inserts the points in the iterator range \( \left[\right.\)`first`, `last` \( \left.\right)\).

Returns the number of inserted points. This function uses spatial sorting (cf. chapter Spatial Sorting) and therefore is not guaranteed to insert the points following the order of `InputIterator`. If the third argument `is_large_point_set` is set to `true` a heuristic for optimizing the insertion of large point sets is applied.

Precondition
  The `value_type` of `first` and `last` are points lying inside the original domain.

## ◆ is_valid() [1/2]

template<typename PT , typename TDS >

bool CGAL::Periodic_3_Delaunay_triangulation_3< PT, TDS >::is_valid | ( | bool | verbose = `false` | ) | const

Checks the combinatorial validity of the triangulation and the validity of its geometric embedding (see Section Representation).

Also checks that all the circumscribing spheres of cells are empty.

When `verbose` is set to true, messages describing the first invalidity encountered (if any) are printed.

## ◆ is_valid() [2/2]

template<typename PT , typename TDS >

bool CGAL::Periodic_3_Delaunay_triangulation_3< PT, TDS >::is_valid | ( | Cell_handle | c,
|  | bool | verbose = `false`
| ) |  | const

Checks the combinatorial and geometric validity of the cell (see Section Representation).

Also checks that the circumscribing sphere of cells is empty.

When `verbose` is set to true, messages are printed to give a precise indication of the kind of invalidity encountered (if any).

## ◆ move_point()

template<typename PT , typename TDS >

Vertex_handle CGAL::Periodic_3_Delaunay_triangulation_3< PT, TDS >::move_point | ( | Vertex_handle | v,
|  | const Point & | p
| ) |  |

Moves the point stored in `v` to `p`, while preserving the Delaunay property.

This performs an action semantically equivalent to `remove(v)` followed by `insert(p)`, but is supposedly faster when the point has not moved much. Returns the handle to the new vertex.

Precondition
  `p` lies in the original domain.

## ◆ nearest_vertex()

template<typename PT , typename TDS >

Vertex_handle CGAL::Periodic_3_Delaunay_triangulation_3< PT, TDS >::nearest_vertex | ( | Point | p,
|  | Cell_handle | c = `Cell_handle()`
| ) |  |

Returns any nearest vertex to the point `p`, or the default constructed handle if the triangulation is empty.

The optional argument `c` is a hint specifying where to start the search. It always returns a vertex corresponding to a point inside the original domain, even if computing in a multiply sheeted covering space.

Precondition
  `c` is a cell of `dt` and `p` lies in the original domain.

## ◆ nearest_vertex_in_cell()

template<typename PT , typename TDS >

Vertex_handle CGAL::Periodic_3_Delaunay_triangulation_3< PT, TDS >::nearest_vertex_in_cell | ( | Cell_handle | c,
|  | Point | p,
|  | Offset | off = `Offset(0, 0, 0)`
| ) |  | const

Returns the vertex of the cell `c` that is nearest to the point-offset pair (`p`,`off`).

Precondition
  `p` lies in the original domain.

## ◆ remove() [1/2]

template<typename PT , typename TDS >
template<class InputIterator >

std::ptrdiff_t CGAL::Periodic_3_Delaunay_triangulation_3< PT, TDS >::remove | ( | InputIterator | first,
|  | InputIterator | beyond
| ) |  |

Removes the vertices specified by the iterator range (`first, beyond`) of value type `Vertex_handle`.

`remove()` is called for each element of the range. The number of vertices removed is returned; this number does not account for periodic copies of removed vertices.

Precondition
  The iterator must not iterate over several periodic copies of the same vertex, use e.g. the `Unique_vertex_iterator`.

## ◆ remove() [2/2]

template<typename PT , typename TDS >

void CGAL::Periodic_3_Delaunay_triangulation_3< PT, TDS >::remove | ( | Vertex_handle | v | ) |

Removes the vertex `v` from the triangulation.

When computing in the 27-sheeted covering space it removes all 27 copies of `v`.

## ◆ side_of_sphere()

template<typename PT , typename TDS >

Bounded_side CGAL::Periodic_3_Delaunay_triangulation_3< PT, TDS >::side_of_sphere | ( | Cell_handle | c,
|  | const Point & | p,
|  | const Offset & | off = `Offset(0, 0, 0)`
| ) |  | const

Returns a value indicating on which side of the circumscribed sphere of `c` the point-offset pair (`p`,`off`) lies.

More precisely, it returns:

- `ON_BOUNDED_SIDE` if (`p`,`off`) lies inside the sphere.
- `ON_BOUNDARY` if (`p`,`off`) lies on the boundary of the sphere.
- `ON_UNBOUNDED_SIDE` if (`p`,`off`) lies outside the sphere.
  Precondition
    `p` lies in the original domain.

## ◆ vertices_in_conflict()

template<typename PT , typename TDS >
template<class OutputIterator >

OutputIterator CGAL::Periodic_3_Delaunay_triangulation_3< PT, TDS >::vertices_in_conflict | ( | Point | p,
|  | Cell_handle | c,
|  | OutputIterator | res
| ) |  |

Similar to `find_conflicts()`, but reports the vertices which are on the boundary of the conflict hole of `p`, in the output iterator `res`.

Returns the resulting output iterator.

Precondition
  `c` is in conflict with `p` and `p` lies in the original domain.