An inclusion-minimal subset of with is called a support set, the points in are the support points. A support set has size at most , and all its points lie on the boundary of . In general, neither the support set nor its size are necessarily unique.
The underlying algorithm can cope with all kinds of input, e.g. may be empty or points may occur more than once. The algorithm computes a support set which remains fixed until the next insert or clear operation.
Note: In this release correct results are only guaranteed if exact arithmetic is used.
#include <CGAL/Min_sphere_d.h>
The template parameter Traits is a traits class that defines the interface between the optimisation algorithm and the point class it uses.
We provide ready-to-use traits class implementations for 2D, 3D and dD CGAL points, see Section below.
|
|
| Representation type. |
| ||
| Point type. | |
|
| Data accessor type. |
The following defines iterator types for traversing the points resp. support points of the smallest enclosing sphere. Such iterators are non-mutable and their value type is Point. The iterator category is given in parentheses.
| |
(bidirectional).
| |
| |
(bidirectional).
|
| |
creates a variable of type CGAL_Min_sphere_d<Traits>
and initializes it to Ø.
|
A CGAL_Min_sphere_d<Traits> object can be created from an arbitrary point set , specified by an iterator range. All points must have the same dimension (see Section how the dimension of a point is accessed).
| |||
| |||
creates a variable min_sphere of type
CGAL_Min_sphere_d<Traits>. It is initialized to
with being the set of points in
the range [first,last).
Precondition: The value type of first and last is Point, and all points have the same dimension.
|
Note: In case a compiler does not support member templates yet, we provide specialized constructors instead. In the current release there are constructors for C arrays (using pointers as iterators), for the STL sequence containers vector<Point> and list<Point> and for the STL input stream iterator istream_iterator<Point>.
|
| |
returns the number of points of min_sphere, i.e. . | ||
|
| |
returns the number of support points of min_sphere, i.e. . | ||
|
| |
returns an iterator referring to the first point of min_sphere. | ||
|
| |
returns the corresponding past-the-end iterator. | ||
| ||
| ||
returns an iterator referring to the first support point of min_sphere. | ||
| ||
| ||
returns the corresponding past-the-end iterator. | ||
|
| |
returns the dimension of the points in . If min_sphere is empty, the ambient dimension is . | ||
|
| |
returns the center of min_sphere.
Precondition: min_sphere is not empty. | ||
|
| |
returns the squared radius of min_sphere.
Precondition: min_sphere is not empty. |
|
| |
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_sphere, resp.
Precondition: if min_sphere is not empty, the dimension of equals ambient_dim(). | ||
|
| |
returns true, iff p lies properly inside
min_sphere. Precondition: if min_sphere is not empty, the dimension of equals ambient_dim(). | ||
|
| |
returns true, iff p lies on the boundary of
min_sphere. Precondition: if min_sphere is not empty, the dimension of equals ambient_dim(). | ||
|
| |
returns true, iff p lies properly outside of
min_sphere. Precondition: if min_sphere is not empty, the dimension of equals ambient_dim(). | ||
|
| |
returns true, iff min_sphere is empty (this implies degeneracy). | ||
|
| |
returns true, iff min_sphere is degenerate, i.e. if min_sphere is empty or equal to a single point, equivalently if the number of support points is less than 2. |
|
| |||
resets min_sphere to Ø. | ||||
| ||||
|
| |||
sets min_sphere to the , where
is the set of points in the range [first,
last). Precondition: The value type of first and last is Point, and all points have the same dimension. | ||||
|
| |||
inserts p into min_sphere. If p lies inside
the current sphere, this is a constant-time operation, otherwise it
might take longer, but in any case substantially less than
recomputing the smallest enclosing sphere from scratch.
Precondition: The dimension of p equals ambient_dim() if min_sphere is not empty. | ||||
| ||||
|
| |||
inserts the points in the range [first,last) into
min_sphere and recomputes the smallest enclosing sphere, by
calling insert for all points in the range.
Precondition: The value type of first and last is Point, and all points have the same dimension. If min_sphere is not empty, this dimension must be equal to ambient_dim(). |
When applied to an empty min_sphere, set( first, last) and insert( first, last) produce the same result. However, the latter method is usually much slower, because it processes the points on-line, while the set method takes advantage of knowing the whole point set in advance.
Note: In case a compiler does not support member templates yet, we provide specialized set and insert functions instead. In the current release there are functions for C arrays (using pointers as iterators), for the STL sequence containers vector<Point> and list<Point> and for the STL input stream iterator istream_iterator<Point>.
An object min_sphere is valid, iff
Note: Under inexact arithmetic, the result of the validation is not reliable, because the checker itself can suffer from numerical problems.
|
| |||
returns true, iff min_sphere 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. |
|
| |
returns a const reference to the traits class object. |
#include<iostream.h> #include<stdlib.h> #include<CGAL/Cartesian.h> #include<CGAL/Min_sphere_d.h> typedef CGAL_Cartesian<double> R; typedef CGAL_Min_sphere_d_traits_d<R> Traits; typedef CGAL_Min_sphere_d<Traits> Min_sphere; typedef CGAL_Point_d<R> Point; const int n = 10; // number of points const int d = 5; // dimension of points int main () { Point P[n]; // n points double coord[d]; // d coordinates for (int i=0; i<n; ++i) { for (int j=0; j<d; ++j) coord[j] = drand48(); P[i] = Point(d, coord, coord+d); // random point } Min_sphere ms (P, P+n); // smallest enclosing sphere CGAL_set_pretty_mode (cout); cout << ms; // output the sphere return (0); }