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 ()
	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)
	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
	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 138 of file PolyhedralAlgorithms_Rn.h.

Constructor & Destructor Documentation

◆ MinkowskiSum() [1/5]

MinkowskiSum::MinkowskiSum ( )

inline

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

Definition at line 143 of file PolyhedralAlgorithms_Rn.h.

◆ MinkowskiSum() [2/5]

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 147 of file PolyhedralAlgorithms_Rn.h.

◆ MinkowskiSum() [3/5]

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 153 of file PolyhedralAlgorithms_Rn.h.

◆ MinkowskiSum() [4/5]

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 346 of file PolyhedralAlgorithms_Rn.cpp.

Here is the call graph for this function:

◆ MinkowskiSum() [5/5]

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 165 of file PolyhedralAlgorithms_Rn.h.

Member Function Documentation

◆ compute()

boost::shared_ptr< Polytope_Rn > MinkowskiSum::compute ( )

protected

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

Definition at line 526 of file PolyhedralAlgorithms_Rn.cpp.

Here is the call graph for this function:

◆ computeCapHalfSpaces()

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

protected

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

◆ computeCommonRefinement()

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
	)

protected

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

Definition at line 399 of file PolyhedralAlgorithms_Rn.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ processNormalFan0()

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 892 of file PolyhedralAlgorithms_Rn.cpp.

Here is the call graph for this function:

◆ processNormalFan1()

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 765 of file PolyhedralAlgorithms_Rn.cpp.

Here is the call graph for this function:

◆ processNormalFan2()

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 627 of file PolyhedralAlgorithms_Rn.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ rebuildSum()

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

◆ _A2C

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

protected

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

Definition at line 237 of file PolyhedralAlgorithms_Rn.h.

◆ _B2C

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

protected

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

Definition at line 239 of file PolyhedralAlgorithms_Rn.h.

◆ _firstOperand

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

protected

Definition at line 228 of file PolyhedralAlgorithms_Rn.h.

◆ _MinkowskiDecomposition

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 253 of file PolyhedralAlgorithms_Rn.h.

◆ _MinkowskiDecompositionOK

std::vector< bool > MinkowskiSum::_MinkowskiDecompositionOK

protected

Tell whether _MinkowskiDecomposition had to be considered or not.

Definition at line 255 of file PolyhedralAlgorithms_Rn.h.

◆ _neighboursA

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 243 of file PolyhedralAlgorithms_Rn.h.

◆ _neighboursB

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 246 of file PolyhedralAlgorithms_Rn.h.

◆ _NF_Cones

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

protected

The normal fan polyhedrical cones list.

Definition at line 258 of file PolyhedralAlgorithms_Rn.h.

◆ _NF_Vertices

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

protected

The list of C vertices.

Definition at line 260 of file PolyhedralAlgorithms_Rn.h.

◆ _secondOperand

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

protected

Definition at line 229 of file PolyhedralAlgorithms_Rn.h.

◆ _sum

boost::shared_ptr<Polytope_Rn> MinkowskiSum::_sum

protected

Definition at line 230 of file PolyhedralAlgorithms_Rn.h.

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

/mnt/c/Users/vindelos/Documents/TEST/TEST/co/politopix/trunk/PolyhedralAlgorithms_Rn.h
/mnt/c/Users/vindelos/Documents/TEST/TEST/co/politopix/trunk/PolyhedralAlgorithms_Rn.cpp

Public Member Functions

Protected Member Functions

Protected Attributes

Detailed Description

Constructor & Destructor Documentation

◆ MinkowskiSum() [1/5]

◆ MinkowskiSum() [2/5]

◆ MinkowskiSum() [3/5]

◆ MinkowskiSum() [4/5]

◆ MinkowskiSum() [5/5]

Member Function Documentation

◆ compute()

◆ computeCapHalfSpaces()

◆ computeCommonRefinement()

◆ processNormalFan0()

◆ processNormalFan1()

◆ processNormalFan2()

◆ rebuildSum()

Member Data Documentation

◆ _A2C

◆ _B2C

◆ _firstOperand

◆ _MinkowskiDecomposition

◆ _MinkowskiDecompositionOK

◆ _neighboursA

◆ _neighboursB

◆ _NF_Cones

◆ _NF_Vertices

◆ _secondOperand

◆ _sum