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>
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.
 
typedef to Traits::Point_d.
Point type used to represent the input points.
 
 
typedef to Traits::FT.
Number type used to return the squared distance
between the two polytopes.
 
 
typedef to Traits::ET.
Number type used to do the exact computations in the underlying
solver for quadratic programs (cf. Implementation).
 
 
nonmutable model of the STL concept RandomAccessIterator
with value type Point. Used to access the points
of the two polytopes.
 
 
nonmutable model of the STL concept RandomAccessIterator
with value type Point. Used to access the support points.
 
 
nonmutable model of the STL concept RandomAccessIterator
with value type int. Used to access the indices of the
support points in the provided input order (starting from 0
in both point sets).
 
 
nonmutable model of the STL concept RandomAccessIterator
with value type ET. Used to access the coordinates of
the realizing points.

 
initializes poly_dist to $$pd(Ø$$,Ø$$).
 
 
 
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.

advanced 
advanced 

 returns the dimension of the points in $$P and $$Q. If poly_dist is $$pd(Ø$$,Ø$$), the ambient dimension is $$1. 

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

 returns the number of points in $$P. 

 returns the number of points in $$Q. 

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

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

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

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

 returns the corresponding pasttheend iterator. 

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

 returns the corresponding pasttheend iterator. 

 
returns an iterator referring to the first coordinate of the
realizing point of $$P.
 

 
returns the corresponding pasttheend iterator. 

 
returns an iterator referring to the first coordinate of the
realizing point of $$Q.
 

 
returns the corresponding pasttheend iterator.  

 
returns the numerator of the squared distance of poly_dist.  

 
returns the denominator of the squared distance of poly_dist. 

 returns true, if $$pd(P,Q) is finite, i.e. none of the two polytopes is empty. 

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

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

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

 
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.
 
 

 
sets poly_dist to $$pd(P,Q) with $$P being the set of points
in the range [p_first,p_last) ($$Q remains unchanged).
 
 

 
sets poly_dist to $$pd(P,Q) with $$Q being the set of points
in the range [q_first,q_last) ($$P remains unchanged).
 


inserts p into $$P.
 


inserts q into $$Q.
 
 

 
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.
 
 

 
inserts the points in the range [p_first,p_last) into
$$P and recomputes the (squared) distance ($$Q remains unchanged).
 
 

 
inserts the points in the range [q_first,q_last) into
$$Q and recomputes the (squared) distance ($$P remains unchanged).

An object poly_dist is valid, iff ...

 
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. 

 returns a const reference to the traits class object. 


writes poly_dist to output stream os.
 


reads poly_dist from input stream is.

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