CGAL 4.7 - Bounding Volumes: Bounding Volumes Reference

\( \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.7 - Bounding Volumes

All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Groups Pages
Modules | Classes | Functions
Bounding Volumes Reference

##

Kaspar Fischer, Bernd Gärtner, Thomas Herrmann, Michael Hoffmann, and Sven Schönherr
This package provides algorithms for computing optimal bounding volumes of point sets. In d-dimensional space, the smallest enclosing sphere, ellipsoid (approximate), and annulus can be computed. In 3-dimensional space, the smallest enclosing strip is available as well, and in 2-dimensional space, there are algorithms for a number of additional volumes (rectangles, parallelograms, \( k=2,3,4\) axis-aligned rectangles). The smallest enclosing sphere algorithm can also be applied to a set of d-dimensional spheres.

Introduced in: CGAL 1.1
BibTeX: cgal:fghhs-bv-15b
License: GPL
Windows Demo: 2D Bounding Volumes
Common Demo Dlls: dlls

## Assertions

The optimization code uses infix `OPTIMISATION` in the assertions, e.g. defining the compiler flag `CGAL_OPTIMISATION_NO_PRECONDITIONS` switches precondition checking off, cf. Section Checks.

## Classified Reference Pages

## Bounding Areas and Volumes

- `CGAL::Min_circle_2<Traits>`
- `CGAL::Min_circle_2_traits_2<K>`
- `MinCircle2Traits`
- `CGAL::Min_ellipse_2<Traits>`
- `CGAL::Min_ellipse_2_traits_2<K>`
- `MinEllipse2Traits`
- `CGAL::Approximate_min_ellipsoid_d<Traits>`
- `ApproximateMinEllipsoid_d_Traits_d`
- `CGAL::min_rectangle_2`
- `CGAL::min_parallelogram_2`
- `CGAL::min_strip_2`
- `CGAL::Min_quadrilateral_default_traits_2<K>`
- `MinQuadrilateralTraits_2`
- `CGAL::rectangular_p_center_2`
- `CGAL::Rectangular_p_center_default_traits_2<K>`
- `RectangularPCenterTraits_2`
- `CGAL::Min_sphere_d<Traits>`
- `CGAL::Min_annulus_d<Traits>`
- `CGAL::Min_sphere_annulus_d_traits_2<K,ET,NT>`
- `CGAL::Min_sphere_annulus_d_traits_3<K,ET,NT>`
- `CGAL::Min_sphere_annulus_d_traits_d<K,ET,NT>`
- `MinSphereAnnulusDTraits`
- `CGAL::Min_sphere_of_spheres_d<Traits>`
- `MinSphereOfSpheresTraits`

## Modules

| Concepts

## Classes

class | CGAL::Approximate_min_ellipsoid_d< Traits >
| An object of class `Approximate_min_ellipsoid_d` is an approximation to the ellipsoid of smallest volume enclosing a finite multiset of points in \( d\)-dimensional Euclidean space \( \E^d\), \( d\ge 2\). More...
class | CGAL::Approximate_min_ellipsoid_d_traits_2< K, ET >
| The class `Approximate_min_ellipsoid_d_traits_2` is a traits class for `CGAL::Approximate_min_ellipsoid_d<Traits>` using the 2-dimensional CGAL kernel. More...
class | CGAL::Approximate_min_ellipsoid_d_traits_3< K, ET >
| The class `Approximate_min_ellipsoid_d_traits_3` is a traits class for `CGAL::Approximate_min_ellipsoid_d<Traits>` using the 3-dimensional CGAL kernel. More...
class | CGAL::Approximate_min_ellipsoid_d_traits_d< K, ET >
| The class `Approximate_min_ellipsoid_d_traits_d` is a traits class for `CGAL::Approximate_min_ellipsoid_d<Traits>` using the d-dimensional CGAL kernel. More...
class | CGAL::Min_annulus_d< Traits >

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. More...

class | CGAL::Min_circle_2< Traits >
| An object of the class `Min_circle_2` is the unique circle of smallest area enclosing a finite (multi)set of points in two-dimensional Euclidean space \( \E^2\). More...
class | CGAL::Min_circle_2_traits_2< K >
| The class `Min_circle_2_traits_2` is a traits class for `Min_circle_2<Traits>` using the two-dimensional CGAL kernel. More...
class | CGAL::Min_ellipse_2< Traits >
| An object of the class `Min_ellipse_2` is the unique ellipse of smallest area enclosing a finite (multi)set of points in two-dimensional euclidean space \( \E^2\). More...
class | CGAL::Min_ellipse_2_traits_2< K >
| The class `Min_ellipse_2_traits_2` is a traits class for `CGAL::Min_ellipse_2<Traits>` using the two-di-men-sional CGAL kernel. More...
class | CGAL::Min_quadrilateral_default_traits_2< K >
| The class `Min_quadrilateral_default_traits_2` is a traits class for the functions `min_rectangle_2`, `min_parallelogram_2` and `min_strip_2` using a two-dimensional CGAL kernel. More...
class | CGAL::Min_sphere_annulus_d_traits_2< K, ET, NT >
| The class `Min_sphere_annulus_d_traits_2` is a traits class for the \( d\)-dimensional optimisation algorithms using the two-dimensional CGAL kernel. More...
class | CGAL::Min_sphere_annulus_d_traits_3< K, ET, NT >
| The class `Min_sphere_annulus_d_traits_3` is a traits class for the \( d\)-dimensional optimisation algorithms using the three-dimensional CGAL kernel. More...
class | CGAL::Min_sphere_annulus_d_traits_d< K, ET, NT >
| The class `Min_sphere_annulus_d_traits_d` is a traits class for the \( d\)-dimensional optimisation algorithms using the \( d\)-dimensional CGAL kernel. More...
class | CGAL::Min_sphere_d< Traits >
| An object of the class `Min_sphere_d` is the unique sphere of smallest volume enclosing a finite (multi)set of points in \( d\)-dimensional Euclidean space \( \E^d\). More...
class | CGAL::Min_sphere_of_points_d_traits_2< K, FT, UseSqrt, Algorithm >
| The class `Min_sphere_of_points_d_traits_2<K,FT,UseSqrt,Algorithm>` is a model for concept `MinSphereOfSpheresTraits`. More...
class | CGAL::Min_sphere_of_points_d_traits_3< K, FT, UseSqrt, Algorithm >
| The class `Min_sphere_of_points_d_traits_3<K,FT,UseSqrt,Algorithm>` is a model for concept `MinSphereOfSpheresTraits`. More...
class | CGAL::Min_sphere_of_points_d_traits_d< K, FT, Dim, UseSqrt, Algorithm >
| The class `Min_sphere_of_points_d_traits_d<K,FT,Dim,UseSqrt,Algorithm>` is a model for concept `MinSphereOfSpheresTraits`. More...
class | CGAL::Min_sphere_of_spheres_d< Traits >
| An object of the class `Min_sphere_of_spheres_d` is a data structure that represents the unique sphere of smallest volume enclosing a finite set of spheres in \( d\)-dimensional Euclidean space \( \E^d\). More...
class | CGAL::Min_sphere_of_spheres_d_traits_2< K, FT, UseSqrt, Algorithm >
| The class `Min_sphere_of_spheres_d_traits_2<K,FT,UseSqrt,Algorithm>` is a model for concept `MinSphereOfSpheresTraits`. More...
class | CGAL::Min_sphere_of_spheres_d_traits_3< K, FT, UseSqrt, Algorithm >
| The class `Min_sphere_of_spheres_d_traits_3<K,FT,UseSqrt,Algorithm>` is a model for concept `MinSphereOfSpheresTraits`. More...
class | CGAL::Min_sphere_of_spheres_d_traits_d< K, FT, Dim, UseSqrt, Algorithm >
| The class `Min_sphere_of_spheres_d_traits_d<K,FT,Dim,UseSqrt,Algorithm>` is a model for concept `MinSphereOfSpheresTraits`. More...
class | CGAL::Rectangular_p_center_default_traits_2< K >
| The class `Rectangular_p_center_default_traits_2` defines types and operations needed to compute rectilinear \( p\)-centers of a planar point set using the function `rectangular_p_center_2()`. More...

## Functions

template<class ForwardIterator , class OutputIterator , class Traits >
OutputIterator | CGAL::min_parallelogram_2 (ForwardIterator points_begin, ForwardIterator points_end, OutputIterator o, Traits &t=Default_traits)
| The function computes a minimum area enclosing parallelogram \( A(P)\) of a given convex point set \( P\). More...
template<class ForwardIterator , class OutputIterator , class Traits >
OutputIterator | CGAL::min_rectangle_2 (ForwardIterator points_begin, ForwardIterator points_end, OutputIterator o, Traits &t=Default_traits)
| The function computes a minimum area enclosing rectangle \( R(P)\) of a given convex point set \( P\). More...
template<class ForwardIterator , class OutputIterator , class Traits >
OutputIterator | CGAL::min_strip_2 (ForwardIterator points_begin, ForwardIterator points_end, OutputIterator o, Traits &t=Default_traits)
| The function computes a minimum width enclosing strip \( S(P)\) of a given convex point set \( P\). More...
template<class ForwardIterator , class OutputIterator , class FT , class Traits >
OutputIterator | CGAL::rectangular_p_center_2 (ForwardIterator f, ForwardIterator l, OutputIterator o, FT &r, int p, const Traits &t=Default_traits)
| Computes rectilinear \( p\)-centers of a planar point set, i.e. a set of \( p\) points such that the maximum minimal \( L_{\infty}\)-distance between both sets is minimized. More...

## Function Documentation

template<class ForwardIterator , class OutputIterator , class Traits >

OutputIterator CGAL::min_parallelogram_2 | ( | ForwardIterator | points_begin,
|  | ForwardIterator | points_end,
|  | OutputIterator | o,
|  | Traits & | t = `Default_traits`
| ) |  |

The function computes a minimum area enclosing parallelogram \( A(P)\) of a given convex point set \( P\).

Note that \( R(P)\) is not necessarily axis-parallel, and it is in general not unique. The focus on convex sets is no restriction, since any parallelogram enclosing \( P\) - as a convex set - contains the convex hull of \( P\). For general point sets one has to compute the convex hull as a preprocessing step.

computes a minimum area enclosing parallelogram of the point set described by [`points_begin`, `points_end`), writes its vertices (counterclockwise) to `o` and returns the past-the-end iterator of this sequence. If the input range is empty, `o` remains unchanged.

If the input range consists of one element only, this point is written to `o` four times.

Precondition
  The points denoted by the range [`points_begin`, `points_end`) form the boundary of a simple convex polygon \( P\) in counterclockwise orientation.

The geometric types and operations to be used for the computation are specified by the traits class parameter `t`. The parameter can be omitted, if `ForwardIterator` refers to a two-dimensional point type from one the CGAL kernels. In this case, a default traits class (`Min_quadrilateral_default_traits_2<K>`) is used.

Requires:

1. If `Traits` is specified, it is a model for `MinQuadrilateralTraits_2` and the value type `VT` of `ForwardIterator` is `Traits::Point_2`. Otherwise `VT` is `CGAL::Point_2<K>` for some kernel `K`.
2. `OutputIterator` accepts `VT` as value type.

See Also
  `CGAL::min_rectangle_2()`
  `CGAL::min_strip_2()`
  `MinQuadrilateralTraits_2`
  `CGAL::Min_quadrilateral_default_traits_2<K>`

Implementation

We use a rotating caliper algorithm [12], [15] with worst case running time linear in the number of input points.

Example

The following code generates a random convex polygon `P` with 20 vertices and computes the minimum enclosing parallelogram of `P`.

File Min_quadrilateral_2/minimum_enclosing_parallelogram_2.cpp

#include <CGAL/Simple_cartesian.h>
#include <CGAL/Polygon_2.h>
#include <CGAL/point_generators_2.h>
#include <CGAL/random_convex_set_2.h>
#include <CGAL/min_quadrilateral_2.h>
#include <iostream>
typedef CGAL::Simple_cartesian<double> Kernel;
typedef Kernel::Point_2 Point_2;
typedef Kernel::Line_2 Line_2;
typedef CGAL::Polygon_2<Kernel> Polygon_2;
typedef CGAL::Random_points_in_square_2<Point_2> Generator;
int main()
{
// build a random convex 20-gon p
Polygon_2 p;
CGAL::random_convex_set_2(20, std::back_inserter(p), Generator(1.0));
std::cout << p << std::endl;
// compute the minimal enclosing parallelogram p_m of p
Polygon_2 p_m;
CGAL::min_parallelogram_2(
p.vertices_begin(), p.vertices_end(), std::back_inserter(p_m));
std::cout << p_m << std::endl;
return 0;
}

`#include <CGAL/min_quadrilateral_2.h>`

Examples:
  Min_quadrilateral_2/minimum_enclosing_parallelogram_2.cpp.

template<class ForwardIterator , class OutputIterator , class Traits >

OutputIterator CGAL::min_rectangle_2 | ( | ForwardIterator | points_begin,
|  | ForwardIterator | points_end,
|  | OutputIterator | o,
|  | Traits & | t = `Default_traits`
| ) |  |

The function computes a minimum area enclosing rectangle \( R(P)\) of a given convex point set \( P\).

Note that \( R(P)\) is not necessarily axis-parallel, and it is in general not unique. The focus on convex sets is no restriction, since any rectangle enclosing \( P\) - as a convex set - contains the convex hull of \( P\). For general point sets one has to compute the convex hull as a preprocessing step.

computes a minimum area enclosing rectangle of the point set described by [`points_begin`, `points_end`), writes its vertices (counterclockwise) to `o`, and returns the past-the-end iterator of this sequence.

If the input range is empty, `o` remains unchanged.

If the input range consists of one element only, this point is written to `o` four times.

Precondition
  The points denoted by the range [`points_begin`, `points_end`) form the boundary of a simple convex polygon \( P\) in counterclockwise orientation.

The geometric types and operations to be used for the computation are specified by the traits class parameter `t`. The parameter can be omitted, if `ForwardIterator` refers to a two-dimensional point type from one the CGAL kernels. In this case, a default traits class (`Min_quadrilateral_default_traits_2<K>`) is used.

Requires:

1. If `Traits` is specified, it is a model for `MinQuadrilateralTraits_2` and the value type `VT` of `ForwardIterator` is `Traits::Point_2`. Otherwise `VT` is `CGAL::Point_2<K>` for some kernel `K`.
2. `OutputIterator` accepts `VT` as value type.

See Also
  `CGAL::min_parallelogram_2()`
  `CGAL::min_strip_2()`
  `MinQuadrilateralTraits_2`
  `CGAL::Min_quadrilateral_default_traits_2<K>`

Implementation

We use a rotating caliper algorithm [14] with worst case running time linear in the number of input points.

Example

The following code generates a random convex polygon `P` with 20 vertices and computes the minimum enclosing rectangle of `P`.

File Min_quadrilateral_2/minimum_enclosing_rectangle_2.cpp

#include <CGAL/Simple_cartesian.h>
#include <CGAL/Polygon_2.h>
#include <CGAL/point_generators_2.h>
#include <CGAL/random_convex_set_2.h>
#include <CGAL/min_quadrilateral_2.h>
#include <iostream>
typedef CGAL::Simple_cartesian<double> Kernel;
typedef Kernel::Point_2 Point_2;
typedef Kernel::Line_2 Line_2;
typedef CGAL::Polygon_2<Kernel> Polygon_2;
typedef CGAL::Random_points_in_square_2<Point_2> Generator;
int main()
{
// build a random convex 20-gon p
Polygon_2 p;
CGAL::random_convex_set_2(20, std::back_inserter(p), Generator(1.0));
std::cout << p << std::endl;
// compute the minimal enclosing rectangle p_m of p
Polygon_2 p_m;
CGAL::min_rectangle_2(
p.vertices_begin(), p.vertices_end(), std::back_inserter(p_m));
std::cout << p_m << std::endl;
return 0;
}

`#include <CGAL/min_quadrilateral_2.h>`

Examples:
  Min_quadrilateral_2/minimum_enclosing_rectangle_2.cpp.

template<class ForwardIterator , class OutputIterator , class Traits >

OutputIterator CGAL::min_strip_2 | ( | ForwardIterator | points_begin,
|  | ForwardIterator | points_end,
|  | OutputIterator | o,
|  | Traits & | t = `Default_traits`
| ) |  |

The function computes a minimum width enclosing strip \( S(P)\) of a given convex point set \( P\).

A strip is the closed region bounded by two parallel lines in the plane. Note that \( S(P)\) is not unique in general. The focus on convex sets is no restriction, since any parallelogram enclosing \( P\) - as a convex set - contains the convex hull of \( P\). For general point sets one has to compute the convex hull as a preprocessing step.

computes a minimum enclosing strip of the point set described by [`points_begin`, `points_end`), writes its two bounding lines to `o` and returns the past-the-end iterator of this sequence.

If the input range is empty or consists of one element only, `o` remains unchanged.

Precondition
  The points denoted by the range [`points_begin`, `points_end`) form the boundary of a simple convex polygon \( P\) in counterclockwise orientation.

The geometric types and operations to be used for the computation are specified by the traits class parameter `t`. The parameter can be omitted, if `ForwardIterator` refers to a two-dimensional point type from one the CGAL kernels. In this case, a default traits class (`Min_quadrilateral_default_traits_2<K>`) is used.

Requires:

1. If `Traits` is specified, it is a model for `MinQuadrilateralTraits_2` and the value type `VT` of `ForwardIterator` is `Traits::Point_2`. Otherwise `VT` is `CGAL::Point_2<K>` for some kernel `K`.
2. `OutputIterator` accepts `Traits::Line_2` as value type.

See Also
  `CGAL::min_rectangle_2()`
  `CGAL::min_parallelogram_2()`
  `MinQuadrilateralTraits_2`
  `CGAL::Min_quadrilateral_default_traits_2<K>`

Implementation

We use a rotating caliper algorithm [14] with worst case running time linear in the number of input points.

Example

The following code generates a random convex polygon `P` with 20 vertices and computes the minimum enclosing strip of `P`.

File Min_quadrilateral_2/minimum_enclosing_strip_2.cpp

#include <CGAL/Simple_cartesian.h>
#include <CGAL/Polygon_2.h>
#include <CGAL/point_generators_2.h>
#include <CGAL/random_convex_set_2.h>
#include <CGAL/min_quadrilateral_2.h>
#include <iostream>
typedef CGAL::Simple_cartesian<double> Kernel;
typedef Kernel::Point_2 Point_2;
typedef Kernel::Line_2 Line_2;
typedef CGAL::Polygon_2<Kernel> Polygon_2;
typedef CGAL::Random_points_in_square_2<Point_2> Generator;
int main()
{
// build a random convex 20-gon p
Polygon_2 p;
CGAL::random_convex_set_2(20, std::back_inserter(p), Generator(1.0));
std::cout << p << std::endl;
// compute the minimal enclosing strip p_m of p
Line_2 p_m[2];
CGAL::min_strip_2(p.vertices_begin(), p.vertices_end(), p_m);
std::cout << p_m[0] << "\n" << p_m[1] << std::endl;
return 0;
}

`#include <CGAL/min_quadrilateral_2.h>`

Examples:
  Min_quadrilateral_2/minimum_enclosing_strip_2.cpp.

template<class ForwardIterator , class OutputIterator , class FT , class Traits >

OutputIterator CGAL::rectangular_p_center_2 | ( | ForwardIterator | f,
|  | ForwardIterator | l,
|  | OutputIterator | o,
|  | FT & | r,
|  | int | p,
|  | const Traits & | t = `Default_traits`
| ) |  |

Computes rectilinear \( p\)-centers of a planar point set, i.e. a set of \( p\) points such that the maximum minimal \( L_{\infty}\)-distance between both sets is minimized.

More formally the problem can be defined as follows.

Given a finite set \( \mathcal{P}\) of points, compute a point set \( \mathcal{C}\) with \( |\mathcal{C}| \le p\) such that the \( p\)-radius of \( \mathcal{P}\),

\[ rad_p(\mathcal{P}) := \max_{P \in \mathcal{P}} \min_{Q \in \mathcal{C}} || P - Q ||_\infty \]

is minimized. We can interpret \( \mathcal{C}\) as the best approximation (with respect to the given metric) for \( \mathcal{P}\) with at most \( p\) points.

computes rectilinear `p`-centers for the point set described by the range [`f`, `l`), sets `r` to the corresponding \( p\)-radius, writes the at most `p` center points to `o` and returns the past-the-end iterator of this sequence.

Precondition
  2 \( \le\) `p` \( \le\) 4.

The geometric types and operations to be used for the computation are specified by the traits class parameter `t`. This parameter can be omitted if `ForwardIterator` refers to a point type from the 2D-Kernel. In this case, a default traits class (`Rectangular_p_center_default_traits_2<K>`) is used.

Requires:

1. Either: (if no traits parameter is given) Value type of `ForwardIterator` is `CGAL::Point_2<K>` for some representation class `K` and `FT` is equivalent to `K::FT`,
2. Or: (if a traits parameter is specified) `Traits` is a model for `RectangularPCenterTraits_2`.
3. `OutputIterator` accepts the value type of `ForwardIterator` as value type.

See Also
  `RectangularPCenterTraits_2`
  `CGAL::Rectangular_p_center_default_traits_2<K>`
  `CGAL::sorted_matrix_search()`

Implementation

The runtime is linear for \( p \in \{2,\,3\}\) and \( \mathcal{O}(n \cdot \log n)\) for \( p = 4\) where \( n\) is the number of input points. These runtimes are worst case optimal. The \( 3\)-center algorithm uses a prune-and-search technique described in [9]. The \( 4\)-center implementation uses sorted matrix search [1], [2] and fast algorithms for piercing rectangles [13].

Example

The following code generates a random set of ten points and computes its two-centers.

File Rectangular_p_center_2/rectangular_p_center_2.cpp

#include <CGAL/Simple_cartesian.h>
#include <CGAL/point_generators_2.h>
#include <CGAL/rectangular_p_center_2.h>
#include <CGAL/IO/Ostream_iterator.h>
#include <CGAL/algorithm.h>
#include <iostream>
#include <algorithm>
#include <vector>
typedef double FT;
typedef CGAL::Simple_cartesian<FT> Kernel;
typedef Kernel::Point_2 Point;
typedef std::vector<Point> Cont;
typedef CGAL::Random_points_in_square_2<Point> Generator;
typedef CGAL::Ostream_iterator<Point,std::ostream> OIterator;
int main()
{
int n = 10;
int p = 2;
OIterator cout_ip(std::cout);
CGAL::set_pretty_mode(std::cout);
Cont points;
CGAL::cpp11::copy_n(Generator(1), n, std::back_inserter(points));
std::cout << "Generated Point Set:\n";
std::copy(points.begin(), points.end(), cout_ip);
FT p_radius;
std::cout << "\n\n" << p << "-centers:\n";
CGAL::rectangular_p_center_2(
points.begin(), points.end(), cout_ip, p_radius, 3);
std::cout << "\n\n" << p << "-radius = " << p_radius << std::endl;
return 0;
}

`#include <CGAL/rectangular_p_center_2.h>`

Examples:
  Rectangular_p_center_2/rectangular_p_center_2.cpp.