\( \newcommand{\E}{\mathrm{E}} \) \( \newcommand{\A}{\mathrm{A}} \) \( \newcommand{\R}{\mathrm{R}} \) \( \newcommand{\N}{\mathrm{N}} \) \( \newcommand{\Q}{\mathrm{Q}} \) \( \newcommand{\Z}{\mathrm{Z}} \) \( \def\ccSum #1#2#3{ \sum_{#1}^{#2}{#3} } \def\ccProd #1#2#3{ \sum_{#1}^{#2}{#3} }\)
CGAL 4.4 - Bounding Volumes
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Groups Pages
CGAL::Min_annulus_d< Traits > Class Template Reference

#include <CGAL/Min_annulus_d.h>

Definition

An object of the class Min_annulus_d is the unique annulus (region between two concentric spheres with radii \( r\) and \( R\), \( r \leq R\)) enclosing a finite set of points in \( d\)-dimensional Euclidean space \( \E^d\), where the difference \( R^2-r^2\) is minimal.

For a point set \( P\) we denote by \( ma(P)\) the smallest annulus that contains all points of \( P\). Note that \( ma(P)\) can be degenerate, i.e. \( ma(P)=\emptyset\) if \( P=\emptyset\) and \( ma(P)=\{p\}\) if \( P=\{p\}\).

An inclusion-minimal subset \( S\) of \( P\) with \( ma(S)=ma(P)\) is called a support set, the points in \( S\) are the support points. A support set has size at most \( d+2\), and all its points lie on the boundary of \( ma(P)\). In general, the support set is not necessarily unique.

The underlying algorithm can cope with all kinds of input, e.g. \( P\) may be empty or points may occur more than once. The algorithm computes a support set \( S\) which remains fixed until the next set, insert, or clear operation.

Template Parameters
Traitsmust be a model for OptimisationDTraits.

We provide the models Optimisation_d_traits_2, Optimisation_d_traits_3, and Optimisation_d_traits_d using the two-, three-, and \( d\)-dimensional CGAL kernel, respectively.

See Also
CGAL::Min_sphere_d<Traits>
CGAL::Optimisation_d_traits_2<K,ET,NT>
CGAL::Optimisation_d_traits_3<K,ET,NT>
CGAL::Optimisation_d_traits_d<K,ET,NT>
OptimisationDTraits

Implementation

The problem of finding the smallest enclosing annulus of a finite point set can be formulated as an optimization problem with linear constraints and a linear objective function. The solution is obtained using our exact solver for linear and quadratic programs [7].

The creation time is almost always linear in the number of points. Access functions and predicates take constant time, inserting a point takes almost always linear time. The clear operation and the check for validity each take linear time.

Examples:
Min_annulus_d/min_annulus_d.cpp, and Min_annulus_d/min_annulus_d_fast_exact.cpp.

Related Functions

(Note that these are not member functions.)

std::ostream & operator<< (std::ostream &os, const Min_annulus_d< Traits > &min_annulus)
 writes min_annulus to output stream os. More...
 
std::istream & operator>> (std::istream &is, Min_annulus_d< Traits > min_annulus &)
 reads min_annulus from input stream is. More...
 

Types

typedef unspecified_type Point
 typedef to Traits::Point_d. More...
 
typedef unspecified_type FT
 typedef to Traits::FT. More...
 
typedef unspecified_type ET
 typedef to Traits::ET. More...
 
typedef unspecified_type Point_iterator
 non-mutable model of the STL concept RandomAccessIterator with value type Point. More...
 
typedef unspecified_type Support_point_iterator
 non-mutable model of the STL concept RandomAccessIterator with value type Point. More...
 
typedef unspecified_type Inner_support_point_iterator
 non-mutable model of the STL concept RandomAccessIterator with value type Point. More...
 
typedef unspecified_type Outer_support_point_iterator
 non-mutable model of the STL concept RandomAccessIterator with value type Point. More...
 
typedef unspecified_type Coordinate_iterator
 non-mutable model of the STL concept RandomAccessIterator with value type ET. More...
 

Creation

 Min_annulus_d (const Traits &traits=Traits(), int verbose=0, std::ostream &stream=std::cout)
 initializes min_annulus to \( ma(\emptyset)\).
 
template<class InputIterator >
 Min_annulus_d (InputIterator first, InputIterator last, const Traits &traits=Traits(), int verbose=0, std::ostream &stream=std::cout)
 initializes min_annulus to \( ma(P)\) with \( P\) being the set of points in the range [first,last). More...
 

Access Functions

int ambient_dimension () const
 returns the dimension of the points in \( P\). More...
 
int number_of_points () const
 returns the number of points of min_annulus, i.e. \( |P|\).
 
int number_of_support_points () const
 returns the number of support points of min_annulus, i.e. \( |S|\).
 
int number_of_inner_support_points () const
 returns the number of support points of min_annulus which lie on the inner sphere.
 
int number_of_outer_support_points () const
 returns the number of support points of min_annulus which lie on the outer sphere.
 
Point_iterator points_begin () const
 returns an iterator referring to the first point of min_annulus.
 
Point_iterator points_end () const
 returns the corresponding past-the-end iterator.
 
Support_point_iterator support_points_begin () const
 returns an iterator referring to the first support point of min_annulus. More...
 
Support_point_iterator support_points_end () const
 returns the corresponding past-the-end iterator. More...
 
Inner_support_point_iterator inner_support_points_begin () const
 returns an iterator referring to the first inner support point of min_annulus.
 
Inner_support_point_iterator inner_support_points_end () const
 returns the corresponding past-the-end iterator.
 
Outer_support_point_iterator outer_support_points_begin () const
 returns an iterator referring to the first outer support point of min_annulus.
 
Outer_support_point_iterator outer_support_points_end () const
 returns the corresponding past-the-end iterator.
 
Point center () const
 returns the center of min_annulus. More...
 
FT squared_inner_radius () const
 returns the squared inner radius of min_annulus. More...
 
FT squared_outer_radius () const
 returns the squared outer radius of min_annulus. More...
 
Coordinate_iterator center_coordinates_begin () const
 returns an iterator referring to the first coordinate of the center of min_annulus. More...
 
Coordinate_iterator center_coordinates_end () const
 returns the corresponding past-the-end iterator.
 
ET squared_inner_radius_numerator () const
 returns the numerator of the squared inner radius of min_annulus.
 
ET squared_outer_radius_numerator () const
 returns the numerator of the squared outer radius of min_annulus.
 
ET squared_radii_denominator () const
 returns the denominator of the squared radii of min_annulus.
 

Predicates

The bounded area of the smallest enclosing annulus lies between the inner and the outer sphere.

The boundary is the union of both spheres. By definition, an empty annulus has no boundary and no bounded side, i.e. its unbounded side equals the whole space \( \E^d\).

CGAL::Bounded_side bounded_side (const Point &p) const
 returns CGAL::ON_BOUNDED_SIDE, CGAL::ON_BOUNDARY, or CGAL::ON_UNBOUNDED_SIDE iff p lies properly inside, on the boundary, or properly outside of min_annulus, resp. More...
 
bool has_on_bounded_side (const Point &p) const
 returns true, iff p lies properly inside min_annulus. More...
 
bool has_on_boundary (const Point &p) const
 returns true, iff p lies on the boundary of min_annulus. More...
 
bool has_on_unbounded_side (const Point &p) const
 returns true, iff p lies properly outside of min_annulus. More...
 
bool is_empty () const
 returns true, iff min_annulus is empty (this implies degeneracy).
 
bool is_degenerate () const
 returns true, iff min_annulus is degenerate, i.e. if min_annulus is empty or equal to a single point.
 

Modifiers

void clear ()
 resets min_annulus to \( ma(\emptyset)\).
 
template<class InputIterator >
void set (InputIterator first, InputIterator last)
 sets min_annulus to \( ma(P)\), where \( P\) is the set of points in the range [first,last). More...
 
void insert (const Point &p)
 inserts p into min_annulus. More...
 
template<class InputIterator >
void insert (InputIterator first, InputIterator last)
 inserts the points in the range [first,last) into min_annulus and recomputes the smallest enclosing annulus. More...
 

Validity Check

An object min_annulus is valid, iff

  • min_annulus contains all points of its defining set \( P\),
  • min_annulus is the smallest annulus containing its support set \( S\), and
  • \( S\) is minimal, i.e. no support point is redundant.

Note: In this release only the first item is considered by the validity check.

bool is_valid (bool verbose=false, int level=0) const
 returns true, iff min_annulus is valid. More...
 

Miscellaneous

const Traits & traits () const
 returns a const reference to the traits class object.
 

Member Typedef Documentation

template<typename Traits >
typedef unspecified_type CGAL::Min_annulus_d< Traits >::Coordinate_iterator

non-mutable model of the STL concept RandomAccessIterator with value type ET.

Used to access the coordinates of the center of the smallest enclosing annulus.

template<typename Traits >
typedef unspecified_type CGAL::Min_annulus_d< Traits >::ET

typedef to Traits::ET.

Number type used to do the exact computations in the underlying solver for quadratic programs (cf. Implementation).

template<typename Traits >
typedef unspecified_type CGAL::Min_annulus_d< Traits >::FT

typedef to Traits::FT.

Number type used to return the squared radii of the smallest enclosing annulus.

template<typename Traits >
typedef unspecified_type CGAL::Min_annulus_d< Traits >::Inner_support_point_iterator

non-mutable model of the STL concept RandomAccessIterator with value type Point.

Used to access the inner support points of the smallest enclosing annulus.

template<typename Traits >
typedef unspecified_type CGAL::Min_annulus_d< Traits >::Outer_support_point_iterator

non-mutable model of the STL concept RandomAccessIterator with value type Point.

Used to access the outer support points of the smallest enclosing annulus.

template<typename Traits >
typedef unspecified_type CGAL::Min_annulus_d< Traits >::Point

typedef to Traits::Point_d.

Point type used to represent the input points.

template<typename Traits >
typedef unspecified_type CGAL::Min_annulus_d< Traits >::Point_iterator

non-mutable model of the STL concept RandomAccessIterator with value type Point.

Used to access the points of the smallest enclosing annulus.

template<typename Traits >
typedef unspecified_type CGAL::Min_annulus_d< Traits >::Support_point_iterator

non-mutable model of the STL concept RandomAccessIterator with value type Point.

Used to access the support points of the smallest enclosing annulus.

Constructor & Destructor Documentation

template<typename Traits >
template<class InputIterator >
CGAL::Min_annulus_d< Traits >::Min_annulus_d ( InputIterator  first,
InputIterator  last,
const Traits &  traits = Traits(),
int  verbose = 0,
std::ostream &  stream = std::cout 
)

initializes min_annulus to \( ma(P)\) with \( P\) being the set of points in the range [first,last).

Requires:
The value type of InputIterator is Point.
Precondition
All points have the same dimension.

Member Function Documentation

template<typename Traits >
int CGAL::Min_annulus_d< Traits >::ambient_dimension ( ) const

returns the dimension of the points in \( P\).

If min_annulus is empty, the ambient dimension is \( -1\).

template<typename Traits >
CGAL::Bounded_side CGAL::Min_annulus_d< Traits >::bounded_side ( const Point p) const

returns CGAL::ON_BOUNDED_SIDE, CGAL::ON_BOUNDARY, or CGAL::ON_UNBOUNDED_SIDE iff p lies properly inside, on the boundary, or properly outside of min_annulus, resp.

Precondition
The dimension of p equals min_annulus.ambient_dimension() if min_annulus is not empty.
template<typename Traits >
Point CGAL::Min_annulus_d< Traits >::center ( ) const

returns the center of min_annulus.

Requires:
An implicit conversion from ET to RT is available.
Precondition
min_annulus is not empty.
template<typename Traits >
Coordinate_iterator CGAL::Min_annulus_d< Traits >::center_coordinates_begin ( ) const

returns an iterator referring to the first coordinate of the center of min_annulus.

Note
The coordinates have a rational representation, i.e. the first \( d\) elements of the iterator range are the numerators and the \( (d\!+\!1)\)-st element is the common denominator.
template<typename Traits >
bool CGAL::Min_annulus_d< Traits >::has_on_boundary ( const Point p) const

returns true, iff p lies on the boundary of min_annulus.

Precondition
The dimension of p equals min_annulus.ambient_dimension() if min_annulus is not empty.
template<typename Traits >
bool CGAL::Min_annulus_d< Traits >::has_on_bounded_side ( const Point p) const

returns true, iff p lies properly inside min_annulus.

Precondition
The dimension of p equals min_annulus.ambient_dimension() if min_annulus is not empty.
template<typename Traits >
bool CGAL::Min_annulus_d< Traits >::has_on_unbounded_side ( const Point p) const

returns true, iff p lies properly outside of min_annulus.

Precondition
The dimension of p equals min_annulus.ambient_dimension() if min_annulus is not empty.
template<typename Traits >
void CGAL::Min_annulus_d< Traits >::insert ( const Point p)

inserts p into min_annulus.

Precondition
The dimension of p equals min_annulus.ambient_dimension() if min_annulus is not empty.
template<typename Traits >
template<class InputIterator >
void CGAL::Min_annulus_d< Traits >::insert ( InputIterator  first,
InputIterator  last 
)

inserts the points in the range [first,last) into min_annulus and recomputes the smallest enclosing annulus.

Requires:
The value type of InputIterator is Point.
Precondition
All points have the same dimension. If min_annulus is not empty, this dimension must be equal to min_annulus.ambient_dimension().
template<typename Traits >
bool CGAL::Min_annulus_d< Traits >::is_valid ( bool  verbose = false,
int  level = 0 
) const

returns true, iff min_annulus is valid.

If verbose is true, some messages concerning the performed checks are written to standard error stream. The second parameter level is not used, we provide it only for consistency with interfaces of other classes.

template<typename Traits >
template<class InputIterator >
void CGAL::Min_annulus_d< Traits >::set ( InputIterator  first,
InputIterator  last 
)

sets min_annulus to \( ma(P)\), where \( P\) is the set of points in the range [first,last).

Requires:
The value type of InputIterator is Point.
Precondition
All points have the same dimension.
template<typename Traits >
FT CGAL::Min_annulus_d< Traits >::squared_inner_radius ( ) const

returns the squared inner radius of min_annulus.

Requires:
An implicit conversion from ET to RT is available.
Precondition
min_annulus is not empty.
template<typename Traits >
FT CGAL::Min_annulus_d< Traits >::squared_outer_radius ( ) const

returns the squared outer radius of min_annulus.

Requires:
An implicit conversion from ET to RT is available.
Precondition
min_annulus is not empty.
template<typename Traits >
Support_point_iterator CGAL::Min_annulus_d< Traits >::support_points_begin ( ) const

returns an iterator referring to the first support point of min_annulus.

Precondition
\( ma(P)\) is not degenerate, i.e., number_of_support_points() is at least one.
template<typename Traits >
Support_point_iterator CGAL::Min_annulus_d< Traits >::support_points_end ( ) const

returns the corresponding past-the-end iterator.

Precondition
\( ma(P)\) is not degenerate, i.e., number_of_support_points() is at least one.

Friends And Related Function Documentation

template<typename Traits >
std::ostream & operator<< ( std::ostream &  os,
const Min_annulus_d< Traits > &  min_annulus 
)
related

writes min_annulus to output stream os.

Requires:
The output operator is defined for Point.
template<typename Traits >
std::istream & operator>> ( std::istream &  is,
Min_annulus_d< Traits > min_annulus &   
)
related

reads min_annulus from input stream is.

Requires:
The input operator is defined for Point.