#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

Traits must 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
	)

Requires:: The output operator is defined for Point_d.

template<typename Traits >

std::istream & operator>>	(	std::istream &	is,
		Polytope_distance_d< Traits > poly_dist &
	)

Requires:: The input operator is defined for Point_d.

Definition

Related Functions

Types

Creation

Access Functions

Predicates

Modifiers

Validity Check

Miscellaneous

Member Typedef Documentation

Constructor & Destructor Documentation

Member Function Documentation

Friends And Related Function Documentation