Compute the Minkowski sum of two polytopes. More...

#include <PolyhedralAlgorithms_Rn.h>

Inheritance diagram for MinkowskiSum:

Collaboration diagram for MinkowskiSum:

Public Member Functions
	MinkowskiSum ()
	Sets up the data structure for the computation of the Minkowski sum of two polytopes. More...

	MinkowskiSum (const boost::shared_ptr< Polytope_Rn > &A, const boost::shared_ptr< Polytope_Rn > &B)
	Sets up the data structure for the computation of the Minkowski sum of two polytopes. More...

	MinkowskiSum (const boost::shared_ptr< Polytope_Rn > &A, const boost::shared_ptr< Polytope_Rn > &B, boost::shared_ptr< Polytope_Rn > &C)
	Compute the Minkowski sum of two polytopes. More...

	MinkowskiSum (const std::vector< boost::shared_ptr< Polytope_Rn > > &arrayOfPolytopes, boost::shared_ptr< Polytope_Rn > &C)
	Compute the Minkowski sum of several polytopes. More...

	MinkowskiSum (const boost::shared_ptr< Polytope_Rn > &A, const boost::shared_ptr< Polytope_Rn > &B, boost::shared_ptr< Polytope_Rn > &C, const std::vector< std::vector< int > > &genitorsOfGeneratorsA, const std::vector< std::vector< int > > &genitorsOfGeneratorsB, std::vector< std::vector< int > > &traceGenerators)
	Compute the Minkowski sum of two polytopes. More...

boost::shared_ptr< Polytope_Rn >	rebuildSum (const std::set< unsigned int > &firstOperandCaps, const std::set< unsigned int > &secondOperandCaps, std::set< unsigned int > &newCaps, double bb_size=1000.)
	Remove the cap half-spaces stored in sets and then truncate again. More...

Protected Member Functions
boost::shared_ptr< Polytope_Rn >	compute () throw (std::domain_error)
	Compute the common refinement of the two operands normal fans and then build the sum. More...

void	computeCommonRefinement (const std::vector< boost::shared_ptr< Generator_Rn > > &listOfGenerators_A, const std::vector< boost::shared_ptr< Generator_Rn > > &listOfGenerators_B, std::vector< boost::shared_ptr< Generator_Rn > > &listOfGenerators_C, const std::vector< boost::shared_ptr< PolyhedralCone_Rn > > &listOfDualCones_A, const std::vector< boost::shared_ptr< PolyhedralCone_Rn > > &listOfDualCones_B, std::vector< boost::shared_ptr< PolyhedralCone_Rn > > &listOfDualCones_C) throw (std::domain_error)
	Just compute the common refinement of the two operands normal fans. More...

void	processNormalFan0 ()
	Do the final job after having intersected all dual cones. The reduction process simply compares all dual cones generators. More...

void	processNormalFan1 ()
	Do the final job after having intersected all dual cones. The reduction process uses neighbourhood properties to identify dual cones generators. More...

void	processNormalFan2 ()
	Do the final job after having intersected all dual cones. The reduction process builds half-spaces and identifies them with they generators lists. More...

void	computeCapHalfSpaces (const std::set< unsigned int > &firstOperandCaps, const std::set< unsigned int > &secondOperandCaps, std::set< unsigned int > &sumCaps) const throw (std::domain_error)
	Return the cap half-spaces of the sum in function of the two operands cap half-spaces. More...

Protected Attributes
const boost::shared_ptr < Polytope_Rn >	_firstOperand

const boost::shared_ptr < Polytope_Rn >	_secondOperand

boost::shared_ptr< Polytope_Rn >	_sum

std::vector< std::vector < unsigned int > >	_A2C
	Store the polyhedrical cap in C of each vertex of A. More...

std::vector< std::vector < unsigned int > >	_B2C
	Store the polyhedrical cap in C of each vertex of B. More...

std::vector< std::vector < unsigned int > >	_neighboursA
	Store the neighbours of each vertex of A. More...

std::vector< std::vector < unsigned int > >	_neighboursB
	Store the neighbours of each vertex of B. More...

std::vector< std::pair < unsigned int, unsigned int > >	_MinkowskiDecomposition
	Store the genitors in A and B of each vertex of C. More...

std::vector< bool >	_MinkowskiDecompositionOK
	Tell whether _MinkowskiDecomposition had to be considered or not. More...

std::vector< boost::shared_ptr < PolyhedralCone_Rn > >	_NF_Cones
	The normal fan polyhedrical cones list. More...

std::vector< boost::shared_ptr < Generator_Rn > >	_NF_Vertices
	The list of C vertices. More...

Detailed Description

Compute the Minkowski sum of two polytopes.

Definition at line 140 of file PolyhedralAlgorithms_Rn.h.

Constructor & Destructor Documentation

MinkowskiSum::MinkowskiSum ( )

inline

Sets up the data structure for the computation of the Minkowski sum of two polytopes.

Definition at line 145 of file PolyhedralAlgorithms_Rn.h.

MinkowskiSum::MinkowskiSum	(	const boost::shared_ptr< Polytope_Rn > &	A,
		const boost::shared_ptr< Polytope_Rn > &	B
	)

inline

Sets up the data structure for the computation of the Minkowski sum of two polytopes.

Definition at line 149 of file PolyhedralAlgorithms_Rn.h.

MinkowskiSum::MinkowskiSum	(	const boost::shared_ptr< Polytope_Rn > &	A,
		const boost::shared_ptr< Polytope_Rn > &	B,
		boost::shared_ptr< Polytope_Rn > &	C
	)

inline

Compute the Minkowski sum of two polytopes.

Definition at line 155 of file PolyhedralAlgorithms_Rn.h.

MinkowskiSum::MinkowskiSum	(	const std::vector< boost::shared_ptr< Polytope_Rn > > &	arrayOfPolytopes,
		boost::shared_ptr< Polytope_Rn > &	C
	)

Compute the Minkowski sum of several polytopes.

Definition at line 349 of file PolyhedralAlgorithms_Rn.cpp.

Here is the call graph for this function:

MinkowskiSum::MinkowskiSum	(	const boost::shared_ptr< Polytope_Rn > &	A,
		const boost::shared_ptr< Polytope_Rn > &	B,
		boost::shared_ptr< Polytope_Rn > &	C,
		const std::vector< std::vector< int > > &	genitorsOfGeneratorsA,
		const std::vector< std::vector< int > > &	genitorsOfGeneratorsB,
		std::vector< std::vector< int > > &	traceGenerators
	)

inline

Compute the Minkowski sum of two polytopes.

Definition at line 167 of file PolyhedralAlgorithms_Rn.h.

Member Function Documentation

boost::shared_ptr< Polytope_Rn > MinkowskiSum::compute	(		)
throw	(	std::domain_error
	)

protected

Compute the common refinement of the two operands normal fans and then build the sum.

Definition at line 529 of file PolyhedralAlgorithms_Rn.cpp.

Here is the call graph for this function:

void MinkowskiSum::computeCapHalfSpaces	(	const std::set< unsigned int > &	firstOperandCaps,
		const std::set< unsigned int > &	secondOperandCaps,
		std::set< unsigned int > &	sumCaps
	)		const
throw	(	std::domain_error
	)

protected

Return the cap half-spaces of the sum in function of the two operands cap half-spaces.

void MinkowskiSum::computeCommonRefinement	(	const std::vector< boost::shared_ptr< Generator_Rn > > &	listOfGenerators_A,
		const std::vector< boost::shared_ptr< Generator_Rn > > &	listOfGenerators_B,
		std::vector< boost::shared_ptr< Generator_Rn > > &	listOfGenerators_C,
		const std::vector< boost::shared_ptr< PolyhedralCone_Rn > > &	listOfDualCones_A,
		const std::vector< boost::shared_ptr< PolyhedralCone_Rn > > &	listOfDualCones_B,
		std::vector< boost::shared_ptr< PolyhedralCone_Rn > > &	listOfDualCones_C
	)
throw	(	std::domain_error
	)

protected

Just compute the common refinement of the two operands normal fans.

Definition at line 398 of file PolyhedralAlgorithms_Rn.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

void MinkowskiSum::processNormalFan0 ( )

protected

Do the final job after having intersected all dual cones. The reduction process simply compares all dual cones generators.

Definition at line 849 of file PolyhedralAlgorithms_Rn.cpp.

Here is the call graph for this function:

void MinkowskiSum::processNormalFan1 ( )

protected

Do the final job after having intersected all dual cones. The reduction process uses neighbourhood properties to identify dual cones generators.

Definition at line 722 of file PolyhedralAlgorithms_Rn.cpp.

Here is the call graph for this function:

void MinkowskiSum::processNormalFan2 ( )

protected

Do the final job after having intersected all dual cones. The reduction process builds half-spaces and identifies them with they generators lists.

Definition at line 584 of file PolyhedralAlgorithms_Rn.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

boost::shared_ptr<Polytope_Rn> MinkowskiSum::rebuildSum	(	const std::set< unsigned int > &	firstOperandCaps,
		const std::set< unsigned int > &	secondOperandCaps,
		std::set< unsigned int > &	newCaps,
		double	bb_size = `1000.`
	)

Remove the cap half-spaces stored in sets and then truncate again.

Returns: The new sum

Member Data Documentation

std::vector< std::vector<unsigned int> > MinkowskiSum::_A2C

protected

Store the polyhedrical cap in C of each vertex of A.

Definition at line 239 of file PolyhedralAlgorithms_Rn.h.

std::vector< std::vector<unsigned int> > MinkowskiSum::_B2C

protected

Store the polyhedrical cap in C of each vertex of B.

Definition at line 241 of file PolyhedralAlgorithms_Rn.h.

const boost::shared_ptr<Polytope_Rn> MinkowskiSum::_firstOperand

protected

Definition at line 230 of file PolyhedralAlgorithms_Rn.h.

std::vector< std::pair< unsigned int, unsigned int > > MinkowskiSum::_MinkowskiDecomposition

protected

Store the genitors in A and B of each vertex of C.

Definition at line 255 of file PolyhedralAlgorithms_Rn.h.

std::vector< bool > MinkowskiSum::_MinkowskiDecompositionOK

protected

Tell whether _MinkowskiDecomposition had to be considered or not.

Definition at line 257 of file PolyhedralAlgorithms_Rn.h.

std::vector< std::vector<unsigned int> > MinkowskiSum::_neighboursA

protected

Store the neighbours of each vertex of A.

neighboursA(a_i,a_j)==1 <=> a_i R a_j

Definition at line 245 of file PolyhedralAlgorithms_Rn.h.

std::vector< std::vector<unsigned int> > MinkowskiSum::_neighboursB

protected

Store the neighbours of each vertex of B.

neighboursB(b_i,b_j)==1 <=> b_u R b_v

Definition at line 248 of file PolyhedralAlgorithms_Rn.h.

std::vector< boost::shared_ptr<PolyhedralCone_Rn> > MinkowskiSum::_NF_Cones

protected

The normal fan polyhedrical cones list.

Definition at line 260 of file PolyhedralAlgorithms_Rn.h.

std::vector< boost::shared_ptr<Generator_Rn> > MinkowskiSum::_NF_Vertices

protected

The list of C vertices.

Definition at line 262 of file PolyhedralAlgorithms_Rn.h.

const boost::shared_ptr<Polytope_Rn> MinkowskiSum::_secondOperand

protected

Definition at line 231 of file PolyhedralAlgorithms_Rn.h.

boost::shared_ptr<Polytope_Rn> MinkowskiSum::_sum

protected

Definition at line 232 of file PolyhedralAlgorithms_Rn.h.

The documentation for this class was generated from the following files:

/home/vindelos/politopix/trunk/PolyhedralAlgorithms_Rn.h
/home/vindelos/politopix/trunk/PolyhedralAlgorithms_Rn.cpp

Public Member Functions

Protected Member Functions

Protected Attributes

Detailed Description

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation