The algorithm implemented here is an incremental algorithm as mentioned in How Good are Convex Hull Algorithms? (1997) by David Avis and David Bremner. Specific and efficient implementations can be found in The double description method revisited (1996) written by Komei Fukuda and Alain Prodon .
Incremental algorithms for the vertex enumeration problem compute the vertex description by intersecting the defining half-spaces sequentially. An initial simplex is constructed from a subset of n+1 half-spaces and its vertices and 1-skeleton are computed. Additional half-spaces are introduced sequentially and the vertex description and 1-skeleton are updated at each stage. Essentially such an update amounts to identifying and removing all vertices that are not contained in the new half-space, introducing new vertices for all intersections between edges and the bounding hyperplane of the new half-space, and generating the new edges between these new vertices.
This algorithm can be instantiated by polytopes or polyhedral cones, and as a second argument can be instantiated by iterators such as minindex, lexmin, lexmax. More...

#include <DoubleDescription_Rn.h>

Collaboration diagram for DoubleDescription< POLYHEDRON, ITERATOR >:

Public Member Functions
	DoubleDescription (POLYHEDRON poly, ITERATOR ite, int truncationStep)

	DoubleDescription (POLYHEDRON poly, ITERATOR ite, int truncationStep, TrackingOperatorToResult &trackerVdesc, TrackingOperatorToResult &trackerHdesc)

virtual	~DoubleDescription ()

unsigned int	init (POLYHEDRON poly, ITERATOR ite, int truncationStep)

bool	getIsEmpty () const

void	computeStatesOfAllGenerators (std::vector< boost::shared_ptr< Generator_Rn_SD > > &arrayOfGenOUT, const boost::shared_ptr< HalfSpace_Rn > &currentHalfSpace, unsigned int halfspaceNumber, unsigned int &nbGeneratorsIn, unsigned int &nbGeneratorsOut, unsigned int &nbGeneratorsOn)
	For each generator compute its state according to the current half-space. More...

HalfSpace_Rn::State	computeGeneratorState (const boost::shared_ptr< Generator_Rn_SD > &Gen, const boost::shared_ptr< HalfSpace_Rn > &currentHalfSpace, unsigned int halfspaceNumber, double halfSpaceNorm, unsigned int &nbGeneratorsIn, unsigned int &nbGeneratorsOut, unsigned int &nbGeneratorsOn)
	Compute the state hs_ON,hs_IN,hs_OUT,hs_UNKNOWN,hs_IN_OR_OUT for a given generator. More...

bool	findBestLinearConstraint (std::vector< boost::shared_ptr< HalfSpace_Rn > >::iterator currentLC, std::vector< boost::shared_ptr< HalfSpace_Rn > >::iterator bestLC)
	Given a list of half-spaces, try to find the one able to cut most of a given segment or to discard it completely. More...

bool	compute (POLYHEDRON poly, ITERATOR iteHS, int truncationStep, std::vector< boost::shared_ptr< Generator_Rn_SD > > &listOfGenSD)
	The main function splitting the polyhedron cone or polytope 1-skeleton with a list of half-spaces. More...

bool	checkNeighbours (POLYHEDRON poly, const boost::shared_ptr< Generator_Rn_SD > &genIn, const boost::shared_ptr< Generator_Rn_SD > &genOut, std::vector< unsigned int > &commonFacets)

void	markHdescription (TrackingOperatorToResult &trackerHdesc, unsigned int truncationStep, unsigned int numberOfProcessedLinearConstraints)

void	unhookRedundantGenerators (POLYHEDRON poly)

bool	checkFuzziness (POLYHEDRON poly, const boost::shared_ptr< Generator_Rn_SD > &gen1, const boost::shared_ptr< Generator_Rn_SD > &fuzz, std::vector< unsigned int > &commonFacets)
	Check whether a fuzzy half-space of the generator fuzz can be a half-space of gen1 when we chop the segment [gen1,fuzz]. More...

Static Public Member Functions
static bool	inferior (const boost::shared_ptr< Generator_Rn_SD > &HS1, const boost::shared_ptr< Generator_Rn_SD > &HS2)
	Internal function: tell whether a given object is declared inferior to another one. More...

static void	dumpListOfGenerators (POLYHEDRON poly, std::vector< boost::shared_ptr< Generator_Rn_SD > > listOfGenSD, std::ostream &this_ostream, bool displayAll=true)

Protected Member Functions
bool	checkDataStructuresConsistency ()
	In debug mode only, check the equality of two data structures. More...

Protected Attributes
double	_TOL

unsigned int	_RnDIM

bool	_isEmpty
	Store the current state of the intersection. More...

unsigned int	_neigbourhoodCondition

std::vector< std::set< boost::shared_ptr< Generator_Rn_SD > > >	_listOfGeneratorsPerLinearConstraint
	For each linear constraint, update and store the list of its associated generators. More...

std::set< unsigned int >	_listOfRedundantLinearConstraints

std::vector< boost::shared_ptr< HalfSpace_Rn > >	_listOfLinearConstraints

std::vector< double >	_listOfLinearConstraintNorms

std::vector< boost::shared_ptr< NormedHalfSpace_Rn > >	_listOfNormedLinearConstraints
	To speed up computations. More...

std::vector< Segment_Rn >	_allNeighbours
	The connections between generators { {gen_a, gen_b}, {gen_a, gen_c}, ...}. More...

unsigned int	_currentSegmentIndexAllNeighbours

Detailed Description

template<class POLYHEDRON, class ITERATOR>
class DoubleDescription< POLYHEDRON, ITERATOR >

The algorithm implemented here is an incremental algorithm as mentioned in How Good are Convex Hull Algorithms? (1997) by David Avis and David Bremner. Specific and efficient implementations can be found in The double description method revisited (1996) written by Komei Fukuda and Alain Prodon .
Incremental algorithms for the vertex enumeration problem compute the vertex description by intersecting the defining half-spaces sequentially. An initial simplex is constructed from a subset of n+1 half-spaces and its vertices and 1-skeleton are computed. Additional half-spaces are introduced sequentially and the vertex description and 1-skeleton are updated at each stage. Essentially such an update amounts to identifying and removing all vertices that are not contained in the new half-space, introducing new vertices for all intersections between edges and the bounding hyperplane of the new half-space, and generating the new edges between these new vertices.
This algorithm can be instantiated by polytopes or polyhedral cones, and as a second argument can be instantiated by iterators such as minindex, lexmin, lexmax.

minindex : Insert the half-spaces in the order given by the input.
lexmin : Insert the half-spaces in the the lexicographic increasing order of coefficient vectors.
lexmax : Insert the half-spaces in the the lexicographic decreasing order of coefficient vectors.

DoubleDescription stores all the connections between generators unlike the class DoubleDescription which recomputes them on the fly.

Definition at line 86 of file DoubleDescription_Rn.h.

Constructor & Destructor Documentation

◆ DoubleDescription() [1/2]

template<class POLYHEDRON , class ITERATOR >

DoubleDescription< POLYHEDRON, ITERATOR >::DoubleDescription	(	POLYHEDRON	poly,
		ITERATOR	ite,
		int	truncationStep
	)

inline

Definition at line 89 of file DoubleDescription_Rn.h.

Here is the call graph for this function:

◆ DoubleDescription() [2/2]

template<class POLYHEDRON , class ITERATOR >

DoubleDescription< POLYHEDRON, ITERATOR >::DoubleDescription	(	POLYHEDRON	poly,
		ITERATOR	ite,
		int	truncationStep,
		TrackingOperatorToResult &	trackerVdesc,
		TrackingOperatorToResult &	trackerHdesc
	)

inline

Compute the double description tracking all entities and considering the operator1 as the V-description and operator2 as the H-description.

Definition at line 171 of file DoubleDescription_Rn.h.

Here is the call graph for this function:

◆ ~DoubleDescription()

template<class POLYHEDRON , class ITERATOR >

virtual DoubleDescription< POLYHEDRON, ITERATOR >::~DoubleDescription ( )

inlinevirtual

Definition at line 245 of file DoubleDescription_Rn.h.

Member Function Documentation

◆ checkDataStructuresConsistency()

template<class POLYHEDRON , class ITERATOR >

bool DoubleDescription< POLYHEDRON, ITERATOR >::checkDataStructuresConsistency ( )

inlineprotected

In debug mode only, check the equality of two data structures.

Definition at line 1823 of file DoubleDescription_Rn.h.

Here is the caller graph for this function:

◆ checkFuzziness()

template<class POLYHEDRON , class ITERATOR >

bool DoubleDescription< POLYHEDRON, ITERATOR >::checkFuzziness	(	POLYHEDRON	poly,
		const boost::shared_ptr< Generator_Rn_SD > &	gen1,
		const boost::shared_ptr< Generator_Rn_SD > &	fuzz,
		std::vector< unsigned int > &	commonFacets
	)

inline

Check whether a fuzzy half-space of the generator fuzz can be a half-space of gen1 when we chop the segment [gen1,fuzz].

Definition at line 1800 of file DoubleDescription_Rn.h.

◆ checkNeighbours()

template<class POLYHEDRON , class ITERATOR >

bool DoubleDescription< POLYHEDRON, ITERATOR >::checkNeighbours	(	POLYHEDRON	poly,
		const boost::shared_ptr< Generator_Rn_SD > &	genIn,
		const boost::shared_ptr< Generator_Rn_SD > &	genOut,
		std::vector< unsigned int > &	commonFacets
	)

inline

Compute the list of common half-spaces between two generators.

Returns: True if they are potential neighbours.

Definition at line 1754 of file DoubleDescription_Rn.h.

Here is the caller graph for this function:

◆ compute()

template<class POLYHEDRON , class ITERATOR >

bool DoubleDescription< POLYHEDRON, ITERATOR >::compute	(	POLYHEDRON	poly,
		ITERATOR	iteHS,
		int	truncationStep,
		std::vector< boost::shared_ptr< Generator_Rn_SD > > &	listOfGenSD
	)

inline

The main function splitting the polyhedron cone or polytope 1-skeleton with a list of half-spaces.

Definition at line 506 of file DoubleDescription_Rn.h.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ computeGeneratorState()

template<class POLYHEDRON , class ITERATOR >

HalfSpace_Rn::State DoubleDescription< POLYHEDRON, ITERATOR >::computeGeneratorState	(	const boost::shared_ptr< Generator_Rn_SD > &	Gen,
		const boost::shared_ptr< HalfSpace_Rn > &	currentHalfSpace,
		unsigned int	halfspaceNumber,
		double	halfSpaceNorm,
		unsigned int &	nbGeneratorsIn,
		unsigned int &	nbGeneratorsOut,
		unsigned int &	nbGeneratorsOn
	)

inline

Compute the state hs_ON,hs_IN,hs_OUT,hs_UNKNOWN,hs_IN_OR_OUT for a given generator.

Definition at line 377 of file DoubleDescription_Rn.h.

Here is the caller graph for this function:

◆ computeStatesOfAllGenerators()

template<class POLYHEDRON , class ITERATOR >

void DoubleDescription< POLYHEDRON, ITERATOR >::computeStatesOfAllGenerators	(	std::vector< boost::shared_ptr< Generator_Rn_SD > > &	arrayOfGenOUT,
		const boost::shared_ptr< HalfSpace_Rn > &	currentHalfSpace,
		unsigned int	halfspaceNumber,
		unsigned int &	nbGeneratorsIn,
		unsigned int &	nbGeneratorsOut,
		unsigned int &	nbGeneratorsOn
	)

inline

For each generator compute its state according to the current half-space.

Definition at line 280 of file DoubleDescription_Rn.h.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ dumpListOfGenerators()

template<class POLYHEDRON , class ITERATOR >

static void DoubleDescription< POLYHEDRON, ITERATOR >::dumpListOfGenerators	(	POLYHEDRON	poly,
		std::vector< boost::shared_ptr< Generator_Rn_SD > >	listOfGenSD,
		std::ostream &	this_ostream,
		bool	displayAll = `true`
	)

inlinestatic

Definition at line 1736 of file DoubleDescription_Rn.h.

Here is the caller graph for this function:

◆ findBestLinearConstraint()

template<class POLYHEDRON , class ITERATOR >

bool DoubleDescription< POLYHEDRON, ITERATOR >::findBestLinearConstraint	(	std::vector< boost::shared_ptr< HalfSpace_Rn > >::iterator	currentLC,
		std::vector< boost::shared_ptr< HalfSpace_Rn > >::iterator	bestLC
	)

inline

Given a list of half-spaces, try to find the one able to cut most of a given segment or to discard it completely.

Definition at line 427 of file DoubleDescription_Rn.h.

Here is the caller graph for this function:

◆ getIsEmpty()

template<class POLYHEDRON , class ITERATOR >

bool DoubleDescription< POLYHEDRON, ITERATOR >::getIsEmpty ( ) const

inline

Definition at line 277 of file DoubleDescription_Rn.h.

Here is the caller graph for this function:

◆ inferior()

template<class POLYHEDRON , class ITERATOR >

static bool DoubleDescription< POLYHEDRON, ITERATOR >::inferior	(	const boost::shared_ptr< Generator_Rn_SD > &	HS1,
		const boost::shared_ptr< Generator_Rn_SD > &	HS2
	)

inlinestatic

Internal function: tell whether a given object is declared inferior to another one.

Definition at line 362 of file DoubleDescription_Rn.h.

Here is the caller graph for this function:

◆ init()

template<class POLYHEDRON , class ITERATOR >

unsigned int DoubleDescription< POLYHEDRON, ITERATOR >::init	(	POLYHEDRON	poly,
		ITERATOR	ite,
		int	truncationStep
	)

inline

Definition at line 247 of file DoubleDescription_Rn.h.

Here is the caller graph for this function:

◆ markHdescription()

template<class POLYHEDRON , class ITERATOR >

void DoubleDescription< POLYHEDRON, ITERATOR >::markHdescription	(	TrackingOperatorToResult &	trackerHdesc,
		unsigned int	truncationStep,
		unsigned int	numberOfProcessedLinearConstraints
	)

inline

Definition at line 1769 of file DoubleDescription_Rn.h.

Here is the call graph for this function:

◆ unhookRedundantGenerators()

template<class POLYHEDRON , class ITERATOR >

void DoubleDescription< POLYHEDRON, ITERATOR >::unhookRedundantGenerators ( POLYHEDRON poly )

inline

In some cases fuzzy generators are located somewhere in a fuzzy zone and are computed with redundant half-spaces. As they are likely not to have the sufficient number of half-spaces through the process, unhook them.

Definition at line 1783 of file DoubleDescription_Rn.h.

Here is the call graph for this function:

Here is the caller graph for this function:

Member Data Documentation

◆ _allNeighbours

template<class POLYHEDRON , class ITERATOR >

std::vector< Segment_Rn > DoubleDescription< POLYHEDRON, ITERATOR >::_allNeighbours

protected

The connections between generators { {gen_a, gen_b}, {gen_a, gen_c}, ...}.

Definition at line 1899 of file DoubleDescription_Rn.h.

◆ _currentSegmentIndexAllNeighbours

template<class POLYHEDRON , class ITERATOR >

unsigned int DoubleDescription< POLYHEDRON, ITERATOR >::_currentSegmentIndexAllNeighbours

protected

Definition at line 1900 of file DoubleDescription_Rn.h.

◆ _isEmpty

template<class POLYHEDRON , class ITERATOR >

bool DoubleDescription< POLYHEDRON, ITERATOR >::_isEmpty

protected

Store the current state of the intersection.

Definition at line 1889 of file DoubleDescription_Rn.h.

◆ _listOfGeneratorsPerLinearConstraint

template<class POLYHEDRON , class ITERATOR >

std::vector< std::set< boost::shared_ptr< Generator_Rn_SD > > > DoubleDescription< POLYHEDRON, ITERATOR >::_listOfGeneratorsPerLinearConstraint

protected

For each linear constraint, update and store the list of its associated generators.

Definition at line 1892 of file DoubleDescription_Rn.h.

◆ _listOfLinearConstraintNorms

template<class POLYHEDRON , class ITERATOR >

std::vector< double > DoubleDescription< POLYHEDRON, ITERATOR >::_listOfLinearConstraintNorms

protected

Definition at line 1895 of file DoubleDescription_Rn.h.

◆ _listOfLinearConstraints

template<class POLYHEDRON , class ITERATOR >

std::vector< boost::shared_ptr<HalfSpace_Rn> > DoubleDescription< POLYHEDRON, ITERATOR >::_listOfLinearConstraints

protected

Definition at line 1894 of file DoubleDescription_Rn.h.

◆ _listOfNormedLinearConstraints

template<class POLYHEDRON , class ITERATOR >

std::vector< boost::shared_ptr<NormedHalfSpace_Rn> > DoubleDescription< POLYHEDRON, ITERATOR >::_listOfNormedLinearConstraints

protected

To speed up computations.

Definition at line 1897 of file DoubleDescription_Rn.h.

◆ _listOfRedundantLinearConstraints

template<class POLYHEDRON , class ITERATOR >

std::set< unsigned int > DoubleDescription< POLYHEDRON, ITERATOR >::_listOfRedundantLinearConstraints

protected

Definition at line 1893 of file DoubleDescription_Rn.h.

◆ _neigbourhoodCondition

template<class POLYHEDRON , class ITERATOR >

unsigned int DoubleDescription< POLYHEDRON, ITERATOR >::_neigbourhoodCondition

protected

Definition at line 1890 of file DoubleDescription_Rn.h.

◆ _RnDIM

template<class POLYHEDRON , class ITERATOR >

unsigned int DoubleDescription< POLYHEDRON, ITERATOR >::_RnDIM

protected

Definition at line 1887 of file DoubleDescription_Rn.h.

◆ _TOL

template<class POLYHEDRON , class ITERATOR >

double DoubleDescription< POLYHEDRON, ITERATOR >::_TOL

protected

Definition at line 1886 of file DoubleDescription_Rn.h.

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

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

Public Member Functions

Static Public Member Functions

Protected Member Functions

Protected Attributes

Detailed Description

template<class POLYHEDRON, class ITERATOR> class DoubleDescription< POLYHEDRON, ITERATOR >

Constructor & Destructor Documentation

◆ DoubleDescription() [1/2]

◆ DoubleDescription() [2/2]

◆ ~DoubleDescription()

Member Function Documentation

◆ checkDataStructuresConsistency()

◆ checkFuzziness()

◆ checkNeighbours()

◆ compute()

◆ computeGeneratorState()

◆ computeStatesOfAllGenerators()

◆ dumpListOfGenerators()

◆ findBestLinearConstraint()

◆ getIsEmpty()

◆ inferior()

◆ init()

◆ markHdescription()

◆ unhookRedundantGenerators()

Member Data Documentation

◆ _allNeighbours

◆ _currentSegmentIndexAllNeighbours

◆ _isEmpty

◆ _listOfGeneratorsPerLinearConstraint

◆ _listOfLinearConstraintNorms

◆ _listOfLinearConstraints

◆ _listOfNormedLinearConstraints

◆ _listOfRedundantLinearConstraints

◆ _neigbourhoodCondition

◆ _RnDIM

◆ _TOL

template<class POLYHEDRON, class ITERATOR>
class DoubleDescription< POLYHEDRON, ITERATOR >