Split a polytope into simplices to compute its volume.
Two Algorithms for Determining Volumes of Convex Polyhedra (1979) by Jacques Cohen and Timothy Hickey
Journal of the ACM (JACM) JACM Homepage archive
Volume 26 Issue 3, july 1979
Pages 401-414
More...

#include <VolumeOfPolytopes_Rn.h>

Collaboration diagram for VolumeOfPolytopes_Rn:

Public Member Functions
	VolumeOfPolytopes_Rn (const boost::shared_ptr< Polytope_Rn > P)
	Constructor. More...

	~VolumeOfPolytopes_Rn ()

void	splitCloudOfVertices (unsigned int DIM)

void	check () const throw (std::domain_error)

double	volume ()
	Sum the volumes of all simplices partitionning the polytope. More...

double	computeSimplexVolume (const std::set< boost::shared_ptr< Generator_Rn > > &listOfSimplexVertices) const

double	determinant (boost::numeric::ublas::matrix< double > a) const

void	dump (std::ostream &this_ostream)

void	dumpDS (std::ostream &this_ostream) const

void	dumpAllSimplices (std::ostream &this_ostream) const

Static Public Member Functions
static double	compute (const boost::shared_ptr< Polytope_Rn > P)
	Return the volume of the given polytope P. More...

Protected Attributes
std::vector< std::vector < unsigned int > >	_verticesByFacets
	The ordered list of all vertices stored by facets. More...

std::vector< std::vector < unsigned int > >	_facetsByVertices
	The ordered list of all facets stored by vertices. More...

std::vector< PolytopeToSimplexes >	_allSimplices
	List to store all the simplices partitioning the polytope. More...

boost::shared_ptr< Polytope_Rn >	_polytope
	The current polytope we are working on. More...

double	_volume
	The volume of the polytope. More...

unsigned int	_dimension
	As the algorithm goes down in lower dimensions, we want to store the starting space dimension. More...

unsigned int	_numberOfFacets
	The number of facets of the current polytope. More...

unsigned int	_numberOfVertices
	The number of vertices of the current polytope. More...

Detailed Description

Split a polytope into simplices to compute its volume.
Two Algorithms for Determining Volumes of Convex Polyhedra (1979) by Jacques Cohen and Timothy Hickey
Journal of the ACM (JACM) JACM Homepage archive
Volume 26 Issue 3, july 1979
Pages 401-414

Definition at line 139 of file VolumeOfPolytopes_Rn.h.

Constructor & Destructor Documentation

VolumeOfPolytopes_Rn::VolumeOfPolytopes_Rn ( const boost::shared_ptr< Polytope_Rn > P )

Constructor.

Definition at line 26 of file VolumeOfPolytopes_Rn.cpp.

Here is the call graph for this function:

VolumeOfPolytopes_Rn::~VolumeOfPolytopes_Rn ( )

inline

Definition at line 146 of file VolumeOfPolytopes_Rn.h.

Member Function Documentation

void VolumeOfPolytopes_Rn::check	(		)	const
throw	(	std::domain_error
	)

Definition at line 74 of file VolumeOfPolytopes_Rn.cpp.

static double VolumeOfPolytopes_Rn::compute ( const boost::shared_ptr< Polytope_Rn > P )

inlinestatic

Return the volume of the given polytope P.

Definition at line 153 of file VolumeOfPolytopes_Rn.h.

Here is the call graph for this function:

Here is the caller graph for this function:

double VolumeOfPolytopes_Rn::computeSimplexVolume ( const std::set< boost::shared_ptr< Generator_Rn > > & listOfSimplexVertices ) const

Compute the volume of a simplex making use of the following formula : $\displaystyle Vol \big( conv(v_0, ..., v_k) \big) = \frac{ \vert det( v_1-v_0, ..., v_k-v_0 ) \vert }{n!}$

Definition at line 228 of file VolumeOfPolytopes_Rn.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

double VolumeOfPolytopes_Rn::determinant ( boost::numeric::ublas::matrix< double > a ) const

Called by computeSimplexVolume() to compute a square matrix determinant. As we run it on small matrices we just use the minors method.

Definition at line 247 of file VolumeOfPolytopes_Rn.cpp.

Here is the caller graph for this function:

void VolumeOfPolytopes_Rn::dump ( std::ostream & this_ostream )

inline

Definition at line 200 of file VolumeOfPolytopes_Rn.h.

Here is the caller graph for this function:

void VolumeOfPolytopes_Rn::dumpAllSimplices ( std::ostream & this_ostream ) const

inline

Definition at line 236 of file VolumeOfPolytopes_Rn.h.

void VolumeOfPolytopes_Rn::dumpDS ( std::ostream & this_ostream ) const

inline

Definition at line 216 of file VolumeOfPolytopes_Rn.h.

Here is the caller graph for this function:

void VolumeOfPolytopes_Rn::splitCloudOfVertices ( unsigned int DIM )

Build all simplices to partition the polytope.

Parameters

DIM	the dimension of the space we work in

Definition at line 81 of file VolumeOfPolytopes_Rn.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

double VolumeOfPolytopes_Rn::volume ( )

Sum the volumes of all simplices partitionning the polytope.

Definition at line 194 of file VolumeOfPolytopes_Rn.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

Member Data Documentation

std::vector< PolytopeToSimplexes > VolumeOfPolytopes_Rn::_allSimplices

protected

List to store all the simplices partitioning the polytope.

Definition at line 251 of file VolumeOfPolytopes_Rn.h.

unsigned int VolumeOfPolytopes_Rn::_dimension

protected

As the algorithm goes down in lower dimensions, we want to store the starting space dimension.

Definition at line 257 of file VolumeOfPolytopes_Rn.h.

std::vector< std::vector< unsigned int > > VolumeOfPolytopes_Rn::_facetsByVertices

protected

The ordered list of all facets stored by vertices.

Definition at line 249 of file VolumeOfPolytopes_Rn.h.

unsigned int VolumeOfPolytopes_Rn::_numberOfFacets

protected

The number of facets of the current polytope.

Definition at line 259 of file VolumeOfPolytopes_Rn.h.

unsigned int VolumeOfPolytopes_Rn::_numberOfVertices

protected

The number of vertices of the current polytope.

Definition at line 261 of file VolumeOfPolytopes_Rn.h.

boost::shared_ptr<Polytope_Rn> VolumeOfPolytopes_Rn::_polytope

protected

The current polytope we are working on.

Definition at line 253 of file VolumeOfPolytopes_Rn.h.

std::vector< std::vector< unsigned int > > VolumeOfPolytopes_Rn::_verticesByFacets

protected

The ordered list of all vertices stored by facets.

Definition at line 247 of file VolumeOfPolytopes_Rn.h.

double VolumeOfPolytopes_Rn::_volume

protected

The volume of the polytope.

Definition at line 255 of file VolumeOfPolytopes_Rn.h.

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

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

Public Member Functions

Static Public Member Functions

Protected Attributes

Detailed Description

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation