CGAL::Polytope_distance_d<Traits>
Definition
An object of the class Polytope_distance_d<Traits> represents the (squared) distance
between two convex polytopes, given as the convex hulls of two finite point
sets in -dimensional Euclidean space . For point sets and
we denote by the distance between the convex hulls of and
. Note that can be
degenerate,
i.e. if or is empty.
Two inclusion-minimal subsets of and of with
are called pair of support
sets, the
points in and are the support points. A pair of support
sets has size at most (by size we mean ). The distance
between the two polytopes is realized by a pair of points and
lying in the convex hull of and , repectively,
i.e. . In general, neither the support sets nor the
realizing points are necessarily unique.
The underlying algorithm can cope with all kinds of input, e.g. and
may be in non-convex position or points may occur more than once. The
algorithm computes a pair of support sets and with realizing
points and which remain fixed until the next set, insert, or clear
operation.
#include <CGAL/Polytope_distance_d.h>
Requirements
The template parameter Traits is 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 -dimensional CGAL kernel, respectively.
Types
Polytope_distance_d<Traits>::Point
|
|
typedef to Traits::Point_d.
Point type used to represent the input points.
|
|
Polytope_distance_d<Traits>::FT
|
|
typedef to Traits::FT.
Number type used to return the squared distance
between the two polytopes.
|
|
Polytope_distance_d<Traits>::ET
|
|
typedef to Traits::ET.
Number type used to do the exact computations in the underlying
solver for quadratic programs (cf. Implementation).
|
|
Polytope_distance_d<Traits>::Point_iterator
|
|
non-mutable model of the STL concept RandomAccessIterator
with value type Point. Used to access the points
of the two polytopes.
|
|
Polytope_distance_d<Traits>::Support_point_iterator
|
|
non-mutable model of the STL concept RandomAccessIterator
with value type Point. Used to access the support points.
|
|
Polytope_distance_d<Traits>::Coordinate_iterator
|
|
non-mutable model of the STL concept RandomAccessIterator
with value type ET. Used to access the coordinates of
the realizing points.
|
Creation
Polytope_distance_d<Traits> poly_dist ( |
Traits traits = Traits(),
int verbose = 0,
std::ostream& stream = std::cout); |
|
|
initializes poly_dist to ØØ.
|
|
template < class InputIterator1, class InputIterator2 >
|
Polytope_distance_d<Traits> poly_dist ( |
InputIterator1 p_first,
InputIterator1 p_last,
InputIterator2 q_first,
InputIterator2 q_last,
Traits traits = Traits(),
int verbose = 0,
std::ostream& stream = std::cout); |
|
|
initializes poly_dist to with and being the
sets of points in the range [p_first,p_last) and
[q_first,q_last), respectively.
Requirement: The value type of InputIterator1 and
InputIterator2 is Point.
Precondition: All points have the same dimension.
|
|
advanced
|
|
If
verbose is set to
,
, or
then some, more, or full
verbose output of the underlying solver for quadratic programs is
written to
stream, resp.
|
advanced
|
|
Access Functions
int
|
poly_dist.ambient_dimension ()
|
| |
returns the dimension of the points in and .
If poly_dist is ØØ, the ambient dimension is .
|
int
|
poly_dist.number_of_points ()
|
| |
returns the number of all points of poly_dist, i.e. .
|
int
|
poly_dist.number_of_points_p ()
|
| |
returns the number of points in .
|
int
|
poly_dist.number_of_points_q ()
|
| |
returns the number of points in .
|
int
|
poly_dist.number_of_support_points ()
|
| |
returns the number of support points of poly_dist, i.e. .
|
int
|
poly_dist.number_of_support_points_p ()
|
| |
returns the number of support points in .
|
int
|
poly_dist.number_of_support_points_q ()
|
| |
returns the number of support points in .
|
Point_iterator
|
poly_dist.points_p_begin ()
|
| |
returns an iterator referring to the first point in .
|
Point_iterator
|
poly_dist.points_p_end ()
|
| |
returns the corresponding past-the-end iterator.
|
Point_iterator
|
poly_dist.points_q_begin ()
|
| |
returns an iterator referring to the first point in .
|
Point_iterator
|
poly_dist.points_q_end ()
|
| |
returns the corresponding past-the-end iterator.
|
Support_point_iterator
|
|
poly_dist.support_points_p_begin ()
|
| |
returns an iterator referring to the first support point in .
|
Support_point_iterator
|
|
poly_dist.support_points_p_end ()
|
| |
returns the corresponding past-the-end iterator.
|
Support_point_iterator
|
|
poly_dist.support_points_q_begin ()
|
| |
returns an iterator referring to the first support point in .
|
Support_point_iterator
|
|
poly_dist.support_points_q_end ()
|
| |
returns the corresponding past-the-end iterator.
|
|
Point
|
poly_dist.realizing_point_p ()
|
| |
returns the realizing point of .
Requirement: An implicit conversion from ET to RT is
available.
Precondition: is finite.
|
|
Point
|
poly_dist.realizing_point_q ()
|
| |
returns the realizing point of .
Requirement: An implicit conversion from ET to RT is
available.
Precondition: is finite.
|
|
FT
|
poly_dist.squared_distance ()
|
| |
returns the squared distance of poly_dist, i.e. .
Requirement: An implicit conversion from ET to RT is
available.
Precondition: is finite.
|
Coordinate_iterator
|
|
poly_dist.realizing_point_p_coordinates_begin ()
|
| |
returns an iterator referring to the first coordinate of the
realizing point of .
Note: The coordinates have a rational
representation, i.e. the first elements of the iterator
range are the numerators and the -st element is the
common denominator.
|
Coordinate_iterator
|
|
poly_dist.realizing_point_p_coordinates_end ()
|
| |
returns the corresponding past-the-end iterator.
|
Coordinate_iterator
|
|
poly_dist.realizing_point_q_coordinates_begin ()
|
| |
returns an iterator referring to the first coordinate of the
realizing point of .
Note: The coordinates have a rational
representation, i.e. the first elements of the iterator
range are the numerators and the -st element is the
common denominator.
|
Coordinate_iterator
|
|
poly_dist.realizing_point_q_coordinates_end ()
|
| |
returns the corresponding past-the-end iterator.
|
|
ET
|
poly_dist.squared_distance_numerator ()
|
| |
returns the numerator of the squared distance of poly_dist.
|
|
ET
|
poly_dist.squared_distance_denominator ()
|
| |
returns the denominator of the squared distance of poly_dist.
|
Predicates
bool
|
poly_dist.is_finite ()
|
| |
returns true, if is finite,
i.e. none of the two polytopes is empty.
|
|
bool
|
poly_dist.is_zero ()
|
| |
returns true, if is zero,
i.e. the two polytopes intersect (this implies degeneracy).
|
|
bool
|
poly_dist.is_degenerate ()
|
| |
returns true, iff is degenerate,
i.e. is not finite.
|
Modifiers
void
|
poly_dist.clear ()
|
resets poly_dist to ØØ.
|
|
template < class InputIterator1, class InputIterator2 >
|
void
|
poly_dist.set ( |
InputIterator1 p_first,
InputIterator1 p_last,
InputIterator2 q_first,
InputIterator2 q_last) |
|
| |
sets poly_dist to with and being the sets of
points in the ranges [p_first,p_last) and
[q_first,q_last), respectively.
Requirement: The value type of InputIterator1 and
InputIterator2 is Point.
Precondition: All points have the same dimension.
|
|
template < class InputIterator >
|
void
|
poly_dist.set_p ( |
InputIterator p_first,
InputIterator p_last) |
|
| |
sets poly_dist to with being the set of points
in the range [p_first,p_last) ( remains unchanged).
Requirement: The value type of InputIterator is Point.
Precondition: All points in have dimension
poly_dist.ambient_dimension() if is not empty.
|
|
template < class InputIterator >
|
void
|
poly_dist.set_q ( |
InputIterator q_first,
InputIterator q_last) |
|
| |
sets poly_dist to with being the set of points
in the range [q_first,q_last) ( remains unchanged).
Requirement: The value type of InputIterator is Point.
Precondition: All points in have dimension
poly_dist.ambient_dimension() if is not empty.
|
|
void
|
poly_dist.insert_p ( Point p)
|
| |
inserts p into .
Precondition: The dimension of p equals
poly_dist.ambient_dimension() if poly_dist is not ØØ.
|
|
void
|
poly_dist.insert_q ( Point q)
|
| |
inserts q into .
Precondition: The dimension of q equals
poly_dist.ambient_dimension() if poly_dist is not ØØ.
|
|
template < class InputIterator1, class InputIterator2 >
|
void
|
poly_dist.insert ( |
InputIterator1 p_first,
InputIterator1 p_last,
InputIterator2 q_first,
InputIterator2 q_last) |
|
| |
inserts the points in the range [p_first,p_last)
and [q_first,q_last) into and , respectively,
and recomputes the (squared) distance.
Requirement: The value type of InputIterator1 and
InputIterator2 is Point.
Precondition: All points have the same dimension.
If poly_dist is not ØØ, this dimension must be equal to
poly_dist.ambient_dimension().
|
|
template < class InputIterator >
|
void
|
poly_dist.insert_p ( |
InputIterator p_first,
InputIterator p_last) |
|
| |
inserts the points in the range [p_first,p_last) into
and recomputes the (squared) distance ( remains unchanged).
Requirement: The value type of InputIterator is Point.
Precondition: All points have the same dimension.
If poly_dist is not empty, this dimension must be equal to
poly_dist.ambient_dimension().
|
|
template < class InputIterator >
|
void
|
poly_dist.insert_q ( |
InputIterator q_first,
InputIterator q_last) |
|
| |
inserts the points in the range [q_first,q_last) into
and recomputes the (squared) distance ( remains unchanged).
Requirement: The value type of InputIterator is Point.
Precondition: All points have the same dimension.
If poly_dist is not empty, this dimension must be equal to
poly_dist.ambient_dimension().
|
Validity Check
An object poly_dist is valid, iff
...
- poly_dist contains all points of its defining set ,
- poly_dist is the smallest sphere containing its support set , and
- is minimal, i.e. no support point is redundant.
bool
|
poly_dist.is_valid ( |
bool verbose = false,
int level = 0) |
|
| |
returns true, iff poly_dist 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.
|
Miscellaneous
const Traits&
|
poly_dist.traits ()
|
| |
returns a const reference to the traits class object.
|
I/O
std::ostream&
|
std::ostream& os << poly_dist
|
| |
writes poly_dist to output stream os.
Requirement: The output operator is defined for Point_d.
|
|
std::istream&
|
std::istream& is >> poly_dist&
|
| |
reads poly_dist from input stream is.
Requirement: The input operator is defined for Point_d.
|
See Also
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 distance between two convex polytopes given as
the convex hulls of two finite point sets can be formulated as an
optimization problem with linear constraints and a convex quadratic
objective function. The solution is obtained using our exact solver
for quadratic programs [GS00].
The creation time is almost always linear in the number of points. Access
functions and predicates take constant time, inserting a point might take
up to linear time. The clear operation and the check for validity each
take linear time.