Polytope_distance

Navigation: Up Table of Contents Package Overview Bibliography Index Title Acknowledging CGAL

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 d-dimensional 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 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. √||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.

#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 d-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>::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).

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

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.

Access Functions

int	poly_dist.ambient_dimension () const
		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 () const
		returns the number of all points of poly_dist, i.e. \|P\|+\|Q\|.
int	poly_dist.number_of_points_p () const
		returns the number of points in P.
int	poly_dist.number_of_points_q () const
		returns the number of points in Q.

int	poly_dist.number_of_support_points () const
		returns the number of support points of poly_dist, i.e. \|S_P\|+\|S_Q\|.
int	poly_dist.number_of_support_points_p () const
		returns the number of support points in S_P.
int	poly_dist.number_of_support_points_q () const
		returns the number of support points in S_Q.

Point_iterator	poly_dist.points_p_begin () const	returns an iterator referring to the first point in P.
Point_iterator	poly_dist.points_p_end () const	returns the corresponding past-the-end iterator.

Point_iterator	poly_dist.points_q_begin () const	returns an iterator referring to the first point in Q.
Point_iterator	poly_dist.points_q_end () const	returns the corresponding past-the-end iterator.

Support_point_iterator	poly_dist.support_points_p_begin () const
		returns an iterator referring to the first support point in S_P.
Support_point_iterator	poly_dist.support_points_p_end () const
		returns the corresponding past-the-end iterator.

Support_point_iterator	poly_dist.support_points_q_begin () const
		returns an iterator referring to the first support point in S_Q.
Support_point_iterator	poly_dist.support_points_q_end () const
		returns the corresponding past-the-end iterator.

Support_point_index_iterator	poly_dist.support_points_p_indices_begin () const
		returns an iterator referring to the index of the first support point in P.
Support_point_index_iterator	poly_dist.support_points_p_indices_end () const
		returns the corresponding past-the-end iterator.

Support_point_index_iterator

poly_dist.support_points_q_indices_begin () const

returns an iterator referring to the index of the first support point in Q.

Support_point_index_iterator

poly_dist.support_points_q_indices_end () const

returns the corresponding past-the-end iterator.

Point

poly_dist.realizing_point_p () const

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 () const

returns the realizing point of Q.

Requirement:

An implicit conversion from ET to RT is available.

Precondition:

pd(P,Q) is finite.

poly_dist.squared_distance () const

returns the squared distance of poly_dist, i.e. (pd(P,Q))².

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

Coordinate_iterator

poly_dist.realizing_point_p_coordinates_end () const

returns the corresponding past-the-end iterator.

Coordinate_iterator

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

Coordinate_iterator

poly_dist.realizing_point_q_coordinates_end () const

returns the corresponding past-the-end iterator.

poly_dist.squared_distance_numerator () const

returns the numerator of the squared distance of poly_dist.

poly_dist.squared_distance_denominator () const

returns the denominator of the squared distance of poly_dist.

Predicates

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

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

bool	poly_dist.is_degenerate () const	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) 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.

Miscellaneous

const Traits&

poly_dist.traits () const

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.

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.

Next: PolytopeDistanceDTraits

Navigation: Up Table of Contents Package Overview Bibliography Index Title Acknowledging CGAL

CGAL Open Source Project. Release 4.1. 23 October 2012.

CGAL::Polytope_distance_d<Traits>

Definition

Requirements

Types

Creation

Access Functions

Predicates

Modifiers

Validity Check

Miscellaneous

I/O

See Also

Implementation