Model a polytope using its two equivalent definitions : the convex hull and the half-space intersection. More...

#include <Polytope_Rn.h>

Inheritance diagram for Polytope_Rn:

Collaboration diagram for Polytope_Rn:

Public Member Functions
	Polytope_Rn ()
	Constructor for polytopes i.e. bounded convex polyhedra. More...

virtual	~Polytope_Rn ()
	Destructor. More...

virtual bool	isBounded () const
	Tell whether this polyhedron is bounded or not, polytopes are bounded. More...

virtual unsigned int	neigbourhoodCondition () const
	Two vertices are neighbours in a polytope <=> they share at least (n-1) facets. More...

virtual unsigned int	numberOfGeneratorsPerFacet () const
	Each facet in a polytope has got n vertices. More...

virtual void	createBoundingSimplex (double M)
	Initialize the truncating algorithm building a M-sized simplex around the polytope. More...

virtual void	createBoundingBox (double M)
	Initialize the truncating algorithm building a M-sized bounding box around the polytope. More...

virtual bool	checkEdges () const
	Always true in the polyhedral cone case. More...

bool	checkEqualityOfVertices (const boost::shared_ptr< Polytope_Rn > &B, bool printOnScreen=false) const
	Check whether two V-polytopes are identical Check whether the sets of vertices of A and B are equal. More...

virtual void	createTruncatedGenerator (const boost::shared_ptr< Generator_Rn_SD > &in, const boost::shared_ptr< Generator_Rn_SD > &out, boost::shared_ptr< Generator_Rn_SD > newV, double ay, double az, double b=0.) const
	This is the intersection vertex in the truncating algorithm, defined by the intersection between an edge and an hyperplane. More...

boost::shared_ptr < PolyhedralCone_Rn >	getPrimalCone (unsigned int i) const throw (std::out_of_range)

boost::shared_ptr < PolyhedralCone_Rn >	getPrimalCone (const boost::shared_ptr< Generator_Rn > &vx) const
	Return the primal cone C(vx) of the polytope A associated to the vertex vx. More...

Public Member Functions inherited from PolyhedralCone_Rn
	PolyhedralCone_Rn ()
	Constructor. More...

	PolyhedralCone_Rn (const PolyhedralCone_Rn &A)
	Constructor. More...

virtual	~PolyhedralCone_Rn ()
	Destructor. More...

virtual unsigned int	dimension () const
	Return the space dimension. More...

void	reset ()
	Remove all half-spaces and generators. More...

unsigned int	numberOfHalfSpaces () const
	Get the total number of half-spaces. More...

boost::shared_ptr< HalfSpace_Rn >	addHalfSpace (boost::shared_ptr< HalfSpace_Rn > hs, bool check=false)
	Add the current half-space in its list. More...

void	removeHalfSpaceFromListAndGenerators (const boost::shared_ptr< HalfSpace_Rn > &hs) throw (std::invalid_argument)
	Remove the half-space given as parameter from its list and from all generators. More...

void	removeHalfSpace (unsigned int j)
	Remove the half-space number j from its list. More...

void	removeHalfSpaces (const std::set< boost::shared_ptr< HalfSpace_Rn > > &setOfRedundantHS)
	Remove the half-space number j from its list. More...

unsigned int	getHalfSpaceNumber (const boost::shared_ptr< HalfSpace_Rn > &F) const throw (std::out_of_range)
	For a given half-space, return its list index. More...

const boost::shared_ptr < HalfSpace_Rn > &	getHalfSpace (unsigned int i) const throw (std::out_of_range)
	Return the i-th generator. More...

listOfGeometricObjects < boost::shared_ptr < HalfSpace_Rn > > &	getListOfHalfSpaces ()
	Return the list of half-spaces. More...

const listOfGeometricObjects < boost::shared_ptr < HalfSpace_Rn > > &	getListOfHalfSpaces () const
	Return the list of half-spaces. More...

unsigned int	numberOfGenerators () const
	Give the total number of generators. More...

void	addGenerator (boost::shared_ptr< Generator_Rn > vx)
	Add the given generator. More...

const boost::shared_ptr < Generator_Rn > &	getGenerator (unsigned int i) const throw (std::out_of_range)
	Return the i-th generator. More...

unsigned int	getGeneratorNumber (boost::shared_ptr< Generator_Rn > G) const throw (std::out_of_range,std::invalid_argument)
	For a given generator, return its list index. More...

const listOfGeometricObjects < boost::shared_ptr < Generator_Rn > > &	getListOfGenerators () const
	Return the list of generators. More...

unsigned int	getListOfGeneratorsSD (std::vector< boost::shared_ptr< Generator_Rn_SD > > &currentListOfGeneratorsSD)

void	setListOfGeneratorsSD (const std::vector< boost::shared_ptr< Generator_Rn_SD > > &gnList)
	Set a new list of generators. The list of half-spaces should have been previously set. More...

void	relocateGenerators ()

void	setListOfGenerators (const listOfGeometricObjects< boost::shared_ptr< Generator_Rn > > &gnList)
	Set a new list of generators. More...

bool	checkNeighbours (const boost::shared_ptr< Generator_Rn > &V1, const boost::shared_ptr< Generator_Rn > &V2, std::vector< boost::shared_ptr< HalfSpace_Rn > > &commonFacets, const std::set< boost::shared_ptr< HalfSpace_Rn > > &listOfRedundantHS) const throw (std::invalid_argument)

bool	isIncluded (const boost::shared_ptr< PolyhedralCone_Rn > &B) const
	Test whether the current polytope V-description is inside the polytope B H-description. More...

bool	checkNeighbours (const boost::shared_ptr< Generator_Rn > &V1, const boost::shared_ptr< Generator_Rn > &V2, std::vector< boost::shared_ptr< HalfSpace_Rn > > &commonFacets, unsigned int topologicalCode=1) const throw (std::invalid_argument)

bool	checkNeighbours (const boost::shared_ptr< Generator_Rn > &V1, const boost::shared_ptr< Generator_Rn > &V2, std::vector< HalfSpace_Rn * > &commonFacets, unsigned int topologicalCode=1) const throw (std::invalid_argument)
	Check for polytopes that vertices share (n-1) facets. For polyhedral cones, it must check that vectors share (n-2) facets. More...

bool	checkNeighbours (const boost::shared_ptr< Generator_Rn_SD > &genIn, const boost::shared_ptr< Generator_Rn_SD > &genOut, std::vector< unsigned int > &commonFacets)
	Check for polytopes that vertices share (n-1) facets. For polyhedral cones, it must check that vectors share (n-2) facets. More...

bool	checkNeighboursWithHSnumbers (const boost::shared_ptr< Generator_Rn > &V1, const boost::shared_ptr< Generator_Rn > &V2, std::vector< HalfSpace_Rn * > &commonFacets, const std::set< boost::shared_ptr< HalfSpace_Rn > > &listOfRedundantHS, unsigned int topologicalCode=1) const throw (std::invalid_argument)
	Check for polytopes that vertices share (n-1) facets. For polyhedral cones, it must check that vectors share (n-2) facets. More...

void	fillNeighbourMatrix (std::vector< std::vector< unsigned int > > &neighboursA, unsigned int topologicalCode=1) const throw (std::out_of_range)

virtual bool	checkTopologyAndGeometry () const
	As stated by Komei Fukuda "the complexity of the polyhedral verification problem is unknown. Is it in P or in coNP-complete?" So only 3 verifications are made in Rⁿ : More...

HalfSpace_Rn::State	checkPoint (const Point_Rn &thisPoint) const
	Check a point state against the whole polyhedron. More...

HalfSpace_Rn::State	checkPoint (const boost::shared_ptr< Generator_Rn > &point, const boost::shared_ptr< HalfSpace_Rn > &halfSpace, double halfSpaceNorm) const
	Check a point state against a half-space. More...

bool	checkDuplicateGenerators (unsigned int &a, unsigned int &b)
	Make sure no duplicate generators are stored. More...

void	checkGenerator (unsigned int vtxNumber, std::ostream &this_ostream) const throw (std::out_of_range)
	Compute all distance from the current point to all half-spaces frontiers. More...

bool	checkGenerators (const listOfGeometricObjects< boost::shared_ptr< Generator_Rn > > &listGenA, const listOfGeometricObjects< boost::shared_ptr< HalfSpace_Rn > > &listHSB, bool check_all=false) const
	Check the number of facets per generator and make sure it is compliant with its current constraints. It must verify the following property : $\forall G=(g_1,...,g_n) \in \mathbb{R}^n, \exists \, (n-1) \, \bar{H}_i = \left\{ x : \sum_{j=1}^n a_{ij}x_j \geq 0 \right\} such \, as \, G \in \bar{H}_i, i \in \{1,...,n-1\}$ . More...

void	removeGenerator (unsigned int j)
	Remove the generator number j from its list. More...

void	checkFacet (unsigned int fctNumber, std::ostream &this_ostream) const throw (std::out_of_range)

bool	checkFacets () const
	Detect redundant half spaces and make sure each facet has the right number of generators. $A = Conv(G_1, ..., G_k) = \displaystyle{ \bigcap_{i=1}^m \bar{H}_i^+ }$ Check that the polytope does not have generators violating a constraint defined by a half-space. $\forall G=(g_1,...,g_n) \in \mathbb{R}^n, \nexists \, \bar{H}_i^+ = \left\{ x : \sum_{j=1}^n a_{ij}x_j \geq 0 \right\} such \, as \, G \not\in \bar{H}_i^+$ Check that the polytope does have at least (n-1) generators per half-space frontier. $\forall \bar{H}_i, \exists \, (n-1) \, G=(g_1,...,g_n) \in \mathbb{R}^n, such \, as \, G \in \bar{H}_i$ . More...

bool	checkEquality (const boost::shared_ptr< PolyhedralCone_Rn > &B, bool getFaceMapping=false) const

void	negate ()
	Compute the symmetrical polyhedral cone. More...

boost::shared_ptr < PolyhedralCone_Rn >	computeDualPolyhedralCone () const
	Build the dual polyhedral cone of the current one whose edge are orthogonal to the primal and vice-versa. More...

virtual void	computeMinkowskiSum (const boost::shared_ptr< PolyhedralCone_Rn > &A, const boost::shared_ptr< PolyhedralCone_Rn > &B)
	Compute the Minkowski sum of two polyhedral cones. More...

void	dump (std::ostream &this_ostream) const
	Dump the polyhedral structure on std::cout. More...

Additional Inherited Members
Protected Attributes inherited from PolyhedralCone_Rn
listOfGeometricObjects < boost::shared_ptr < HalfSpace_Rn > >	_listOfHalfSpaces
	The list of half-spaces defining the polytope. More...

listOfGeometricObjects < boost::shared_ptr < Generator_Rn > >	_listOfGenerators
	The convex hull of connected points. More...

Detailed Description

Model a polytope using its two equivalent definitions : the convex hull and the half-space intersection.

Definition at line 34 of file Polytope_Rn.h.

Constructor & Destructor Documentation

Polytope_Rn::Polytope_Rn ( )

inline

Constructor for polytopes i.e. bounded convex polyhedra.

Definition at line 38 of file Polytope_Rn.h.

virtual Polytope_Rn::~Polytope_Rn ( )

inlinevirtual

Destructor.

Definition at line 41 of file Polytope_Rn.h.

Member Function Documentation

bool Polytope_Rn::checkEdges ( ) const

virtual

Always true in the polyhedral cone case.

Reimplemented from PolyhedralCone_Rn.

Definition at line 115 of file Polytope_Rn.cpp.

Here is the call graph for this function:

bool Polytope_Rn::checkEqualityOfVertices	(	const boost::shared_ptr< Polytope_Rn > &	B,
		bool	printOnScreen = `false`
	)		const

Check whether two V-polytopes are identical Check whether the sets of vertices of A and B are equal.

Parameters

A	The V-polytope

Returns: true if
$\mathcal{V}_A = \mathcal{V}_B$
, false otherwise.

Definition at line 324 of file Polytope_Rn.cpp.

Here is the call graph for this function:

void Polytope_Rn::createBoundingBox ( double M )

virtual

Initialize the truncating algorithm building a M-sized bounding box around the polytope.

When only the polytope facets are given, include it in a huge cube that we are going to truncate.

Reimplemented from PolyhedralCone_Rn.

Definition at line 237 of file Polytope_Rn.cpp.

Here is the call graph for this function:

void Polytope_Rn::createBoundingSimplex ( double M )

virtual

Initialize the truncating algorithm building a M-sized simplex around the polytope.

When only the polytope facets are given, include it in a huge simplex that we are going to truncate.

Reimplemented from PolyhedralCone_Rn.

Definition at line 162 of file Polytope_Rn.cpp.

Here is the call graph for this function:

void Polytope_Rn::createTruncatedGenerator	(	const boost::shared_ptr< Generator_Rn_SD > &	in,
		const boost::shared_ptr< Generator_Rn_SD > &	out,
		boost::shared_ptr< Generator_Rn_SD >	newV,
		double	ay,
		double	az,
		double	b = `0.`
	)		const

virtual

This is the intersection vertex in the truncating algorithm, defined by the intersection between an edge and an hyperplane.

This is the intersection vertex in the truncating algorithm. It is defined by the intersection between an edge, i.e. a 1-face, and an hyperplane, i.e. a (n-1)-face.

Reimplemented from PolyhedralCone_Rn.

Definition at line 309 of file Polytope_Rn.cpp.

boost::shared_ptr< PolyhedralCone_Rn > Polytope_Rn::getPrimalCone	(	unsigned int	i	)	const
throw	(	std::out_of_range
	)

Return the i-th primal cone C(i) of the polytope A. If A has k vertices then $A = \displaystyle{ \bigcap_{i=1}^k C(i) }$ where $C(i) = \displaystyle{ \bigcap_{i=1}^l \bar{H}_i^+ }$

Definition at line 367 of file Polytope_Rn.cpp.

boost::shared_ptr< PolyhedralCone_Rn > Polytope_Rn::getPrimalCone ( const boost::shared_ptr< Generator_Rn > & vx ) const

Return the primal cone C(vx) of the polytope A associated to the vertex vx.

Definition at line 404 of file Polytope_Rn.cpp.

Here is the call graph for this function:

virtual bool Polytope_Rn::isBounded ( ) const

inlinevirtual

Tell whether this polyhedron is bounded or not, polytopes are bounded.

Reimplemented from PolyhedralCone_Rn.

Definition at line 44 of file Polytope_Rn.h.

virtual unsigned int Polytope_Rn::neigbourhoodCondition ( ) const

inlinevirtual

Two vertices are neighbours in a polytope <=> they share at least (n-1) facets.

Reimplemented from PolyhedralCone_Rn.

Definition at line 47 of file Polytope_Rn.h.

Here is the call graph for this function:

virtual unsigned int Polytope_Rn::numberOfGeneratorsPerFacet ( ) const

inlinevirtual

Each facet in a polytope has got n vertices.

Reimplemented from PolyhedralCone_Rn.

Definition at line 50 of file Polytope_Rn.h.

Here is the call graph for this function:

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

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

Public Member Functions

Additional Inherited Members

Detailed Description

Constructor & Destructor Documentation

Member Function Documentation