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

Table of Contents

Union_of_balls_surface_volume_3

Authors: F. Cazals and T. Dreyfus and S. Loriot

Introduction

This package provides a generic geometric data structure and algorithm for computing the surface area and the volume of the union of a family of 3D balls. Compared to other algorithms, it warranties:

  • time efficiency (...)
  • bounded errors.

Calculations are handled in a "as most as possible" exact (due to trigonometric functions, the volume and surface area cannot be exact), or using interval arithmetics.

Algorithms

Surfaces and Volumes

Having commented above on the decomposition of a union of balls into restrictions, it is sufficient to comment on the geometry of a restriction. As established in [43] , a partition of a restriction can be defined using two types of pyramids, as shown on Fig. Pyramides:

  • Type I: pyramids with flat base: the apex of such a pyramid is the center of the ball processed, and its base is (a portion of) the Voronoi facet shared with a neighboring ball in the Voronoi diagram.
  • Type II pyramids with curved base: the apex of such a pyramid is the center of the ball processed, and its based is a spherical polygon on the sphere processed.

As established using Gauss' divergence theorem, computing the volume of a pyramid is easily done from the surface area of its base [43] , be it flat or curvy:

  • For a type I pyramid, whose flat base is bounded by Vononoi line-segments and possibly circle arcs, the surface area of the base is computed using Gauss' divergence theorem.
  • For a type II pyramid, the surface area of the corresponding spherical cap is computed using the local version of the Gauss-Bonnet theorem [70] . This requires computing the geodesic curvature of circle arcs, and also angle tilts when two circle arcs bounding the spherical cap meet. Note that this latter operation involves an arc cosine which is computed using arithmetic interval from the Boost Interval Arithmetic Library. (Note that the result is stored as a pair of doubles representing an interval containing the true result.)

Thus, the primitive algorithm is the computation of the boundary of the union [4] , which is implemented in the package Union_of_balls_boundary_3.

Partitioning a restriction. The two types of pyramides

Implementation

Main Class

The main class is SBL::GT::T_Union_of_Balls_surface_volume_3< AlphaComplex3 , SphericalKernel3 , Union_of_balls_boundary_3 > : it takes as input a family of 3D balls, and stores for each 3D ball its contribution to the surface area and volume of the union of the whole family. The three template parameters are:

  • SphericalKernel3 : geometric kernel defining predicates and data structures for computations over a 3D sphere; a model for SphericalKernel3 is the CGAL data structure CGAL::Spherical_kernel_3, that is the default type; CGAL::Spherical_kernel_3 is instantiated such that it is compliant with the template parameter AlphaComplex3

An example of use of SBL::GT::T_Union_of_Balls_surface_volume_3 is shown in section Computing the Volume and Surface Area of Input 3D Balls .

Serialization

The class SBL::GT::T_Union_of_Balls_surface_volume_3 is partially serializable – see the section Partial Serialization. The partial serialization becomes available by including the file SBL/IO/Union_of_balls_surface_volume_3_oserialization.hpp in the source file where it is required.

An example of partial serialization of SBL::GT::T_Union_of_Balls_surface_volume_3 is shown in section Serializing the Contributions of 3D Balls to the Volume and Surface Area of their Union .

Module

This package provides also the module SBL::CSB::T_Union_of_balls_surface_volume_3_module< ModuleTraits , OutputArchive > that computes the surface area and the volume of the union of a family of 3D balls that are represented by:

  • a $\alpha$-complex data structure or,
  • a boundary data structure.

In the first case, the computation of the boundary has to be done before computing the surface area and volume. The two template parameters are:

  • ModuleTraits : traits class of the module defining the type Alpha_complex,
  • OutputArchive : type of the output archive for partial serialization; it can be the Boost output archives (default is boost::archive::xml_oarchive, for a XML archive), or the custom archives provided by the package Multiple_archives_serialization.

The module provides also options for switching between different computation modes (exact or interval arithmetics, number of floating points, etc...)

An example of usage of this module is shown in section Using Modules for Computing the Volume and Surface Area .

Examples

Computing the Volume and Surface Area of Input 3D Balls

This example shows how to compute the surface area and the volume of the union of a family of 3D balls:

  • (i) the 2D balls are loaded from a given file,
  • (ii) the surface are and volume is computed at the creation of the corresponding data structure,
  • (iii) and the volume and surface area are printed in the standard output.

Serializing the Contributions of 3D Balls to the Volume and Surface Area of their Union

This example shows how to partially serialize the data structure SBL::CSB::T_Union_of_balls_surface_volume_3. The steps are the same as the example of section Computing the Volume and Surface Area of Input 3D Balls, except the third step, for which a Boost XML archive is created, and then the contribution of each 3D ball is partially serialized in this archive.

Using Modules for Computing the Volume and Surface Area

This example presents the module SBL::CSB::T_Union_of_balls_surface_volume_3_module:

  • (i) the class Module_traits defines only the Alpha_complex type,
  • (iii) the $\alpha$-complex of the input balls is computed,
  • (iv) and the module is initialized and run, with statistics dumping at the end of the run.