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

Authors: F. Cazals and T. Dreyfus
This package provides a generic geometric data structure and the accompanying algorithm to compute the boundary of an union of a family of 3D balls. The boundary is represented using a combinatorial data structure that is warranted to be exact. Two options are provided to handle the construction intersection points (found at the intersection of three spheres); their coordinates can indeed be represented exactly (using degree two algebraic numbers), or using interval arithmetics.
The boundary of an union of 3D balls is represented with a data structure composed of three items :
The specification of the boundary involves two types of information:
Hence, our representation of the boundary decouples these two aspects, based on the halfedge data structure from the CGAL library . This structure is composed of :
We now describe the different steps to build the boundary with this data structure.
Consider the complex of an input family of 3D balls : it is a filtration of the simplices (vertices, edges ,triangles and tetrahedra) of an underlying Delaunay/regular triangulation. Each simplex has a status :
Also, by construction, it is possible to create an artificial vertex located at the infinite, so that it is easy to find the simplices corresponding to the boundary of the union of balls. In particular, a tetrahedron containing an infinite vertex is called exterior and allows to define which part of the boundaries are exterior or bound cavities.
The overall algorithm computing the boundary of the union uses the complex [3], and goes through six steps:
building the vertices: this is done by visiting the triangles in the complex. When the triangle is interior, none of the two intersection points of the three 3D balls represented by the triangle are at the boundary. When regular, there is exactly one intersection point at the boundary, and when singular, there are exactly two intersection points. Hence, we can totally determine the set of vertices.
building the halfedges: this is done by visiting the edges in the complex. When the edge is interior, there is no intersection arc on the boundary. When singular, the intersection arc is a full circle and we just add a pair of opposite halfedges. When regular, there are possibly multiple intersection arcs, and we need to visit each vertex bounding the arcs to reconstruct a pair of opposite halfedges for each arc. To know which pair of vertices are the endpoints of the same arc, we simply visit the incident pairs of triangles in the complex bounding a same tetrahedron that is not in the complex.
linking the halfedges: this is done by grouping all halfedges corresponding to intersection arcs at the surface of a ball, then by linking pairs of halfedges for which the endpoint of the first one is the startpoint of the second one. Since halfedges are paired and are oriented, we can always associate to halfedges the bounding ball on their left, allowing to easily group them. Then, a UnionFind algorithm over the vertices bounding the halfedges in the same group allows to link those halfedges.
building the faces: this is done by visiting the vertices in the complex. An interior vertex has no associated spherical cap on the boundary. A singular vertex corresponds to a full sphere, represented by a unique face with no bounding halfedge. When regular, we need to know how many not connected spherical caps are bounding the corresponding 3D ball : this is done by grouping adjacent tetrahedra of the underlaying triangulation that are not in the complex. A simple UnionFind algorithm allows to group those adjacent tetrahedra, defining one face per independent set; For each face, we also need to determine the boundaries of this face. To do so, we use again a UnionFind algorithm for grouping the connected halfedges around a face. Each connected component of halfedges is called a CCB. We arbitrarily set the first CCB of each face as its face boundary, all other ones defining its face holes.
linking the faces: this is done by simply running an UnionFind algorithm over the halfedges for linking all the adjacent faces. At the end of the process, the resulting connected components are the different connected components of the boundary of the union of input 3D balls.
finding the exterior and cavity boundaries: this is done by simply running an UnionFind algorithm over all tetrahedra of the underlaying triangulation that are not in the complex : the connected component having infinite tetrahedra correspond to exterior connected components of the boundary, while all other ones correspond to cavities' boundary connected components.
The boundary is represented by the class SBL::GT::T_Union_of_balls_boundary_3_data_structure< WeightedAlphaComplex3 , IS_CCW , HalfedgeDSBase >. This data structure needs a builder providing an algorithm to build it, either from a family of 3D balls, either directly from an input complex. The underlying data structure is an halfedge data structure. Such a structure is made of vertices, oriented edges and faces : each adjacent faces are connected through a pair of opposite oriented edges, hence the name halfedges. In this case, the halfedges represent the intersection arcs / circles between the surface of the 3D balls, thus defining the faces as the connected pieces of surfaces for each sphere, and the vertices as the intersection points between the arvs. The orientation of all halfedges around their bounding face is set to be the same for all faces, that is either clockwise(CW) or counterclockwise (CCW). (As detailed below this is set by a tag.)
The three template parameters are :
WeightedAlphaComplex3 : representation of the 3D alphacomplex to be used to build the boundary, as detailed in the CGAL 3D alphacomplex user manual;
IS_CCW : boolean tag indicating in which sense are oriented the arcs in the boundary data structure (default is true, i.e CCW);
HalfedgeDSBase : base data structure used for representing the boundary, as detailed in the CGAL halfedge data structure user manual (default is CGAL::HalfedgeDS_vector).
The main functionality provided by this data structure are :
traversing : in addition of the base way to explore the data structure (iterating over vertices, halfedges, and faces, or iterating on successive halfedges), it is possible to iterate over the set of holes of a face, (SBL::GT::T_Union_of_balls_boundary_3_data_structure::holes_begin, SBL::GT::T_Union_of_balls_boundary_3_data_structure::holes_end) and over the connected components of faces of the boundary (SBL::GT::T_Union_of_balls_boundary_3_data_structure::connected_components_of_faces_begin, SBL::GT::T_Union_of_balls_boundary_3_data_structure::connected_components_of_faces_end)
accessing : it is possible to access geometric information such as the geometric point corresponding to a vertex (SBL::GT::T_Union_of_balls_boundary_3_data_structure::get_point), the geometric arc (SBL::GT::T_Union_of_balls_boundary_3_data_structure::get_circular_arc) or supporting circle (SBL::GT::T_Union_of_balls_boundary_3_data_structure::get_supporting_circle) corresponding to halfedge, and the geometric supporting sphere (SBL::GT::T_Union_of_balls_boundary_3_data_structure::get_supporting_sphere) corresponding to a face; note that the boundary data structure is combinatorial, meaning that these geometric constructions require an appropriate geometric kernel to be built; thus, the corresponding methods are templated by a spherical kernel as defined in the CGAL 3D Spherical Kernel user manual
The algorithm described in section Algorithms is implemented in the builder class
SBL::GT::T_Union_of_balls_boundary_3_builder< UnionOfBallsBoundaryDS , ExactNT >. It takes as input a range of 3D balls, or an already computed complex, and computes the associated boundary. Note that the algorithm is parametrized by a dimension parameter specifying if only vertices should be built, or vertices and halfedges, or vertices, halfedges and facets.
The two template parameters are :
UnionOfBallsBoundaryDS : representation of the boundary of the union of 3D balls, such as SBL::GT::T_Union_of_balls_boundary_3_data_structure;
ExactNT : representation of an exact number type, like rational numbers; it is by default the rational number representation from CGAL : Gmpq
This package also provides the module SBL::Modules::T_Union_of_balls_boundary_3_module< ModuleTraits , ExactNT > that computes the boundary of the union of a family of 3D balls that are represented by a complex data structure :
The two template parameters are:
An example of usage of this module is shown in section Using the boundary module .
This example shows how to simply compute the boundary of an input union of 3D balls and print some statistics about this boundary.
This example shows how to instantiate the provided module SBL::Modules::T_Union_of_balls_boundary_3 in a biological context by computing the boundary of a molecule loaded from a PDB file:
This example shows how to print a VMD output representing the boundary of an input family of 3D balls :