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

Table of Contents

Spherical_kernel_extension_3

Authors: F. Cazals and T. Dreyfus

Introduction

This package provides constructions and predicates related to the CGAL Spherical_kernel_3 [33] . In particular, it allows to compute an orientation for the circular arcs. Given two spheres $S_1(c_1, r_1)$, $S_2(c_2, r_2)$ that intersect on a circle $C(c, r)$, a point $p$ on this circle and a circular arc $C_p$ starting at $p$ oriented with a tangent vector $\overrightarrow{T_{C_p}}$ at $p$, we say that $C_p$ is counter-clockwise oriented w.r.t $S_1$ iff the following mixed product is positive: $\overrightarrow{T_{C_p}}.(\overrightarrow{cp}\times\overrightarrow{c_1c_2})$. More intuitively, this means that $S_1$ bounds $C_p$ on its "left".

While the computation of $\overrightarrow{c_1c_2}$ is straightforward, computing $\overrightarrow{cp}$ and $\overrightarrow{T_{C_p}}$ require managing degree two algebraic operations. To understand why, assume that $C_p$ is counter-clockwise oriented:

  • for $\overrightarrow{cp}$, while $c$ has coordinates linearly computed from the coordinates and radii of the two spheres, $p$ belongs to the intersection circle and the coordinates may be degree two algebraic numbers, resulting on degree two algebraic numbers for the coordinates of $\overrightarrow{cp}$;
  • for $\overrightarrow{T_{C_p}}$, we can compute its from the cross product ( $\overrightarrow{cp}\times\overrightarrow{c_1c_2}$), that results on a vector with degree two algebraic coordinates.

Now, given a third sphere $S_3(c_3, r_3)$, assume that $p$ is the intersection point between $S_1$, $S_2$ and $S_3$, and consider the plane $P$ tangent to $S_3$ at $p$. Note that $P$ cannot contain $\overrightarrow{T_{C_p}}$ nor $\overrightarrow{pc_3}$. Since $p$ is the source of $C_p$, $\overrightarrow{T_{C_p}}$ and $\overrightarrow{pc_3}$ have to point to different sides of $P$. If it is not the case, this means that $C_p$ is not counter-clockwise oriented.

We use these properties for determining the orientation of a circular arc defining by three intersecting spheres $S_1$, $S_2$ and $S_3$, and a reference point $p_{ref}$ allowing to locate the source of the circular arc:

  • $S_1$ is the reference sphere for the orientation,
  • $S_1$ and $S_2$ define the support circle of the circular arc,
  • $S_1$, $S_2$, $S_3$ define at most two possible sources of the circular arc, and $p_{ref}$ determines the side of the plane $(c_1, c_2, c_3)$ that contains the source of the circular arc.

Implementation

The SBL::GT::T_Spherical_kernel_extension_3 < SphericalKernel3 > is designed as a traits class defining the functors corresponding to the different constructions and predicates. The template parameter is one of the CGAL three dimensional spherical kernel, that could be the exact one (CGAL::Exact_spherical_kernel_3) or the generic one (CGAL::Spherical_kernel_3). See the Example section.

Dependencies

This package has no internal dependency.

The only one external dependency is the CGAL library, for the representation of 3D geometric objects. Note that this part of the CGAL library is generic and consists only of C++ header files.

Example

The following example presents the SBL::GT::T_Spherical_kernel_extension_3::Is_counter_clockwise_oriented predicate, with exact or inexact computations.