CGAL 5.6.1 - Bounding Volumes
MinSphereOfSpheresTraits Concept Reference


A model of concept MinSphereOfSpheresTraits must provide the following constants, types, predicates and operations.

Has Models:






Has Models:


static const int D
 specifies the dimension of the spheres you want to compute the minsphere of.


typedef unspecified_type Sphere
 is a typedef to to some class representing a sphere. More...
typedef unspecified_type FT
 is a (exact or inexact) field number type. More...
typedef unspecified_type Cartesian_const_iterator
 non-mutable model of the STL concept ForwardIterator with value type FT. More...
typedef unspecified_type Use_square_roots
 must typedef to either CGAL::Tag_true or CGAL::Tag_false. More...
typedef unspecified_type Algorithm
 selects the method to compute the minsphere with. More...

Access Functions

FT radius (const Sphere &s)
 returns the radius of sphere s. More...
Cartesian_const_iterator center_cartesian_begin (const Sphere &s)
 returns an iterator referring to the first of the D Cartesian coordinates of the center of s.

Member Typedef Documentation

◆ Algorithm

selects the method to compute the minsphere with.

It must typedef to either CGAL::Default_algorithm, CGAL::LP_algorithm or CGAL::Farthest_first_heuristic. The recommended choice is the first, which is a synonym to the one of the other two methods which we consider "the best in practice." In case of CGAL::LP_algorithm, the minsphere will be computed using the LP-algorithm [11], which in our implementation has maximal expected running time \( O(2^d n)\) (in the number of operations on the number type FT). In case of CGAL::Farthest_first_heuristic, a simple heuristic will be used instead which seems to work fine in practice, but comes without a guarantee on the running time. For an inexact number type FT we strongly recommend CGAL::Default_algorithm, or, if you want, CGAL::Farthest_first_heuristic, since these handle most degeneracies in a satisfying manner. Notice that this compile-time flag is taken as a hint only. Should one of the methods not be available anymore in a future release, then the default algorithm will be chosen.

◆ Cartesian_const_iterator

non-mutable model of the STL concept ForwardIterator with value type FT.

Used to access the center coordinates of a sphere.

◆ FT

is a (exact or inexact) field number type.

Template Parameters
FTmust either be double or float, or an exact field number type. (An exact number type is one which evaluates arithmetic expressions involving the four basic operations and comparisons with infinite precision, that is, like in \( \mathbb{R}\).)

◆ Sphere

is a typedef to to some class representing a sphere.

(The package will compute the minsphere of spheres of type Sphere.) The type Sphere must provide a copy constructor.

◆ Use_square_roots

must typedef to either CGAL::Tag_true or CGAL::Tag_false.

The algorithm uses (depending on the type MinSphereOfSpheresTraits::Algorithm) floating-point arithmetic internally for some intermediate computations. The type Use_square_roots affects how these calculations are done: When Use_square_roots is Tag_true, the algorithm computing the minsphere will perform square-root operations on doubles and floats where appropriate. On the other hand, if Use_square_roots is CGAL::Tag_false, the algorithm will work without doing square-roots.

Note: On some platforms the algorithm is much faster when square-roots are disabled (due to lacking hardware support).

Member Function Documentation

◆ radius()

FT MinSphereOfSpheresTraits::radius ( const Sphere s)

returns the radius of sphere s.

The returned number is greater or equal to \( 0\).