\( \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.5 - Optimal Distances
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Groups Pages
CGAL::Polytope_distance_d< Traits > Class Template Reference

#include <CGAL/Polytope_distance_d.h>

Definition

An object of the class Polytope_distance_d represents the (squared) distance between two convex polytopes, given as the convex hulls of two finite point sets in \( d\)-dimensional Euclidean space \( \E^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)=\infty\) if \( P\) or \( Q\) is empty.

Two inclusion-minimal 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{||p-q||}=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 non-convex 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.

Template Parameters
Traitsmust be a model for PolytopeDistanceDTraits.

We provide the models Polytope_distance_d_traits_2, Polytope_distance_d_traits_3, and Polytope_distance_d_traits_d using the two-, three-, and \( d\)-dimensional CGAL kernel, respectively.

See Also
CGAL::Polytope_distance_d_traits_2<K,ET,NT>
CGAL::Polytope_distance_d_traits_3<K,ET,NT>
CGAL::Polytope_distance_d_traits_d<K,ET,NT>
PolytopeDistanceDTraits

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 [2].

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.

Examples:
Polytope_distance_d/polytope_distance_d.cpp, and Polytope_distance_d/polytope_distance_d_fast_exact.cpp.

Related Functions

(Note that these are not member functions.)

std::ostream & operator<< (std::ostream &os, const Polytope_distance_d< Traits > &poly_dist)
 writes poly_dist to output stream os. More...
 
std::istream & operator>> (std::istream &is, Polytope_distance_d< Traits > poly_dist &)
 reads poly_dist from input stream is. More...
 

Types

typedef unspecified_type Point
 typedef to Traits::Point_d. More...
 
typedef unspecified_type FT
 typedef to Traits::FT. More...
 
typedef unspecified_type ET
 typedef to Traits::ET. More...
 
typedef unspecified_type Point_iterator
 non-mutable model of the STL concept RandomAccessIterator with value type Point. More...
 
typedef unspecified_type Support_point_iterator
 non-mutable model of the STL concept RandomAccessIterator with value type Point. More...
 
typedef unspecified_type Support_point_index_iterator
 non-mutable model of the STL concept RandomAccessIterator with value type int. More...
 
typedef unspecified_type Coordinate_iterator
 non-mutable model of the STL concept RandomAccessIterator with value type ET. More...
 

Creation

 Polytope_distance_d (const Traits &traits=Traits(), int verbose=0, std::ostream &stream=std::cout)
 initializes poly_dist to \( pd(\emptyset, \emptyset)\).
 
template<class InputIterator1 , class InputIterator2 >
 Polytope_distance_d (InputIterator1 p_first, InputIterator1 p_last, InputIterator2 q_first, InputIterator2 q_last, const 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. More...
 

Access Functions

int ambient_dimension () const
 returns the dimension of the points in \( P\) and \( Q\). More...
 
int number_of_points () const
 returns the number of all points of poly_dist, i.e. \( |P|+|Q|\).
 
int number_of_points_p () const
 returns the number of points in \( P\).
 
int number_of_points_q () const
 returns the number of points in \( Q\).
 
int number_of_support_points () const
 returns the number of support points of poly_dist, i.e. \( |S_P|+|S_Q|\).
 
int number_of_support_points_p () const
 returns the number of support points in \( S_P\).
 
int number_of_support_points_q () const
 returns the number of support points in \( S_Q\).
 
Point_iterator points_p_begin () const
 returns an iterator referring to the first point in \( P\).
 
Point_iterator points_p_end () const
 returns the corresponding past-the-end iterator.
 
Point_iterator points_q_begin () const
 returns an iterator referring to the first point in \( Q\).
 
Point_iterator points_q_end () const
 returns the corresponding past-the-end iterator.
 
Support_point_iterator support_points_p_begin () const
 returns an iterator referring to the first support point in \( S_P\).
 
Support_point_iterator support_points_p_end () const
 returns the corresponding past-the-end iterator.
 
Support_point_iterator support_points_q_begin () const
 returns an iterator referring to the first support point in \( S_Q\).
 
Support_point_iterator support_points_q_end () const
 returns the corresponding past-the-end iterator.
 
Support_point_index_iterator support_points_p_indices_begin () const
 returns an iterator referring to the index of the first support point in \( P\).
 
Support_point_index_iterator support_points_p_indices_end () const
 returns the corresponding past-the-end iterator.
 
Support_point_index_iterator support_points_q_indices_begin () const
 returns an iterator referring to the index of the first support point in \( Q\).
 
Support_point_index_iterator support_points_q_indices_end () const
 returns the corresponding past-the-end iterator.
 
Point realizing_point_p () const
 returns the realizing point of \( P\). More...
 
Point realizing_point_q () const
 returns the realizing point of \( Q\). More...
 
FT squared_distance () const
 returns the squared distance of poly_dist, i.e. \( (pd(P,Q))^2\). More...
 
Coordinate_iterator realizing_point_p_coordinates_begin () const
 returns an iterator referring to the first coordinate of the realizing point of \( P\). More...
 
Coordinate_iterator realizing_point_p_coordinates_end () const
 returns the corresponding past-the-end iterator.
 
Coordinate_iterator realizing_point_q_coordinates_begin () const
 returns an iterator referring to the first coordinate of the realizing point of \( Q\). More...
 
Coordinate_iterator realizing_point_q_coordinates_end () const
 returns the corresponding past-the-end iterator.
 
ET squared_distance_numerator () const
 returns the numerator of the squared distance of poly_dist.
 
ET squared_distance_denominator () const
 returns the denominator of the squared distance of poly_dist.
 

Predicates

bool is_finite () const
 returns true, if \( pd(P,Q)\) is finite, i.e. none of the two polytopes is empty.
 
bool is_zero () const
 returns true, if \( pd(P,Q)\) is zero, i.e. the two polytopes intersect (this implies degeneracy).
 
bool is_degenerate () const
 returns true, iff \( pd(P,Q)\) is degenerate, i.e. \( pd(P,Q)\) is not finite.
 

Modifiers

void clear ()
 resets poly_dist to \( pd(\emptyset, \emptyset)\).
 
template<class InputIterator1 , class InputIterator2 >
void 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. More...
 
template<class InputIterator >
void 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). More...
 
template<class InputIterator >
void 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). More...
 
void insert_p (const Point &p)
 inserts p into \( P\). More...
 
void insert_q (const Point &q)
 inserts q into \( Q\). More...
 
template<class InputIterator1 , class InputIterator2 >
void 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. More...
 
template<class InputIterator >
void 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). More...
 
template<class InputIterator >
void 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). More...
 

Validity Check

bool is_valid (bool verbose=false, int level=0) const
 returns true, iff poly_dist is valid. More...
 

Miscellaneous

const Traits & traits () const
 returns a const reference to the traits class object.
 

Member Typedef Documentation

template<typename Traits >
typedef unspecified_type CGAL::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.

template<typename Traits >
typedef unspecified_type CGAL::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).

template<typename Traits >
typedef unspecified_type CGAL::Polytope_distance_d< Traits >::FT

typedef to Traits::FT.

Number type used to return the squared distance between the two polytopes.

template<typename Traits >
typedef unspecified_type CGAL::Polytope_distance_d< Traits >::Point

typedef to Traits::Point_d.

Point type used to represent the input points.

template<typename Traits >
typedef unspecified_type CGAL::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.

template<typename Traits >
typedef unspecified_type CGAL::Polytope_distance_d< Traits >::Support_point_index_iterator

non-mutable 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).

template<typename Traits >
typedef unspecified_type CGAL::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.

Constructor & Destructor Documentation

template<typename Traits >
template<class InputIterator1 , class InputIterator2 >
CGAL::Polytope_distance_d< Traits >::Polytope_distance_d ( InputIterator1  p_first,
InputIterator1  p_last,
InputIterator2  q_first,
InputIterator2  q_last,
const 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.

Requires:
The value type of InputIterator1 and InputIterator2 is Point.
Precondition
All points have the same dimension.
Attention
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.

Member Function Documentation

template<typename Traits >
int CGAL::Polytope_distance_d< Traits >::ambient_dimension ( ) const

returns the dimension of the points in \( P\) and \( Q\).

If poly_dist is \( pd(\emptyset, \emptyset)\), the ambient dimension is \( -1\).

template<typename Traits >
template<class InputIterator1 , class InputIterator2 >
void CGAL::Polytope_distance_d< Traits >::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.

Requires:
The value type of InputIterator1 and InputIterator2 is Point.
Precondition
All points have the same dimension. If poly_dist is not \( pd(\emptyset, \emptyset)\), this dimension must be equal to poly_dist.ambient_dimension().
template<typename Traits >
void CGAL::Polytope_distance_d< Traits >::insert_p ( const Point p)

inserts p into \( P\).

Precondition
The dimension of p equals poly_dist.ambient_dimension() if poly_dist is not \( pd(\emptyset, \emptyset)\).
template<typename Traits >
template<class InputIterator >
void CGAL::Polytope_distance_d< Traits >::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).

Requires:
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<typename Traits >
void CGAL::Polytope_distance_d< Traits >::insert_q ( const Point q)

inserts q into \( Q\).

Precondition
The dimension of q equals poly_dist.ambient_dimension() if poly_dist is not \( pd(\emptyset, \emptyset)\).
template<typename Traits >
template<class InputIterator >
void CGAL::Polytope_distance_d< Traits >::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).

Requires:
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<typename Traits >
bool CGAL::Polytope_distance_d< Traits >::is_valid ( bool  verbose = false,
int  level = 0 
) const

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.

An object poly_dist is valid, iff \( ldots\)

  • 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.
template<typename Traits >
Point CGAL::Polytope_distance_d< Traits >::realizing_point_p ( ) const

returns the realizing point of \( P\).

Requires:
An implicit conversion from ET to RT is available.
Precondition
\( pd(P,Q)\) is finite.
template<typename Traits >
Coordinate_iterator CGAL::Polytope_distance_d< Traits >::realizing_point_p_coordinates_begin ( ) const

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.
template<typename Traits >
Point CGAL::Polytope_distance_d< Traits >::realizing_point_q ( ) const

returns the realizing point of \( Q\).

Requires:
An implicit conversion from ET to RT is available.
Precondition
\( pd(P,Q)\) is finite.
template<typename Traits >
Coordinate_iterator CGAL::Polytope_distance_d< Traits >::realizing_point_q_coordinates_begin ( ) const

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.
template<typename Traits >
template<class InputIterator1 , class InputIterator2 >
void CGAL::Polytope_distance_d< Traits >::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.

Requires:
The value type of InputIterator1 and InputIterator2 is Point.
Precondition
All points have the same dimension.
template<typename Traits >
template<class InputIterator >
void CGAL::Polytope_distance_d< Traits >::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).

Requires:
The value type of InputIterator is Point.
Precondition
All points in \( P\) have dimension poly_dist.ambient_dimension() if \( Q\) is not empty.
template<typename Traits >
template<class InputIterator >
void CGAL::Polytope_distance_d< Traits >::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).

Requires:
The value type of InputIterator is Point.
Precondition
All points in \( Q\) have dimension poly_dist.ambient_dimension() if \( P\) is not empty.
template<typename Traits >
FT CGAL::Polytope_distance_d< Traits >::squared_distance ( ) const

returns the squared distance of poly_dist, i.e. \( (pd(P,Q))^2\).

Requires:
An implicit conversion from ET to RT is available.
Precondition
\( pd(P,Q)\) is finite.

Friends And Related Function Documentation

template<typename Traits >
std::ostream & operator<< ( std::ostream &  os,
const Polytope_distance_d< Traits > &  poly_dist 
)
related

writes poly_dist to output stream os.

Requires:
The output operator is defined for Point_d.
template<typename Traits >
std::istream & operator>> ( std::istream &  is,
Polytope_distance_d< Traits > poly_dist &   
)
related

reads poly_dist from input stream is.

Requires:
The input operator is defined for Point_d.