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 $$ddimensional Euclidean space $$ _{d}. For point sets $$P and $$Q
we denote by $$pd(P,Q) the distance between the convex hulls of $$P and
$$Q. Note that $$pd(P,Q) can be
degenerate,
i.e. $$pd(P,Q)= if $$P or $$Q is empty.
Two inclusionminimal subsets $$S_{P} of $$P and $$S_{Q} of $$Q with
$$pd(S_{P},S_{Q})=pd(P,Q) are called pair of support
sets, the
points in $$S_{P} and $$S_{Q} are the support points. A pair of support
sets has size at most $$d+2 (by size we mean $$S_{P}+S_{Q}). The distance
between the two polytopes is realized by a pair of points $$p and
$$q lying in the convex hull of $$S_{P} and $$S_{Q}, repectively,
i.e. $$sqrt(pq)=pd(P,Q). 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. $$P and $$Q
may be in nonconvex position or points may occur more than once. The
algorithm computes a pair of support sets $$S_{P} and $$S_{Q} with realizing
points $$p and $$q 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 $$ddimensional 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


nonmutable 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


nonmutable model of the STL concept RandomAccessIterator
with value type Point. Used to access the support points.


Polytope_distance_d<Traits>::Coordinate_iterator


nonmutable 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 $$pd(Ø$$,Ø$$).


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 $$pd(P,Q) with $$P and $$Q 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
$$1,
$$2, or
$$3 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 $$P and $$Q.
If poly_dist is $$pd(Ø$$,Ø$$), the ambient dimension is $$1.

int

poly_dist.number_of_points ()

 
returns the number of all points of poly_dist, i.e. $$P+Q.

int

poly_dist.number_of_points_p ()

 
returns the number of points in $$P.

int

poly_dist.number_of_points_q ()

 
returns the number of points in $$Q.

int

poly_dist.number_of_support_points ()

 
returns the number of support points of poly_dist, i.e. $$S_{P}+S_{Q}.

int

poly_dist.number_of_support_points_p ()

 
returns the number of support points in $$S_{P}.

int

poly_dist.number_of_support_points_q ()

 
returns the number of support points in $$S_{Q}.

Point_iterator

poly_dist.points_p_begin ()

 
returns an iterator referring to the first point in $$P.

Point_iterator

poly_dist.points_p_end ()

 
returns the corresponding pasttheend iterator.

Point_iterator

poly_dist.points_q_begin ()

 
returns an iterator referring to the first point in $$Q.

Point_iterator

poly_dist.points_q_end ()

 
returns the corresponding pasttheend iterator.

Support_point_iterator


poly_dist.support_points_p_begin ()

 
returns an iterator referring to the first support point in $$S_{P}.

Support_point_iterator


poly_dist.support_points_p_end ()

 
returns the corresponding pasttheend iterator.

Support_point_iterator


poly_dist.support_points_q_begin ()

 
returns an iterator referring to the first support point in $$S_{Q}.

Support_point_iterator


poly_dist.support_points_q_end ()

 
returns the corresponding pasttheend iterator.


Point

poly_dist.realizing_point_p ()

 
returns the realizing point of $$P.
Requirement: An implicit conversion from ET to RT is
available.
Precondition: $$pd(P,Q) is finite.


Point

poly_dist.realizing_point_q ()

 
returns the realizing point of $$Q.
Requirement: An implicit conversion from ET to RT is
available.
Precondition: $$pd(P,Q) is finite.


FT

poly_dist.squared_distance ()

 
returns the squared distance of poly_dist, i.e. $$(pd(P,Q))^{2}.
Requirement: An implicit conversion from ET to RT is
available.
Precondition: $$pd(P,Q) is finite.

Coordinate_iterator


poly_dist.realizing_point_p_coordinates_begin ()

 
returns an iterator referring to the first coordinate of the
realizing point of $$P.
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.

Coordinate_iterator


poly_dist.realizing_point_p_coordinates_end ()

 
returns the corresponding pasttheend iterator.

Coordinate_iterator


poly_dist.realizing_point_q_coordinates_begin ()

 
returns an iterator referring to the first coordinate of the
realizing point of $$Q.
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.

Coordinate_iterator


poly_dist.realizing_point_q_coordinates_end ()

 
returns the corresponding pasttheend 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 $$pd(P,Q) is finite,
i.e. none of the two polytopes is empty.


bool

poly_dist.is_zero ()

 
returns true, if $$pd(P,Q) is zero,
i.e. the two polytopes intersect (this implies degeneracy).


bool

poly_dist.is_degenerate ()

 
returns true, iff $$pd(P,Q) is degenerate,
i.e. $$pd(P,Q) is not finite.

Modifiers
void

poly_dist.clear ()

resets poly_dist to $$pd(Ø$$,Ø$$).


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 $$pd(P,Q) with $$P and $$Q 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 $$pd(P,Q) with $$P being the set of points
in the range [p_first,p_last) ($$Q remains unchanged).
Requirement: The value type of InputIterator is Point.
Precondition: All points in $$P have dimension
poly_dist.ambient_dimension() if $$Q is not empty.


template < class InputIterator >

void

poly_dist.set_q ( 
InputIterator q_first,
InputIterator q_last) 

 
sets poly_dist to $$pd(P,Q) with $$Q being the set of points
in the range [q_first,q_last) ($$P remains unchanged).
Requirement: The value type of InputIterator is Point.
Precondition: All points in $$Q have dimension
poly_dist.ambient_dimension() if $$P is not empty.


void

poly_dist.insert_p ( Point p)

 
inserts p into $$P.
Precondition: The dimension of p equals
poly_dist.ambient_dimension() if poly_dist is not $$pd(Ø$$,Ø$$).


void

poly_dist.insert_q ( Point q)

 
inserts q into $$Q.
Precondition: The dimension of q equals
poly_dist.ambient_dimension() if poly_dist is not $$pd(Ø$$,Ø$$).


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 $$P and $$Q, 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 $$pd(Ø$$,Ø$$), 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
$$P and recomputes the (squared) distance ($$Q 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
$$Q and recomputes the (squared) distance ($$P 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 $$P,
 poly_dist is the smallest sphere containing its support set $$S, and
 $$S 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.