An instance S of the data type Sphere_d is an oriented sphere in some d-dimensional space. A sphere is defined by d+1 points (class Point_d<Kernel>). We use A to denote the array of the defining points. A set A of defining points is legal if either the points are affinely independent or if the points are all equal. Only a legal set of points defines a sphere in the geometric sense and hence many operations on spheres require the set of defining points to be legal. The orientation of S is equal to the orientation of the defining points, i.e., orientation(A).


the linear algebra layer.

a read-only iterator for points defining the sphere.


Sphere_d<Kernel> S;
introduces a variable S of type Sphere_d<Kernel>.

template <class ForwardIterator>
Sphere_d<Kernel> S ( int d, ForwardIterator first, ForwardIterator last);
introduces a variable S of type Sphere_d<Kernel>. S is initialized to the sphere through the points in A = tuple [first,last).
Precondition: A consists of d+1 d-dimensional points.
Requirement: The value type of ForwardIterator is Point_d<Kernel>.


int S.dimension () returns the dimension of the ambient space.

Point_d<Kernel> S.point ( int i) returns the ith defining point.
Precondition: 0 i dim.

point_iterator S.points_begin () returns an iterator pointing to the first defining point.

point_iterator S.points_end () returns an iterator pointing beyond the last defining point.

bool S.is_degenerate () returns true iff the defining points are not full dimensional.

bool S.is_legal () returns true iff the set of defining points is legal. A set of defining points is legal iff their orientation is non-zero or if they are all equal.

Point_d<Kernel> () returns the center of S.
Precondition: S is legal.

FT S.squared_radius () returns the squared radius of the sphere.
Precondition: S is legal.

Orientation S.orientation () returns the orientation of S.

Oriented_side S.oriented_side ( Point_d<Kernel> p)
returns either the constant ON_ORIENTED_BOUNDARY, ON_POSITIVE_SIDE, or ON_NEGATIVE_SIDE, iff p lies on the boundary, properly on the positive side, or properly on the negative side of sphere, resp.
Precondition: S.dimension()==p.dimension().

Bounded_side S.bounded_side ( Point_d<Kernel> p)
returns ON_BOUNDED_SIDE, ON_BOUNDARY, or ON_UNBOUNDED_SIDE iff p lies properly inside, on the boundary, or properly outside of sphere, resp.
Precondition: S.dimension()==p.dimension().

bool S.has_on_positive_side ( Point_d<Kernel> p)
returns S.oriented_side(p)==ON_POSITIVE_SIDE.
Precondition: S.dimension()==p.dimension().

bool S.has_on_negative_side ( Point_d<Kernel> p)
returns S.oriented_side(p)==ON_NEGATIVE_SIDE.
Precondition: S.dimension()==p.dimension().

bool S.has_on_boundary ( Point_d<Kernel> p)
returns S.oriented_side(p)==ON_ORIENTED_BOUNDARY, which is the same as S.bounded_side(p)==ON_BOUNDARY.
Precondition: S.dimension()==p.dimension().

bool S.has_on_bounded_side ( Point_d<Kernel> p)
returns S.bounded_side(p)==ON_BOUNDED_SIDE.
Precondition: S.dimension()==p.dimension().

bool S.has_on_unbounded_side ( Point_d<Kernel> p)
returns S.bounded_side(p)==ON_UNBOUNDED_SIDE.
Precondition: S.dimension()==p.dimension().

Sphere_d<Kernel> S.opposite () returns the sphere with the same center and squared radius as S but with opposite orientation.

Sphere_d<Kernel> S + Vector_d<Kernel> v returns the sphere translated by v.
Precondition: S.dimension()==v.dimension().

Non-Member Functions

bool weak_equality ( S1, S2) Test for equality as unoriented spheres.
Precondition: S1.dimension()==S2.dimension().


Spheres are implemented by a vector of points as a handle type. All operations like creation, initialization, tests, input and output of a sphere s take time O(s.dimension()). dimension(), point access take constant time. The center()-operation takes time O(d3) on its first call and constant time thereafter. The sidedness and orientation tests take time O(d3). The space requirement for spheres is O(s.dimension()) neglecting the storage room of the points.