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>
|
| | DoubleDescription (POLYHEDRON poly, ITERATOR ite, REDUNDANCY_PROCESSING redproc, int truncationStep) |
| |
| | DoubleDescription (POLYHEDRON poly, ITERATOR ite, REDUNDANCY_PROCESSING redproc, int truncationStep, TrackingOperatorToResult &trackerVdesc, TrackingOperatorToResult &trackerHdesc) |
| |
| bool | getIsEmpty () const |
| |
| void | computeVertexStates (std::vector< boost::shared_ptr< Generator_Rn_SD > > &GN_list, const boost::shared_ptr< HalfSpace_Rn > ¤tHalfSpace, std::vector< double > &GN_IN_sp, std::vector< double > &GN_OUT_sp, std::vector< boost::shared_ptr< Generator_Rn_SD > > &GN_IN, std::vector< boost::shared_ptr< Generator_Rn_SD > > &GN_OUT, std::vector< boost::shared_ptr< Generator_Rn_SD > > &GN_ON) |
| | For each generator compute its state according to the current half-space. 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...
|
| |
template<class POLYHEDRON, class ITERATOR, class REDUNDANCY_PROCESSING>
class DoubleDescription< POLYHEDRON, ITERATOR, REDUNDANCY_PROCESSING >
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.
Definition at line 49 of file DoubleDescription_Rn.h.
template<class POLYHEDRON , class ITERATOR , class REDUNDANCY_PROCESSING >
template<class POLYHEDRON , class ITERATOR , class REDUNDANCY_PROCESSING >
Compute the double description tracking all entities and considering the operator1 as the V-description and operator2 as the H-description.
Definition at line 77 of file DoubleDescription_Rn.h.
template<class POLYHEDRON , class ITERATOR , class REDUNDANCY_PROCESSING >
| bool DoubleDescription< POLYHEDRON, ITERATOR, REDUNDANCY_PROCESSING >::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 203 of file DoubleDescription_Rn.h.
template<class POLYHEDRON , class ITERATOR , class REDUNDANCY_PROCESSING >
| void DoubleDescription< POLYHEDRON, ITERATOR, REDUNDANCY_PROCESSING >::computeVertexStates |
( |
std::vector< boost::shared_ptr< Generator_Rn_SD > > & |
GN_list, |
|
|
const boost::shared_ptr< HalfSpace_Rn > & |
currentHalfSpace, |
|
|
std::vector< double > & |
GN_IN_sp, |
|
|
std::vector< double > & |
GN_OUT_sp, |
|
|
std::vector< boost::shared_ptr< Generator_Rn_SD > > & |
GN_IN, |
|
|
std::vector< boost::shared_ptr< Generator_Rn_SD > > & |
GN_OUT, |
|
|
std::vector< boost::shared_ptr< Generator_Rn_SD > > & |
GN_ON |
|
) |
| |
|
inline |
For each generator compute its state according to the current half-space.
Definition at line 138 of file DoubleDescription_Rn.h.
template<class POLYHEDRON , class ITERATOR , class REDUNDANCY_PROCESSING >
| bool DoubleDescription< POLYHEDRON, ITERATOR, REDUNDANCY_PROCESSING >::getIsEmpty |
( |
| ) |
const |
|
inline |
template<class POLYHEDRON , class ITERATOR , class REDUNDANCY_PROCESSING >
template<class POLYHEDRON , class ITERATOR , class REDUNDANCY_PROCESSING >
| REDUNDANCY_PROCESSING DoubleDescription< POLYHEDRON, ITERATOR, REDUNDANCY_PROCESSING >::_redundancyProcessing |
|
protected |
This class is dedicated to dealing with redundant half-spaces with the desired policy.
Definition at line 462 of file DoubleDescription_Rn.h.
The documentation for this class was generated from the following file:
1.8.7 
