Structural Bioinformatics Library
Template C++ / Python API for developping structural bioinformatics applications.
User Manual

Table of Contents

Triangulations_extensions_3

Authors: F. Cazals and T. Dreyfus

Introduction

This package provides constructions, predicates and Output / Input functionality related to the three dimensional triangulations data structures of CGAL. Three kind of triangulations are concerned:

  • Triangulation_3, that is a simple 3D triangulation of a set of points,
  • Delaunay_triangulation_3, that is a 3D Delaunay triangulation of a set of points,
  • Regular_triangulation_3, that is a 3D triangulation of a set of multiplicative weighted points.

In the following, we describe more precisely the provided functionality for each kind of triangulation.

Triangulation_3

Four main functionality are provided:

  • The canonical representation of the edges and facets. The edges of the CGAL Triangulation_3 are represented by a cell bounded by this edge and the indices of the two vertices in the cell bounding the edge. The facets of the CGAL Triangulation_3 are represented by a cell bounded by this facet and the index of the vertex in the cell that does not bound the facet. Both representations are not unique since an edge or a facet may bound several cells. For the edges, we can canonically represent an edge with the two bounding vertices ordered with a lexicographical order (assuming that there is an order over the vertices). For the facets, we can canonically represent a facet with the cell that compares the lesser (assuming that there is an order over the cells). These representations allow in particular to manipulate container of canonical edges and facets requiring a total order over its elements.
  • The manipulation of faces and cofaces of a simplex: we provide three functors allowing to (i) access to the two edges of a given facet that are not equal to a given edge, (ii) access to the facet common to two given cells, and (iii) check that a given simplex is the co-face of another given simplex.
  • The serialization of the whole triangulation: it consists to save into an archive (a xml file for example) the simplices of the triangulation, and to load a triangulation from an archive.
  • The print of the triangulation onto a VMD file format: it consists to save the triangulation into a file readable by the VMD software.

See the Triangulation_extension_3 Example section for an example.

Delaunay_triangulation_extension_3

This extension provides functors for accessing statistics on the dual of the edges and facets of a Delaunay triangulation:

  • for the edges, one functor constructs its dual Voronoi face as a sequence of points, while the other functor constructs the area (possibly infinite) of the dual Voronoi face.
  • for the facets, there is only one functor that constructs the squared length (possibly infinite) of a Voronoi dual edge, the original Delaunay triangulation of CGAL providing the construction of the dual Voronoi edge.

See the Delaunay_triangulation_extension_3 Example section for an example.

Regular_triangulation_extension_3

See the Regular_triangulation_extension Example section for an example.

Implementation

Each extension is represented by one class designed as a traits class defining the functors corresponding to the different constructions and predicates:

  • SBL::GT::T_Regular_triangulation_extension_3< RegularTriangulation3 >, where the template parameter corresponds to the RegularTriangulation3 concept of CGAL.

Furthermore, there data structures allowing to serialize in an archive, or to print in a VMD file format, the simplices of:

  • a 3D Triangulation: SBL::GT::T_Triangulation_3_serialization_output_traits< Triangulation3 > and SBL::GT::T_Triangulation_3_VMD_output_traits< Triangulation3 >,
  • a 3D Delaunay Triangulation: SBL::GT::T_Delaunay_triangulation_3_serialization_output_traits< DelaunayTriangulation3 > and SBL::GT::T_Delaunay_triangulation_3_VMD_output_traits< DelaunayTriangulation3 >,
  • a 3D Regular Triangulation: SBL::GT::T_Regular_triangulation_3_serialization_output_traits< RegularTriangulation3 > and SBL::GT::T_Regular_triangulation_3_VMD_output_traits< RegularTriangulation3 >.

Dependencies

This package has one internal dependency, that is the Spherical_kernel_extension_3 package for the use of the SBL::GT::T_Spherical_kernel_extension_3::Is_counter_clockwise_oriented predicate .

There are also two external dependencies:

  • the CGAL library, for the representation of 3D Triangulations and $\alpha$-complexes. Note that this part of the CGAL library is generic and consists only of C++ header files.
  • the Boost.Serialization library, for serializing the simplices of a 3D Triangulation. Note that this part of the Boost library is not generic and requires to be linked during the compilation of a program using the serialized data structures. However, if you are not using the serialized data structures, you can skip this step, even if you are using this package.

Examples

Triangulation_extension_3 Example

The following example presents the class SBL::GT::T_Triangulation_extension_3 with a simple triangulation from CGAL. It reads a file containing three dimensional points and insert them in the triangulation. Then, it stores and sorts all the facets of the triangulation. Then two predicates from the SBL::GT::T_Triangulation_extension_3 class are applied to the smallest facet.

Delaunay_triangulation_extension_3 Example

The following example presents the class SBL::GT::T_Delaunay_triangulation_extension_3 with a Delaunay triangulation from CGAL. It reads a file containing three dimensional points and insert them in the triangulation. Then, it compute the area of the dual of all finite edges in the triangulation.

Regular_triangulation_extension Example

The following example presents the class SBL::GT::T_Regular_triangulation_extension_3 with a 3D regular triangulation from CGAL. It reads a file containing three dimensional spheres and insert them in a weighted $\alpha$-complex. Then, for each finite cell with a regular or singular facet, it checks the orientation of this facet.